我有一组不相交的直线，其中一些在顶点处连接。我正在尝试找到最小的多边形（如果存在），该多边形包围给定的点。因此，在下面的图像中，从所有线段的列表中，给定红色点，我只想获取蓝色线段。我正在使用Python，但可能可以从其他语言中调整算法；我不知道这个问题叫什么名字。
如何从一组线段中找到包含一个点的多边形？
5
- Skyler
5
我认为问题陈述不正确（不明确）。红点周围最小的多边形可以由该点西南方向的顶点和东侧的黑色线段组成。 - Alexey Frunze
1我的意思是，由已经存在的线条组成的最小多边形。 - Skyler
@JoshSchultz：尽管赏金已经过期，但你想从n.m.的答案中获取哪些细节？ - Teepeemm
@Teepeemm 我本来希望能看到一两个实现的例子，说实话。也许需要更清晰的描述。我想我需要实现类似当前最佳答案的东西。 - Josh Schultz
@JoshSchultz 我正在开发一个实现方案，但在悬赏过期之前没有进展得足够快。 FWIW. - Teepeemm
4个回答
7
首先，删除所有至少有一个自由端点且与其他线段不重合的线段。重复此操作直到不再存在这样的线段。
现在你已经将平面很好地分成了多边形区域。
找到距离你的点最近的线段。注意，不是最近的端点，而是最近的线段。找出你需要沿着线段的哪个方向（你的点应该在定向线段的右侧）。前往端点，向右转（也就是说，取从你来的那条线段开始顺时针计数的下一条线段）。继续前往下一个端点并向右转，直到再次遇到最近的线段。
然后，检查多边形是否包围给定点。如果没有，那么你找到了一个“孤岛”；删除该多边形及其所属的整个连通组件，并重新选择最近的线段。可以使用简单的DFS找到连通组件。
这会给你一个顺时针方向的多边形。如果你想要逆时针方向，这通常是软件和文献中默认的“正”方向，请从你左侧的点开始，在每个交点处向左转。
如果能够快速找到与端点相连的所有线段，那肯定会有所帮助。
- n. m.
6
1@WolframH：是的，当然，忘记加上了。一个点可能在任何封闭多边形之外。 - n. m.
如果最近的线段在不包含该点的另一个多边形中，该怎么办？ - Skyler
@Skyler：抱歉，我总是忘记提到重要的事情。我已经有一段时间没有做计算几何算法了。回答已更新。 - n. m.
你可以通过暴力构建所有可能的多边形，然后检查每个多边形是否包含目标点。如果问题规模较小或需要重复多次针对不同点进行计算，这种方法可能比先尝试寻找附近边缘更好。 - agentp
@george: 是的，对于多个点的预处理应该会带来一些优势。 - n. m.
"找到与您的点最接近的线段。" - 这听起来像需要全局最接近的线段，但在给定方向上最接近的线段不是完全足够的吗？ - O. R. Mapper
1
方法. 我建议将输入解释为一个由顶点和边组成的 PSLG G。然后你的问题就变成了找到被点 p 打中的 G 的面。这可以通过从 p 射出一条射线来找到面边界的一条边，并沿着面边界向某个方向遍历来完成。然而，第一条被击中的边可能是一个没有被 p 击中的面，而是被 p 击中的面所包围的面。因此，我们可能需要沿着由 p 发出的射线继续搜索。
实现细节. 在下面的代码中，我朝东方射出一条射线，并按顺时针方向沿着面运行，即在每个顶点处取下一个逆时针边，直到再次回到第一个顶点。结果的面以 G 的顶点序列返回。
如果你想返回一个 简单多边形，那么你需要通过修剪 G 中的树来清理输入图形，只保留简单的面。
def find_smallest_enclosing_polygon(G, p, simple=False):
"""Find face of PSLG G hit by point p. If simple is True
then the face forms a simple polygon, i.e., "trees"
attached to vertices are pruned."""
if simple:
# Make G comprise simple faces only, i.e., all vertices
# have degree >= 2.
done = False
while not done:
done = True
for v in [v in vertices if degree(v) <= 1]:
# Remove vertex v and all incident edges
G.remove(v)
done = False
# Shoot a ray from p to the east direction and get all edges.
ray = Ray(p, Vector(1, 0))
for e in G.iter_edges_hit(ray):
# There is no enclosing face; p is in the outer face of G
if e is None:
return None
# Let oriented edge (u, v) point clockwise around the face enclosing p
u, v = G.get_vertices(e)
if u.y < v.y
u, v = v, u
# Construct the enclosing face in clockwise direction
face = [u, v]
# While not closed
while face[-1] != face[0]:
# Get next counter-clockwise edge at last vertex at last edge.
# If face[-1] is of degree 1 then I assume to get e again.
e = G.get_next_ccw_edge(face[-2], face[-1])
face.append(G.get_opposite_vertex(e, face[-1]))
# Check whether face encloses p.
if contains(face, p):
return face
return None
复杂性。 设n表示顶点数。请注意，在PSLG中，边的数量为O(n)。修剪部分可能需要O(n^2)的时间来执行上面的实现方式。但是可以通过识别度数为1的顶点并从它们开始遍历，在O(n)的时间内完成修剪操作。
射线相交例程可以轻松在O(n)时间内实现。构建面需要O(m)时间，其中m为构建的多边形大小。我们可能需要测试多个多边形，但所有多边形的大小之和仍然为O(n)。测试contains(face, p)可以通过检查face是否包含由G.iter_edges_hit(ray)返回的奇数条边来完成，即在O(m)的时间内完成。
通过计算几何中传统的点定位算法，可以进行一些预处理，建立一个数据结构，在O(log n)的时间内找到被p击中的面，并可以事先存储简单和/或非简单情况下的结果多边形。
- S. Huber
1
这实际上只是@n.m.答案的一种实现。这是在赏金到期之前我所做的努力；它完全没有经过测试。
def smallestPolygon(point,segments):
"""
:param point: the point (x,y) to surrond
:param segments: the line segments ( ( (a,b),(c,d) ) , . . . )
that will make the polygon
(assume no duplicates and no intersections)
:returns: the segments forming the smallest polygon containing the point
"""
connected = list(segments)
def endPointMatches(segment1,segment2):
"""
Which endpoints of segment1 are in segment2 (with (F,F) if they're equal)
"""
if ( segment1 == segment2 or segment1 == segment2[::-1] ):
return ( False, False )
return ( segment1[0] in segment2 , segment1[1] in segment2 )
keepPruning = True
while ( keepPruning ):
keepPruning = False
for segment in connected:
from functors import partial
endPointMatcher = partial(endPointMatches,segment1=segment)
endPointMatchings = map(endPointMatcher,connected)
if ( not and(*map(any,zip(*endPointMatchings))) ):
connected.remove(segment)
keepPruning = True
def xOfIntersection(seg,y):
"""
:param seg: a line segment ( (x0,y0), (x1,y1) )
:param y: a y-coordinate
:returns: the x coordinate so that (x,y) is on the line through the segment
"""
return seg[0][0]+(y-seg[0][1])*(seg[1][0]-seg[0][0])/(seg[1][1]-seg[0][1])
def aboveAndBelow(segment):
return ( segment[0][1] <= point[1] ) != ( segment[1][1] <= point[1] )
# look for first segment to the right
closest = None
smallestDist = float("inf")
for segment in filter(aboveAndBelow,connected):
dist = xOfIntersection(segment,point[1])-point[0]
if ( dist >= 0 and dist < smallestDist ):
smallestDist = dist
closest = segment
# From the bottom of closest:
# Go to the other end, look at the starting point, turn right until
# we hit the next segment. Take that, and repeat until we're back at closest.
# If there are an even number of segments directly to the right of point[0],
# then point is not in the polygon we just found, and we need to delete that
# connected component and start over
# If there are an odd number, then point is in the polygon we found, and we
# return the polygon
- Teepeemm
0
如果您需要多次使用相同的线和不同的点进行此操作，预处理以找出所有多边形将是值得的。然后就很简单了：从该点向无限远处（概念上）绘制一条直线。每次穿过一条线时，增加该线所属的每个多边形的交叉计数。最后，具有奇数交叉计数的第一个多边形是最小的包围多边形。由于任何任意的线都可以像其他任何线一样做得很好（甚至不需要是直线），因此通过绘制垂直或水平线来简化算术，但要注意穿过实际端点。
您可以通过在穿过每条线时创建多边形来完成此操作。这基本上缩小到n.m.的算法，但没有所有特殊情况的检查。
请注意，一条线可以属于两个多边形。实际上，它可能属于更多，但我不清楚如何告诉您：请考虑以下内容：
您可以通过在穿过每条线时创建多边形来完成此操作。这基本上缩小到n.m.的算法，但没有所有特殊情况的检查。
请注意，一条线可以属于两个多边形。实际上，它可能属于更多，但我不清楚如何告诉您：请考虑以下内容：
+---------------------------+
| |
| +-------------------+ |
| | | |
| | +-----------+ | |
| | | | | |
| | | | | |
+---+---+-----------+---+---+
- rici
5
你的例子中考虑多少个多边形 - 3还是6？你如何找到它们？ - Reinstate Monica
有3个最小多边形（不是其他多边形的一部分），恰好有6条线段属于两个多边形（两个内部Π形状的折线）。 - n. m.
@WolframH：显然有三个多边形。如果你不知道它们是哪些，那么你必须假设没有一个多边形包含另一个。但是，如果两个外部多边形向下掉落了一小部分像素（最外层的两个多边形掉落了两个小部分），那么你会得到不同的读数。 - rici
@n.m.：我有点同意，但是你如何定义“不是其他多边形的一部分”，以一种排除岛屿的方式呢？只是好奇...我认为通过分析单独的线段，你无法得出其他答案。 - rici
@rici：为了保持一致性，最好以带孔的多边形为基础进行操作。然后岛屿就不是问题了，它们不是其他多边形的一部分，它们只是适合某个洞中。然而，实现起来会更加复杂。我的算法不计算孔。如果需要孔，可以像下面这样搜索：给定一个多边形，开始检查所有不属于它的顶点。如果一个顶点位于该多边形内部，则找到并消除其连接组件，然后找到其外边界；这是一个孔。然后检查下一个剩余的顶点等。 - n. m.
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接