Title: **A graph problem (not necessarily math-heavy)**

Post by:**Hayleia** on **November 09, 2016, 11:01:40 am**

Post by:

Well, I have a graph problem. Yeah, that's the title.

Basically, imagine nodes in a plane (well, they'll be in space but let's say plane to keep things simple), without any edge for now, because the problem is exactly to find out where to put the edges. And where do we want edges? We want edges between neighbour nodes, meaning that a node will have an edge with all the closest nodes. What does that mean "closest"? There is a difference between "the 5 closest" and "the 20 closest", so yeah, my definition doesn't mean s***, that's exactly my problem :P

So I'll give an example. Here are 3 nodes in line with the wanted edges. There is no edge between 1 and 3 because 2 is closer.

Well, that was one stupid example. But basically, imagine more nodes, not necessarily in line. Well, imagine you're a point, moving in the plane. There is obviously a node that you're closest to, that we will call X. And a node Y would be called a "closest node to X" if your point can move from X to Y while having its closest node being always either X or Y.

In the above example, that's why 1 isn't a "closest node to 3", because whatever you do, if you try to move from 3 to 1, at some point the closest node to you will be 2.

So I have to code this, but I can't code something I didn't even define by words and rules, so does anyone have any idea how to get these rules down on paper?

Basically, imagine nodes in a plane (well, they'll be in space but let's say plane to keep things simple), without any edge for now, because the problem is exactly to find out where to put the edges. And where do we want edges? We want edges between neighbour nodes, meaning that a node will have an edge with all the closest nodes. What does that mean "closest"? There is a difference between "the 5 closest" and "the 20 closest", so yeah, my definition doesn't mean s***, that's exactly my problem :P

So I'll give an example. Here are 3 nodes in line with the wanted edges. There is no edge between 1 and 3 because 2 is closer.

Code Select

1-2-3

Well, that was one stupid example. But basically, imagine more nodes, not necessarily in line. Well, imagine you're a point, moving in the plane. There is obviously a node that you're closest to, that we will call X. And a node Y would be called a "closest node to X" if your point can move from X to Y while having its closest node being always either X or Y.

In the above example, that's why 1 isn't a "closest node to 3", because whatever you do, if you try to move from 3 to 1, at some point the closest node to you will be 2.

So I have to code this, but I can't code something I didn't even define by words and rules, so does anyone have any idea how to get these rules down on paper?

Title: **Re: A graph problem (not necessarily math-heavy)**

Post by:**kotu** on **November 09, 2016, 11:04:47 am**

Post by:

i have no idea how to approah this

i skim-read your post because it looked difficult to understand, i doubt i could understand it if i had read it (without you explaining in person) and tbh i think you need someone trained in graph theory lol

*edit*

is it possible to make a picture of the 1-2-3 example?

i skim-read your post because it looked difficult to understand, i doubt i could understand it if i had read it (without you explaining in person) and tbh i think you need someone trained in graph theory lol

*edit*

is it possible to make a picture of the 1-2-3 example?

Title: **Re: A graph problem (not necessarily math-heavy)**

Post by:**Hayleia** on **November 09, 2016, 11:07:06 am**

Post by:

I am not sure of it really. On the contrary, someone trained in graph theory or algorithms would start thinking about Dijkstra and stuff and where to apply it and then would get a biased definition with a forced Dijkstra in it even though that may be unnecessary or even false. Or they would skim-read too and answer "that's just the minimum spanning tree" even though nope, it's not, I'm sure I can get cycles in the stuff I want (just imagine 3 points at an equal distance, you want the three edges, not just 2).

Title: **Re: A graph problem (not necessarily math-heavy)**

Post by:**p2** on **November 09, 2016, 11:12:06 am**

Post by:

thats some dificult to understand post you made there O.o

But for finding the next neighbors just use aa FOR loop on all other node and calculate the distance A(Xa|Ya) <--->B(Xb|Yb) by doing squareroot(Xa-Xb)^2+(Ya-Yb)^2)

but for putting it down on paper in a formula...

I dont know if thats even possible... xD

I hope that's what you ment. But it seems too easy to be the answer to your question... <_<

But for finding the next neighbors just use aa FOR loop on all other node and calculate the distance A(Xa|Ya) <--->B(Xb|Yb) by doing squareroot(Xa-Xb)^2+(Ya-Yb)^2)

