5

我有一组不相交的线，其中一些在顶点处连接。我试图找到包含给定点的最小多边形（如果存在）。所以，在下图中，在所有线段的列表中，给定红色的点，我只想得到蓝色的点。我正在使用 Python，但可能会采用其他语言的算法；我不知道这个问题叫什么。

例子

4

4 回答 4

7

首先，删除所有具有至少一个自由端点且与任何其他线段不重合的线段。重复这样做，直到没有这样的段。

现在你有一个很好地细分为多边形区域的平面。

找到最接近您的点的段。请注意，不是最近的端点，而是最近的段。找出您需要沿线段的哪个方向（您的点应该在有向线段的右侧）。走到终点，右转（也就是走你来的路旁边的路段，逆时针计数）。继续前往下一个端点并右转，直到再次到达最近的路段。

然后，检查多边形是否包含给定点。如果不是，那么你找到了一个“岛”；删除该多边形及其所属的整个连接组件，然后通过再次选择最近的线段重新开始。可以通过简单的 DFS 找到连接的组件。

这为您提供了一个顺时针方向的多边形。如果你想要逆时针，这通常是软件和文献中默认的“正”方向，从你左边的点开始，然后在每个路口左转。

如果给定一个端点，您可以快速找到与它相关的所有片段，这肯定会有所帮助。

于 2013-04-22T10:17:14.953 回答
1

这实际上只是@nm 答案的一个实现。这是我在赏金到期前走了多远；它完全未经测试。

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
于 2013-11-14T21:11:28.193 回答
0

如果您使用相同的线和不同的点多次执行此操作，则值得进行预处理以找出所有多边形。然后很简单：从点到无穷大画一条线（从概念上讲）。每次越过一条线时，增加该线所属的每个多边形的交叉计数。最后，第一个具有奇数交叉计数的多边形是最小的封闭多边形。由于任何任意线都将与任何其他线一样好（它甚至不需要是直的），通过绘制垂直或水平线来简化算术，但要注意交叉实际端点。

您可以通过在穿过每条线时创建多边形来执行此操作而无需预处理。这基本上简化为 nm 的算法，但没有所有特殊情况检查。

请注意，一条线可以属于两个多边形。事实上，它可能属于更多，但我不清楚你会如何说：考虑以下内容：

+---------------------------+
|                           |
|   +-------------------+   |
|   |                   |   |
|   |   +-----------+   |   |
|   |   |           |   |   |
|   |   |           |   |   |
+---+---+-----------+---+---+
于 2013-04-23T04:05:46.457 回答
0

方法。 我建议将输入解释为PSLG， G ，它由顶点和边组成。然后你的问题就简化为找到被点 p 击中的 G 的面。这是通过从 p 向某个方向发射光线来找到面部边界的边缘并沿某个方向穿过面部边界来完成的。然而，第一个边缘命中可能是一个未被 p 命中的面，但它本身被 p 命中的面包围。因此，我们可能需要继续沿着 p 发出的射线进行搜索。

实施细节。 在下面的代码中，我向东方向射出一条光线并以顺时针方向绕着脸部运行，即在每个顶点处我取下一个逆时针边，直到我再次到达第一个顶点。结果面作为 G 的顶点序列返回。

如果你想返回一个简单的多边形，那么你必须通过修剪 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 击中的人脸，并且您可以预先存储生成的多边形，用于简单和/或非简单案例。

于 2017-11-02T19:01:45.347 回答