判断多边形是否存在自相交 算法

判断多边形是否存在自相交的常用算法是扫描线算法：

1. 将多边形的所有顶点按照顺时针或逆时针排序，使得相邻两个顶点确定的边不相交。

2. 从上到下扫描整个多边形。扫描线从上往下移动时，维护一个有序集合（如红黑树）来存储当前在扫描线上的线段。

3. 扫描到一个顶点时，如果该顶点是左端点，则将其对应的线段插入有序集合中；如果该顶点是右端点，则将其对应的线段从有序集合中删除。

4. 在插入或删除线段时，检查当前线段是否与其它线段相交。如果存在相交，则说明多边形存在自相交。

需要注意的是，该算法只适用于简单多边形，即多边形的任意两条边之间最多只有一个交点。对于复杂多边形，还需要考虑将其拆分成简单多边形进行处理。