将随机点与非自交直角折线连接

Question

我发现了一些帖子，并且知道可以使用 ciecle 对随机点进行排序。然后可以按照排序的点顺序绘制非自交多段线。 然而，就我而言，我需要两点之间的每个连接都是直角。我尝试在每两点之间创建圆圈，并从起点制作水平或垂直线，以找到圆圈和连接线之间的交点。这样就可以保证所有的连接都是直角的。为了避免自相交，我选择了不在之前的圆圈中的交点。它适用于大多数情况。但是，当点彼此非常接近时，圆可能会嵌套。在这种情况下，除非点顺序被交换，否则自交似乎无法避免。 我担心顺序切换是否会导致其后续连接出现更多交叉点。 还有其他算法可以解决这个问题吗？谢谢。

Answer 1

有很多方法可以做到这一点。我想我会像这样递归地做到这一点：

1. 如果只有2个点，则将它们连接起来。否则...
2. 找到具有中值 x 位置或中值 y 位置的点。如果点集的宽度大于高度，请选择 x。
3. 围绕中点将点集分为两半，但在两半中都包括中点。
4. 递归连接每一半的点。

当你在步骤4中递归连接两边的点时，任何一半的连接都不会越过中线。这保证了整个折线将避免自相交。