algorithm - 如何找到建立在多边形顶点上的所有线段的交点？

Question

给定顶点坐标已知的凸多边形。每对顶点由一条线段连接。是否有有效的算法来找到结果线段的交点？

例如，对于正十二边形，所有线段形成这张图片：

如何有效地找到这张图片上所有交叉点的坐标？

Answer 1

内部交叉点的数量上限为 n 选择 4，其中 n 是顶点数。不幸的是，对于一般位置的凸多边形，它们都是不同的，因此一种有效的算法是枚举 4 个组合（例如，使用这种方法）并计算每个组合产生的一个交点（如果你在顺时针顺序，然后是从最低到第二高的线段与从第二低到最高的线段的交点）。

如果您特别对规则多边形感兴趣，则可能会做得更好。

Answer 2

如果我是对的，在任何正多边形中，所有线段都与所有线段0-i相交，因此存在交叉点。然后您可以轮换时间以获得所有解决方案。j-k0<j<ii<k<n-1O(n³)n2π/n

有重复的交叉点，但我怀疑（没有证据）这不会改变渐近行为，并且蛮力可能是有效的。我不知道如何避免重复。