如何用直线分割多边形?

我最近不得不这么做。就像在图中一样,只沿着多边形走是不适用于凹多边形的。下面是我的算法的草图,灵感来自 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.

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

遍历多边形边,并为每个边确定它是否与直线相交。找到第一个这样的边缘。继续遍历,直到找到另一条这样的边,但将沿途遇到的每个边添加到一个新多边形(包括第一条边被“此边”上的线分割的部分,以及最后一条边的部分)。最后,向新多边形添加闭合边。现在继续处理边-在直线的另一侧,以相同的方式创建另一个多边形。现在有两个多边形在直线上分割。如果你小心的话,同样的技术也可以将非凸多边形分割成多个多边形。

当心角情况,例如线与多边形顶点相交,线与多边形根本不相交。

编辑: 正如Xan指出的,这并不能正确地处理所有非凸的情况。这可以通过对算法的小修改来解决。在按上述方式添加闭合边之前,必须首先检查原始多边形的任何其他边是否与该闭合边相交;如果是,则只能闭合到该边,并继续处理该点的其他边。

你只需要一个多边形剪辑。您可以在此处查看概述: Polygon clipping 我认为这里有一些Penty实现,您可以从中学习。

这是完全可能的。我假设您使用的是Java2D。您已经在其中找到了一个名为intersects的方法。用它你可以做到。

你可能需要修改 this 实现多边形,再编写一个相交方法,该方法传递一个Line2d对象,并对其进行自定义,使其传递一个数组多边形(可能的原因是相同的线切割可以生成无限多个多边形-假定为之字形多边形)或空。

1994年,乔治·瓦内切克(George Vanecek)提出了一个三维的解决方案,并在图形宝石V“平面对多边形的空间划分”中发表了该解决方案。源代码在 Graphic Gems Repository .

最近,DavidGeier发布了一个Vanecek算法的二维实现,并解释了该算法。见 David's Blog: Splitting an arbitrary polygon by a line