擅长:python、mysql、java
<p>一个低成本的空间分隔可能是把飞机分成9块</p>
<p>这是一张糟糕的图表。想象一下,如果你愿意的话,这些线只是接触到圆圈。</p>
<pre>
| |
__|_|__
__|O|__
| |
| |
</pre>
<p>我们感兴趣的区域中有8个围绕着这个圆圈。中间的正方形对于一个便宜的测试来说用处不大,但是你可以在圆内放置一个<code>r/sqrt(2)</code>的正方形,所以它的角只是接触圆。</p>
<p>允许标记区域</p>
<pre>
A |B| C
__|_|__
D_|O|_E
| |
F |G| H
</pre>
<p>中心的<code>r/sqrt(2)</code>的平方我们称之为<code>J</code></p>
<p>我们将调用图中所示的中心正方形中不在<code>J</code>,<code>Z</code>中的点集</p>
<p>用它的字母代码标记多边形的每个顶点。</p>
<p>现在我们可以很快看到</p>
<pre>
AA => Outside
AB => Outside
AC => Outside
...
AJ => Intersects
BJ => Intersects
...
JJ => Inside
</pre>
<p>这可以变成一个查找表</p>
<p>因此,根据您的数据集,您可能已经为自己节省了大量工作。但是,任何端点位于<code>Z</code>中的内容都需要进行测试。</p>