# How to divide points on a 3D complex surface into two regions based on a closed curve defined on this surface?

My problem seems simple but I can't find an algorithm that will do that for me for any 3D complex surface.

I have a really complex shape 3D surface and a closed curve on it defined by some points (see picture below, that black curve is the closed curve). My purpose is to detach that bulge from the rest of the surface based on that closed curve. In fact, if I find a way to distinguish between the points that are on the side of that closed curve on the bulge from the rest of the points, that would be suffice for me. Any idea how to do that? I couldn't find anything in VTK. So, I appreciate any suggestion or recommendation.

Update:

The closest thing, which I was able to find is vtkImplicitSelectionLoop class in VTK library. I used it this way:

from vtk import *

return pd

def vtkPolyDataWriter(filename,pd):
writer = vtkXMLPolyDataWriter()
writer.SetFileName(filename)
writer.SetInputData(pd)
writer.Write()

selectionPoints = neck_curve.GetPoints()

loop = vtkImplicitSelectionLoop()
loop.SetLoop(selectionPoints)

clippedOutput = vtkClipPolyData()
clippedOutput.SetClipFunction(loop)
clippedOutput.SetInputData(model)
clippedOutput.SetInsideOut(True)
clippedOutput.Update()

vtkPolyDataWriter('sac.vtp',clippedOutput.GetOutput())


Basically, I create an implicit function based on my closed curve (i.e. loop) and then I just clip it. But the result is far from satisfactory and it is somewhat confusing:

The red regions are the regions that are picked as within the closed curve by using vtkImplicitSelectionLoop, which are obviously not the thing that I'm expected here. Any idea?

The way you answer this is as follows. Say, you want to find out whether node $$n$$ is on this side or that side of the line (pick one side of the line and call it "this side"). Choose once and for all a node $$n^\ast$$ that is on this side of the line. Then find a path from $$n$$ to $$n^\ast$$ that does not include any of the edges of the line (marked in black). Count how many times your path hits a node that is part of the black line. If this number is even (including zero), then $$n$$ is on the same side of the black line as $$n^\ast$$. If it is odd, then they are on different sides.
Of course, identifying all nodes that are on one side of the line is easy too: You pick one node $$n^\ast$$ that is unambiguously on, say, this side and then just do a breadth-first traversal of the graph tagging all neighbors of $$n^\ast$$, then their neighbors, and so on, always excluding nodes that are part of the black line. Eventually, you will run out of nodes to tag, and assuming that the black line dissects the graph into exactly two pieces, then you're done.
• It looks like a really great algorithm. Two technical questions here: 1. The points on the black curve sometimes are not part of the points of the mesh. I mean some points in the black curve may be close or even identical to the mesh points but that's not the case always. It originates from the fact that that black curve is generated by somebody else that works on exactly the same topology or geometry but not exactly on the same mesh necessarily. Does this create a problem here or if yes probably, is there any easy workaround? 2. The path from $n$ to $n^{*}$ should be a geodesic path? – Alone Programmer Dec 18 '19 at 16:56
• Whether or not the black curve consists of nodes, you'll have to figure out whether your path from $n$ to $n^\ast$ crosses it. That's easy if the black line consists of edges of the graph, whereas if it is not, you'll have to come up with another way of determining intersection. For your question 2: No, it doesn't have to be a geodesic. Any path will do, whatever you find convenient to come up. – Wolfgang Bangerth Dec 18 '19 at 23:55