Find whether n closed curves intersect

Question

I have a number of closed curves (contours) which I want split into groups of mutually intersecting curves. The contours are made of straight lines and bezier curves. How could I do that? Thanks!

Answer 1

Hopefully the package that allows you to draw Bezier curves also allows you to a) draw arbitrary lines and b) compute the number of intersections between a line and a Bezier curve. With those to things given: Suppose that $\alpha$ and $\beta$ are contours. From your comment I assume that $\alpha$ and $\beta$ do not self-intersect, nor do they intersect each other. Let $B$ be the region (a disk) bounded by $\beta$. So there are two cases to ponder. Either $\alpha$ is contained in $B$ or it isn't. So:

Suppose that $p$ is a point in the plane. Let $L_p$ be the vertical ray based at $p$. Now suppose that $q$ is a point on $\alpha$. Using the primitives of your program or otherwise, compute $N_q = |L_q \cap \beta|$, the number of intersections between $L_q$ and $\beta$. In general, $\alpha$ is contained in $B$ if and only if $N_q$ is odd.

There is a subtle point here: the ray $L_q$ needs to meet $\beta$ transversely for this to work. That is, $L_q$ must not be tangent to any point of $\beta$. One hack to get around this: compute the parity of $N_q$ for several random points $q \in \alpha$ and accept the "generic" answer.

By the way, Google finds a nice introduction to Bezier curves on-line - http://processingjs.nihongoresources.com/bezierinfo/