Reconstructing a Paragraph From Random Set of Words Goal: Take a collection of randomly shuffled words that represent x and y coordinates on a plane, re-order them such to construct the original paragraph those words came from.


*

*Each word represents an actual word taken from a set of sentences on a real document. Therefore, perfect vertical alignment and spacing between each word is not to be expected.

*The set of words span multiple lines. 

*The input collection (words) are randomly shuffled in the array such that a comma on a second line can appear first before all other words.

*Each word has a x and y coordinate, width and height.

*Words consist of numbers, nouns, verbs, comas, periods and other English symbols.


What is the most efficient algorithm or set of functions to produce the end result given the input?
This is actually a computer programming question, meaning, what I really need is some code in Java to do this, however, I would like to start from a philosophical or mathetical perspective on the best approach, then convert it into code. However, some code would be helpful.
 A: This is how I solved it. I have tested it with several unit tests and have proved a consistent result. However, I would like to see if someone else has a better answer that involves faster algorithms. Another implementation example would be nice for comparison.


*

*Randomly shuffle list of words to ensure that the output will always remain the same regardless of how the words are originally ordered.

*List the font height of each word in collection.

*Take the median or mean font height as a font height filter.

*Move all words that don’t meet the font height filter to a reserved list of words which should contain mostly punctuation.

*For each word, iterate through the word collection building a lookup rect. This lookup rect is joined to the next rect that intersects with it, expanding the lookup rect boundary. The intersection is done on a rect bounding the center of the word with slight padding. 

*For each intersecting word, remove it from the list and join it to the words, calculating a center y as the key from the lookup rect.

*Continue until all words have been grouped or there are no longer any more words to group.

*List the center y keys of each group and merge groups that are vertically close.

*Take the reserved punctuation list and find the best group to merge each word with based on the top or bottom y coordinate of that word. A punctuation can either join the group if it intersects at it’s top or bottom (instead of center).

