CODEWITHSUNDEEP
algorithmgraph-traversal
Peter K.
Peter K.

Reputation: 161

Determinate the closest bounding border (graph theory and geometry)

Example figure

Graph

  • Point A: { x: xA; y: yA; neighbors: { B, J } }
  • Point B: { x: xB; y: yB; neighbors: { A, C } }
  • Point C: { x: xC; y: yC; neighbors: { B, D, G, H } }
  • etc.

Input

Set of verticies (points, cartesian coordinate system).

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.

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?

Upvotes: 0

Views: 290

Answers (1)

J.P. Tosoni
J.P. Tosoni

Reputation: 573

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.

Upvotes: 1

Related Questions