Determinate the closest bounding border (graph theory and geometry)

Question

Example figure

• Point A: { x: x_A; y: y_A; neighbors: { B, J } }
• Point B: { x: x_B; y: y_B; neighbors: { A, C } }
• Point C: { x: x_C; y: y_C; neighbors: { B, D, G, H } }
• etc.

Input

Set of verticies (points, cartesian coordinate system).

• Some verticies are connected to others.
• There is no edge's intersection on the input.

Question

How to find the closest bounding border for the given point (for example one of the green points 1, 2, 3)? I can use only connected verticies.

• Solution for point 1 is { A, B, C, D, E, F, G, I, J }.
  • (Not { A, B, D } – there is no edge between { B and D } and { D and A }).
• Solution for point 2 is { C, D, E, F, G }.
• Solution for point 3 is { C, G, H }.

My idea

Find intersection of the vertical line (this line goes through question point) and the edge (between 2 verticies). I know 2 verticies now. How continue??

Can I use any algorithm from graph theory for this situation?

Answer 1

First, there are three corner cases in your idea, that must be dealt with:

• the vertical line intersects above and below, you must choose one
• the vertical line could intersect with a vertex not an edge
• the vertical line could intersect with an edge that is also vertical (so that there is an infinity of common points)

This said,

Say you find an edge below the point. So you found 1 edge and 2 vertices. You can select the left vertex, compute the angle of the found edge relative to each segment originating from this vertex, and select the segment with the lowest angle. Then you follow this new edge to find a new vertex, and iterate.