确定线段集合的非凸包

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. 当你回到起点时停下来.现在,您记录的端点列表构成了凹形船体顶点的有序列表.

注意:如果存在不与任何其他线段相交的"自由浮动"外围线段,则会失败.但是,您指定"条形图唯一定义解决方案",这将排除此失败条件.(边远部分可以实现两种截然不同的解决方案.)

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

编辑实际上,如果您的分段集合"非常凹",也可能会失败,即如果在您的一堆段的隐士角落中隐藏着端点.在下图中,我添加了一个黑色部分.我的算法会非法将其端点连接到另一个端点(灰色虚线).我会留下我的答案,万一其他人倾向于建立它.

在给出这个更多的想法之后编辑:即使在"非常凹"的情况下,这个解决方案肯定会以正确的顺序给你凹陷的所有点,但是它们可能会穿插额外的,不合适的点,如黑色一.所以可能有太多的分数.

当然,答案是做一些修剪.这将是相当复杂的修剪,特别是如果你可以有多个连续的"隐藏点",如黑色,所以我没有考虑智能算法.但即使是盲目的,蛮力也是可行的.每个点都可以被接受或拒绝(布尔值),因此如果你的凹形船体中有N个正确排序的候选点,那么只有2 ^ N个可能性来检查.这是方式,方法比蛮力您的原始排列的问题,这将有可能减少SUM of (n!/(n-k)!) for k=1:(n-1)的可能性(请原谅我的符号).因此,该算法显着缩小了您的问题.

我认为这是要走的路.