Bentley Ottmann 扫描线法

比较传统的老办法，只能求交不能布尔。

目前最好的文章是这篇。

建议先依据该算法把扫描线的结构搭出来。

Martinez 扫描线法

相关论文。

还可以看一下 Boost::polygon 的源码，虽然我没看完，但是感觉用的就是 Martinez 扫描线法（流程很相似），而且它论文上也说它用的是扫描线。

还在网上找到唯一一篇讲解 Martinez 扫描线法的中文文章。

求交

求交不需要考虑特殊情况，唯有一些需要人为调控的精度误差，具体思路在论文中已经介绍的很详细了，就不赘述了。

  1. 按照 Bentley Ottmann 扫描线法的逻辑将所有点事件加入优先队列中，并依次处理；

点事件排序时，对于坐标值相同的节点事件，应把终点放在起点前面，其次如果都是起点再继续比较另一个端点（终点）的纵坐标（优先）和横坐标。

  1. 如果存在线段相交，应将其裁剪并将新的点事件加入优先队列，同时根据布尔规则选取有效线段加入集合中。

布尔

因为最近在忙别的任务，暂时只研究了一些。

代码

代码讲解。