java - 给定数百万个点，找到位于直线上或距直线 0.2 mm 范围内的点

Question

关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。












想改进这个问题？将问题更新为 on-topic对于堆栈溢出。

8年前关闭。




Improve this question




给定一组具有 (x,y) 坐标的数百万个点，我必须选择在线 [(x1,y1)-(x2,y2)] 或范围(距离)为 0.2 的点从线毫米。

解决这个问题的一种方法
1)将每个点都放在直线方程中，如果满足则点位于直线上
2) 计算点与线的垂直距离，如果距离小于0.2mm则选择该点

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

任何帮助将不胜感激!谢谢。

感谢您的回复，您提出的所有建议我都浏览了一遍。我想，我会给你一些问题的背景。

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

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

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

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

我尝试了以下方法:

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

在第二种方法中，我计划对坐标进行排序，然后在给定线的两侧以 0.2 毫米的距离绘制平行线....但不知道如何识别位于平行线之间的点。还建议这个方法好不好

你们中的一些人建议使用 r 树，2-variant 方法，因为我是编程新手，请建议一些在线教程来理解和如何实现相同

Answer 1

要比较所有的点，你所能做的就是比较所有的点。

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

先做简单的实现，看看它是否足够快，然后再尝试使事情复杂化。