我正在尝试执行一个带圆圈列表的函数,并仅返回完全重叠的圆形列表(一个在另一个内部).问题是该算法至少为O(n²),这是由于getConcentricCircles函数中的嵌套for,以及大数据集的年龄.有没有办法优化它？
编辑：我不知道这是否有帮助,但我使用该算法来检测虹膜和瞳孔检测中的假阳性.如果圆圈完全位于另一个圆圈内,则可能是瞳孔,外部是虹膜.它们应该是同心的,简化了很多,但是人眼中的瞳孔并不完全位于虹膜的中心,这就是我这样做的原因.
编辑2：我已经用Peter Lawrey的解决方案替换了isCircleInCircle,对于某些情况我的不正确
用于检查圆圈是否在圆圈内的功能：
private static boolean isCircleInCircle(Circle a,Circle b) {
// the circle is inside if the distance between the centre is less than the difference in the radius
double dx = a.getX() - b.getX();
double dy = a.getY() - b.getY();
double radiusDifference = a.getRadius() - b.getRadius();
double centreDistanceSquared = dx*dx + dy*dy; // edited
return radiusDifference * radiusDifference > centreDistanceSquared;
}
然后我互相检查列表中的每个元素,并只保存重叠的圆圈(和重叠的圆圈)：
public HashSettocheck : circleList) {
// if the circles are not the same and one is inside another,if (!tocheck.equals(circle) && isCircleInCircle(circle,tocheck)) {
// add both to the hashset
toReturn.add(circle);
toReturn.add(tocheck);
}
}
}
return toReturn;
}
为了帮助加快您的计划,您必须专注于平均情况：
这意味着小圆圈包含在较大圆圈中.构建有向图,其节点表示圆,其边表示源圆包含目标圆.从半径最大的圆开始.使用深度优先搜索构建图形.如果您知道圆圈a包含在另一个圆圈中.然后尝试找到包含在a中的圆圈b.如果b存在,首先继续b.如果b中没有更多内容,请向前退一步,继续使用未包含在另一个找到的圆圈中的所有圆圈.在最好的情况下,这给出了O(nlog(n))的复杂性.这是由于在搜索包含的节点时管理剩余的节点以及按半径排序.这里最好的情况是所有圆圈具有相同的中心和不同的半径.
编辑：
answer of Aki让我想起了另一种加快速度的方法.在一般情况下,圆圈将形成群集,其中一个圆圈部分地与其他圆圈重叠.所以你可以先计算一个依赖集的分区(不,我不是指独立集,因为这将是NP难的).这减少了上述算法必须使用的数据大小.
然后,在寻找可能完全重叠的候选者时,可能会有另一种改进.由于圆圈包含在平面中,因此可以使用诸如R树或四叉树的空间数据结构来找到可以完全重叠,更有效的候选者.
但是我不认为这会降低最坏情况的复杂性,即使这些建议也会改善上述最坏情况下的性能.新的最坏情况可能是圆形,其中心是规则网格的点,但是在将其与常规网格中的点之间的距离进行比较时具有非常大的半径.
