algorithm - 需要一种编程算法来围绕线段进行紧密封闭

Question

我有一个列表，其中可能包含数百个随机角度的未排序 2D 线段，如上图蓝色所示，我需要从中确定点 a – i 的排序序列，如红色所示。以下是一些限制条件和观察结果:

• 红色折线序列 a - i 形成了外部的紧密包围所有段的点。它就像一个凸包，但“吸”成凹陷。所有部分的整体紧密封闭将是一个很好的解决方案；我可以删除未使用的部分。
• 围栏确实存在。这些片段不是完全随机的。
• 每段一个点的y值为0，另一端为a点在外壳上。
• 围栏不能穿过任何线段或它本身。这也是意味着所有线段都在封闭折线的一侧。
• 将有一个或两个外壳段连接到每个包围点 a - i。
• 点的间距可能大相径庭，不像图中那样整齐。
• 如果有必要，我应该能够确定点 a 或 i 开始算法。

似乎从围绕所有段的边界框开始并将其缩小以形成紧密的包围是一种合理的方法，但我想不出一个像样的算法。这最终将用 C# 编码，但算法或伪代码会很好。

Answer 1

历史:这个答案现在被标记为社区 wiki。原猜想被@dont talk just code证明是错误的. @Matt Timmermans在问题下的评论中提供了当前的猜想。

---

以下猜想未经证明提交:比较两条线段的顺序，比较底部的x，如果线段交叉则返回相反的值。

如果猜想成立，则可以编写一个比较器用于任何比较排序。比较器的伪代码:

compare(segment A, segment B)
   if A crosses B
      return B.bottom.x - A.bottom.x
   else
      return A.bottom.x - B.bottom.x

如果两条线段具有相同的 bottom.x，则可以通过比较它们与 x 轴所成的角度来确定它们的顺序，例如

具有较大角度的线段在前。 atan2 函数可用于计算角度。

---

请注意，该猜想绝对不适用于所有可能的安排。必须约束线段以便存在解。这是一个解决方案不存在的示例(因为 C 不能在不穿过蓝线的情况下连接到 A 或 B):

A 和 B 交叉，因此反转 x 比较，A 在 B 之前。 C 不与 A 或 B 交叉，因此比较底部的 x 值，B 在 C 之前，C 在 A 之前。这就形成了剪刀石头布的局面:A 先于 B，B 先于 C，C 先于 A。这种不及物比较会导致比较排序失败。