scraperwiki/pdftables — pull request #43 by pwaller (2013-09-10 15:31:23+00:00)
Title: Add some new line segment manipulation algorithms

Summoning @scraperdragon @IanHopkinson @paulfurley

Some useful algorithms for efficiently processing line segments.

Comments welcome, particularly if anything is too hard to understand.

I believe they have an algorithmic complexity equivalent to sorting the input list of segments. There is no requirement for the input to be sorted.

The input interface is "barks like a list of 2-tuples", so if you feed it something which can be tuple expanded to a 2-tuple `(start, end)` then you can feed it to this thing. The output is as shown in the docstrings, with the exception of `segments_generator` where the range tuples are the ones that are starting/ending at that position. One can imagine making an algorithm on top of `segments_generator` which could scan a page efficiently to look at gaps between lines, for example.

Some invariants to help wrap your brain around it:

* input looks like `[(start0, end0), (start1, end1)...]`
* `number of unique positions = len(set(starts) | set(ends))`
* `len(list(segments_generator(x)) == 2 * len(x)` (because output reflects start+end for each tuple)
* `len(list(histogram_segments(x)) == len(number of unique positions) - 1`
* `map(len, segment_histogram(x)) == (len(number of unique positions), len(number of unique positions) - 1)`