javascript - 如何在两个已知 y 值之间剪裁线段？

Question

我正在实现一种算法来为多边形找到最佳标签位置。可以查到HERE.

要点是我必须根据它们的 y 值对多边形的顶点进行排序。然后，为每个 y 在该点“绘制”一条水平线。这将多边形分成 strip ，最终看起来像这样:

创建这些 strip 后，我必须找到每个 strip 中包含的所有线段的中点。这就是我卡住的地方。例如，在 strip #2 中，最左边的段没有端点来在该 strip 的范围内定义它。它的端点位于 strip #1 的顶部和 strip #3 的底部。

如何将较长的线段剪裁成完全包含在 strip #2 的上下边界中的线段？

更具体地说，我如何确定这两个端点( strip 1 的顶部， strip 3 的底部)是与左侧 strip #2 相交的线的端点？

Answer 1

经典方法是保留一个“事件列表”，该列表存储跨当前坐标的边的索引。当您从一个纵坐标转到下一个纵坐标时，边可以进入或离开列表(它们只会这样做一次)。保持更新。

列表最初为空，最终为空，并且始终包含偶数条边。

如果多边形边从不交叉，您可以保持列表从左到右排序。