Optimal map printing algorithm

Question

I do the occasional long distance hike and often require printing 10+ A3 maps.

I'm trying to find an algorithmic solution to the manual process of printing off multiple maps of a route.

The manual process is often non-optimal, in which I mean pages should be kept to a minimum. Eg. Extra pages are added, where as if I had moved previous pages over slightly here and there it would have encompassed the route in fewer pages.

To complicate things printing can be done in both portrait and landscape modes.

Id really appreciate a push in the right direction. Is there a simple solution or does it require some more elaborate thinking?

To clarify: Given a list of 2d points, find the minimum amount of boxes they will fit in. With the boxes being either wh (portrait) or hw (landscape). Also the maps cannot be rescaled.

Answer 1

A modified K-means clustering algorithm solves this problem almost optimally.

• Loop until all route coordinates are covered by a clusters page
  • Add a new cluster. Starting position is selected as a random coordinate not currently covered by any clusters page
  • Iterate x times
    • Assign route coordinates to the nearest clusters centroid
    • Calculate centroid as the middle of its range (midrange) of assigned coordinates
    • Choose orientation that fits the most uncovered coordinates

Source: https://github.com/DM-UK/PageFit

Using the midrange for calculating the centroids position, instead of a mean average led to fitting in fewer pages.

I can only describe this behavior as: clusters using the mean would get 'stuck', where as using midrange would 'spread' into space along the whole path.