WHIRLPOOL: an example of spatial searching data structures

Choice of data structure must serve the purpose of the algorithm. Careful desing can imporve performance significantly. Polygon overlay is one such application, though a rather complex one for an introductory class...

WHIRLPOOL was the core engine of ODYSSEY, a predecessor of Arc...

This lecture is based on the WHIRLPOOL program, written during 1977-1979 at Harvard Lab for Computer Graphics. A paper on this subject was presented at Spatial Data Handling in Charleston SC 1992. .pdf version available, for fair use instructional purposes only, copyright by International Geographical Union. Lecture based on slides presented at Charleston.

Pseudo code for HADES / CIRCE

appropriate initialization (set epsilon, open Red and Blue files - sorted chains)

Procedure SOUSA [the band manager]

preload keys (Y min) from both files (large value if not present)
REPEAT until (both files exhausted)

select lower of two keys, set Y level (SCUM := key - epsilon)
request CIRCE processor SPIN to clear clusters below SCUM
create "New chain"
invoke HADES (New chain)
reload key for file that contributed new chain

SPIN (big number) [to purge last chains]

Procedure HADES (Input.chain)

set intersection records to null; create temporary "entry" for chain; set X min
locate chain whose Xmin is the largest less than Input_chain.Xmax+epsilon
REPEAT until Xmin < Input_chain.Xmin - epsilon - Xlong

IF (chain windows overlap) SHADES (old.chain, Input.chain, tree)
next chain by walking tree structure

FOR each chain in LongList

IF (chain windows overlap) SHADES (old.chain,Input.chain, LongList)
next chain by walking list structure

SHADES (Input.chain, self, new)
FOR each remaining intersection record

construct pseudo "chain" for points introduced along old chains
perform all above steps as if this were an input chain

Procedure SHADES (old.chain, new.chain, flag) [flag values: tree, long, new]

if (flag NOT EQUAL new)

INTERS (old.chain, new.chain, CROSS)
if (no intersection records generated) EXIT

BLDSRT
HYDRA [chops the input chain into the new chains generated]
CHARON [ushers these new chains into the underworld - queues them to be inserted]
TWIST [inform CIRCE of new chain ends to manage (or new location of old data)]

Specific data structures featured

usage of Shell's sort in the congruence processor
HEAP structure as alternative to sorting when only lowest element needed

Hash table for spatial lookup (expecting to find few of the records requested)

Tree for cross-band sorted list; basic message: avoiding intersection checks

Indirect "handles" for everything, designed for dynamic memory

Overlay with a tolerance:

Fuzzy definition of intersections

points within tolerance must be coallesced; points should never move more than the tolerance

Congruence of lines (caused by moving points)

Fuzzy Creep: in the ESRI implementation, some points can move more than once, potentially limitless, producing all kinds of damage