# Find whether n closed curves intersect

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!

-

How much is "a number"? If there aren't that many, you could probably brute-force check by taking two contours at a time... – J. M. Apr 17 '11 at 9:12
Yep, there are a little number of contours. I would do exactly that. However, I really wonder how would I check for intersections? And I should also clarify, because I didn't say it right the first time, that I'm interested in checking not the curves, but the closed regions they encircle. Could you suggest something? Sorry if I'm asking for an obvious thing, I'm slow with math. :-) – Albus Dumbledore Apr 17 '11 at 9:38
Could you tell us why you need this?  Knowing the background is helpful for choosing the level of the answer. – Sam Nead Apr 17 '11 at 16:47

## 1 Answer

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/

-

Just perfect! Thanks for the bother! – Albus Dumbledore Apr 17 '11 at 17:22
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 25, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9491332769393921, "perplexity_flag": "head"}