[geos-devel] searching for the right algorithm

Norman Vine nhv at cape.com
Fri Aug 29 06:52:04 EDT 2003

bartvde at xs4all.nl writes:
> 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.

Sorry I don't know of an algorithm for this. My guess is computing the
vornoi diagram of the polygon centroids and then walking in the desired 
direction, being careful not to isolate any cell(s) from the ordering scheme,
using the current cell's edge neighbors list for the 'next' candidates should
lead to an approximation of what you are looking for. 

FWIW It is provable that for the general polygon case what you are asking
for is impossible.  i.e. a single parcel whose extent is greater then the height
of your area of interest is a simple case in point.



More information about the geos-devel mailing list