I have an undirected graph, where
- every node has coordinates (x, y)
- every edge is a straight line segment
- no two edges intersect
Some nodes of the graph are marked.
Edges are marked when both their end nodes are marked.
I also have instances that have positions (x, y). For each such instance I want to know whether it is inside a cycle of marked edges, and if so, get a list of all edges in the smallest-area marked cycle containing it.
How should I go about that? I figured I could use the subgraph consisting of only the marked edges, and ignore all the other edges (and nodes). I was thinking of finding an algorithm that decides how this subgraph splits up the plane in faces (of which one is the infinitely large outer face) and checking whether any instance is in a face that is different from the outer face. However I don't see how I could do that. I was alos thinking about using intersecting rays from the position of the instance, however, cycles don't need to be convex. (Because there are no intersecting edges, cycles can be expected to be simple polygons).
Another way would be to try to run "snakes" from the instance and see if I can find a snake that could "escape" without crossing marked edges. If not, the instance must be enclosed. But this feels more like a heuristic than a definite algorithm.
The algorithm doesn't have to be very fast, I only need to check it when the edges are marked or unmarked, which is about once every few seconds.
Any tips, ideas?