擅长:python、mysql、java
<p>问题不在于“找出给定点是否落在二维空间的某个矩形内”</em>?在</p>
<p>可以在空间上分开,不是吗?给每个矩形一个ID,然后将其分成一维范围的列表(<code>(id, x0, x1)</code>,<code>(id, y0, y1)</code>),并找到点所在的两个维度中的所有范围。(我相当肯定有非常有效的算法来解决这个问题。见鬼,你甚至可以利用,比如说,sqlite)然后只要相交你得到的ID集,你就可以找到所有的矩形点,如果有的话。(当然,如果有一个一维查询没有返回结果,您可以提前退出。)</p>
<p>但不确定这是否比R-trees或<a href="http://en.wikipedia.org/wiki/Spatial_index" rel="nofollow">other spatial indexes</a>更快或更聪明。希望这有帮助。在</p>