but for putting it down on paper in a formula...

I dont know if thats even possible... xD

I hope that's what you ment. But it seems too easy to be the answer to your question... <_<

Title: **Re: A graph problem (not necessarily math-heavy)**

Post by:**Hayleia** on **November 09, 2016, 11:15:38 am**

Post by:

Quote from: p2 on November 09, 2016, 11:12:06 amNope, because that would give me the X closest nodes, not the "closest nodes" I'm looking for. They are most probably contained in some "X closest nodes" set, but which one? Especially annoying to know since X depends on the node (see the stupid example where 1 has X=1 closest nodes and 2 has X=2 closest nodes).

thats some dificult to understand post you made there O.o

But for finding the next neighbors just use aa FOR loop on all other node and calculate the distance A(Xa|Ya) <--->B(Xb|Yb) by doing squareroot(Xa-Xb)^2+(Ya-Yb)^2)

but for putting it down on paper in a formula...

I dont know if thats even possible... xD

I hope that's what you ment. But it seems too easy to be the answer to your question... <_<

Title: **Re: A graph problem (not necessarily math-heavy)**

Post by:**p2** on **November 09, 2016, 11:45:57 am**

Post by:

okeyyy, then to get the 5 nearest ones:

create "SMALLEST" var set to >9000

FOR loop on all nodes

IF distance < "SMALLEST" var

Then distance --> SMALLEST

save node handle somewhere

EndFOR

that'd e the right code to get the smallest one.

if you need multiple results:

add an array for the node handles instead of just one single var

add if-condition in for-loop: to skip a node if it'S handle is already in the handle-array

use a for-loop to execute the previous for-loop as many times you want, eah time saving the resulting node handle in the Nth position of the array.

what you get is the node's handles, sorted by their distances to your current node. :)

is this even helpful? Or am I just repeating stuff you already know but didnt use as it was a too crappy way of doing things? ^^

create "SMALLEST" var set to >9000

FOR loop on all nodes

IF distance < "SMALLEST" var

Then distance --> SMALLEST

save node handle somewhere

EndFOR

that'd e the right code to get the smallest one.

if you need multiple results:

add an array for the node handles instead of just one single var

add if-condition in for-loop: to skip a node if it'S handle is already in the handle-array

use a for-loop to execute the previous for-loop as many times you want, eah time saving the resulting node handle in the Nth position of the array.

what you get is the node's handles, sorted by their distances to your current node. :)

is this even helpful? Or am I just repeating stuff you already know but didnt use as it was a too crappy way of doing things? ^^

Title: **Re: A graph problem (not necessarily math-heavy)**

Post by:**Hayleia** on **November 09, 2016, 01:28:47 pm**

Post by:

It is not helpful, but not because it's a crappy way to do things (you should read my code, you'd see I don't care about crappy stuff :P), just because it is not what I want.

Title: **Re: A graph problem (not necessarily math-heavy)**

Post by:**Hayleia** on **November 09, 2016, 01:53:19 pm**

Post by:

Kind of an update so I double post.

First, I have images, as asked by @kotu, see below.

Second, I have an almost mathematical definition of what I'm looking for.

The nodes X and Y are neighbours if there exists a path between X and Y (straight line or not) such as for all points p on that line, the closest node to p is either X or Y.

