6

One of the projects I am working on has asked me to assign a code (starting from 1 and counting up) to polygons that represent enumeration areas so the statistician can sample the areas. I have been asked that the assigning of the code uses a serpentine numbering method. The image below shows an example of what I am trying to achieve. You start in the North West part of the area and snake bank and forth assigning numbers.

Example

Now I've searched various sites to see if anyone had developed a tool or even an algorithm that could be implemented that would achieve this. All I have found are numerous powerpoint slides and pdf files that simply say they have used serpentine numbering. I can only assume they have done this manually.

Does anyone know of an existing tool that would take a shapefile and number as described?

It seems to me that someone may have attempted this before but I have not been successful in finding a suitable reference as I don't usually get involved in census type data processing.

6
  • There's already a question/answer out there that addresses this. It involved binning using PostgreSQL and allocating in order by bin. – Vince Jan 9 '16 at 18:28
  • @Vince, please don't make me beg! :) If I type into the search box on GIS SE "serpentine postgresql" I do not find the Q&A you are referring too. Could you please post the link to it? – Hornbydd Jan 9 '16 at 20:31
  • It's hard to find stuff from a phone, so I don't bother. I think a variant on this would work for you... My search was "postgresql order label" . Getting the serpentine would require a modulus for direction across the scanline. – Vince Jan 10 '16 at 3:41
  • I'm starting to think this problem of serpentine numbering can be abstracted away to some sort of "Hamiltonian path". I just need a maths genius to step in? ;) – Hornbydd Jan 11 '16 at 22:29
  • Shouldn't be a big deal. Capture labels with X & Y values. Use Y scanlines of 5-20% of the height. Sort points in each Y row by X, with a modulus of Y row to control direction. Viola. – Vince Jan 11 '16 at 22:40
5

Assume 5 rows with five gridded polygons for each row. Further assume each row of height 1 and each polygon of width 1, with centroids at the physical centers, sequentially named "A" through "Y" in random order:

unordered

The query to grid the cells in this table (ArcGIS 10.2 geodatabase in PostgreSQL with SDE.ST_GEOMETRY) would be:

SELECT floor(sde.ST_MaxY(shape)) as ycell,
       floor(sde.ST_MinX(shape) + sde.ST_MaxX(shape) / 2.0) as xcell,
       objectid
FROM   polytab

And the code to label top-to-bottom, left to right would be:

UPDATE polytab SET seq_order = vtab.rownum
FROM 
(   SELECT row_number()
        over (order by ycell desc, xcell) as rownum, fkey
    FROM 
    (   SELECT floor(sde.ST_MaxY(shape)) as ycell,
               floor(sde.ST_MinX(shape) + sde.ST_MaxX(shape) / 2.0) as xcell,
               objectid as fkey
        FROM   polytab
    ) AS vpoly
) AS vtab
WHERE polytab.objectid = vtab.fkey;

Which would result in:

scanline order

So far, this is the same solution as in the previous question, but now we break new ground: In order to "reverse the polarity" on even scanlines, a modulus function can be used to alter the "xcell" values, based on whether "ycell modulus 2" is one or zero:

UPDATE polytab SET serp_order = vtab.rownum
FROM 
(   SELECT row_number()
        over (order by ycell desc, xcell) as rownum, fkey
    FROM 
    (   SELECT floor(sde.ST_MaxY(shape)) as ycell,
                (floor(sde.ST_MinX(shape) + sde.ST_MaxX(shape) / 2.0) *
            (cast(floor(sde.ST_MaxY(shape)) as integer) % 2) +
                (5 - floor(sde.ST_MinX(shape) + sde.ST_MaxX(shape) / 2.0)) *
            (cast((1 + floor(sde.ST_MaxY(shape))) as integer) % 2)) as xcell,
                objectid as fkey
        FROM   polytab
    ) AS vpoly
) AS vtab
WHERE polytab.objectid = vtab.fkey;

(As you can see, modulus operations must be integer, so the terms start to get unwieldy as a CAST is necessary; also note that the width is hard-coded as "5").

Now the labels are:

serpentine order

Porting this to an application which works with a generic file geodatabase is left as an exercise.

2
  • Wow! Math Guru or database God, how would you like to be acknowledged? :) – Hornbydd Jan 13 '16 at 17:26
  • 't'weren't nothin', really. The only pain was in the CAST syntax and balancing all those parenthesis. – Vince Jan 13 '16 at 17:32

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.