找到与给定点最近的点的最快方法是什么? [英] What is the fastest way to find the closest point to a given point?

问题描述

在数据数组中找到与给定点最近的点的最快方法是什么?

What is the fastest way to find closest point to the given point in data array?

例如，假设我有一个由 3D 点(坐标 x、y 和 z，像往常一样)和点 (x_p, y_p, z_p) 组成的数组 A.如何在 A 中找到最接近 (x_p, y_p, z_p) 的点?

For example, suppose I have an array A of 3D points (with coordinates x, y and z, as usual) and point (x_p, y_p, z_p). How do I find the closest point in A to (x_p, y_p, z_p)?

据我所知，最慢的方法是使用线性搜索.有没有更好的解决方案?

As far as I know, slowest way to do it is to use linear search. Are there any better solutions?

可以添加任何辅助数据结构.

Addition of any an auxiliary data structure is possible.

推荐答案

您可以在 八叉树中组织您的观点.那么你只需要搜索一个小的子集.

You may organize your points in an Octree. Then you only need to search a small subset.

八叉树是一种相当简单的数据结构，您可以自己实现(这将是一次宝贵的学习经验)，或者您可能会找到一些有用的库来帮助您实现.

A Octree is a fairly simple data structure you can implement yourself (which would be a valuable learning experience), or you may find some helpful libraries to get you going.

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