查找包含特定点的圆

Question

我有一个包含许多circles的数据库（每个都有x、y和半径）。我需要找到每个圆，其中包括一个由x/y给出的特定点。

有办法在better than linear time中做到这一点吗？测试每一个圆圈都会大大降低我的应用程序的速度。

提前谢谢。

Answer 1

在没有几何索引的情况下，在一些RDBMS中，您可以为以下对象创建基于函数的索引：

x-r
x+r
y-r
y+r

并在查询中添加谓词：

select ...
where  point_x between x-r and x+r and
       point_y between y-r and y+r and
       ... etc ...

这至少会让你成为候选人。

Answer 2

除非你已经设法按照非常特定的顺序对圆圈进行排序，否则我看不出这怎么能比线性时间更快。

不过，如果您向我们提供您的查询，可能还有一些很好的优化工作要做。