如何用线分割多边形？

Question

如下所示,

是否可以用线分割多边形？(分为两个多边形).如果线没有一直穿过多边形,那么它将失败.

这可能吗？如果是这样,我该怎么做？

Answer 1

我最近不得不这样做.只是走多边形不适用于凹多边形,如图中所示.下面是我的算法草图,灵感来自Greiner-Hormann多边形裁剪算法.分割比多边形裁剪更容易和更难.更简单,因为您只剪切线而不是矩形或其他多边形; 更难,因为你需要保持双方.

Create an empty list of output polygons
Create an empty list of pending crossbacks (one for each polygon)
Find all intersections between the polygon and the line.
Sort them by position along the line.
Pair them up as alternating entry/exit lines.
Append a polygon to the output list and make it current.
Walk the polygon. For each edge:
    Append the first point to the current polygon.
    If there is an intersection with the split line:
        Add the intersection point to the current polygon.
        Find the intersection point in the intersection pairs.
        Set its partner as the crossback point for the current polygon.
        If there is an existing polygon with a crossback for this edge:
            Set the current polygon to be that polygon.
        Else
            Append a new polygon and new crossback point to the output lists and make it current.
        Add the intersection point to the now current polygon.

Answer 2

这是可能的,但如果多边形不是凸面,那么将它分割成一条线可能会导致两个以上的多边形.

遍历多边形边,并为每条边确定它是否与线相交.找到第一个这样做的边缘.继续遍历,直到找到另一个这样的边,但将沿途遇到的每个边添加到一个新的多边形(包括第一条边的一部分,该部分由"此侧"的线分开,同样适用于最后一条边).最后,为新的Polygon添加一个结束边.现在继续处理边缘 - 在线的另一侧,以相同的方式创建另一个多边形.您现在有两个多边形分割线.如果您小心,将非凸多边形分割为多个多边形,相同的技术将起作用.

注意角落情况,例如穿过多边形顶点的线,以及根本不与多边形相交的线.

编辑:正如xan指出的那样,这将无法正确处理所有非凸案例.这可以通过对算法的小修改来修复.在如上所述添加结束边之前,必须首先检查原始多边形的任何其他边是否与该结束边相交; 如果是这样,您只关闭该边缘并继续处理该点的更多边缘.