algorithm - Find indices of polygon vertices nearest to a point -

algorithm - Find indices of polygon vertices nearest to a point -

heading

i need find indices of polygon nearest point

so in case ouput 4 , 0. such if reddish point added know place vertex in array. know start?

(sorry if title misleading, wasnt sure how phrase properly)

in case ouput 0 , 1, rather closest 4.

point p lies on segment ab, if 2 simple conditions met together: ap x pb = 0 //cross product, vectors collinear or anticollinear, p lies on ab line ap . pb > 0 //scalar product, exclude anticollinear case ensure p within segment

so can check 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 //with tolerance if point coordinates 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 p belongs (i,i+1) segment

this fast direct (brute-force) method. special info structures exist in computer geometry select candidate segments - example, r-tree. these complicated methods gain long (many-point) polylines , case same polygon used many times (so pre-treatment negligible)

algorithm math polygon computational-geometry