给定数百万个点,找到位于线上或距离线0.2毫米范围内的点

Question

给定一组具有(x,y)坐标的数百万个点,我必须选择线[(x1,y1) - (x2,y2)]上的点或者在0.2的范围(距离)内mm离线.

解决这个问题的一种方法1)将每个点放在线的方程中,如果满足那么点位于线2)计算点和线之间的垂直距离,如果距离小于0.2 mm则选择此点

但是对于数百万点来说它不是最好的解决方案,所以我正在寻找新的算法或技术,我们可以用它来解决上述问题.

任何帮助将非常感谢!谢谢.

感谢您的回复,我已经完成了您发布的所有建议.我想,我会给你一些问题的背景知识.

我是c ++编程的新手,我面临的问题描述如下

1. 程序的输入是一个逗号分隔的文本文件,其中包含数百万或数十亿的x&y坐标,每个点都有一些值,例如x1,y1,value1

2. 然后程序绘制数千行([x1,y1] - [x2,y2])

3. 对于每条线,我必须选择一组位于线上或在0到0.2毫米范围内的点

我试过以下方法:

1. 计算每个点距离线的距离,如果距离<= 0.2然后选择这样的点,并为数千行做了...但它不是有效的算法

2. 在第二种方法中,我计划对坐标进行排序,然后在给定线的两侧绘制平行线,距离为0.2 mm ....但不知道如何识别位于平行线之间的点.还建议这种方法是否合适

你们有些人建议使用r树,2变种方法,因为我是编程pl的新手,建议了解一些在线教程以及如何实现相同的

Answer 1

为了比较所有的点,你可以做的就是比较所有的点.

您可以在多个线程上拆分任务以更快地处理它,但我认为您低估了计算机的速度.

首先执行简单的实现,然后在尝试使事情复杂化之前查看它是否足够快.