我正在为旅行推销员问题绘制一个多边形，并想测试任何路径的不相交，作为自适应停止遗传搜索的一种手段。我尝试简单地检查线段或交叉点，但有时会得到不正确的结果，即使保留一个或多个交叉点也会终止搜索。
问问题
128 次
1 回答
1
这个问题本质上等同于检测任意一组线段中的交叉点。
例如，可以使用本特利-奥特曼算法来解决这个问题。当然，您可以在找到一个交叉点后立即终止。
一个简单的检查只会检查每条边与每条其他边（在多边形中不相邻，因为它们不能相交），但由于您只需要找到一个交点，因此输出敏感算法（如bentley-ottmann）可以加快你的支票相当多。
于 2011-05-17T22:32:29.740 回答