c++ - 在由形成凸四边形的 4 个点定义的一组 6 个线段中查找对角线的算法

Question

这是一个简单的 2D 计算几何问题，我一直未能解决:

we have four points A, B, C, D defining a CONVEX QUADRILATERAL 

(not a square or a rectangle!)

we know the (x, y) coordinates of each point.

有6段连接2点:

AB, AC, AD, BC, BD, CD

这些线段的交点之一将在图形内部形成一个点:两条对角线的交点。

一对对角线有 3 种可能:

[AB] and [CD]
[AC] and [BD]
[AD] and [BC]

(见下图)

我正在寻找一种简单的算法来找出当我改变 A、B、C、D 的 (x, y) 坐标时发生的 3 种可能情况中的哪一种

Answer 1

1. 取 AB、AC、AD 线。
2. 测量它们之间的角度(两个归一化 vector 的点积是它们之间角度的余弦值)。 测量角度 CAB、CAD、BAD 并找出两个最小的角度。
3. 这两个最小的角共用一条边。这边是对角线。属于非共享边的点形成另一条对角线。

例子。

1. 测量角度 BAC、CAD、BAD。
2. BAC 和 CAD 是两个最小的角。 (另外，角度 BAC 和 CAD 的总和将等于角度 BAD，因此您也可以检查它)。
3. 他们共用一侧 AC。这使得 AC 第一个对角线，这意味着 BD 是另一个对角线。

不适用于凹面几何体。

更好的解释(附图表)

在这张图片中，∠DAB = ∠DAC + ∠BAC .因此，∠DAC < ∠DAB和 ∠BAC < ∠DAB . AC 是共享的，并且是对角线的。 BC 是另一个对角线。

即在所有情况下，两个小角形成“大”角，它们的共享边将“大”角分成两个小角。对于凸四边形中的单个顶点，只需检查 3 个角，这足以找到所有对角线。

vector 归一化。

归一化 vector 是长度为1.0的 vector . 要标准化 vector ，请按 1.0/length 的因子对其进行缩放.长度可以用点积计算。

normalizedVector = scale(originalVector, 1/length(originalVector)) (注意此处长度为 0 的 vector 。)
length(vector) = sqrtf(dotProduct(vector, vector))
“缩放” vector 是将它与标量相乘。