求高效的圆圈内所有点的算法？

Question

一个平面上，有近200万的坐标点，这些坐标点是无序的。
如果在平面上随意画一个圆，如何快速找出圆内的点和圆圈上的点？

Answer 1

首先必须得到圆心坐标(x0, y0)和半径r判断的原理是点至圆心的距离d
但由于离散系统, 所以必须按以下修正
如果  r - 0.5 <= d <= r + 0.5 , 则可以认为点在圆上
如果  d < r-0.5, 则可以认为点在圆内为了快速判断, 首先对于所有点(x, y)
如果 (x - x0 > r+1) or (y - y0 > r + 1), 则可以直接判断其在圆外
然后只对剩下的点, 计算距离d, 并使用上面的方法进行判断

Answer 2

如果你想提高速度, 在此之前, 你可以根据以下条件就可以判断点肯定在圆内
|x-x0| + |y-y0| <= r - 1    (注: |x| 表示 x 的绝对值), 当然, 这是原理, 实现的你时候,
你如果调用两次绝对值函数那就慢了算法很快的, 你只用使用距离的平方比较就可以了 
对于 (r-0.5)^2 及 (r+0.5)^2 只需要计算一次, 并取整保存备用即可
则 (x-x0)^2 + (y-y0)^2  计算很快, 两次整数减法 两次整数乘法 一次整数加法
再加三次整数比较
对每个点计算机处理的时钟周期在100之内
就算前几步没有滤除点, 200万个点全计算一次, 对于 2.0 GHz的CPU, 也只需要1秒钟不到使用以上算法, 在一般情况下, 0.5秒内可以计算出结果, 在最差情况下, 1秒也可以计算出结果
(对于 2.0GHz CPU)楼主想要在多长时间内完成