Redefining Line Maximization

The process of line maximization, reducing overlapping lines in a design into the fewest maximal lines possible, is critical to the embed-fuse cycle implemented in a shape grammar interpreter. The choice of how to represent maximal lines internally within a shape grammar interpreter influences how line maximization is performed computationally. A common strategy in existing interpreters, representing maximal lines by their endpoints, is critiqued, and a new representation that enables simpler and faster computation is devised. An implementation of line maximization using the new representation is compared to the endpoint-based implementation in Shape Machine for Rhino, a general purpose 2D shape grammar interpreter, for correctness and efficiency.