Euclidean steiner tree algorithm applied to street networks?


(Mcfjoshua) #1

Has anyone tried to apply this geometric problem to street networks? Specifically, where road ends are points, trying to find minimal path connections? I’ve found a research paper on this script but can’t make too much sense of it. Perhaps there is a similar thread?

Thanks,

Research paper:
http://papers.cumincad.org/data/works/att/caadria2014_102.content.pdf

Area 2_ FRAMEWORK_steiner tree.3dm (2.5 MB)


(Tom) #2

I guess this is because you have missing to read about graph theory and programming? Hope this helps.


(Mcfjoshua) #3

@TomTom Thanks for the insight. While the paper doesn’t mention these two things specifically, most of the technical language remains absent. I’m fairly new at grasshopper and haven’t had the chance to jump into graph theory and programming. Sounds like your an expert in this area?


(Mcfjoshua) #4

I’ve used a python script here which I think could be useful. Does anyone know how to:

  1. use a different boundary, ie polygon/curve instead of a rectangle
  2. used specified points inside of the boundary

See attached image and files,

Interconnectpoints.gh (22.1 KB)
Framework_interconnectpoints.3dm (2.5 MB)


(Mcfjoshua) #5

Getting closer here but does anyone know how to adjust this so that the connecting lines stay inside the polygon shape? And the points should be road connections?

I’m using plugins: 1. kangaroo physics 2. karamba 3. human

JoshInterconnectpoints.gh (21.2 KB)
Framework_interconnectpoints.3dm (2.6 MB)


(Laurent Delrieu) #6

Just to point an old discussion.


(Tom) #7

I wouldn’t consider myself being expert. Generally spoken graph theory is a big topic in many disciplines, in programming its widely used. Many search algorithms are based on graph theory. If you use google you basically apply graphs. Part of the graph theory are route problems, steiner tree is one example. Another is the shortest path or traveling salesman. Often route problems are explained with street networks. So its natural using it for city planning. However a real application is found in programming.

If you don’t know about the basics you won’t understand it, that’s was the intention of my first post.

Edit: I saw the Python script. If you already know programming and how to write graphs, then just google for it. There are many implementations around.


(Laurent Delrieu) #8

Just using classical components plus Shortestwalk. I am there. Now it needs some edges bundling …


minimal path.gh (45.4 KB)


(Laurent Delrieu) #9

I reuse the Kernel Edge Bundling with a little change. No lines in inputs but Polylines. With just that I am there

You must program something to suppress curves going out of the perimeter.
With 60 iterations it took 3 minutes here. The more iterations the less roads.

200 iterations


Kernel Density Estimation-based Edge Bundling for Streets.gh (50.7 KB)


(Mcfjoshua) #10

@laurent_delrieu Thanks! I’m not sure that the kernel edge bundling was what I had in mind but i’m going to try and play with this a little further. Ultimately, would like to bake the generative options as street centerlines. Tough learning curve on my part but seems like I need to dive into programming a bit more? The attached image is what I had in mind. (image: Lopes J., Paio A., Sousa J, 2014)


(Tom) #11

You don’t need to learn anything. Just beg or google for a script and give your optimisation a meaning. That’s it, you’ll pass the exam and probably never ever use this again. That’s the truth about this pseudo-blabla you hear about in any university nowadays. I wonder if there is anyone out there planning streets with these algorithms anyway.


(Chris Hanley) #12

This is a very good question. Space Syntax has done some extremely relevant/successful work using graph theory…as a PART of their analysis/design process. On the other hand, In my experience sitting on some juries for academic urban planning studios…it often falls into the “voronoi syndrome”, (improperly/overly used with out a fundamental understanding of the underlying methodology).
For example, one could argue that more connections to a street/path can indicate a “positive” metric. While this is often true, it CANNOT be considered the only metric. While many graph theory approaches have some type of weight for nodes/connections, it becomes all the more important to understand why you, (the designer of the implementation of the chosen graph theory approach), need to understand…or theorize, what the quality of the street/path the theory is proving or disproving.
Ugh…quite a large discussion, and perhaps not unique to the application of graph theory, but perhaps applicable to any parametric design approach.
Shortest path is not always the “best path”…because you need to decide what “best” is. Distance? Ease of access? Quality of experience?
:: need more coffee…end tangent.


(Chris Hanley) #13

I should add, (on the technical side), there are a few posts regarding the implementation of NetworkX:
https://networkx.github.io/

" NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks".

https://discourse.mcneel.com/search?q=Networkx