algorithm - Determinate the closest bounding border (graph theory and geometry) -

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 connected others.
• there no edge's intersection on input.

question

how find closest bounding border given point (for example 1 of green points 1, 2, 3)? can use connected verticies.

• solution point 1 { a, b, c, d, e, f, g, i, j }.
  • (not { a, b, d } – there no edge between { b , d } , { d , }).
• solution point 2 { c, d, e, f, g }.
• solution point 3 { c, g, h }.

my idea

find intersection of vertical line (this line goes through question point) , edge (between 2 verticies). know 2 verticies now. how continue??

can use algorithm graph theory situation?

first, there 3 corner cases in idea, must dealt with:

• the vertical line intersects above , below, must choose one
• the vertical line intersect vertex not edge
• the vertical line intersect edge vertical (so there infinity of common points)

this said,

say find edge below point. found 1 edge , 2 vertices. can select left vertex, compute angle of found edge relative each segment originating vertex, , select segment lowest angle. follow new edge find new vertex, , iterate.