# Numbering polygons according to their spatial relationships?

I have, for example, this layer in postgresql (polygons):

``````table : poly (objectid: integer, num: integer, shape: geometry)
`````` I want to enumerate the polygons from left to right and top to bottom like this: I am working with Vb.net, ArcEngine, PostgreSQL, and ArcSDE.

### Solution that I proposed

I think to create grid lines (red layer; see picture) and iterate it, then verify intersection and finally enumerate the polygons. Will this work? • Did you try sorting the centroid coordinates by Y, X descending? BTW, ArcGIS has a Sort tool that will sort the geometry as you describe. – klewis Oct 10 '13 at 13:11
• A naïve sort on Y, X will be the same as just sorting on Y as no two are likely to have exactly the same centroid Y. – Russell at ISC Oct 10 '13 at 13:51
• The illustrated numbering has an ad hoc look to it: it appears to be based on some compromise between the desire to create numbered bands (from top to bottom) where each band consists of a strip of contiguous polygons proceeding very roughly from left to right. A clearer description of the criteria used to determine this numbering would help inspire good answers. – whuber Oct 10 '13 at 16:27
• The illustrated numbering seems to be based on a quite arbitrary contiguity. In fact, proceeding from N to S and then from E to W (like it seems to be), I'm wondering for instance why your 3 (or 7) is not 2. IMHO, there's not a clear and robust workflow which answers to this question, but only debatable proof of concepts! – Antonio Falciano Oct 11 '13 at 8:18

## 3 Answers

If you create an ancillary table with the attributes (fkey,xcell,ycell), populated from the objectid and a gridding of the maximum Y coordinate (or centroid coordinate or upper-center envelope coordinate), then you could use SQL to update the table, with something like:

``````    UPDATE poly SET num = vtab.rownum
FROM
(   SELECT row_number() over (order by ycell desc, xcell) as rownum, fkey
FROM ancillary_tab
) AS vtab
WHERE poly.objectid = vtab.fkey;
``````

(The UPDATE syntax is different from RDBMS to RDBMS, and PostgreSQL doesn't have the ROWNUM reserved word of ORACLE, but the moral equivalent would work in other databases.)

You didn't specify the cell size, but if it's just 1 degree, then a floor() math function would work. The more generic formula would be:

``````     cell = floor(coord / cellsize)
``````

[Updated for gridding algorithm]

UPDATE: Thinking about it, you don't even need an ancillary table. I had to stand up a new database for this to prototype it, but after loading a similar dataset in PG 9.1.9 with ArcSDE 10.1sp1, this query:

``````UPDATE poly SET num = 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   poly
) AS vpoly
) AS vtab
WHERE poly.objectid = vtab.fkey;
``````

Turned this: Into this: • This will effectively just order on yval alone since it will be very rare for two shapes to have exactly the same yval. – Russell at ISC Oct 10 '13 at 13:49
• @Russel Yes, of course, but that's the intent, so it's fine. – Vince Oct 10 '13 at 14:25
• That's not what the poster asked for. He wants bands from N to S numbered from east to west. – Russell at ISC Oct 10 '13 at 14:33
• So populate the yval and xval values with floor({x/y}coord /scalefactor) * scalefactor and it's gridded. – Vince Oct 10 '13 at 14:50
• Yes, that works! – Russell at ISC Oct 10 '13 at 14:55

Using GDAL >= 1.10.0 compiled with SQLite and SpatiaLite, it's quite simple.

Suppose we want to order the labels from left to right. Firstly, we have to calculate the distance of each feature from a common reference on the left of all geometries (e.g. -180th meridian) and then order the geometries by distance.

``````ogr2ogr FRA_adm1_temp.shp FRA_adm1.shp -dialect sqlite -sql "SELECT *, ST_Distance(geometry, GeomFromText('LINESTRING(-180 90, -180 -90)')) AS DIST FROM FRA_adm1 ORDER BY DIST"
``````

Finally, simply update the table adding a LABEL column with autoincremental numbers:

``````ogr2ogr FRA_adm1_label.shp FRA_adm1_temp.shp -sql "SELECT FID+1 AS LABEL, * FROM FRA_adm1_temp"
``````

This approach can be used also in PostgreSQL. • That's fine for ordering on only one dimension but will break down on two dimensions because it's unlikely any two have exactly the same value in the first dimension. – Russell at ISC Oct 10 '13 at 13:48
• Why? ST_Distance() returns the 2-dimensional Cartesian minimum distance between two geometries, so the LINESTRING used as reference can be oriented in a whatever direction. – Antonio Falciano Oct 10 '13 at 13:53
• With a LINESTRING as in the query shown, the sort would be exactly the same as just sorting on min Y. Using the North pole as a point would work, but only in geographic coordinates and geodesic computations. Using projected data or treating lat/lon as raw numbers rather than using a geodetic approach would produce numbering in arcs rather than bands. – Russell at ISC Oct 10 '13 at 14:04
• Actually, even with the N pole and geodesic, you wouldn't get east-west bands 2,3,4... 2,3, and 4 would all be at similar latitudes but the order would be arbitrary. – Russell at ISC Oct 10 '13 at 14:06

Since it's unlikely that any two polygons have exactly the same northmost extent, you will need some compromise to order by both north-to-south and east-to-west.

Personally, I'd use either bounding boxes (looking at first maxY, then minX) or centroids (looking at first y, then x). I'd decide how much tolerance I'd allow and still consider y values to be approximately equal. Then I would collect sets from northmost to southmost (descending y ranges), arrange each set by ascending x values, and number across the sets. Ideal tolerance would probably need to be determined by trial and error.

This is very like a grid approach but probably simpler.

Note that I can't see latitude lines in your drawing but I assume not curved since your grid is not curved. I think both my approach and your grid approach would put 7 in the same set with 2-6, and 7 would be numbered 2.

A centroid approach might group 2,3, and 7 in one group, 4-6 and 9 in another. Bounding box might put 2-5 and 7 in one, 12, 9 and 6 in another.