我有一个System.Windows.Shapes.Polygon
对象,其布局完全由一系列点决定。我需要确定这个多边形是否是自相交的,即多边形的任何边是否在一个不是顶点的点处与任何其他边相交。
有没有一种简单/快速的方法来计算这个?
简单、缓慢、低内存占用:将每个段与所有其他段进行比较并检查交叉点。复杂度O(n 2 )。
稍快,中等内存占用(上面的修改版本):将边缘存储在空间“桶”中,然后在每个桶的基础上执行上述算法。m个桶的复杂度O(n 2 / m)(假设均匀分布)。
快速和高内存占用:使用空间散列函数将边分割成桶。检查碰撞。复杂度O(n)。
最后一个是我最喜欢的,因为它具有良好的速度-内存平衡,尤其是Bentley-Ottmann 算法。实现也不是太复杂。
检查是否有任何一对不连续的线段相交。
为了完整起见,我在此讨论中添加了另一种算法。
假设读者知道轴对齐的边界框(如果不知道,请谷歌它)使用“扫描和修剪算法”快速找到具有 AABB 冲突的边缘对可能非常有效。(去谷歌上查询)。然后在这些对上调用交叉点例程。
这里的优点是您甚至可以与非直边(圆和样条)相交,并且该方法更通用,尽管几乎同样有效。
我是这里的新蜜蜂,这个问题已经够老了。但是,这是我的 Java 代码,用于确定由一组有序点定义的多边形的任何一对边是否交叉。您可以删除用于调试的打印语句。我也没有包含返回找到的第一个交叉点的代码。我正在使用标准 java 库中的 Line2D 类。
/**
* Checks if any two sides of a polygon cross-over.
* If so, returns that Point.
*
* The polygon is determined by the ordered sequence
* of Points P
*
* If not returns null
*
* @param V vertices of the Polygon
*
* @return
*/
public static Point verify(Point[] V)
{
if (V == null)
{
return null;
}
int len = V.length;
/*
* No cross-over if len < 4
*/
if (len < 4)
{
return null;
}
System.out.printf("\nChecking %d Sided Polygon\n\n", len);
for (int i = 0; i < len-1; i++)
{
for (int j = i+2; j < len; j++)
{
/*
* Eliminate combinations already checked
* or not valid
*/
if ((i == 0) && ( j == (len-1)))
{
continue;
}
System.out.printf("\nChecking if Side %3d cuts Side %3d: ", i, j);
boolean cut = Line2D.linesIntersect(
V[i].X,
V[i].Y,
V[i+1].X,
V[i+1].Y,
V[j].X,
V[j].Y,
V[(j+1) % len].X,
V[(j+1) % len].Y);
if (cut)
{
System.out.printf("\nSide %3d CUTS Side %3d. Returning\n", i, j);
return ( ... some point or the point of intersection....)
}
else
{
System.out.printf("NO\n");
}
}
}
return null;
}