search

nmwsharp / potpourri3d

An invigorating blend of 3D geometry tools in Python.
MIT License
414 stars 31 forks source link

`find_geodesic_path_poly` fails when there’s overlap in the dijkstraPath #17

Open Petingo opened 4 months ago

Petingo commented 4 months ago
Screenshot 2024-04-04 at 15 25 54

As the diagram shows, find_geodesic_path_poly will generate something unsatisfactory when there's overlap in the dijkstraPath. I remember the original author of the papar said that there's some problem when overlap / knot / loop presents in the initial path.

My workaround is to find the edge path by myself, making sure there's no overlapped vertices before calling the function.

nmwsharp commented 2 months ago

Hi! You're correct in your understanding.

The underlying algorithm does support this case, but the API exposed in these python bindings does not. The problem is that you need to communicate the input path in a richer way: that in the overlapping region, the paths sit on top of each other but do not strictly cross.

In the underlying C++ implementation (from geometry-central), we represent paths which are coincident along an edge as a stacked sequence (see Fig 11 in the paper). However passing the polyline does not give the "stacking".

This limitation is not easily fixed. We could give an "advanced" API to communicate the stacking. Or we could write some heuristic functions to infer it in cases like this, where it's pretty obvious what the desired topology of paths are... I don't have plans to immediately implement either of those things, but would gladly accept a PR if anyone wants to try it.