Shortest path analysis in Sketchup?

Jussivee

Hello all,

As of now I don't have any experience in programming ruby (within sketchup or elsewhere), but I have an idea in mind that I´d like to try out. Namely some basic network analysis, how to get from A to B along the shortest path within a network. What I´d like to know from those of you who do have experience in ruby programming in sketchup (I guess everyone reading this) is how difficult/challenging do you think the idea is to carry out in sketchup? Is there some fundamental way sketchup does or doesn't do things that make this way too difficult?

Basically the idea would be to have a network of interconnected edges, and the plugin should find the shortest path from some vector A along the network to some vector B (using Dijkstra's or some other algorithm). I´ll attach a simple picture to illustrate.

Is the idea plausible? Yes? No? Maybe?

from A to B

Dan Rathbun

You mean point A to point B ?

In the example I can see 4 paths that are of equaltotal length, but only 1 that has 2 segments (ie, one intermediate vertice.)

One approach might be to draw a construction guide between the two points.
Then move along that guide, finding the first edge vertice that is closest to the guide line, and pushing it into an array.
Find the next, and IF (and only if,) there is an edge connecting the 1st and 2nd, push the 2nd into the array.
Repeat.

If you reach an impasse, where no suitable vertices can be found, to complete the path, the code backs up , popping vertices out of the array, and searching by vertices that are not as close as the "popped" vertice.

The general idea, would be to find a path, that follows the direct guideline, as near as is possible.

Jussivee

Yes, point A to B.

Theres algorithms to solve this alright (http://en.wikipedia.org/wiki/Dijkstra's_algorithm). I'm just trying to figure out how easy/difficult it would be to actually implement it in SketchUp using Ruby (through a 3d-polyline network drawn in SketchUp). The thing is I have no experience in Ruby yet (just some rather limited experience in Java), and I would like to form an idea of just how doable this is. But it seems you can do pretty much anything with the SketchUp/Ruby combination?

The reason why I´d like to do this in Sketchup is that it would provide a decent platform for urban planning/design issues where this shortest path analysis would be relevant.

sdmitch

I found a Ruby version for Dijkstra's algorithm but unfortunately it is written for Ruby version 1.9.2+ while Sketchup is still in the 1.8 world.

Dijkstra's algorithm - Rosetta Code

Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source...

Rosetta Code (rosettacode.org)

Dan Rathbun

It says that solution is incorrect and inefficient.

It seems the best solution is the C++ one, so translating that to Ruby might be a good idea.

sdmitch

@jussivee said:

Yes, point A to B.

Theres algorithms to solve this alright (http://en.wikipedia.org/wiki/Dijkstra's_algorithm). I'm just trying to figure out how easy/difficult it would be to actually implement it in SketchUp using Ruby (through a 3d-polyline network drawn in SketchUp). The thing is I have no experience in Ruby yet (just some rather limited experience in Java), and I would like to form an idea of just how doable this is. But it seems you can do pretty much anything with the SketchUp/Ruby combination?

The reason why I´d like to do this in Sketchup is that it would provide a decent platform for urban planning/design issues where this shortest path analysis would be relevant.

Jussivee, I have written my own Ruby version of the Dijkstra algorithm and it has passed all test on the somewhat simple example you posted. Could you provide a more "real world" example to test own?

Jussivee

Great Sdmitch!

I guess the answer to my question then is "yeah its easily doable".

Well, for a more real world example the network could be made more complex ad infinity, and the points A and B could be dynamic in the sense that they´re not vertices of the network itself but points which could be moved around and which would snap to the nearest point along the network (a new dynamic line would be drawn from point A/B that would snap perpendicularly to the nearest edge of the network). I dont have any example files at hand at the moment, but if you can get your hands on some street data of some city for example that would be a nice playground. Essentially the kind of routing you get in google maps etc.

What I'm most interested though is fine grained catchment areas, of a tram stop for example. Say you´re designing a new housing area, and you want the apartments to have as good accessibility to the tram stop as possible. Well, you can just place the housing volume approximately within some certain distance from the stop, but because numbers are cool and because you want to be able to accurately compare different design alternatives on the go (as youre doing the design in sketchup) you might want to do something that i´ve tried to illustrate in the attached photos.

First you have the 3d-model of your design, the building volumes and the (pedestrian) street network. The circle represents the tram stop.

Then with this plugin by TheDro http://sketchucation.com/forums/viewtopic.php?f=323&t=36063 you voxelize your buildings to discrete volume units.

Now for each of those volume units you calculate the shortest possible route through the network to the tram stop.

With this data then you can do all sorts of analysis, see how much of the volume falls within a 300 meter radius from the stop for example, or what is the overall distribution of the building volume as a function of the distance to the stop. Or what is the most used section of the network.

The network would need to include the staircases (so that the volume units would snap to realistic places in the network) and probably theres something else to fix in this too but you get the idea.

How about that?

thomthom

Interesting topic.

As for these places you talk about, in the SketchUp Ruby API you can assign attributes to geometry, so you can use that to define markers for your script as to processes the model.

I'd also think you wouldn't need to actually create the voxel geometry, but it could be used just in memory. Maybe an overlay UI using a tool - which also let you place your points.

sdmitch

So let me see if I understand the problem. We have a fixed point "B", the tram station, and we want to figure out where the nearest point "A" to each "unit" in the buildings would be on the "network" then how far it is from A to B.

Jussivee

We have a point A (tram station) and a whole bunch of points B (the voxels, I guess some center point in each one of them).

We also have a network.

Then we just calculate the shortest path from A to each B1...Bn.

The result is something like this:

A->B1 : 241 meters
A->B2 : 243 meters
.
.
.
A->B5202 : 764 meters

And thats the actual raw data we get. Then we can analyse it in excel or possibly integrated into the plugin, for example what is the average/median distance, or how many of these B are under 300 meters from A. Because the voxels are volume units if we calculate (the number of B under 300 meters) / (the number of all B) the result will tell us how big percentage of the planned housing volume is under 300 meters from the tram station. Etc.

I guess you could do this without voxelisation too but that would result in a lot more difficult math. And Thomthom, if I understood you correctly you suggest the voxelisation would be done for the calculation purpose but not shown on the screen? Yes that is also possible, but I thought the voxelisation would also provide a good form to visualise the results and thus give instant feedback to the designer. The voxels could be color coded based on their distance to the calculation point (the tram station in this example).

thomthom

Sure, if they are useful as geometry then of course. Just aired the other option as generating geometry in SU are slow operations, slows down depending on how much you have in the context you add to.

sdmitch

The voxels are component instances with a .definition.name prefixed with "VoxBox" so it is no problem to find them and use the .bounds.center to define its location. Then it is a matter or projecting that point to each edge of the network to find the closest edge. But, unlike a vertex, the point isn't associated with the edge in anyway that would allow you to retreive the edge and traverse back to point A. The best results I have been able to achieve so far required dividing the edges then picking the vertex closest to the projected point and using that as point "B"

Dan Rathbun

@sdmitch said:

The voxels are component instances with a .definition.name prefixed with "VoxBox" so ...

I knew someone would need that someday ...

@sdmitch said:

Then it is a matter or projecting that point to each edge of the network to find the closest edge. But, unlike a vertex, the point isn't associated with the edge in anyway that would allow you to retreive the edge and traverse back to point A.

Fire a vector from the bounds.center using:

Geom::intersect_line_line

or Geom::intersect_line_plane

or use Model#raytest()

arlibby

I have been working on something similar and have had some success with Dijkstra's algorithm. This is my first project with SketchUp and Ruby so my plugin has been built by trial and error and isn't very pretty.

The Calculate Shortest Routes command in the Plugins menu writes the results to the Ruby Console window. There is another command that writes the results to a .csv file.

dijkstra.rb

dijkstra_example.skp