Here is the line example. You can see that there is a path between 1 and 2 such as you're always closest to 1 or 2 (on the yellow part of the path you're closest to 1, and on the red one you're closest to 2). same for 2 and 3, and there is no requirement to be a straight line. But for 1 and 3 nope, you can't find a path without a point p that will have 2 as its closest node (note, I put colors roughly where I think stuff is closest, but don't start measuring, these are just examples made in 5 minutes).

(https://tiplanet.org/forum/images/forum_uploads/6947_1478699265_582329014952f.png)

And here is a triangle example. You can see that 1 and 3 become neighbours because if we go far enough towards the bottom, we can avoid getting close to 2. And 1 and 2 are still neighbours, same for 2 and 3 but you know that.

(https://tiplanet.org/forum/images/forum_uploads/6947_1478699271_58232907b0591.png)

First, I have images, as asked by @kotu, see below.

Second, I have an almost mathematical definition of what I'm looking for.

The nodes X and Y are neighbours if there exists a path between X and Y (straight line or not) such as for all points p on that line, the closest node to p is either X or Y.

Here is the line example. You can see that there is a path between 1 and 2 such as you're always closest to 1 or 2 (on the yellow part of the path you're closest to 1, and on the red one you're closest to 2). same for 2 and 3, and there is no requirement to be a straight line. But for 1 and 3 nope, you can't find a path without a point p that will have 2 as its closest node (note, I put colors roughly where I think stuff is closest, but don't start measuring, these are just examples made in 5 minutes).

(https://tiplanet.org/forum/images/forum_uploads/6947_1478699265_582329014952f.png)

And here is a triangle example. You can see that 1 and 3 become neighbours because if we go far enough towards the bottom, we can avoid getting close to 2. And 1 and 2 are still neighbours, same for 2 and 3 but you know that.

(https://tiplanet.org/forum/images/forum_uploads/6947_1478699271_58232907b0591.png)

Title: **Re: A graph problem (not necessarily math-heavy)**

Post by:**kotu** on **November 09, 2016, 02:17:33 pm**

Post by:

just seems like a load of calls to sqrt() * to determine 2D distances

* (if you're using C orC++)

yeah ok you can't test a path in its purest sense, as you will have to break the path down into points (pixels for example)

that would require a formulaic solution and more processing time. the pixels based approach would probably suffice, i guess

* (if you're using C orC++)

yeah ok you can't test a path in its purest sense, as you will have to break the path down into points (pixels for example)

that would require a formulaic solution and more processing time. the pixels based approach would probably suffice, i guess

Title: **Re: A graph problem (not necessarily math-heavy)**

Post by:**Snektron** on **November 09, 2016, 02:18:50 pm**

Post by:

Have you tried Delaughney triangularization? Or Isosurfaces? Or voronoi-like algoritms? Im not sure, but maybe either of those might help you.

On a side note, bute force drawing it in a shader might be possible.

Also what kind of results are you supposed to get? because there are either one, infinite or zero possibilities i think (which makes me think of matrices).

On a side note, bute force drawing it in a shader might be possible.

Also what kind of results are you supposed to get? because there are either one, infinite or zero possibilities i think (which makes me think of matrices).

Title: **Re: A graph problem (not necessarily math-heavy)**

Post by:**Hayleia** on **November 09, 2016, 02:45:23 pm**

Post by:

Quote from: kotu on November 09, 2016, 02:17:33 pmNope, can't do that. Far too slow. I mean, cutting a path into discrete subpaths is possible, but combined to the fact there are quite a big number of paths to test, this is not doable.

yeah ok you can't test a path in its purest sense, as you will have to break the path down into points (pixels for example)

that would require a formulaic solution and more processing time. the pixels based approach would probably suffice, i guess

Quote from: Snektron on November 09, 2016, 02:18:50 pmNo idea what isosurfaces are doing here :P

Have you tried Delaughney triangularization? Or Isosurfaces? Or voronoi-like algoritms? Im not sure, but maybe either of those might help you.

On a side note, bute force drawing it in a shader might be possible.

But the other two seem very related indeed. I'll check these out.

Quote from: Snektron on November 09, 2016, 02:18:50 pmWell I'd like to get the one result when there is one result :P

Also what kind of results are you supposed to get? because there are either one, infinite or zero possibilities i think (which makes me think of matrices).

Title: **Re: A graph problem (not necessarily math-heavy)**

Post by:**kotu** on **November 09, 2016, 03:33:14 pm**

Post by:

Are you trying to generate 2D meshes from general shape definitions? Because I played about with something like that about 12 years ago..... just finding the file. It might not help you though... will post some pics in a bit

*update*

(https://s15.postimg.org/6e162qzsn/image.png) (https://postimg.org/image/6e162qzsn/)

the program generates flat 2D 'panels' based on points that you input...... however I'm not sure if the app fulfils yours criteria as I'm not sure if it would do this...

(https://s21.postimg.org/p3pz8cuzn/image.png) (https://postimg.org/image/p3pz8cuzn/)

or this......

(https://s17.postimg.org/nnm2mncez/image.png) (https://postimg.org/image/nnm2mncez/)

in a given situation. It does however allow for holes in a mesh...

(https://s13.postimg.org/hdv6qy3cj/image.png) (https://postimg.org/image/hdv6qy3cj/)

There is a bug in it though... see this,,

(https://s12.postimg.org/5jhn9ni8d/image.png)

You can have the source if it helps you

Sorry if this wasn't relevant to you lol

*update*

(https://s15.postimg.org/6e162qzsn/image.png) (https://postimg.org/image/6e162qzsn/)

the program generates flat 2D 'panels' based on points that you input...... however I'm not sure if the app fulfils yours criteria as I'm not sure if it would do this...

(https://s21.postimg.org/p3pz8cuzn/image.png) (https://postimg.org/image/p3pz8cuzn/)

or this......

(https://s17.postimg.org/nnm2mncez/image.png) (https://postimg.org/image/nnm2mncez/)

in a given situation. It does however allow for holes in a mesh...

(https://s13.postimg.org/hdv6qy3cj/image.png) (https://postimg.org/image/hdv6qy3cj/)

There is a bug in it though... see this,,

(https://s12.postimg.org/5jhn9ni8d/image.png)

You can have the source if it helps you

Sorry if this wasn't relevant to you lol

Title: **Re: A graph problem (not necessarily math-heavy)**

Post by:**Snektron** on **November 09, 2016, 05:20:05 pm**

Post by:

Should the path be a smooth function? Because then you might be able to do something with parametric or parabolic equations.

The problem is the closest path will always (with 3 nodes) be either a straight line, or 2 straight lines with a sharp turn. Which isn't very mathematicy.

The only solution i can think of right now requires an awful lot of vector math (calculate {p | d(A, p) = d(B, p) = d(C, p) ^ A != B ^ A != C ^ B !+ C} and calculate a path through that. That also requires a special case for when the sortest path is "straight").

The problem is the closest path will always (with 3 nodes) be either a straight line, or 2 straight lines with a sharp turn. Which isn't very mathematicy.

The only solution i can think of right now requires an awful lot of vector math (calculate {p | d(A, p) = d(B, p) = d(C, p) ^ A != B ^ A != C ^ B !+ C} and calculate a path through that. That also requires a special case for when the sortest path is "straight").

Title: **Re: A graph problem (not necessarily math-heavy)**

Post by:**kotu** on **November 09, 2016, 05:52:40 pm**

Post by:

if you are looking at ways of making efficient networks between many nodes (for example to design an underground rail system) you might want to look at slime molds. these single-cell organisms get quite large (20cm across easily) and they form inter-cell paths for food to travel down. found to create very efficient networks, equivalent to expert human designers (for example of rail system)

(https://s-media-cache-ak0.pinimg.com/originals/d2/a0/8f/d2a08f7321542d41e3537e758fdd1696.jpg)

apparently they use pulses to coordinate the maze mapping (i think)

(https://s-media-cache-ak0.pinimg.com/originals/d2/a0/8f/d2a08f7321542d41e3537e758fdd1696.jpg)

apparently they use pulses to coordinate the maze mapping (i think)

Title: **Re: A graph problem (not necessarily math-heavy)**

Post by:**Hayleia** on **November 10, 2016, 09:55:58 am**

Post by:

Quote from: kotu on November 09, 2016, 03:33:14 pm

Are you trying to generate 2D meshes from general shape definitions? Because I played about with something like that about 12 years ago..... just finding the file. It might not help you though... will post some pics in a bit

*snip*

You can have the source if it helps you

Sorry if this wasn't relevant to you lol

I don't know if this would work, depending on the algorithm you use to generate meshes (not mentioning the bug).

See this example:

(https://tiplanet.org/forum/images/forum_uploads/6947_1478771495_58244327403b3.png)

Both meshes are valid meshes for the 4 given points, but the right one according to what I want is the one on the right.

Quote from: Snektron on November 09, 2016, 05:20:05 pm

Should the path be a smooth function? Because then you might be able to do something with parametric or parabolic equations.

The problem is the closest path will always (with 3 nodes) be either a straight line, or 2 straight lines with a sharp turn. Which isn't very mathematicy.

The only solution i can think of right now requires an awful lot of vector math (calculate {p | d(A, p) = d(B, p) = d(C, p) ^ A != B ^ A != C ^ B !+ C} and calculate a path through that. That also requires a special case for when the sortest path is "straight").

I don't care about the path :P

The input is nodes, the output is nodes' neighbours, and you can use whatever you want in between, not paths, paths, whatever paths, smooth or not.

But I think I'll give up on this complicated subject, I'll just use the X closest ones (where I'd have to find a working X) instead of trying something smart...