查找最接近点的多边形顶点的索引 [英] Find indices of polygon vertices nearest to a point

问题描述

我需要找到最接近点的多边形的索引

I need to find the indices of the polygon nearest to a point

因此，在这种情况下，输出将为4和0.这样，如果添加了红点，我便知道将顶点放置在数组中的位置.有人知道从哪里开始吗?

So in this case the ouput would be 4 and 0. Such that if the red point is added I know to where to place the vertex in the array. Does anyone know where to start?

(很抱歉，如果标题有误导性，我不确定如何正确说出它的意思)

(Sorry if the title is misleading, I wasnt sure how to phrase it properly)

在这种情况下，输出将是0和1，而不是最接近的4.

In this case the ouput would be 0 and 1, rather than the closest 4.

推荐答案

点 P 位于分段 AB 上:
AP x PB = 0//叉积，向量为共线或反共线，P位于AB线上
AP . PB > 0//标量积，排除反共线情况以确保P在段内

Point P lies on the segment AB, if two simple conditions are met together:
AP x PB = 0 //cross product, vectors are collinear or anticollinear, P lies on AB line
AP . PB > 0 //scalar product, exclude anticollinear case to ensure that P is inside the segment

因此您可以检查所有顺序的顶点对(伪代码):

So you can check all sequential vertice pairs (pseudocode):

if (P.X-V[i].X)*(V[i+1].Y-P.Y)-(P.Y-V[i].Y)*(V[i+1].X-P.X)=0 then
//with some tolerance if point coordinates are float
   if (P.X-V[i].X)*(V[i+1].X-P.X)+(P.Y-V[i].Y)*(V[i+1].Y-P.Y)>0
       then P belongs to (i,i+1) segment

这是快速直接(强力)方法.
计算机几何中存在特殊的数据结构，可以快速选择候选段-例如， r-tree .但是，这些复杂的方法将获得长(多点)折线以及多次使用同一多边形的情况(因此可以忽略不计)

This is fast direct (brute-force) method.
Special data structures exist in computer geometry to quickly select candidate segments - for example, r-tree. But these complicated methods will gain for long (many-point) polylines and for case where the same polygon is used many times (so pre-treatment is negligible)

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