如何在平面上的4个随机放置的点之间连接一条线，以使该线不交叉
迈克尔·塞尔滕瑞希
您会在一个平原上获得4个点的坐标。您需要用一条线将它们全部连接起来。线不能交叉。
你的策略是什么？
看图片 
我的第一个直觉是将这些点组织为“左上”，“右上”，“左下”和“右下”，并继续连接它们，以使左上到左下，左下到下右，右下到右上，右上又回到左上。
在大多数情况下，这是可行的，但并非全部。有更好的策略吗？
谢谢你们。
伊夫·达乌斯特（Yves Daoust）
取三个点并形成一个顺时针三角形（将面积计算为两侧的叉积-如果为负，则交换两个顶点）。
取第四点，并计算与前者的每个（定向）边形成的三角形的面积。当找到负值区域时，在这一侧插入新顶点，即可完成操作。
可以发现没有负区域，这意味着第四个点在三角形内。您可以将其插入任何一侧。
if Area(P0, P1, P2) < 0
Swap(P0, P1)
if Area(P0, P1, P3) < 0
Solution: P0-P3-P1-P2
else if Area(P1, P2, P3) < 0
Solution: P1-P3-P2-P0
else if Area(P2, P0, P3) < 0
Solution: P2-P3-P0-P1
else
Solution: P0-P1-P2-P3
更新
您可以使用所谓的轨迹方法来考虑它。假设您已经形成并定向了一个三角形，并希望插入第四个点。选择要插入的边，可以绘制所有不会导致边交叉的位置的草图。
看到允许区域的形状，您会看到它是半平面相对于插入侧与原始三角形的并集。
三角形的三条支撑线将平面划分为7个区域。在任何区域内，您都可以在侧面插入1、2或3种可能性（在图中，我们处于类型1的区域）中进行选择。
这种看似人为设计的方法向您展示了您必须将第四个点与三角形的边进行比较（区域测试），在最坏的情况下，您不能避免与三个边的比较。
边界的形状告诉您将需要使用哪种方程，而区域的数量则提示您必须执行多少次测试。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
如何在谷歌地图中的两点之间画一条线？
- 2
HTML 和 CSS：如何在表的某些行而不是所有行之间放置一条线
- 3
在图形的2点之间绘制一条线
- 4
在点之间画一条线
- 5
如何绘制以不同角度对齐的点并通过一条线连接这些点？
- 6
如何在python中从2D数组的不同行获取的点之间绘制一条线？
- 7
R：在ggplot中的两个点之间画一条线
- 8
在两个不相交的点集之间画一条线
- 9
如何在两个圆之间划一条线，使其与两个圆接触？
- 10
在两个div之间画一条线（多个连接）
- 11
C# 如何在窗体上的两个对象之间画一条线？
- 12
检测一条线（具有多个点）是单独的还是连接到另一条线的
- 13
如何根据一个点和一个斜率画一条线？（SD线）
- 14
JavaFX：如何通过一条线连接两个节点？
- 15
如何在SwiftUI中在Shape之间画一条线？
- 16
如何在zsh shell中的命令之间画一条线
- 17
如何在导航抽屉中的菜单项之间画一条线
- 18
如何在网格窗格的间隙之间对齐一条线？
- 19
如何在Blazor中划一条线？
- 20
如何在画布上画一条线？
- 21
如何在Cygwin中选择一条线
- 22
如何在gmaps上画一条线和一个框？
- 23
将一条线的两个端点连接到点表中的两个点
- 24
如何在d3中的两个不同坐标系/变换中将两条点与一条线连接起来？
- 25
如何在一条线中水平对齐3个跨度？
- 26
如何在一条线中水平对齐3个跨度？
- 27
在Corona SDK中，如何在绘制另一条线时使一条线消失？
- 28
在Corona SDK中，如何在绘制另一条线时使一条线消失？
- 29
是否可以在TChart“点”图上的点之间画一条线
我来说两句