3

Imagine a 2D area, with a number (array) of nodes (or points) defined within it, in arbitrary (but known) positions (integer x,y coordinates), like this:

Image showing a number of nodes on a graph

From there I want to be able to, programmatically, add as many "links" as possible. A "link" is a straight line between any two nodes, but a link cannot cross another link. I already have a method created that can verify if two links cross. eg

Image showing links and an invalid link

With any given set of nodes, there is a finite number of ways that links can be laid out and I want to be able to generate all of those possible (valid) combinations.

However, I have absolutely no idea where to start on this. I could randomly fill the nodes with valid links, but I don't know how to iteratively generate each possible permutation.

I'm guessing that some kind of algorithm exists for problems like this, probably based around recursion, but my searches so far have been fruitless.

I'm not looking for a coded solution, I can do that part. What I need is the high level design process, or algorithm, that can be followed to solve this problem.

  • Have you looked at CS.SE yet? – MetaFight Feb 18 '15 at 14:03
  • Google Voronoi. – GameAlchemist Feb 18 '15 at 14:19
  • This is a hard problem, with 7 point you have like 21 possible paths which would make for like 2^21 possible states of your situation. – Pieter B Feb 18 '15 at 14:43
  • 1
    @GameAlchemist I just looked at Voronoi, and it isn't applicable here. Voronoi has a single output (not permutations) given a fixed set on inputs, and deals with half-way points rather than links. – Dave Feb 19 '15 at 9:53
  • @PieterB Yes, hence why I need help working out what would be the best way forward! I'm not sure if it is better to cycle through all permutations, and discard the majority that have invalid links, or work towards an algorithm that just generates valid layouts. – Dave Feb 19 '15 at 9:56
2

You've got quite hard a problem here.

I'm thinking of a method resembling Sieve of Eratosthenes .

First, you can "name" or "number" each link. Let's assume we just have 5 nodes, so we'll have 10 links. Number each one from 1 until 10.

Now, we can put them all into an array.

Let's assume we have this list represents two links who intersect each other:

  • 1 - 3
  • 1 - 4
  • 1 - 7
  • 1 - 10
  • 2 - 4
  • 2 - 8
  • 3 - 4
  • 6 - 9
  • 6 - 10

Now let's visualize this. First, I choose to draw link 1.

*For the images below, green means I choose to draw the link, red means the link cannot be drawn (because it intersects a selected link), and white means the link can be drawn.

enter image description here

Then, check each element from link #2 to link #10: does it intersect link #1? If yes, we should eliminate them (means we must not draw them). In this case : links #3, #4, #7, #10 (from the list above)

enter image description here

Now, you can choose which one is the next to draw: either #2, #5, #6, #8, or #9? Let's say you choose #2, then you do the same procedure. Check the rest of the element: If it's already red then you may skip it, but if it's white (can still be drawn), check if it intersects link #2. Link #2 intersects with #4 and #8, but since #4 is already eliminated, we just eliminate #8.

enter image description here

Then, pick another link, and so on. Note that we can make use of two arrays: one integer array containing the links, and the other a boolean array to check if it's eliminated or not.

You can do this in iteration: picking which link to draw and eliminate the ones intersecting them. This way, you can avoid drawing unnecessary links.

Well, it's just an idea that might work. But, I neither think this way is easy to implement, nor do I think it can be considered "efficient" in terms of complexity.

1

To cut down on the count of recursive calls I thought of introducing a strict ordering of links to be able to eliminate duplicates in the initialization phase (before any recursion):

  • on the links define any (arbitrary) strict ordering order
  • on the links define a method doesNotCrossWith() returning the set of links of higher order which this link does not cross (capable of executing in constant time after initialization)
  • on the links define a method doesNotCrossWithIntersectionOf(Set<Link>) returning the intersection of the parameter and doesNotCrossWith()
  • define the main recursive method getValidPermutations(Link link, Set<Link> linksNotForbidden) (Pseudocode):

    Set<Set<Link>> validPermutationsIncludingLink;
    
    // add the current link (alone) itself to the possible permutations (to be added to):
    validPermutations.add(new Set(link));
    
    Set<Link> linksStillAllowed = link.doesNotCrossWithIntersectionOf(linksAllowed);
    
    for (Link otherLink : linksStillAllowed) {
        Set<Set<Link>> validPermutationsOfOther;
    
        //recursive call:
        for (Set<Link> validPermutation : getValidPermutations(otherLink, linksStillAllowed)) {
            validPermutation.add(otherLink);
            validPermutationsOfOther.add(validPermutation);
        }
        validPermutations.addAll(validPermutationsOfOther);
    }
    
    return validPermutations;
    
  • call getValidPermutations for each link and build a union of the results.

The maximum recursive depth is the number of (possible) links n.

P.S.: With 7 nodes roughly arranged as in your example I get ~150ms running time with this implementation on my machine resulting in 37055 possible permutations, for a large number of nodes additional optimizations might be needed.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.