基于自定义几何库判断三角形顶点是否共线的实现求助

问题背景 #

正在开展一项基于齐次坐标的几何任务，需从文件中读取顶点并构造外接圆。目前已完成中垂线计算与交点确定，外接圆暂以半径31.5绘制，但卡在了判断三角形三个顶点是否共线的代码实现步骤。使用教授自定义的libcfcg库，现有代码如下：

import sys
import time
import math
import numpy as np
from enum import Enum
from libcfcg import cf

pointsV = [] # python representation of point vectors
cfPoints = [] # internal 2D representation with x and y
pointVectorsV = [] # internal pointVector representation with x, y, and w

def myEqualZero(value):  # if you expect 0 it's mostly a very small number but not 0!!!
    return abs(value) < 0.001

def mySign(value):  # difference to NumPy:  mySign(0)=1    !!!
    if value < 0:
        return -1
    return 1

def readPoints():
    dataV = cf.readDatFilePointVector("geometry_files/UMKREIS1.DAT")

    for i in range(0, dataV.size()):
        pV = dataV.get(i)
        pointsV.append([pV.getX(), pV.getY(), pV.getW()])

    for pV in range(0, len(pointsV)):
        if pointsV[pV][2] != 1:
            raise ValueError;
        cfPoints.append(cf.Point(pointsV[pV][0], pointsV[pV][1]))  # drawable points
        pointVectorsV.append(cf.PointVector(pointsV[pV][0], pointsV[pV][1])) # list of Point-Vectors

readPoints()

# part 1, create coordinatesystem & draw all points/lines
window = cf.WindowCoordinateSystem(600, cf.Interval(-10, 270), cf.Interval(-10, 270), "Coordinatesystem")
window.setWindowDisplayScale(1.0)
window.drawAxis(cf.Color.BLACK, 10, 10)

# Read points of the triangle
for pV in pointsV:
    print("Drawing point: ", pV)
    sys.stdout.flush() # force output
    time.sleep(0.1) # wait for console; increase if necessary
    window.drawPoint(cf.Point(pV[0], pV[1])) # default color is black
# Draw points of the triangle
for i in range(0, len(cfPoints)):
    p0 = cfPoints[i]
    p1 = cfPoints[(i+1) % len(cfPoints)] 
    window.drawLine(p0, p1)

window.show() # no display of drawings without this line!!!


Mittelpunkte = []
Punkte = []

#Determine and draw perpendiculars
print("Taste drücken, um Mittelsenkrechten einzuzeichnen")
sys.stdout.flush() # force output
time.sleep(0.1) # wait for console; increase if necessary
window.waitKey()
for pV in range(0,2):
    
    #Calculate the center point from two points
    MPV1 = pointVectorsV[pV].add(pointVectorsV[pV+1])
    MPV1.normalize()
    Mittelpunkte.append(MPV1)
    MP1 = cf.Point(MPV1)
    window.drawPoint(MP1)
    window.show()
    
    #Direction vector for G, PointV1 - MPV1
    RMPV1 = pointVectorsV[pV+1].sub(MPV1)
    
    #Calculate normal direction vector from direction vector
    NMPV1 = RMPV1.clone()
    NEWX = RMPV1.getY()*(-1)
    NEWY = RMPV1.getX()
    NMPV1.setX(NEWX)
    NMPV1.setY(NEWY)
    
    # Calculate X1 from H with r=3
    X1 = MPV1.add(NMPV1*3)
    Punkte.append(X1)
    XP1 = cf.Point(X1)
    window.drawPoint(XP1, cf.Color.BLUE)
    window.show()
    
    # Draw perpendiculars through X1 and X2
    window.drawLine(MP1, XP1, cf.Color.BLUE, cf.Window2D.LineType_DEFAULT, 1)
    window.show()
    

#Calculate and draw the intersection of the perpendiculars
print("Taste drücken, um den Schnittpunkt der Mittelsenkrechten einzuzeichnen")
sys.stdout.flush() # force output
time.sleep(0.1) # wait for console; increase if necessary
window.waitKey()

N1 = Mittelpunkte[0].crossProduct(Punkte[0])
N2 = Mittelpunkte[1].crossProduct(Punkte[1])
N1.normalize()
N2.normalize()
S = N1.crossProduct(N2)
S.normalize()
print("Test", S.getX(), S.getY(), S.getW())
SP1 = cf.Point(S)
window.drawPoint(SP1, cf.Color.RED)
window.show()


#Draw a circle around the center of the vertical and at the three corner points
print("Taste drücken, um den den Kreis der 3 Punktvektoren einzuzeichnen")
sys.stdout.flush() # force output
time.sleep(0.1) # wait for console; increase if necessary
window.waitKey()

window.drawCircle(SP1, 31.5, cf.Color.GREEN)
window.show()



#check whether the three vertices of the triangle are collinear
print("Taste drücken, um zu überprüfen ob die Punkte Kollinear sind")
sys.stdout.flush() # force output
time.sleep(0.1) # wait for console; increase if necessary
window.waitKey()



    
# end
print("Press any key to finish")
sys.stdout.flush() # force output
time.sleep(0.1) # wait for console; increase if necessary
window.waitKey()

window = None

解决方案：判断三点共线的实现 #

判断三个点是否共线，核心思路是计算由这三个点构成的三角形面积是否趋近于0（考虑浮点运算误差）。对于2D点，可通过向量叉乘的结果来判断：

• 取三个点 P0, P1, P2
• 计算向量 v1 = P1 - P0，v2 = P2 - P0
• 计算叉乘结果：cross = v1.getX() * v2.getY() - v1.getY() * v2.getX()
• 若 cross 的绝对值小于设定的误差阈值（如0.001，可复用已有的myEqualZero函数），则三点共线

代码实现 #

在现有代码的共线判断区域（#check whether the three vertices of the triangle are collinear下方）插入以下代码：

# 提取三个顶点的PointVector
p0 = pointVectorsV[0]
p1 = pointVectorsV[1]
p2 = pointVectorsV[2]

# 计算向量
v1 = p1.sub(p0)
v2 = p2.sub(p0)

# 计算叉乘
cross_product = v1.getX() * v2.getY() - v1.getY() * v2.getX()

# 判断是否共线
if myEqualZero(cross_product):
    print("三个顶点共线，无法构造外接圆")
    # 可视化提示：用红色虚线标注共线状态
    window.drawLine(cf.Point(p0), cf.Point(p2), cf.Color.RED, cf.Window2D.LineType_DASH, 2)
else:
    print("三个顶点不共线，可以构造外接圆")

window.show()

说明 #

• 复用代码中已定义的myEqualZero函数处理浮点误差，避免因计算精度问题误判
• 若三点共线，添加可视化提示让结果更直观
• 建议将共线判断逻辑放在构造外接圆之前执行，避免无效计算

内容的提问来源于stack exchange，提问作者zebat