求高效的圆圈内所有点的算法? 一个平面上,有近200万的坐标点,这些坐标点是无序的。如果在平面上随意画一个圆,如何快速找出圆内的点和圆圈上的点? 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 首先必须得到圆心坐标(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, 并使用上面的方法进行判断 如果你想提高速度, 在此之前, 你可以根据以下条件就可以判断点肯定在圆内|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)楼主想要在多长时间内完成 求救:将DBGrid的列名写到Excel的列名中的问题? 图象处理问题 能不能给一些Delphi消息系统的实例,多谢了! 有关三层动态SQL参数问题。 又是DCOM联接问题(新) 为什么我的UDP总是出现STREAM WRITE ERROR delphi书籍 如何将SQL的数据库打包成安装盘?送100分!! Nt/2000的服务程序,如何准确的捕获用户登录/退出的信息?急急!!! 进度条问题: 初学indy,udp发送信息问题 求个取字符串函数
但由于离散系统, 所以必须按以下修正
如果 r - 0.5 <= d <= r + 0.5 , 则可以认为点在圆上
如果 d < r-0.5, 则可以认为点在圆内为了快速判断, 首先对于所有点(x, y)
如果 (x - x0 > r+1) or (y - y0 > r + 1), 则可以直接判断其在圆外
然后只对剩下的点, 计算距离d, 并使用上面的方法进行判断
如果你想提高速度, 在此之前, 你可以根据以下条件就可以判断点肯定在圆内
|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)楼主想要在多长时间内完成