Search code examples
algorithmgraph

Generate random edges between vertexes without intersection

I have an arbitrary set of vertexes in 2D space. I'd like to generate edges nearly randomly between these vertexes such that the following three conditions hold true:

  1. Every vertex has at least one edge.
  2. No two edges intersect each other, except possibly at a common vertex.
  3. No new vertexes need to be added beyond the initial set.

I can't quite figure out how to solve this, in general. I originally tried to forcibly structure my vertexes into neat columns (though with arbitrary vertical spacing between vertexes in the same column), and then form the edges one column at a time, with vertexes only connecting to ones in the next column. I thought I'd be able to then check if a vertex higher up in the current row connects to a vertex lower down in the next row and, if so, prevent any edges that meet that condition. (In other words, if V[j,k] is "the k'th vertex from the top of column j", then I would prevent any edges between V[j,k1] and V[j+1,k2] if there exists an edge between any vertex V[j,k3] and V[j+1,k4], where k4>k2 and k3<k1.)

But it didn't seem to work, and even worse, it left some vertexes without any edges. How can I make this work out? (If possible, without that forced column structure at all; I'd like this to work on as general a set of vertexes as possible.)

Solution

  • Attack this from a viewpoint of polar coordinates and interval operations. Make a list of your unconnected vertices; apply a random shuffle.

    For each unconnected point P:

    • Make a list of all points "visible" from P: those that are not blocked by an edge (see below).
    • Choose a "visible" point Q at random; add edge PQ to the graph

    To determine whether a point is "visible" can be tedious, but the search space can be greatly improved in practice.

    • Translate all of the coordinates such that P is the origin.
    • Compute the polar coordinates (r, theta) of each other point.
    • For each edge AB, the range of angles (A.theta, B.theta) with wraparound at angle (0, 2*pi) describes a pie-slice of space with its vertex at P. Trivially, any point C in that slice is invisible if C.r > max(A.r, B.r) -- if it's farther from P than either endpoint. Similarly, if it's closer than either endpoint, it's still under consideration. Going through this for each point C should seriously reduce your list of candidates.

    For the remaining maybe-visible points: - The closest point to P must be visible. - For any other point C, perform an intersection check with all edges AB that cover its angle (theta), such that r.A < r.C < r.B or vice versa (C is "between" A and B in radius). For such edges check to see whether PC intersects AB (a straightforward check in rectangular coordinates).

    What remains is a list of all points visible from P (note that there must be at least one, unless P is the only point in the graph; if the graph has at least 2 points not at the same angle from P, there must be at least two such points). Pick one at random and add the edge.

    This may not be the most compute-effective algorithm. However it's easy to visualize, straightforward to implement each step, and is easily seen to provide a solution to the given problem.