algorithm - 多边形算法中的多边形

Question

问题比较简单，确定一个多边形是完全在里面，完全在外面，还是被另一个多边形切割，但是，多边形可能共享顶点或部分边。首先，我想检查多边形 A 中的每个顶点是否位于多边形 B 的内部/外部，一旦 B 切割 A，这就会失败，请参阅：

左：A 将被归类为 B 之外

右：A 将被归类为 B 的内部

下一个想法是，检查是否有交叉点，如果有，则将其归类为切割，如果没有，则检查 A 的任何点，如果它在 B 内部。但是，如果该检查点落在B，它可以是两者，内部或外部。

因此，只需检查 A 与 B 的所有点，直到找到一个不位于 B 边缘的点，但是，如果 A 的所有点都位于 B 的边缘，这也可能失败，请参阅：

左：A 应归类为内部

右：A 应归类为外部

所以问题仍然存在，在这种情况下，您如何毫无疑问地确定多边形 A 是否位于多边形 B 内部或外部，是否可以共享边和顶点。

标签： algorithmpolygon

Answer 1

所以绿色多边形的所有顶点都位于黑色多边形的边界上，并且没有“明显”的 x 形边缘交叉点（你应该已经消除了那些；或者你可以在每个交叉点插入一个人工顶点以减少以下情况的问题）。

首先，对于位于另一个多边形边界上的任一多边形的每个顶点，在该点向另一个多边形插入一个人工顶点（如果那里还没有一个）。你对所有绿色顶点都这样做，也许还有一些黑色顶点。这是必要的，以便所有边缘交叉点都很简单。两条边没有公共点，一个公共点（在它们的公共顶点处），或所有公共点（两个顶点和它们之间的所有东西；这些边是相同的）。

一旦所有的交叉点都简单，问题就简单了。

对于绿色边缘的所有中点，确定所述中点是在黑色多边形内部还是外部。丢弃那些在边界上的。

如果它们都在里面，那么绿色多边形就在黑色多边形里面。如果都在外面，那么它不在里面（可能在外面，或者黑色的可能在绿色的里面；颠倒角色并再次执行程序以确定是哪种情况）。如果有些在里面，有些在外面，那就是一个有趣的交叉点。

没有任何不在边界上的中点？这两个多边形是相同的。