如何判断多边形是否自相交

来源：百度知道 编辑：UC知道 时间：2024/06/07 07:24:54
自相交是指一个多边形不相邻的边相交。
如何快速判断是否自相交？
时间复杂度应在O(n^2)以下
求出来再给附加d

首先需要一个“快速”判断线段相交的算法（网上一大把，自己搜索一下）；
逐边两两判断，如果存在2个线段相交，则多边形自相交；
否则（最坏情况），多边形“不自相交”，比较次数n*(n-1)/2