From time to time I have to produce mapbook to show points of interest. First step to create pages, using regular mesh:

enter image description here

I don't like the solution because a) there are some pages with single points (e.g. page 25) sitting on the edge and b) too many pages.

First issue is easy to fix using code, - move rectangle of page extent to center of relevant points extent:

enter image description here

I still don't like it, it looks very crowded because number of pages remains the same. Remember, they all end up being actual A3 paper pages in multiple copies of report !.

So I've cooked a code that reduce number of pages. In this example from 45 to 34.

enter image description here

I am not sure if this the best result that can be achieved,

What is the best strategy (pseudo code, publication, Python library) to shuffle through points in order to minimise number of given size rectangles to capture all of the points? Surely, someone discovered it in game theory, military art or fishing industry

This is update to original question:

This shows real extent and page size required:

enter image description here

Closer zoom showing 10 out of 164 pages:

enter image description here

Sample Point Feature Class

Rectangle size can change as soon as it stays within the limits, i.e. smaller is fine.

  • 2
    In my opinion the regular mesh is the best option. Map readers are expecting something like that because they are used to it. The other options are crowded and, in my opinion, confusing. There are certainly optimising algorithms that will do what you want, but I don't think your audience will appreciate them. +1 though because I appreciate what you are trying to do. Finally, one way to reduce the number of pages is to change the scale. – Fezter Jul 19 '15 at 10:01
  • I mostly agree with Fezter. There are cases where a non-continuous map book has its place and I'll be interested to see answers (even your current code if you want to share). For example a book of trails where you want each trail on its own map and don't care about showing the others (though you might still want a smaller scale single map showing them all in relative position). Just looking at your example images I think in this case you would want a continuous coverage between pages, even if it means extras, unless the points have an inherent grouping property. – Chris W Jul 19 '15 at 18:55
  • @Fezter, regular mesh works when page size is comparable to total extent, both this and scale change aren't the case here – FelixIP Jul 19 '15 at 21:02
  • 1
    @MichaelMiles-Stimson, what I've done using Avenue is doable in Python. Used former because in geometry games former is still superior. Pick point, find nearest manhattan distance neighbour, create multipoint, get extent. Quit if over extent. Removed grouped from original list, proceed with remaining. I thought the sorting order important, tried to change. Very little difference... – FelixIP Jul 20 '15 at 6:43
  • 1
    Yes it's doable in python with significant effort. When dealing with geometries I prefer ArcObjects in C#. As Chris said they already look fairly minimal why not stick with what you've got and call it done. – Michael Stimson Jul 20 '15 at 21:45

This is not the answer, I just thought I post Python solution for those who interested:

# ---------------------------------------------------------------------------
# ---------------------------------------------------------------------------
# Import arcpy module
import arcpy, traceback, os, sys
from arcpy import env


    def showPyMessage():
            arcpy.AddMessage(str(time.ctime()) + " - " + message)
    mxd = arcpy.mapping.MapDocument("CURRENT")
    points = arcpy.mapping.ListLayers(mxd,"points")[0]
    pgons = arcpy.mapping.ListLayers(mxd,"pages")[0]

    geometryList=[p.firstPoint for p in geometryList]
    curT = arcpy.da.InsertCursor(pgons,"SHAPE@")
    while True:
        for p in geometryList:
            if cHeight>height or cWidth>width:
        LL=arcpy.Point (xC-width/2,yC-height/2)
        UL=arcpy.Point (xC-width/2,yC+height/2)
        UR=arcpy.Point (xC+width/2,yC+height/2)
        LR=arcpy.Point (xC+width/2,yC-height/2)
        short=filter(lambda x: x not in small,geometryList)
        arcpy.AddMessage('Grabbed %i points, %i to go' %(len(small),len(short)))
        if len(short)==0: break
    del mxd
    message = "\n*** PYTHON ERRORS *** "; showPyMessage()
    message = "Python Traceback Info: " + traceback.format_tb(sys.exc_info()[2])[0]; showPyMessage()
    message = "Python Error Info: " +  str(sys.exc_type)+ ": " + str(sys.exc_value) + "\n"; showPyMessage()

applied it lately for survey planning:

enter image description here


It seems that for some patterns dealing with ‘stray’ points first is the way to go. I’ve used ‘convex hull’ peel to identify them, idea of whuber, can’t find post, sorry.

enter image description here

  • Is this the post by @whuber that you were looking for? gis.stackexchange.com/a/161855/115 – PolyGeo Feb 7 '17 at 7:17
  • Yes it is. I used to to sort points before "hunt" start. I'll update my own answer tomorrow. Not easy without desktop – FelixIP Feb 7 '17 at 7:20

This looks like a geometric version of the Maximum Coverage Problem which is closely related to the Set Cover Problem, and those two are NP-Complete.

So to solve it, one could use approximation. I would try the following algorithm and it seems to work perfectly. Although due to the complexity of problem, we cannot find the best answer.

  1. Foreach point generate N=10 rectangles in random distances; just to make sure the rectangle covers the point (each rectangle has at least one point belongs to it and each point belongs to at least one rectangle)
  2. Repeat until all points are covered: get rectangle covering max number of uncovered points. Mark points as covered.

an implementation of this algorithm, only for circle, is here: http://jsfiddle.net/nwvao72r/3/

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.