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

Question

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 *

def vtkPolyDataReader(filename):
        reader = vtkXMLPolyDataReader()
        reader.SetFileName(filename)
        reader.Update()

        pd = reader.GetOutput()

        return pd

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

model = vtkPolyDataReader('model.vtp')
neck_curve = vtkPolyDataReader('neck_curve.vtp')

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?

Answer 1

I don't know whether there is a way to do this with VTK functionality, but what you have here is a well-understood question. If you think of all of the vertices of the mesh as the nodes of a graph, where nodes are connected by the edges of the mesh, then your black line is a path through that graph. In essence, you are asking whether a node is on one side of that line through the graph or the other.

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.