Skip to main content
Software Engineering

Return to Question

Tweeted twitter.com/#!/StackProgrammer/status/568366822099181569
added 15 characters in body
Source Link
Dave
Dave
  • 131
  • 4

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.

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 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 process, or algorithm, that can be followed to solve this problem.

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.

Source Link
Dave
Dave
  • 131
  • 4

How to iterate through all permutations of valid links between nodes

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 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 process, or algorithm, that can be followed to solve this problem.