java – 优化圈内检测算法中的圆低于O(n2)
我正在尝试执行一个带圆圈列表的函数,并仅返回完全重叠的圆形列表(一个在另一个内部).问题是该算法至少为O(n2),这是由于getConcentricCircles函数中的嵌套for,以及大数据集的年龄.有没有办法优化它? 编辑:我不知道这是否有帮助,但我使用该算法来检测虹膜和瞳孔检测中的假阳性.如果圆圈完全位于另一个圆圈内,则可能是瞳孔,外部是虹膜.它们应该是同心的,简化了很多,但是人眼中的瞳孔并不完全位于虹膜的中心,这就是我这样做的原因. 编辑2:我已经用Peter Lawrey的解决方案替换了isCircleInCircle,对于某些情况我的不正确 用于检查圆圈是否在圆圈内的功能:
然后我互相检查列表中的每个元素,并只保存重叠的圆圈(和重叠的圆圈):
最佳答案
该算法的复杂性不能低于O(n ^ 2).想象一个规则网格,其点是圆心,圆的半径是1,相邻网格点之间的距离是2.任何其他圆中都不包含圆.为了证明这一点,你必须检查每一个圆圈.如果你没有证明每个组合,那么存在圆圈a和b,它们没有相互测试.所以现在让矩阵看起来有点不同:圆圈a比b小一点,它们共用同一个中心.所以你没有发现a包含在b中,因此你的算法是不正确的.对于复杂性的证明非常重要.
为了帮助加快您的计划,您必须专注于平均情况: 编辑: 然后,在寻找可能完全重叠的候选者时,可能会有另一种改进.由于圆圈包含在平面中,因此可以使用诸如R树或四叉树的空间数据结构来找到可以完全重叠,更有效的候选者. 但是我不认为这会降低最坏情况的复杂性,即使这些建议也会改善上述最坏情况下的性能.新的最坏情况可能是圆形,其中心是规则网格的点,但是在将其与常规网格中的点之间的距离进行比较时具有非常大的半径. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |