I have addressed this issue in a commercial product in the past. You asked about analytic curves, but I will talk more about this for curves that are at least twice differentiable. Polygon processing as a set of individual line segments. There is no need to segment the curves, but if you want, you can adapt the algorithm a bit.
Also, you might want to see my matrix-based ellipse geometry on V graphs to find the intersections between your ellipses.
Main idea:
- Consider the ray from your test point in the + x direction.
- Now consider an ant running along your beam from a control point.
- When ant hits the first intersection with one of the curves, it makes the sharpest one on the left, and leaves an arrow at that intersection indicating the direction it has chosen. (If there is no intersection, then obviously the point is not bounded.)
- If it comes to the end of the curve, it doubles back on itself.
- If several curves intersect at this point, she selects the curve that is most on the left.
- If one or more curves actually touch the ray at the intersection, higher derivatives can be used to determine which curve and direction to choose. (This ant knows the calculus.)
- Now, when ant walks along the curves, he always makes the largest left turn, as indicated above. If there is a touch between the curves at the intersection, use higher derivatives to select the one that is “most on the left”. (Details left on ant).
- In his travels, ant can appear at the initial intersection with the beam several times. But as soon as he is in the direction of the arrow (the one that he left in step 3), he makes movements, and he crossed the "contour". The problem comes down to deciding whether a point is in this circuit.
"Contour" is a topological entity. This is a closed ring of "segments" connected at the "peaks".
A “segment” is a piece of a curve used by a path in a specific direction.
A “top” is a link between segments. A vertex is associated with the position (x, y) on the plane, but there can be several vertices in the same position, one for each pair of segments in the contour that occur at this point. There is a vertex for each endpoint of the curve (the top of the spur) or the intersection of the curve of the curve found in ant.
A path (in this context) is not a geometric object! Do not think of it as a simple closed path on a plane. ant can go along a segment, get to the end and return as it appeared - this is called a “spur” and includes two contour segments, one for each direction. Or it can go along one direction of the curve segment, wander a little along other curves and return along the other direction of the segment.
So, even if your set of curves has only one line in it from A to B (I assume that you do not have infinite lines) and your ray falls into P, you still have the outline V0 (P) -V1 (A ) -V2 (P) -V3 (B) -V0 with 4 segments V0-V1, V1-V2, V2-V3, V3-V0. Note that V0 and V2 are different vertices, both located at point P.
Now to check if your point is in the outline.
Find the intersections of your ray (any ray emanating from your test point) with the outline. We really need the parity (even or odd) of the number of intersections with the contour. If the parity is odd, the point is bounded by curves, if not even that.
Since double-moving segments do not affect parity, we can ignore them. This is due to the fact that there is always an even number of intersections on twice intersecting segments, since they are in the contour twice.
Examples:
Consider this curve. I use strings, so I'm not working too hard:
Case 1 - the point is not limited. Outline use of curve segments is indicated by dashed arrows. The parity number of the intersection of rays and contours is even.
Case 2 - the point is bounded. The parity of the intersection of the rays and the contour is odd.
Here's what might go wrong:
You cannot find the outline for various numerical reasons. For example, you can skip intersections, for example. the two curves almost touch the curve. You can see this as one intersection, but when you check the parity check for the intersection of the rays, you will see one cross, so that the parity flips when it should not.
You may not be able to calculate sufficient derivatives to make the right turn decisions. In the case of analytic geometry, this should never be.
Your beam hits the top (the connection between the segments) of your path. (Note that at one (x, y) point there can be several vertices, each of which must be processed separately.)
In this case, you need to decide whether the incoming and outgoing vertex segments are on the same side of the ray at the vertex. If they are on one side, parity is not affected. Otherwise, the parity is flipped. If one of the curves touches the ray at the top, you may need to use higher derivatives to solve this.
- The line segment is collinear to your test beam. This is actually a special case 2, but easy to handle: Ignore it.
There are many details, but you should be able to handle them. Be sure to use spatial trees to avoid calculating unnecessary intersections.
The answer to your second question is to remove any double-moved segments from the path. This can lead to several subcontours. One of them will contain your point.