Shortest Path On A Surface Between Two Points

[grasshopper]

I'm looking for a way to derive a curve that describes the shortest path along the surface of an object between two points that also lie on the object's surface. For what I want to achieve the solution doesn't have to be optimal just close to it. Anyone have any ideas?

Thanks,

John

[Jason]

I'm looking for a way to derive a curve that describes the shortest path along the surface of an object between two points that also lie on the object's surface.  For what I want to achieve the solution doesn't have to be optimal just close to it.  Anyone have any ideas?

Thanks,

John

28622[/snapback]

Hm, is there a way you can lever the Shortest Path thing in the PolySplt operator?

[peship]

curve + project (+ trim) ?

[Marc]

add sop (connect the points)->resample->ray?

Should be pretty accurate.

M

[Jason]

Hm, is there a way you can lever the Shortest Path thing in the PolySplt operator?

28624[/snapback]

I just looked at this and it seems like the PolySplit unfortunately does not have a feature to optionally the newly created (highlighted) points to a new point group... a good and probably easy RFE for SESI?

[sibarrick]

Worth noting that the polysplit shortest path option doesn't work to well on geometry the changes direction a lot. If its fairly uniform then your ok. I don't think the algorithm is terribly sophisticated, probably just a ray casting method much as has already been suggested.

[grasshopper]

Thanks guys. The way I'd been investigating was along Marc's lines using a resampled line with the ray SOP but this sometimes fails if the points are around a hole or an arch. So I tried looking at slicing up the object per point on the line and aiming the normals at the nearest points but this also sometimes fails too if the object is quite an irregular shape.

My current thinking for an algorithm would be to find a way to group points in the object by connectedness from the source point. So the points directly connected would have a value of 1 and the points connected to group 1's points would have a value of 2 and so on. You keep growing the groups until you include the goal point for the path. Then you start working backwards so that you connect the goal point to a point in the next-but-last group and then to each inner group until you get back to the source.

john.

[grasshopper]

Okay, a bit more playing around with polysplit and I think it is going to work for me. Thanks for pointing me in the right direction Jason as I wouldn't have thought of it. But it is tricky to get the points into the polysplit and then to get the results out so I agree with you about an RFE for SESI to make this friendlier.

I've attached a hip showing how I used the shortest path in the polysplit. Sometimes the added edge gets reversed so you need to check whether to reverse the point order or not. I did this with an expression that measures the distance between the first and last points in the created edge to the source point. To see what I mean try changing the source point from 464 to, say, 1156.

Cheers,

John.

shortestPath.hip

[George]

I just looked at this and it seems like the PolySplit unfortunately does not have a feature to optionally the newly created (highlighted) points to a new point group...  a good and probably easy RFE for SESI?

28628[/snapback]

That's a good one Jason, I logged it, thanks.

Simon is right, the "Shortest Path" algorithm in PolySplit won't really give you the shortest path on an arbitrary mesh. It is a little more complicated than just ray casting (see attached contrived file, for an example of how it can traverse bridges -- only the two end edges were selected). But it is greedy and will try to only move in the direction that gets it closer to its target. I also can't climb walls that are at 90 degrees.

Quad strip on the other hand is nice because it doesn't care at all about your geometry, it cuts based on the topology.

Take care,

George.

polysplit_bridge.hip.gz