0

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.)

IceMetalPunk
  • 5,476
  • 3
  • 19
  • 26
  • Is there a problem with picking two random vertices, [determining if the line segment formed causes an intersection with *any* existing edges in your edge set](https://stackoverflow.com/a/9997374/6454387), and adding the edge to your edge set if doesn't create an intersection? – ljeabmreosn Dec 21 '18 at 20:49
  • Maybe? Related to restriction 1: every vertex must have at least 1 edge. Picking points at random and then possibly not adding the edge between them (in case they intersect another edge) means that, given restriction 1, this algorithm would be possibly unbounded, right? I'd like to avoid the possibility of a frozen application :) *EDIT* Although this gives me an idea... I can iterate through the vertexes and, for each, shuffle a list of all other vertexes and iterate through those until one has no intersection... is that guaranteed to satisfy condition 1? I'm not sure... – IceMetalPunk Dec 21 '18 at 20:51
  • Yes, that is true. How about enumerating all `O(n^2)` pairs of vertices in a random order? *EDIT*: I believe that is guaranteed to satisfy condition 1. In the worst case, the resulting graph would result in a [star](https://en.wikipedia.org/wiki/Star_(graph_theory)) components which is always possible to construct without intersections. – ljeabmreosn Dec 21 '18 at 20:54
  • The articles about [Voronoi diagrams](https://en.wikipedia.org/wiki/Voronoi_diagram) and [Delaunay_triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation) may help you get started. I've solved this problem for a graph with 50-100 vertices, but it's too much code to share here. My code computed the Voronoi diagram. It then added all valid edges. A valid edge is any edge that connects two vertices while staying in the areas controlled by those vertices. This is guaranteed to connect the graph. Then you can reduce clutter by removing edges without disconnecting the graph. – user3386109 Dec 21 '18 at 21:58
  • This is the known as the 'non-crossing matching problem'. – micycle Jun 08 '22 at 15:15

2 Answers2

2

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.

Prune
  • 76,765
  • 14
  • 60
  • 81
  • I really like this approach! I'll try and implement it; if I run into roadblocks, I'll ask here, and if it works, I'll accept the answer :) Thank you! – IceMetalPunk Dec 21 '18 at 22:48
  • If it's any help, Python has an `interval` package. However, it doesn't support wrap-around -- you might have to add logic to re-map intervals that cross 0 / 2*PI. Note that no interval can be wider than PI, so if you re-map to (-PI, +PI) when you hit those, you'll still be able to do the proper interval algebra. – Prune Dec 21 '18 at 23:07
  • Thanks, but I'm not using Python :) I'm currently using GML, though I may switch to simple Javascript/Canvas in the future (maybe). – IceMetalPunk Dec 21 '18 at 23:18
  • I recently got a new computer, and my compiler doesn't seem to want to work properly on it. Rather than make you wait until I get everything sorted, I'm accepting your answer on its own merits now :) Thank you! – IceMetalPunk Dec 25 '18 at 17:37
0
  1. Triangulate the vertex set.
  2. Convert the triangulation into a graph.
  3. Process the graph with a matching algorithm.
  4. The matching produces a set of edges such that each vertex is adjacent to at most one edge; these form edges that fulfil your three conditions.

In the example below, I triangulate a random point set using Tinfour, covert the triangulation into a jGraphT graph and process this using jGraphT's implementation of the blossom algorithm: KolmogorovWeightedPerfectMatching – this is a maximum-weight matching algorithm, that will consequently maximise edge lengths.

micycle
  • 3,328
  • 14
  • 33