我有一个计算几何问题，我认为应该有一个相对简单的解决方案，但我无法弄清楚。
我需要确定由多条线段定义的区域的非凸轮廓。
我知道各种非凸包算法（例如alpha形状），但是在大多数情况下，由于线段定义了唯一的解决方案，我不需要完全通用的算法。
正如@Jean-FrançoisCorbett所指出的那样，有些情况存在多个解决方案。我显然需要更多地思考我的定义。
然而，我的目的是反向工程并使用专有文件格式，以便我可以对自己和他人收集的数据进行基本分析。文件格式足够简单，但确定他们用来定义边界的算法要困难得多。
加入许多会导致非唯一解的特殊情况会导致相关软件在没有警告的情况下崩溃或未能静默读取文件。
因此，在存在多个解时，生成一个可接受的解之一或能够确定存在多个解都是可以接受的。
多边形的轮廓不应跨越任何线段，并且应由连接所有线段端点的直线组成。 所有线段必须完全位于或沿着多边形的边界上。 大多数软件库需要多边形成为封闭的，因此不考虑通过在末尾添加第一个点来“关闭”多边形。
在满足此标准的情况下存在多个解决方案时，任何一个这些解决方案都是可以接受的。（能够确定解决方案是否不唯一会很好，但这并非严格必要。）
例如，如果我有以下情况：
，我希望描绘出以下区域：
。
它也适用于不相交的线段。 例如：
根据前面概述的标准，在任一情况下都有一个唯一的解决方案吗？（编辑：通常不存在唯一解决方案，如@Jean-FrançoisCorbett所指出。 然而，我仍然对能够生成可接受解之一的算法感兴趣。）
以下是生成上述图形的代码。 我在此使用python，但问题与编程语言无关。
我需要确定由多条线段定义的区域的非凸轮廓。
我知道各种非凸包算法（例如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。这使问题更加“圆形”），但是这会产生解决方案，在许多情况下与线段相交。虽然很容易检测到并从那里进行蛮力处理，但肯定有更好的方法，对吧？
