algorithm - How to find the nearest line segment to a specific point more efficently? -

this problem came across , i'm searching more effective way solve it. take @ pics:

let's want find shortest distance red point line segment a_n. assume know start/end point (x,y) of segments , point. can done in o(n), n line segments, checking every distance point line segment. imo not effective, because in worst case there have n-1 distance checks till right 1 found.

this can real performance issue n = 1000 f.e. (which number), if distance calculation isn't done in euclidean space pythagorean theorem example geodesic method haversine formula or vincenty's.

this general problem in different situations:

• is point inside radius of vertices?
• which set of vertices nearest point?
• is point surrounded line segments?

to answer these questions, approach know o(n). know if there data structure or different strategy solve these problems more efficiently?

to make short: i'm searching way, line segments / vertices "filtered" somehow set of potential candidates before start distance calculations. reduce complexity o(m) m < n.

probably not acceptable answer, long comment: appropriate answer here depends on details did not state in question.

if want perform test once, there no way avoid linear search. however, if have fixed set of lines (or set of lines not change on time), may employ various techniques accelerating queries. these referred spatial indices, quadtree.

you'll have expect trade-off between several factors, query time , memory consumption, or query time , time required updating data structure when given set of lines changes. latter depends on whether structural change (lines being added or removed), or whether positions of existing lines change.