[geos-devel] RE: Algorithm to label polygons consecutively

[Martin Davis]

> is anybody aware of an algorithm in which a collection of polygon shapes
> (parcels) can be given unique numbers starting at the top, right and in
> such a way that all the numbers are consecutive in geographical space.

I agree with Norman - I don't think it's even possible to determine a labelling with this property in the general case, let alone come up with a reasonable algorithm for it.

How about this as an algorithm to generate a labelling "close" to the desired one?

- Compute a "location point" for each polygon (Not sure what the best point to choose would be - JTS has an algorithm for inside point, or you could use the centroid of the envelope, or you could simply use the uppermost point of the polygon)
- Form the adjacency graph of the coverage
- Assign costs to the edges based on the relative locations of the edge nodes (based on some sort of distance function such the distance between location points)
- Do a depth-first traversal of the graph assigning the labelling, always choosing the minimum cost edge to follow 

The hard part here is forming the adjacency graph, but even that's not that hard if you're willing to do it in a brute-force kind of way.  Simply spatially index the polygons and use the touches predicate to find all neighbours

Martin Davis, Senior Technical Architect
Vivid Solutions Inc.
Suite #1A-2328 Government Street   Victoria, B.C.   V8T 5G5
Phone: (250) 385 6040    Fax: (250) 385 6046
EMail: mbdavis at vividsolutions.com  Web: www.vividsolutions.com


> -----Original Message-----
> From: bartvde at xs4all.nl [mailto:bartvde at xs4all.nl]
> Sent: Friday, August 29, 2003 1:40 AM
> To: geos-devel at geos.refractions.net
> Subject: [geos-devel] searching for the right algorithm
> 
> 
> Hi list,
> 
> is anybody aware of an algorithm in which a collection of 
> polygon shapes
> (parcels) can be given unique numbers starting at the top, 
> right and in
> such a way that all the numbers are consecutive in 
> geographical space. For
> instance the parcel with number 3 must be adjacent to the parcel with
> number 2 and 4 etc.
> 
> Second question, is there an algorithm like this in GEOS?
> 
> Thanks in advance,
> Bart
>