0

这是一个我未能成功解决的二维计算几何的简单问题：

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 种可能情况中的哪一种

4

5 回答 5

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

例子。

  1. 测量角度 BAC、CAD、BAD。
  2. BAC 和 CAD 是两个最小的角度。（另外，角度 BAC 和 CAD 的总和将等于角度 BAD，所以你也可以检查一下）。
  3. 他们共享侧交流电。这使得 AC 第一个对角线，这意味着 BD 是另一个对角线。

不适用于凹几何。

更好的解释（附图表）

图表

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

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

向量归一化。

归一化向量是长度为 的向量1.0。要归一化向量，请将其缩放1.0/length. 长度可以用点积计算。

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

于 2013-11-06T23:10:21.140 回答
2

点 {A,B,C,D} 形成 4 个三角形：ABC、ABD、ACD 和 BCD。计算它们的方向会产生一个 4 位二进制签名，该签名确定凸包的顺序如下：

       signature key: "+" for counterclockwise, "-" for clockwise

A A A B
B B C C   convex hull, in counterclockwise order:
C D D D

+ + + +   quadrilateral ABCD
+ + + -   triangle ABD (C is internal)
+ + - +   triangle ABC (D is internal)
+ + - -   quadrilateral ABDC
+ - + +   triangle BCD (A is internal)
+ - + -   (should not happen)
+ - - +   quadrilateral ADBC
+ - - -   triangle ADC (B is internal)

          (inverting all signature bits reverses hull orientation)

- + + +   triangle CDA (B is internal)
- + + -   quadrilateral CBDA
- + - +   (should not happen)
- + - -   triangle DCB (A is internal)
- - + +   quadrilateral CDBA
- - + -   triangle CBA (D is internal)
- - - +   triangle DBA (C is internal)
- - - -   quadrilateral DCBA

您可以计算任何给定三角形的方向（顺时针或逆时针），如下所示：

struct Point {
  float x, y;
  Point(float xx,float yy):x(xx),y(yy){}
};
Point operator+(Point A, Point B) { return Point(A.x+B.x,A.y+B.y); }
Point operator-(Point A, Point B) { return Point(A.x-B.x,A.y-B.y); }

float orientation(Point A, Point B, Point C) {
  Point AB = B - A;
  Point AC = C - A;
  return AB.x*AC.y - AB.y*AC.x; // 2-D equivalent to the 3-D cross-product
}

如果三角形 ABC 是逆时针的，该函数orientation(A,B,C)返回一个正值，如果它是顺时针的，该函数返回一个负值，如果它是退化的，则返回零。（如果你的坐标系是左手而不是右手，那么顺时针换成逆时针，但这并不重要......）

于 2013-11-07T03:07:13.100 回答
1

我能弄清楚的简单点：

  1. 取点 A。
  2. 测量向量 AB、AC、AD 的斜率。

  3. 看他们之间的关系。

      Case 1: SAC>SAB>SAD,
  Case 2: SAB>SAC>SAD,
  Case 3: SAB>SAD>SAC.

    考虑到 360 度的差异。

PS我不确定你是否关心角度> 180的四边形。如果是，你必须另外考虑它们。

于 2013-11-06T22:36:00.000 回答
1

提示：我认为你应该从定义凸包点和线开始。维基格雷厄姆扫描算法。可用于确定参与创建凸包的线段。一旦确定了线段，就可以很容易地找到对角线。使用链接中的示例，可以将以下线段（按算法确定的顺序）存储在数组中（每对点定义一个线段）：

P,A
A,B
B,D
D,P

从这个数组中，您可以立即得到对角点为 P,B 和 A,D。

该算法不需要角度计算，也没有关于区域形状的假设。

于 2013-11-06T23:03:30.797 回答
0

如果您的坐标是：

0,0
0,1
1,0
1,1

您可以识别出具有相同 x 和 y 坐标的那些构成对角线，而具有不同 x 和 y 坐标的那些构成对角线。

所以如果坐标是：

1,1
1,3
3,1
3,3

然后 a,b 处的字母 a=b 形成一，a,b 处的字母 a!=b 形成一，因此 1,1 和 3,3 处的字母为一，1,3 和3,1。

请注意，这只适用于正方形。

此外，在任何情况下，您都可以这样做：

您可以匹配不共享相同坐标的对。

为了

A--B
|  |
C--D

您将能够知道 A 和 D 是一对，因为 A 和 C 共享一个 X 坐标，而 A 和 B 共享一个 Y 坐标。

没有共同的坐标==对角线。（对于这种方式的任何正方形或矩形。）

希望这可以帮助。

于 2013-11-06T22:28:19.407 回答