I have an algorithmic question for you:

Given: 3D triangle surface mesh, open polygonal chain A, closed polygon B, closed polygon C, all on the mesh.

Wanted: A line that closes A such that B lies within the enclosed area and C does not.

A correct solution would be the green line, a wrong solution would be the red line.

I am currently looking at it as a graph and walking through the graph with a shortest path algorithm. While I can guarantuee that the solution does not intersect polygons B and C by blocking the relevant edges, I have trouble finding a way to prescribe that they can/cannot be enclosed.

I realize I am asking two things at once, a) "how to include a given area?" and b) "how to exclude a given area?". So if you have a solution for either one or even both questions, please let me know, I am grateful for any help!

Edit: I think question a) "how to include a given area?" can be solved with a convex hull algorithm. Extrude B by a small amount to form D, then put all nodes of A and D into the convex hull algorithm and the resulting polygon should provide an accurate solution. Opinions?

Now I am still looking for an answer to b).

enter image description here


This site is temporarily in read only mode and not accepting new answers.

Browse other questions tagged .