Galapagos and Delaunay edge network optimization

Hi everyone!

I have created a Delaunay edge model that connects every green spaces of the city (with a maximal distance of 500m, which means that each edge has a maximal length of 500m). I’ve used the nurbs control points of the polygons as reference points for each green spaces:

As you can see closely, the edges are not all connected with each others’s. Either there are small solitary edges or polygons that are simply not included in the Delaunay edge at all:

My aim is to connect all green spaces (all polygons) in “one all connected” Delaunay edge model (with max 500m).

To make those bridges between each polygon I can add defined existing points into the model. I have a huge amount of those possible locations, and when I consider all of them I obtain a “one all connected” Delaunay edge model, but too dense:

I would like to optimize this Delaunay edge model by adding a MINIMUM of extra points that are necessary to close the network of my green spaces polygons.

I’ve thought Galapagos could be a great help, but I didn’t find a solution yet.

So in summary,

Aim : connecting all the green parks points in one Delaunay edge model with a minimum amount of “extra” points (that have a fix location). That means finding the best extra points locations to close the Delaunay edge network.

I’ve thought of this first, but I don’t know what to put on the genome :

Thanks a lot for your help and advices !!!!!

Replies to This Discussion

Permalink Reply by Md01 on July 17, 2016 at 9:48am

Hiiii still no help, ideas or advices ? :)

Permalink Reply by peter fotiadis on July 19, 2016 at 11:30am

Well ... if I was you ... I would consider a Ball Pivot approach for that type of stuff.

Get the gist about what this thing is (Google it as well) by studying the demo images:

where

(a) either random pts on a sphere are used for triangulation (user controlled search radius [yielding "discreet" mini meshes/"islands"] or auto [yielding a closed mesh])

(b) or random N of points are generated in random M regions and then used for the triangulation. Spot Islands that may or may not (depending on the search radius) occur.

Permalink Reply by Md01 on July 27, 2016 at 3:00am

Thanks a lot for your answer!!! I've checked the method out, it is really interesting way to solve the problem.

I've actually found earlier another solution that consists in increasing the connection distance in maximum to get all the possible connections between the polygons and then applying a minimum spanning tree (spider web plug in) to get only one connection among all of them >

Aim : finding the set of edges connecting all nodes such that the sum of the edge length is minimized.

Then i take all the edges with l>500m and look for constructing "bridges" with the shortest path box among the list of extra points i have since the beginning.

Now, another of my problem

PROBLEM 1

some polygons are inside other polygons and I get some "wanted" edges for the network that would be actually not necessary since they are already in green spaces.... (in the image below they are the dark green polygons inside the green space)

Do you maybe know a way to delete them (of course not manualy).

Like identifying the polygons that are inside other polygons and cull them from the list...

PROBLEM 2

I would like to not take only the center of the polygons but also for some really big surfaces take the limits of the polygons (but only a defined number of points according to the length of the contour)

I've thought about the control points - but im not satisfied with the result...

....& Thanks a lot for the ball pivot method, it is really cool solution (maybe still too complex for my level)

Permalink Reply by peter fotiadis on July 27, 2016 at 4:12am

Well ... these problems are easily addressable via code (but you don't speak, say, C# I guess). Reason for the code instead of components? Too many to list here (not to mention that I suspect that this puzzle of yours is only the beginning - am I correct?). Note: for very large amount of data code provides means of // processing as well (but the best approach is not always obvious nor it exists a magic button that if pressed it accelerates the solution by 12345%).

Provide some demo data (Note: some "indicative" portion, NOT 1TB of stuff) and we'll see what we could do on that matter. But that I mean what portions of code classified as internal (like the high performance ball pivot captured above) I could post here.

Permalink Reply by peter fotiadis on July 27, 2016 at 8:34am

Here's some very simple def that does random polylines/regions ("similar" with green regions within an urban layout ... anyway ... kinda).

It's a very common approach in programming: we create 2 "parallel" ways to do things:

A demo one and another that works with the actual data. In most of times the demo can save you time for locating/preventing/addressing "odd" situations (and bugs) that may are not apparent using a given real-life data set.

Using code ... because the next step is only doable via code (but is removed). Of course the bad news are that this is a black box for you ... but ... the very same applies for all the compiled GH components, he he.

Leaving aside "connections" (whatever this may be) this def Is useful to you in order to line-up your thoughts:

what actually is the desired output? what other requirements may appear in the future? what kind of "filtering" suits you best? what could be the theoretical benefits of // processing? Is it worthy? Are your data that big? That sort of stuff.

Attachments:

Random_polylines_V1.gh, 121 KB

Permalink Reply by Md01 on July 27, 2016 at 10:56am

hiii!

Thanks for your interest!

Indeed I dont know programing languages and it's quite a weak point to deal with such amount of data ....

I'm checking out your grasshopper file right now.

I dont understand everything of it. The left side of the box is used to generate some random geometry?

The filtering "value list constants" is exactly what i need!

what is interesting me is :

if A inside B, remove A

(none of the polygons are intersecting)

Stupid questions but where should i put my own polygons?

it is indeed a smart way to deal with big amount for data.

I've tried a solution as demo as you adviced me (see attached) but

- it's wouldnt work when i will add all the points of the city :(

- some polygons are dispearing even if they shouldnt ....

I definitely have to investigate the great definition you've made and apply it on my polygons

Attachments:

testpolygons.gh, 273 KB

Permalink Reply by peter fotiadis on July 27, 2016 at 11:00am

Well...

1. The purpose of the def provided IS NOT to teach you how to make "demo"/test random polylines. Therefore don't bother to understand what this is (or how it's made, not to mention why, he he).

