最近点的给定点 [英] Closest point to a given point

问题描述

我有一个2D图像的一组随机选择的像素K个。对于图像中每隔一个像素，我需要找出哪些像素集K是最接近它（使用标准的sqrt（DX ^ 2 + DY ^ 2）进行度量）。据我所知，可能存在针对每个像素一个以上的溶液。很明显，它可以通过对集合中的每一个像素蛮力做，但我宁愿避免这种情况，因为它是没有效率。任何其他好的建议？

I have a set K of randomly selected pixels in a 2D image. For every other pixel in the image I need to find out which pixel in set K is closest to it (using the standard sqrt(dx^2 + dy^2) measure of distance). I am aware that there may be more than one solution for each pixel. Obviously it can be done by brute force against every pixel in the set, but I'd rather avoid this as it's not efficient. Any other good suggestions?

干杯。

推荐答案

不要忘记，你不必费心的平方根。

Don't forget that you don't need to bother with the square root.

如果你只是想找到最近的一个（而不是它的实际距离），只需使用 DX ^ 2 + DY ^ 2 ，这将给你方的距离在每一个项目，这是一样有用的。

If you just want to find the nearest one (and not it's actual distance) just use dx^2 + dy^2, which will give you the distance squared to the each item, which is just as useful.

如果你没有数据结构包裹像素的这份名单，你就需要对他们的一切都只是测试。

If you have no data structure wrapping this list of pixels up, you will need to just test against them all.

如果您有一定的灵活性，也有很好的办法负荷减少了工作量。做一个四叉树或保留像素（排序x和排序Y）的排序列表更快速缩小搜索范围

If you have some flexibility, there are loads of good ways to reducing the workload. Make a Quadtree, or keep sorted list of the pixels (sorted by x and sorted by y) to narrow your search more quickly.

这篇关于最近点的给定点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！