如何用一条线分割多边形？
如下图，
是否可以用线分割多边形？ （分成两个多边形）。如果这条线没有完全穿过多边形，它就会失败。
这可能吗？如果是这样，我该怎么做？
As shown below,
Is it possible to split a Polygon by a Line? (into two Polygons). If the line doesn't go all the way across the polygon it would fail.
Is this possible? If so, how would I do this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
我最近不得不这样做。仅行走多边形对于凹多边形不起作用，如图所示。下面是我的算法草图，灵感来自 Greiner-Hormann 多边形裁剪算法。分割比多边形裁剪既容易又困难。更容易，因为您只剪切一条线而不是矩形或另一个多边形；更难，因为你需要保留双方。
I had to do this recently. Just walking the polygon won't work for concave polygons, as in your diagram. Below is a sketch of my algorithm, inspired by the Greiner-Hormann polygon clipping algorithm. Splitting is both easier and harder than polygon clipping. Easier because you only clip against a line instead of a rect or another polygon; harder because you need to keep both sides.
这是可能的，但如果多边形不是凸的，那么将其分割成一条线可能会导致两个以上的多边形。
遍历多边形边，并为每条边确定它是否与线相交。找到第一个这样做的边。继续遍历，直到找到另一个这样的边，但将沿途遇到的每个边添加到一个新的多边形（包括第一条边被“这一边”上的线分割的部分，最后一条边也是如此）。最后，为新多边形添加一条闭合边。现在继续处理边 - 在线的另一侧，以相同的方式创建另一个多边形。现在您有两个沿直线分开的多边形。如果您小心的话，同样的技术也可以将非凸多边形分割成多个多边形。
请注意极端情况，例如穿过多边形顶点的线以及根本不与多边形相交的线。
编辑： 正如 xan 指出的那样，这不能正确处理所有非凸情况。这可以通过对算法进行小的修改来解决。在如上所述添加闭合边之前，必须首先检查原始多边形的任何其他边是否会与该闭合边相交；如果是这样，则仅关闭该边缘并继续处理从该点开始的其他边缘。
It's possible, but if the polygon is not convex then splitting it across a line potentially leads to more than two polygons.
Traverse the polygons edges, and for each edge determine whether it intersects the line. Find the first such edge which does so. Continue traversing until you find another such edge, but add each you encounter along the way to a new polygon (including the part of the first edge which was split by the line which is on "this side" and likewise for the last edge). Finally, add a closing edge to the new Polygon. Now continue processing edges - on the other side of the line, creating another Polygon in the same manner. You now have two polygons split across the line. The same technique will work, if you are careful, with splitting a non-convex polygon into multiples polygons.
Beware of corner cases such as the line crossing a vertex of the polygon, and the line not intersecting the polygon at all.
Edit: As xan points out, this won't handle all non-convex cases properly. This can be fixed with a small modification to the algorithm. Before you add the closing edge as described above, you must first check if any further edge of the original polygon would intersect that closing edge; if so, you close only up to that edge and continue processing further edges from that point.
1994年，George Vanecek为此制定了3D解决方案，并在Graphic Gems V“Spatial Partitioning of the Polygon by a Plane”中发表了该解决方案。源代码仍然可以在 Graphic Gems 存储库 中找到。
最近，David Geier 发布了 Vanecek 算法的 2D 实现以及对该算法的解释。请参阅David 的博客：用一条线分割任意多边形
In 1994, George Vanecek worked out a solution for this in 3D, and published the solution in Graphic Gems V "Spatial Partitioning of the Polygon by a Plane". The source code is still available in the Graphic Gems Repository.
More recently, David Geier published a 2D implementation of Vanecek's algorithm with an explanation of the algorithm. See David's Blog: Splitting an arbitrary polygon by a line
您所需要的只是一个多边形裁剪算法。您可以在此处查看概述：
多边形裁剪 我认为有一些实现你可以从哪里学习。
All you need is a polygon clipping alogrithem. You can see an overview here:
Polygon clipping I think there are penty implementations out there where you can learn from.
这是完全有可能的。我假设您正在使用 Java2d 来实现此目的。您在其中找到了一种称为相交的方法。使用它你可以做到这一点。
您可能需要修改这个多边形的实现，并编写一个再传递一个 intersects 方法Line2D 对象并对其进行自定义，以便它传递数组多边形（可能是因为相同的线切割可以产生无限多边形 - 假设为锯齿形多边形）或 null。
Its perfectly possible. I am assuming you're using Java2d for this. You have find a method in it called as intersects. Using that you can do this.
You might have to modify this implementation of polygon and write one more intersects method which passes a Line2D object and customize it so that it passes an array polygons (possible since the same line cut can produce infinite polygons - assume a zigzag polygon) or null.
无论您使用什么多边形库，如果它具有标准操作集，它应该能够通过使用零宽度多边形而不是直线来做到这一点。从输入中减去零宽度多边形，您将得到单独的部分。如果您的包不支持真正的零宽度多边形，则为其提供尽可能小的宽度，并在必要时撤消与结果的轻微偏移。
Regardless of what polygon library you are using, if it has the standard set of operations it should be able to do this - by using a zero-width polygon rather than a line. Subtract the zero width polygon from the input and you'll have the separate parts. If your package doesn't support true zero-width polygons then give it the smallest possible width and if necessary undo that slight offset from the results.