我正在寻找一种快速的方法来确定矩形和圆形之间的交叉区域(我需要进行数百万次这些计算).
一个特定的属性是,在所有情况下,圆和矩形总是有2个交点.
我有一个二维点列表,我想获得它们中的哪一个属于半圆.
最初,目标形状是与x和y轴对齐的矩形.因此,当前算法通过它们的X坐标和二进制搜索对对进行排序,以便第一个可以落入矩形内.然后它按顺序迭代每个点.当它击中超出目标矩形的X和Y上限的那个时,它会停止.
这不适用于半圆,因为您无法确定它的有效上/下x和y边界.半圆可以具有任何方向.
最糟糕的情况是,我会在半圆形中找到维度(比如x)的最小值,二元搜索到超出它的第一个点,然后依次测试这些点,直到超出该维度的上限.基本上测试整个乐队在网格上的价值点.这样的问题最终将检查许多不在范围内的点.