2. The ONLY purpose is to expose to you various shapes and give you inspiration/ideas about what a filtering policy may be. Many times designers are absorbed by the current case ... and forget that there's a zillion others around: that's what the demo mode does.

3. This thing it doesn't care about your data (works only on "demo" mode)... but the next update will do that.

4. Filtering is not working because no "instructions" for that are included (yet). The options were there to give you some ideas.

BTW: The Boundary native component is smart enough to detect curve containment: try it and see the results.

But still and regardless of any filtering policy > we haven't even scratched the surface:

Connections that is: Ball pivot, Karma, Alien Power, Fate, Delauney (avoid) or what?

Permalink Reply by peter fotiadis on July 27, 2016 at 2:18pm

That said, here's what the Boundary thingy can do: all the dirty job (Curve containment stuff et all), that is

Using your data.

Attachments:

testpolygons_V1.gh, 145 KB

Permalink Reply by Md01 on July 28, 2016 at 4:21am

Hi!

Thanks for your interest again!

I've used the boundary native component, you're right .... it is so much more simple heheh... and works well!

the connections I want is a network that connects all the points (with the smallest distance between each green space)

I've used a minimum spanning tree (spider web), it works well and satisfies me so far, you can see it attached!

here you can see other problems I've met when I was creating the gh file

First, the problem that for larger green spaces, it adds some "useless" distance to go inside (center point) the polygons even if going until the border would be enough

Should i use the control points of the larger polygons and then keep only 10% of it...?

Second,

My amount of data of extra points to create bridges for edges larger than 500m

It is huge !!! I've created a filter (filtering the points in the surroundings of the wanted bridges) but it's not that efficient .... :(

Do you think of a smarter way to filter those points (to then implement them in this bridges construction logic with the shortest paths between points (spider web)

Thank you for your help!!!

All the best,

Kim

Attachments:

testpolygons2.gh, 395 KB

Permalink Reply by peter fotiadis on July 28, 2016 at 5:51am

Well ... that's hard to test since I very rarely use add-ons (other than Kangaroo) because I don't use components for the internal defs on duty (that supposedly do something "meaningful"). Thus I have no idea what Spider Web is and what it does.

But if I was you and provided that you know which polylines describe green spaces (and/or you exploit possible scenarios for green spaces) I would give the proximity native thingy a go. That said if scenarios are required ... it's 100% impossible to address that type of puzzle without code.

Proximity means: for each node (centroid of some green area) find the prox centroids that satisfy a given distance "filter" and make a line graph out of these node-to-node connections (+ connectivity Trees). This is very fast since Rhino provides a special point collection that is ultra efficient/speedy for locating the closest index (FROM a node TO a collection of other nodes > then you remove the visited node from the collection and start another closest index search).

Accepting or rejecting a given connection is also easy via a variety of ways ... but to be honest with you working with components is not my forte.

But the big thing here is that if this is some kind of go-from-here-to-there "guide" (or some infrastructure graph, say for irrigating purposes etc) ... this graph is 10000% Academic since in real life similar stuff takes into account the available roads/access paths/existed infrastructure et all (a fact that leads us to Dijkstra graphs and other ultra freaky adventures [only doable via code]).

RSS