Connect points with lines to Center and minmize length

Hi everybody,

I’m using Grasshopper quite a while, but this issue is unsolvable for me…

I try to connect points through several lines (4 points per line) to a center point and try to minimize the length of the lines.
I want to use Galapagos to solve the issue after setting up the structure.

Has anybody a hint for me to solve this riddle?

/Bernd

Post the file!

Can the curves intersect ?

This is a discrete combinatorial problem that can’t be easily expressed as some sort of gradient descent, so Galapagos probably isn’t suitable.

Basically your algorithm has a huge number of binary decisions to make (Do I connect these two vertices or not?). A subset of those decisions result in a valid graph according to your conditions, and you’re trying to find the minimum valued solution out of that subset according to total edge length

A naive brute force approach would need to perform \frac{16!}{4!} = 871782912000 checks which is still relatively okay – easy to script and a computer could do probably solve it in a few minutes with a few early exit conditions. Of course, any few more points and it blows up very rapidly…

(Don’t think there’s a much use for a posted file for this question, it’s basically a Pop2d and a point)

There is also a center point and a list of start (or end?) points? Or is the puzzle that all points will have shortest possible path (“walk”) to the center point, each with four points per path and without using the same point in more than one path? The latter would preclude intersections or using segments in more than one path. Too ambiguous to solve as described.

I made a Definition. I would say a bad one, but still it‘s something. Just randomly shuffling the list of points, Partion it and shuffle again or sort by distance to midpoint.
Why bad one? Cause it‘s just randomly testing and it depends on luck if It finds a good result or not. But hey, at least I tried and I don‘t have any idea at the moment to improve.
Unfortunately I had to change the train and no WiFi anymore. Will upload the definition as soon as possible :slight_smile:

That’s still probably a better approach than brute force… I take back my previous assumption about it being tractable - made a quick ugly Python script using 12 vertices, and it takes 7 minutes to spit out a solution :dizzy_face:


… and 16 vertices would take 43680 times as long. Definitely some smarter logic needed here!

I’m surprised there aren’t any easy-to-use GH plugins out there for these sort of basic network graph operations, besides “Shortest Walk”, which I’m not sure would be applicable in this case.

But at least you get always the same result. Mine are nearly everytime different.

Ok here’s the script.

conn2conn1conn

As you can see in the last Picture, sometimes it’s just unlucky :smiley: (two Points on red and blue should be changed)

Nearly evertime I run on this amount of Points, the results are Close, but not absolutly.

I used Silvereye, but you can replace it with Galapagos (Fitness in var 1=jitter seed and genepool, in var 2=only jitter seed)

conn_opt.gh (20.1 KB)

Hi Joseph, qythium &Tim,

thank you so much for your input and discussion and sorry for the late reply.

As you mention a randomly generated solution is not the best option, but the only one I see for time being.
16!/4! is just too much iterations, especially when I wand to increase so number of points.

I’m not sure if the shortest walk will help me, because somehow I need to define the boundaries for this walk, and this is what I want the program to do.

I tried Tim’s solution and find this a nice script. Qythium’s python solution does not work until now. I know python but I haven’t used it for grasshopper. Can you maybe post the file?

Here is solution without intersection (if there is no 4++ pts where centerPt & 4++pts are collinear, centerPt is starting point and other are following).
Solution should produce “very short” result.

connPt_wCP.gh (10.3 KB)

1 Like

This script runs very good, thank you Radovan!
Although I’m not absolutly sure how each step of the C# skript works.
Can you please give me a hint?

Hi
Explanation of the code is in comments inside C# component.
Everything is based on fact that we order points (vector defined by centerPoint-point[i]) by angle and then process three by three points …
connPt_wCP2.gh (7.8 KB)

Yes understood! Thanks
Is it also possible to create loops at the end of the lines? Thus connect two lines at the end with this script?
What do you think?

Yes, definetly it is possible to connect end points of two neighbour-polylines to get one closed polyline.
But in such case it may happen that resulting closed polyline will self-intersect.

Is it acceptable?

Ah, I think I misunderstood the problem initially - thought it was about finding 4 equal-length branches of overall shortest length, not branches of 4 points each!
The latter problem is significantly easier, and @RadovanG’s solution using a ‘greedy’ algorithm should be good enough, except it seems to tend towards clockwise-curling branches, maybe due to the nature of the ordering?

(Don’t know why I even suggested a brute-force algorithm in the first place, must have had a long day when I posted that :sweat_smile:)

Is in not always clockwise as long as three ponts are permutated and shortest polyline (CenterPoint + 3points-permutation) is selected. Without permutation it would be clockwise-curling.

Radovan, the intersection of points is ok for me. Without intersection would be the high-end solution…
Is this integrable into your script?

To admit I still struggle with the c# script. I’ll need some knowledge on c# in grasshopper. Maybe some reading and youtube can help me.

Here is updated code that “connects endpoints” of 2 neighbour polylines.
connPt_wCP3.gh (9.5 KB)

3 Likes

Thanks a lot, Radovan,
works brilliantly!