python - 确定线段集合的非凸包

Question

我有一个计算几何问题，我觉得应该有一个相对简单的解决方案，但我想不通。

我需要确定由几条线段定义的区域的非凸轮廓。

我知道各种非凸壳算法(例如 alpha 形状)，但我不需要完全通用的算法，因为线段在大多数情况下定义了唯一的解决方案。

---

正如@Jean-FrançoisCorbett 所指出的，在某些情况下存在多种解决方案。我显然需要更多地考虑我的定义。

但是，我想做的是逆向工程并使用专有文件格式，这样我就可以对自己和其他人收集的数据进行基本分析。文件格式很简单，但确定他们用来定义边界的算法要困难得多。

加入许多会导致非唯一解决方案的边缘情况会导致相关软件在没有警告的情况下崩溃或静默无法读取文件。

因此，当有多个解决方案时，生成一个可接受的解决方案或能够确定存在多个解决方案都是可以接受的。

---

问题定义:

多边形的轮廓不应跨越任何线段，并且应由连接所有线段端点的线组成。所有线段必须完全位于多边形的内部或沿多边形的边界。在轮廓中不能多次使用端点(对于需要关闭多边形的软件库，通过在末尾添加第一个点来忽略“关闭”多边形。)。

如果有多个解决方案符合此标准，则可以接受其中任何一个解决方案。 (能够确定解决方案何时不唯一会很好，但这并不是绝对必要的。)

---

示例:

作为一个例子，我有一些类似的东西:

我想划定以下区域:

它也应该适用于非相交段。例如

我认为 (?) 在这两种情况下都有一个独特的解决方案，但要符合前面概述的标准。 (编辑:正如@Jean-FrançoisCorbett 所指出的那样，一般没有唯一的解决方案。但是，我仍然对能够生成可接受解决方案之一的算法感兴趣。)

测试用例

对于一个测试用例，这里是生成上述数字的代码。我在这里使用 python，但问题与语言无关。

import matplotlib.pyplot as plt

def main():
    test1()
    test2()
    plt.show()

def test1():
    """Intersecting segments."""
    segments = [[(1, 1), (1, 3)],
                [(3.7, 1), (2, 4)],
                [(2, 0), (3.7, 3)],
                [(4, 0), (4, 4)],
                [(4.3, 1), (4.3, 3)],
                [(0, 2), (6, 3)]]

    desired_outline = [segments[0][0], segments[5][0], segments[0][1], 
                       segments[1][1], segments[2][1], segments[3][1],
                       segments[4][1], segments[5][1], segments[4][0],
                       segments[3][0], segments[1][0], segments[2][0],
                       segments[0][0]]

    plot(segments, desired_outline)

def test2():
    """Non-intersecting segments."""
    segments = [[(0, 1), (0, 3)],
                [(1, 0), (1, 4)],
                [(2, 1), (2, 3)],
                [(3, 0), (3, 4)]]

    desired_outline = [segments[0][0], segments[0][1], segments[1][1],
                       segments[2][1], segments[3][1], segments[3][0], 
                       segments[2][0], segments[1][0], segments[0][0]]

    plot(segments, desired_outline)


def plot(segments, desired_outline):
    fig, ax = plt.subplots()
    plot_segments(ax, segments)
    ax.set_title('Segments')

    fig, ax = plt.subplots()
    ax.fill(*zip(*desired_outline), facecolor='gray')
    plot_segments(ax, segments)
    ax.set_title('Desired Outline')

def plot_segments(ax, segments):
    for segment in segments:
        ax.plot(*zip(*segment), marker='o', linestyle='-')
    xmin, xmax, ymin, ymax = ax.axis()
    ax.axis([xmin - 0.5, xmax + 0.5, ymin - 0.5, ymax + 0.5])

if __name__ == '__main__':
    main()

有什么想法吗？

我开始怀疑我试图重现其结果的软件在某种“内部”坐标系中使用了径向扫描算法(例如，带有 x-prime 的坐标系> 和 y-prime 沿由点的扩展定义的主轴缩放和旋转。这使问题更加“圆形”。)但是，这会产生轮廓与线段相交的解决方案在许多情况下.检测到这一点并从那里暴力破解很容易，但肯定有更好的方法吗？

Answer 1

1. 选择一个安全的起点。可以是例如具有最大 x 的端点。
2. 沿着线段行进。
3. 遇到任何十字路口时，请始终左转并沿此新路段行进。
4. 遇到端点，记录下来。转到 2。
5. 回到起点后停下。您记录的端点列表现在构成了凹壳顶点的有序列表。

注意:如果存在不与任何其他线段相交的“自由 float ”外围线段，这将失败。但是，您指定“条形唯一地定义一个解决方案”，这排除了这种失败情况。 (外围分割市场可能有两种不同的解决方案。)

EDIT ...或者更确切地说，外围段可以使两种不同的解决方案成为可能——取决于确切的布局。证明:下面是一个例子，我添加的黄色部分使两种解决方案成为可能(蓝色和灰色可怕的手绘线)。如果黄色部分的方向垂直于它现在的绘制方式，那么只有一种解决方案是可能的。听起来您的问题定义不明确。

编辑实际上，如果您的段集合“非常凹”，即如果有端点隐藏在您的段堆的隐蔽角落，这也可能会失败。在下图中，我添加了一个黑色段。我的算法会非法将其端点连接到另一个端点(灰色虚线)。我会留下我的答案，以防其他人倾向于建立它。

在考虑更多之后进行编辑:即使在“非常凹”的情况下，这个解决方案也一定会为您提供所有凹形外壳的点按正确的顺序排列，但它们可能会穿插额外的、不适当的点，例如黑色点。所以可能有太多点。

答案当然是进行一些修剪。修剪会相当复杂，特别是如果你可以有多个连续的“隐士点”，比如黑色的，所以我没有想到一个智能算法。但即使是盲目的蛮力也是可行的。每个点都可以被接受或拒绝( bool 值)，所以如果你的凹壳中有 N 个正确排序的候选点，那么只有 2^N 种可能性来检查.对于您原来的排列问题，这种方式方式的可能性比蛮力要少，这将有 SUM of (n!/(n-k)!) for k=1:(n-1)可能性(请原谅我的符号)。所以这个算法大大缩小了你的问题。

我认为这是要走的路。