6

I need a good (robust) algorithm for splitting a polygon into two sets(left/right) by a line segment. My polygon representation is simply a list of integer coordinates(ordered clock wise, never self intersecting) and the line segment is represented by a start and end point. The line always starts and ends outside the polygon, i.e. intersects the polygon an even number of times.

Here is an example:

The polygon should be split into two sets of two polygons each.

The output of the algorithm should be the two sets(travelling clock wise):

  • Left: HABCH, FGDEF
  • Right: HCDGH, BAB, FEF

I can identify the points A-H by iterating the polygon and checking if a polygon segment crosses the line, taking care to respect border cases. I can also determine which side each multi-line belongs to. I cannot though, for the life of me, decide how to string these segment together.

Before you suggest a general purpose clipping library: I am using boost polygon which is very good at clipping polygons against each other, but I haven't found any library which let's you clip a polygon against a line segment and it is not possible in general to turn the line segment into a polygon which I could clip with.

EDIT: I had missed FEF and the fact that a polygon can have parts on both sides of the line segment.

4

3 回答 3

1

好的，这是一个相当简单的方法来得出答案：

从按顺时针方向移动轮廓排序的交点集开始：

  • ABCDEFGH

根据与行首的距离对它们进行排序：

  • HCFEDGBA

我们还需要记住每个点是从左到右还是从右到左的交叉点。

  • 从任何一点开始。假设 G。顺时针跟随轮廓并将 GH 添加到当前多边形。
  • 现在我们需要沿着这条线旅行。方向取决于我们在直线的哪一侧。我们在右边，所以我们需要在排序集中选择 H 右边的值： C. 将 HC 添加到当前多边形。
  • 顺时针跟随轮廓并将 CD 添加到当前多边形。
  • 我们在右边，所以我们需要在排序集中选择 D 右边的值： G. 将 DG 添加到当前多边形。
  • 我们现在已经到达起点，所以让我们保存多边形（GHCDG）并从列表中删除使用的点。
  • 从另一点重新开始。
于 2015-03-17T09:28:00.753 回答
0 
For each intersection of the polygon border with the line segment:
    Add a new point to the polygon.
    Remember the new points in a new-point set.

Add the original polygon to the polygon set.

For each pair of points in the new-point set:
    For each polygon in the current polygon set:
        If the line segment between the points is completely inside the polygon.
           Replace the polygon in the polygon set with two polygons 
           generated by dividing the original polygon along the line 
           segment between the points.

For each polygon in the polygon set:
    Add it to the Left result set or the Right result set.
    (Note this may not be possible.  
        Consider your example of the segment starting between C and F: 
        You will end up with a polygon (GABCFG) that touches both 
        sides of the dividing segment.  Is that a Left or a Right?
于 2015-03-10T15:42:53.943 回答
0

我曾经解决过类似的问题，但我放弃了变得聪明。

  1. 围绕所有顶点运行，使它们成为连接的线段，每次与切割线相交时，都会从一个新点开始一个新的线段。
  2. 找到所有共享一个端点的段，然后将它们重新连接成一个更长的段。
  3. 连接所有开口端。
于 2015-03-10T15:50:55.963 回答