确定线段集合的非凸包 [英] Determine non-convex hull of collection of line segments
问题描述
我有一个计算几何问题，我觉得应该有一个相对简单的解决方案，但我无法弄清楚。
我需要确定非 - 凸几何线段定义的区域的轮廓线。
我知道各种非凸外壳算法（例如alpha形状），但我不需要这是一个完全一般的算法，因为线段在大多数情况下定义了一个独特的解决方案。正如@ Jean-FrançoisCorbett指出的那样：
有些情况下有多种解决方案。我显然需要更多地考虑我的定义。然而，我想要做的是反向工程，并使用专有文件格式，以便我可以对自己和其他人收集的数据进行基本分析。文件格式非常简单，但确定它们用来定义边界的算法相当困难。
引入许多导致非唯一解决方案的边缘情况会导致相关软件崩溃而无法警告或无法默认读取文件。因此，当存在多种解决方案时，无论是生成一种可接受的解决方案还是能够确定存在多种解决方案都是可以接受的。
问题定义：
多边形的轮廓不应该交叉任何细分市场，应该由连接所有细分市场端点的线组成。所有的段必须完全位于多边形的内部或沿着多边形的边界。
在轮廓中不能使用多个端点（通过在需要关闭多边形的软件库末尾添加第一个点来忽略关闭多边形。如果有多种解决方案符合这一标准，那么这些解决方案中的任何一种都可以接受。 （能够确定解决方案何时是非唯一的，但这不是绝对必要的。）例子：
举例来说，我有这样一些内容：
我想划定以下区域：
它也适用于不相交的细分市场。例如
无论在哪种情况下都有独特的解决方案，但须遵守前面的标准。 （编辑：一般来说，没有一个独特的解决方案，正如@ Jean-FrançoisCorbett指出的那样。但是，我仍然对算法产生一种可接受的解决方案感兴趣。）
测试用例
对于测试用例，下面是生成上述数字的代码。
import matplotlib.pyplot as plt
$在这里使用python，但问题是语言不可知的。 b $ b def main（）：
test1（）
test2（）
plt.show（）
def test1（）：
相交线段。
segments = [[（1,1），（1,3）]，
[（3.7,1），（2,4）]，
（4,0），（4,4，4）]，
[（4.3,1），（4.3,3）]，
[（0,2），（6,3）]]
desired_outline = [segments [0] [0]，segments [5] [0]，segments [0] [ 1]，
段[1] [1]，段[2] [1]，段[3] [1]，
段[4] [1]，段[5] [1] ，段[4] [0]，
段[3] [0]，段[1] [0]，段[2] [0]，
段[0] [0]]
plot（segments，desired_outline）
def test2（）：
非相交线段。
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]，
段[2] [1]，段[3] [1]，段[3] [0]，
段[2] [0]，段[1] [0]，段[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'）
$ b $ def plot_segments（ax，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 沿着由点扩展定义的主轴进行缩放和旋转。这使问题更加循环）。但是，这在很多情况下会产生轮廓与线段相交的解决方案。它很容易检测到这个，并从那里蛮力，但肯定有更好的办法？
<李>选择一个安全的起点。可以是例如最大x的端点。
注意：如果存在不与任何其他线段相交的自由浮动外线段，则会失败。但是，您需要指定酒吧唯一定义的解决方案，它排除了这种失败情况。 （外围细分可以提供两种独特的解决方案。）
编辑 ...或者说，离线细分可以制作两种独特的解决方案 - 取决于确切的布局。证明：下面是一个例子，我添加的黄色部分提供了两种解决方案（蓝色和灰色可怕的手绘线条）。如果黄色片段现在垂直于其绘制的方向，则只有一种解决方案是可能的。听起来像你的问题定义不清。
编辑实际上，如果您的细分收藏非常凹，也就是说，如果有隐藏的端点隐藏在隐居处你的一堆细分的角落。在下图中，我添加了一个黑色部分。我的算法会非法将其端点连接到另一个端点（灰色虚线）。如果其他人倾向于依靠它，我会留下我的回答。 即使在非常凹陷的情况下，这个解决方案也一定会按照正确的顺序给你所有凹面点的所有点，但是它们可能会穿插有额外的不适当的点，比如黑色点。所以可能会有太多 点。
当然，答案是做一些修剪。这将会非常复杂，特别是如果你可以有多个连续的隐居点，比如黑色的，所以我没有一个聪明的算法。但即使是盲目的，蛮横的力量也是可行的。每个点都可以被接受或被拒绝（布尔），所以如果你的凹壳中有适当的候选点，那么只有2 ^ N的可能性来检查。对于你原来的排列问题，对于k = 1 :(（n！/（nk）！）的和， n-1）可能性（原谅我的记法）。所以这个算法显着缩小了你的问题。
我想这是要走的路。 $ b
I have a computational geometry problem that I feel should have a relatively simple solution, but I can't quite figure it out.
I need to determine the non-convex outline of a region defined by several line segments.
I'm aware of various non-convex hull algorithms (e.g. alpha shapes), but I don't need a fully general algorithm, as the line segments define a unique solution in most cases.
As @Jean-FrançoisCorbett has pointed out, there are cases where there are multiple solutions. I clearly need to think more about my definition.
However, what I'm trying to do is reverse-engineer and use a proprietary file format so that I can run basic analyses on data collected by myself and others. The file format is simple enough, but determining the algorithm they use to define the boundary is considerably harder.
Putting in many of the edge cases that would result in a non-unique solution causes the software in question to either crash without warning or silently fail to read the file.
Therefore, when there are multiple solutions, either generating one of the acceptable solutions or being able to determine that there are multiple solutions would be acceptable.
Problem Definition:
The polygon's outline should never cross any of the segments and should be formed of lines joining all of the segments' endpoints. All segments must lie entirely inside or along the boundary of the polygon. No endpoint may be used more than once in the outline (Ignoring "closing" the polygon by adding the first point at the end for software libraries that require polygons to close.).
In cases where there are multiple solutions that meet this criteria, any one of those solutions would be acceptable. (It would be nice to be able to determine when the solution is non-unique, but this isn't strictly necessary.)
Examples:
As an example, I have something along these lines:
And I'd like to delineate the following area:
It also should work for non-intersecting segments. E.g.
I think (?) there's a unique solution in either case, subject to the criteria outline earlier. (Edit: There isn't a unique solution in general, as @Jean-FrançoisCorbett pointed out. However, I'm still interested in an algorithm that would either generate one of the acceptable solutions.)
Test Cases
For a test case, here's the code to generate the above figures. I'm using python here, but the question is language-agnostic.
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()
Any ideas?
I'm beginning to suspect that the software whose results I'm trying to reproduce uses a radial-sweep algorithm in some sort of "internal" coordinate system (e.g. A coordinate system with x-prime and y-prime scaled and rotated along the principal axes defined by the spread of points. This makes the problem more "circular".) However, this produces solutions where the outline intersects line segments in many cases. It's easy enough to detect this and brute force it from there, but surely there's a better way?
- Pick a safe starting point. Can be e.g. the endpoint with maximum x.
- March along the line segment.
- Upon encountering any intersection, always turn left and march along this new segment.
- Upon encountering an endpoint, record it. Goto 2.
- Stop when you have returned to your starting point. Your list of recorded endpoints now makes up the ordered list of vertices of your concave hull.
NB: This will fail if there is a "free-floating" outlying line segment that does not intersect any other line segment. However, you specify that "the bars uniquely define a solution", which rules out this fail condition. (Outlying segments make possible two unique solutions.)
EDIT ... or rather, outlying segments can make two unique solutions possible -- depending on the exact layout. Proof: Below is an example where the yellow segment that I added makes two solutions possible (blue and grey horribly hand-drawn lines). Were the yellow segment orientated perpendicular to the way it's drawn now, only one solution would be possible. Sounds like your problem is poorly defined.
EDIT Actually this can also fail if your segment collection is "very concave", i.e. if there are endpoints tucked away in recluse corners of your pile of segments. In the figure below I added a black segment. My algorithm would illegally join its endpoint to another endpoint (dashed grey line). I'll leave my answer be in case others are inclined to build upon it.
EDIT after giving this some more thought: Even in the "very concave" case, this solution will definitely give you all of the points of your concave hull in the proper order, but they may be interspersed with extra, inappropriate points such as the black one. So there may be too many points.
The answer is then, of course, to do some pruning. It would be fairly complicated pruning especially if you can have multiple, consecutive "recluse points" like the black one, so I don't have a smart algorithm in mind. But even blind, brute force could be feasible. Each point can be either accepted or rejected (boolean), so if you have N properly ordered candidate points in your concave hull, then there are only 2^N possibilities to check. This is way, way fewer possibilities than brute force for your original problem of permutations, which would have SUM of (n!/(n-k)!) for k=1:(n-1) possibilities (pardon my notation). So this algorithm narrows down your problem significantly.
I think this is the way to go.
这篇关于确定线段集合的非凸包的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
