Sunday, June 10, 2007

Monotone Chains: the unknown technique

When I was originally developing JTS, I spent quite of bit of time thinking about and researching techniques for efficiently computing arrangements (intersections) of sets of linestrings. There's a relatively large body of literature on this subject, as you might expect since it is such a key aspect of many geometric algorithms. As usual, however, much of this literature is fairly academic in nature, and usually doesn't address some of the more mundane issues which an implementor has to deal with.

One issue that crops up with intersecting sets of linestrings is that there is a tension between increasing performance and decreasing memory use. The fastest way should be to indexing individual line segments. However, this implies creating a new memory structure for each line segment, which can be both time and memory intensive. The most memory-effective structure is of course to leave the original linestrings undivided, but this does not provide good performance.

It seemed to me that there must be an intermediate between these two extremes. After some thought I came up with the idea that I called "monotone chains". A monotone chain is a string of line segments which are monotonic in both X and Y directions. This structure has some nice properties:
  • Monotone chains cannot self-intersect
  • Two monotone chains intersect in at most one connected set of line segments.
  • The envelopes of any two subsequences of a monotone chain are interior-disjoint. This means that the envelopes of successive bisections of the chain form a "pyramid" of envelopes. In turn, this allows comparing two chains for intersection can be carried out using a binary search technique using the two envelope pyramids.
In addition, splitting linear geometry into monotone chains is a good heuristic for partitioning the geometry. Often digitized linework representing natural features contains quite long sequences of segments which are monotone (since the linework follows natural curved features.

I was pretty pleased with my "discovery", and used it to good effect in JTS. For quite a while I was unaware of any prior use of this technique, but recently I came across a reference to a paper by Warren Burton in 1977 which apparently discusses this technique. I was led to this by the paper on Whirlpool by Nick Chrisman et al., which used this technique under the name "monotone sections".

It doesn't come as too much of a surprise that such a simple and useful technique has been used before, but what I do find a bit surprising is how little this technique is discussed in computational geometry literature. I presume the reason for this is that the technique is too simple to be of continuing interest to academics, while it is too special-purpose to be worth presenting to students. There's a dearth of computational geometry literature directed at the true practitioner - which probably indicates how few practitioners there are!

References

Burton, Warren 1977: Representation of many-sided polygons and polygonal lines for rapid processing, Communications ACM, vol. 20, no.3.

Chrisman, N.R., Dougenik, J.A. and White, D. 1992: Lessons for the design of polygon overlay processing from the Odyssey Whirlpool algorithm, Proc. 5th Int. Symp. on Spatial Data Handling, 2, 401-410.

5 comments:

William Blake said...

It is looking very interesting, now i'll try to look into this algorithm. It is semms better in the sense of memory consuming (as you point it in article) than balanced binary trees.
Thank you!

danidif said...

Hi Martin, I want to ask you which is the techinque used on JTS for obtaining monotone chains from a Geometry such as Polygons or LineString. Thank you in advance

Dr JTS said...

danidif,

The algorithm to build monotone chains from arbitrary edges is pretty straightforward. Basically it just walks through the sequence of points, and creates a new chain any time moving to the next coordinate would violate the monotonicity constraint. Check out the MonotoneChainIndexer class in the JTS source.

danidif said...

Thank you for the answer, I saw the MonotoneChainIndexer Class. I took a look at Line-Segment intersection too: is it based on the Bentley-Ottmann algorithm, which use a sweep line and two data structure?
Sorry for my bad english and thank you so much.

Dr JTS said...

Line Segment intersection in JTS is accomplished in a couple of different ways. The core algorithm used in geometry overlay uses a sweep-line index, but it's not full-blown Bentley-Ottman, since it doesn't use a segment-tree index for the sweepline.