查找最接近的线段的点的最佳方式 [英] The best way for finding the closest line segment to a point

问题描述

如在下面图中可以看出，我有任何两个关节（红点），如关节J1和J2之间的线之间的一些行（有限长）。我也有一些点，如P1和P2。

As can be seen in figure below, I have some lines (finite length) between any two joints (red points), such as the line between joints J1 and J2. I have also some points such as P1 and P2.

我点和关节的坐标。所以，有可能计算线路方程（表达式y = mx + b）的。所以，它能够计算一个点之间的距离的任何线路。因此，最低的距离让我最接近行的地步。

I have the coordinates of points and joints. So, it is possible to calculate the line equations (y=mx+b). So, it is possible to calculate the distance between a point to any line. So, the lowest distance gives me the closest line to the point.

由于有在此问题的巨大的点数，它需要一个庞大的计算。 我在寻找一个高效，快捷的方法。

Since there are a huge number of points in this problem, it takes a huge calculations. I am looking for an efficient and fast method for that.

使用重心坐标，我能找到的任何点周围有哪些行。这一招会降低计算的数量。但是，我在寻找更多的花样，使其更快。

Using the Barycentric coordinate system, I can find any point is surrounded with which lines. This trick will decrease the number of calculations. But, I am looking for more tricks to make it faster.

推荐答案

Voronoi图可以让你快速查找。我想你可以使用红点的Voronoi图。国际海事组织最接近线是同一类的最近点。

A voronoi diagram can gives you fast lookup. I think you can use the red points for the voronoi diagram. IMO the closest line is the same like the closest point.

这篇关于查找最接近的线段的点的最佳方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！