如何重绘完全自相交的多边形？

Question

问题是重绘自相交2D多边形，它的边界是总是其内部和其外部之间的分隔线并完全横穿本身在某些点（即，在这些点，多边形内部开关的侧边界，从左到右，反之亦然）。

什么是可以做的，最简单的算法？

初始多边形（左）和重绘一个（右）：

。

我又添加了一个更复杂的初始多边形示例，它仍然非常简单（它只有一个自交顶点）in this third picture其中多边形内部填充（点A，B，C，D， E在绘制多边形边框时最初以字母顺序出现）。

Answer 1

你问的不是那么简单。

您可以使用扫描程序。一般原则如下。

当您在多边形画出水平线，它满足偶数边缘。将交叉点从左向右排列，并将它们成对链接，即可获得内部细分。

如果你这样做了横向的所有位置，你就会分解在一些单调链的多边形，即折线一直走下去。

当多简单，链在顶点是成对出现的，在另一对消失，住自己的静物。但是当多边形交叉时，链可以相互交叉。这可以通过以下事实来检测：从水平的一个位置到下一个位置，交叉点的顺序改变。

现在你已经通过“uncrossing”的枷锁，这是由在交叉点分割边做修复。

我不能开发出更多的这里，试图查找“扫掠迹线算法”。