Wise ones, I humbly seek enlightenment (but not the window manager :)
We have a project that is geographically orientated, and have a need to determine whether a polygonal structure has any edges that cross at any point.
For an example, consider a line describing the shore-line of a lake: the polygon should enclose a single shape (it may not be closed, as the lake may be part of a larger body - such as the Great Lakes in North America), yet no line should cross any other line (otherwise you'd have two lakes).
We do not need to know which lines cross, nor do we need to know where the lines cross, we only need to determine whether any lines cross - a boolean return! (although this information would help in the long term).
In somes ways, this is similar to the Brouwer Fixed Point Theorem: It states a fact, which can be mathematically proven, but does not seek to determine the actual points of concurrency.
We have looked at the examples in chapter 10 of the Mastering Algorithms with Perl book, however this does not scale to the 14,000+ points we are working with.
Has anyone ever had to solve this problem, or know of a mathematical solution to this problem?
-- Ian Stuart
A man depriving some poor village, somewhere, of a first-class idiot.
In reply to Line intersection, scaled to thousands of points by kiz
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |