很好的解释，加雷斯。我想弄清楚的是如何实现相反的解决方案，即如何从一组矩形开始并引导到多边形。
我的解决方案适用于所有情况，除非两个或多个矩形的部分或整个边缘相互重叠。
如何摆脱构成重叠边缘的点？
问问题
125 次
1 回答
0
根据链接的问题，我将假设矩形是轴对齐的，并且它们具有成对不相交的内部。将每个矩形分解为四个线段，顺时针方向。对水平和垂直段重复以下过程。
按 y 划分水平段。对于每个 y，每个段都会产生两个事件：尾部的开始事件和头部的停止事件。按 x 对事件进行排序（请注意，向左的线段的停止事件位于相应的开始事件之前）。初始化一个变量sign = 0，然后迭代，sign += 1在每个开始事件和sign -= 1每个停止处执行。无论何时sign从0到1，在当前扫描位置开始一个定向段，其尾部。无论何时sign从1到0，在当前扫描位置结束该段，如果它是退化的则丢弃它。类似地，无论何时sign从0到，都以其头部-1开始一个定向段在当前扫描位置。无论何时sign从-1到0，在当前扫描位置结束该段，如果它是退化的，则丢弃它。
于 2014-09-10T14:57:17.813 回答