Given is a set of points (PFeature) in a map which are at maximum distance from their closest obstacles. these points are obtained after generating the generalized voronoi diagram and applying a metric filter. Each of these points has a radius r, which is the distance to the closest obstacle. Each point has a given circle, defined by the point itself as the circles center and radius r.
I need to construct a graph between the obstacles. My hypothesis is as follows:
"Connect those points for which their given circles overlap. This results in a graph for which the edges will never collide with any obstacles and where all possible paths between the obstacles remain."
I need help to proof my hypothesis, as I will be performing path search algorithms on the constucted graph. Here are two images I have rendered to make the problem more clear.
Example map with PFeatures and circles
Constructed graph from PFeatures
Another question. How can I calculate a good tolerane for how much the circles need to overlap before the points are connected. Sometimes edges are added which are redundant, yet don't collide with any obstacles.
Thank you in advance