The Sort tool can sort by attributes and spatial characteristics. Once sorted spatially, efficiency of spatial or geometric operations is enhanced.
To sort features spatially (that is, by location), use the Field(s) parameter to specify the input's geometry field (typically named Shape). Using the Shape field enables the Spatial Sort Method parameter. The Spatial Sort Method parameter supports the following sort options: Upper left, Upper right, Lower left, Lower right, and Peano.
Spatial sorting
The Upper left, Upper right, Lower left, and Lower right options scan the features like a plotter or a printer. If the Upper right option is chosen, scanning begins at the upper right corner, selecting the top feature first. Moving from the top down, if two or more features are at the same horizontal line, they are ordered from right to left. The scanning continues downward and leftward until it reaches the opposite (lower left in this case) corner. Features are sorted in the same order (or opposite order if the Descending option is specified) as they are scanned or visited.
The Upper right sorting option can be demonstrated by taking a uniformly distributed set of points as input.
The numbers in the above diagram represent the sorted sequence for the Upper right option. The order is reversed if the Lower left option is specified.
Below is an illustration of how the upper and right components of the sort work together.
The upper component of the spatial sort gets priority over the right component. The right component is taken into consideration only when some features are at the same horizontal level.
Peano spatial sort
The Peano option uses the Peano curve algorithm. The algorithm visits all the locations of a smaller neighborhood, before moving on to the next neighborhood. Thus, nearby locations are closer along the curve (or path). Instead of searching the whole extent, it searches smaller neighborhoods one by one. After finishing a larger area, the search moves to another larger area. It then restarts sorting from a smaller neighborhood within that bigger area.
In the above diagram, arrows indicate the scanning sequence. The algorithm scans each of the four rectangular neighborhoods separately. If the area were larger, the search would continue for another set of neighborhoods, and so on. If the points were more dense, it would search a much smaller neighborhood.
The following are advantages of a space-filling algorithm:
- It is fast.
- It does not require calculating distances between locations.
- It is parallelizable.
The algorithm has applications in solving the traveling salesperson problem, building a routing system, and controlling a pen-plotter for drawing maps.