昨天被人问了个SQL的问题，实在想不出答案

Question

昨天一朋友问我，有一数据表，存储的是很多个坐标点，也就是他们的x和y，例如：

id, X, Y

1, 0, 0

2, 2, 3

3,10,-1



请听题，给定一个坐标(x,y)和一个半径r，如何从数据表中获得这个圆内的所有点？

我想了半天，只能考虑先选出这个圆外切的正方形内所有的点，然后在逐个计算这些点距离(x,y)的长度是否小于r



这个办法比较笨，不知道有没有好的方案呢？
问题补充

hahalizx 写道

应该不难吧，先选X，用给定的X减去记录中的X，然后取绝对值，比R小或等的符合，然后是Y，再把那两个条件结合起来

这样选出来的是个矩形吧
问题补充

Lucas Lee 写道

buaawhl 写道

select * from t

where (X - cx) ^2 + (Y - cy) ^2 < R ^ 2



到圆心的距离小于半径，就在圆内。

两点之间的距离公式，应该就是上面写的。凭印象。

这个是基本解法。

但这需要扫描表中所有记录。

如要提高性能，可以加入冗余条件，它可以利用索引减少目标范围：

select * from t

where (X - cx) ^2 + (Y - cy) ^2 < R ^ 2

and X<cx+r and="" x="">cx-R

and Y<cy+r and="" y="">cy-R

这样可以利用X和Y上的索引。

是的，应该如此。

如果直接算两点距离的话，全表扫描逐条运算，查询速度很慢（mysql里面试的，10万左右的数据）。所以我才打算先选出边长为2r的正方形，查询快很多，然后交给程序过滤多余的记录。

如果只说SQL，老兄的方法挺好的。简单的条件应该放到前面去

Answer 1

[quote="buaawhl"]select * from t
where (X - cx) ^2 + (Y - cy) ^2 < R ^ 2

到圆心的距离小于半径，就在圆内。
两点之间的距离公式，应该就是上面写的。凭印象。[/quote]

这个是基本解法。
但这需要扫描表中所有记录。
如要提高性能，可以加入冗余条件，它可以利用索引减少目标范围：
select * from t
where (X - cx) ^2 + (Y - cy) ^2 < R ^ 2
and Xcx-R
and Ycy-R
这样可以利用X和Y上的索引。