连接 4 个坐标的算法，它总是导致四边形
Algorithm to join 4 co-ordinates such that it always results in a quadilateral
我们得到了二维平面上 4 个点的坐标。我们怎样才能找到一个顺序，用线条将它们连接起来形成一个 quadilateral（只要有可能）？
几个阶段，假设最终结果需要4对点（and/or它们之间的直线方程）：
- 取任意三个点，组成一个三角形。
- 如果第四点在三角形内，则将其与三个点中的ny交换。
- 只剩下最后一个点，计算您要将它附加到哪两个点。这是通过玩线方程并找到相交点的位置来完成的。澄清如下。
- Return三角形的两条边+第四点和你在第二阶段选择的点之间的两条线。
第 2 步说明：
假设点 A 不在三角形（即 BCD）中。每一条线都将平原分为两侧。我们想找到点（B、C 或 D）s.t。它和 A 之间的线在其他两个之间运行（它们位于线的两侧）。这是我们不想附加到 A 的点。
示例：
给定 A(0,0)、B(10,0)、C(10,10) 和 D(0,10)。我们有三角形 BCD。 BC 线将 A 和 D 留在平原的同一侧。 DC也是。线 AC 在平原的相对两侧离开 B 和 D - 所以我们想将 A 连接到 B 和 C。
编辑：正如评论中所指出的，它只在特定情况下有效，因此是一个错误的答案。
4个点中哪一对点的距离最大，就可以画出四边形。找到这对后，通过将剩余的两个点与该对中的每个点相连来绘制四边形。
编辑： 这个答案已经被证明是错误的。
- 计算四个点的中心。
- 枚举逆时针方向（或顺时针方向）的点。
- Link他们在一起。
考虑绘制由前三个点定义的三条直线得到的平面的划分。它定义了 7 个区域。通过三个带符号的面积测试（三角形ABD、BCD、CAD的代数面积）可以很容易地找到第四个点属于哪个区域。
在每种情况下绘制四边形都很简单（每种情况可以有一个、两个或三个解决方案）。
在下面的示例中，D 在区域 -++ 中，ADBC 就可以。
实际上两个区域评估就足够了：如果第一个测试returns -（区域-+-、-++或--+），ADBC是一个solution, else if the second test returns - (regions +-+ or +--), ABDC is a solution, else (regions ++- or +++) ABCD 是一个解决方案。
您可以使用任何 well-known algorithms for convex hull 的化简。贾维斯会很容易。如果凸包是三角形，则四边形是凸的。只需在边缘列表中的任意位置插入缺失点即可。如果凸包是一条线（2 个端点），只需对 x 或 y 坐标上的所有点进行排序即可获得退化四边形。 （如果更接近水平（abs delta x > abs delta y），则使用 x 进行排序，否则使用 y。）
我想，你每次只需要连接两个点，我们会得到一个线段并检查剩下的其他两个点是否在该线段的同一侧，如果不是那不是线段需要四边形，如果是，则继续处理不同的点集（即点可以是该线段的坐标之一，另一个点可以是剩余的两个点）并检查相同的东西，直到你得到 4 线段
考虑仿射变换
Px = Ax + u (Bx - Ax) + v (Cx - Ax)
Py = Ay + u (By - Ay) + v (Cy - Ay)
它将(0, 0)映射到A，(1, 0)映射到B，(0, 1)映射到C。 （这将三角形 ABC 置于规范位置。）
求解 2x2 线性系统
Dx = Ax + u (Bx - Ax) + v (Cx - Ax)
Dy = Ay + u (By - Ay) + v (Cy - Ay)
为您提供对应于 D 的 (u, v) 的值。
然后，
if u < 0 => ABCD
else if v < 0 => BCAD
else => CABD
生成的四边形与三角形的方向相同 ABC。
为了清楚起见，我将坐标 (x_n, y_n).
的点视为点 p_n
要连接 4 个点，您可以按照以下步骤操作：
- 得到最小
x的点p_1。
- 计算从
p_1 到每个剩余点的 3 条线中的 slope。
- 连接
p_1 和点 p_2 组成斜率最大的直线。
- 将
p_1 与构成斜率最小的直线的点 p_3 相连。
- 将剩余的点
p_4与p_2和p_3连接起来。
如果有什么不清楚的地方，请告诉我。
四处寻找凸包算法。其中一个包含两个步骤：在给定的一组顶点（可能是凹的）上构建一个普通的多边形，然后移除 'concave vertices' 使剩余的多边形变为凸的。
第一步是解决您的问题。
当然有点矫枉过正了。对于 4 个顶点，只需按顺序（以任何顺序）设置它们，然后验证连接点 1-2 和 3-4 的线段是否相交；如果是，交换第 2 点和第 3 点；或者可能边 2-3 和 1-4 相交——然后交换点 3 和 4。完成。
验证线段 AB 和 CD 是否相交测试点 A 和 B 是否在线 CD 的相对两侧以及点 C 和 D 是否在线 AB 的相对两侧。
要确定点 K 所在的直线 PQ 的一侧，请计算 PQ×PK 向量积的 Z 部分：(xq-xp)(yk-yp)-(yq-yp)(xk-xp)。表达式在线的一侧为正，另一侧为负（在线为零）。
借助一个判断两条线段是否相交的函数，可以很容易地解决这个问题。
给定点 A、B、C、D，只有三种不同的顺序连接顶点：ABCD、ABDC 和 ACBD（顶点 A 连接到顶点 B 或不连接。如果连接，则有订购 C 和 D 的两种方式。如果不是，则 A 连接到 C 和 D，并且每个都必须连接到 B）。
如果边 none 相交（角除外），则四个点的排序生成四边形。这给出了查找工作订单的程序：
If AB intersects with CD then return ACBD.
If AD intersects with BC then return ABDC.
Otherwise return ABCD.
这个有效的证明很简单：
- ABCD 和 ABDC 都包含边 AB 和 CD，所以如果这对边相交，则好的顺序必须是 ACBD。
- ABCD 和 ACBD 都包含边 AD 和 BC，所以如果这对边相交，那么好的顺序必须是 ABDC。
- 如果AB/CD和AD/BC都不相交，则ABCD阶生成四边形。
判断两条线段是否相交的代码，自己看不懂的可以在网上找。
这是一种简单的非数学方法。我已经在几个例子中试过了，但无法证明它是错的。如果您知道或知道如何让它变得更好，请告诉我：
- 选择其他点右边的两个点，比如点 1 和点 2。
- Link 一起点1-2，还有点3-4.
- 每个点都必须 linked 到另外两个点，所以只有 2 种可能性：linking 点 1-3 和 2-4，或者点 1-4 和 2- 3.
- 检查每条线是否与另一条线相交。
应该可以了。
注意：在选择前两点时，有一些特殊情况：
- 点 1 在所有其他点的右侧，但点 2 和点 3 在相同的 x 坐标上。选择最接近点 1 的点。
- 如果三个点 1,2 和 3 具有相同的 x 坐标，link 最接近的两个点。如果点分布均匀，选择两种可能性中的一种。
我们得到了二维平面上 4 个点的坐标。我们怎样才能找到一个顺序，用线条将它们连接起来形成一个 quadilateral（只要有可能）？
几个阶段，假设最终结果需要4对点（and/or它们之间的直线方程）：
- 取任意三个点，组成一个三角形。
- 如果第四点在三角形内，则将其与三个点中的ny交换。
- 只剩下最后一个点，计算您要将它附加到哪两个点。这是通过玩线方程并找到相交点的位置来完成的。澄清如下。
- Return三角形的两条边+第四点和你在第二阶段选择的点之间的两条线。
第 2 步说明：
假设点 A 不在三角形（即 BCD）中。每一条线都将平原分为两侧。我们想找到点（B、C 或 D）s.t。它和 A 之间的线在其他两个之间运行（它们位于线的两侧）。这是我们不想附加到 A 的点。
示例： 给定 A(0,0)、B(10,0)、C(10,10) 和 D(0,10)。我们有三角形 BCD。 BC 线将 A 和 D 留在平原的同一侧。 DC也是。线 AC 在平原的相对两侧离开 B 和 D - 所以我们想将 A 连接到 B 和 C。
编辑：正如评论中所指出的，它只在特定情况下有效，因此是一个错误的答案。
4个点中哪一对点的距离最大，就可以画出四边形。找到这对后，通过将剩余的两个点与该对中的每个点相连来绘制四边形。
编辑： 这个答案已经被证明是错误的。
- 计算四个点的中心。
- 枚举逆时针方向（或顺时针方向）的点。
- Link他们在一起。
考虑绘制由前三个点定义的三条直线得到的平面的划分。它定义了 7 个区域。通过三个带符号的面积测试（三角形ABD、BCD、CAD的代数面积）可以很容易地找到第四个点属于哪个区域。
在每种情况下绘制四边形都很简单（每种情况可以有一个、两个或三个解决方案）。
在下面的示例中，D 在区域 -++ 中，ADBC 就可以。
实际上两个区域评估就足够了：如果第一个测试returns -（区域-+-、-++或--+），ADBC是一个solution, else if the second test returns - (regions +-+ or +--), ABDC is a solution, else (regions ++- or +++) ABCD 是一个解决方案。
您可以使用任何 well-known algorithms for convex hull 的化简。贾维斯会很容易。如果凸包是三角形，则四边形是凸的。只需在边缘列表中的任意位置插入缺失点即可。如果凸包是一条线（2 个端点），只需对 x 或 y 坐标上的所有点进行排序即可获得退化四边形。 （如果更接近水平（abs delta x > abs delta y），则使用 x 进行排序，否则使用 y。）
我想，你每次只需要连接两个点，我们会得到一个线段并检查剩下的其他两个点是否在该线段的同一侧，如果不是那不是线段需要四边形，如果是，则继续处理不同的点集（即点可以是该线段的坐标之一，另一个点可以是剩余的两个点）并检查相同的东西，直到你得到 4 线段
考虑仿射变换
Px = Ax + u (Bx - Ax) + v (Cx - Ax)
Py = Ay + u (By - Ay) + v (Cy - Ay)
它将(0, 0)映射到A，(1, 0)映射到B，(0, 1)映射到C。 （这将三角形 ABC 置于规范位置。）
求解 2x2 线性系统
Dx = Ax + u (Bx - Ax) + v (Cx - Ax)
Dy = Ay + u (By - Ay) + v (Cy - Ay)
为您提供对应于 D 的 (u, v) 的值。
然后，
if u < 0 => ABCD
else if v < 0 => BCAD
else => CABD
生成的四边形与三角形的方向相同 ABC。
为了清楚起见，我将坐标 (x_n, y_n).
p_n
要连接 4 个点，您可以按照以下步骤操作：
- 得到最小
x的点p_1。 - 计算从
p_1到每个剩余点的 3 条线中的 slope。 - 连接
p_1和点p_2组成斜率最大的直线。 - 将
p_1与构成斜率最小的直线的点p_3相连。 - 将剩余的点
p_4与p_2和p_3连接起来。
如果有什么不清楚的地方，请告诉我。
四处寻找凸包算法。其中一个包含两个步骤：在给定的一组顶点（可能是凹的）上构建一个普通的多边形，然后移除 'concave vertices' 使剩余的多边形变为凸的。
第一步是解决您的问题。
当然有点矫枉过正了。对于 4 个顶点，只需按顺序（以任何顺序）设置它们，然后验证连接点 1-2 和 3-4 的线段是否相交；如果是，交换第 2 点和第 3 点；或者可能边 2-3 和 1-4 相交——然后交换点 3 和 4。完成。
验证线段 AB 和 CD 是否相交测试点 A 和 B 是否在线 CD 的相对两侧以及点 C 和 D 是否在线 AB 的相对两侧。
要确定点 K 所在的直线 PQ 的一侧，请计算 PQ×PK 向量积的 Z 部分：(xq-xp)(yk-yp)-(yq-yp)(xk-xp)。表达式在线的一侧为正，另一侧为负（在线为零）。
借助一个判断两条线段是否相交的函数，可以很容易地解决这个问题。
给定点 A、B、C、D，只有三种不同的顺序连接顶点：ABCD、ABDC 和 ACBD（顶点 A 连接到顶点 B 或不连接。如果连接，则有订购 C 和 D 的两种方式。如果不是，则 A 连接到 C 和 D，并且每个都必须连接到 B）。
如果边 none 相交（角除外），则四个点的排序生成四边形。这给出了查找工作订单的程序：
If AB intersects with CD then return ACBD.
If AD intersects with BC then return ABDC.
Otherwise return ABCD.
这个有效的证明很简单：
- ABCD 和 ABDC 都包含边 AB 和 CD，所以如果这对边相交，则好的顺序必须是 ACBD。
- ABCD 和 ACBD 都包含边 AD 和 BC，所以如果这对边相交，那么好的顺序必须是 ABDC。
- 如果AB/CD和AD/BC都不相交，则ABCD阶生成四边形。
判断两条线段是否相交的代码，自己看不懂的可以在网上找。
这是一种简单的非数学方法。我已经在几个例子中试过了，但无法证明它是错的。如果您知道或知道如何让它变得更好，请告诉我：
- 选择其他点右边的两个点，比如点 1 和点 2。
- Link 一起点1-2，还有点3-4.
- 每个点都必须 linked 到另外两个点，所以只有 2 种可能性：linking 点 1-3 和 2-4，或者点 1-4 和 2- 3.
- 检查每条线是否与另一条线相交。
应该可以了。
注意：在选择前两点时，有一些特殊情况：
- 点 1 在所有其他点的右侧，但点 2 和点 3 在相同的 x 坐标上。选择最接近点 1 的点。
- 如果三个点 1,2 和 3 具有相同的 x 坐标，link 最接近的两个点。如果点分布均匀，选择两种可能性中的一种。