Hi people,
What is the best approach finding the shortest distance between a point and a polygon or a route (route = first and last point are not connected)?
I think that the brute force here is take the shortest distance between this point and all the segments and It takes O(n) time where n is the segments amount of the polygon or the size of the segments set in the route, but ...
Can we do it better?
Is O(logn) possible if we know this segments set and we can store it sorted using some criteria?
Any hint or documentation will be appreciate.
Thanks in advance!
This problem will be easier if the poligon is convex, and points in queries are outside the poligon.
In this case, we can sort poligon's vertices and queries. And use two pointers.
Please take a look this situation:
Does exist some generic way to sort the rectangles (sorting without depending of the point given) and then search only for rectangles we need?
For example:
Point A -> Why do we need to search for the end segment?
Thanks for your help!
An obvious idea for an O(logN) per query is to build a Voronoi diagram and use some point location algorithm.
But your Voronoi diagram will be of very special form, since you have line segments instead of points. I think that the algorithms for building it in
will be quite similar to ones for ordinary Voronoi diagram, but I'm not completely sure.
Anyway I've given you some keywords that should help you with googling :).
Thank you very much. I will search using your keywords.