Time zone shapes compiled for fast, exact point-in-polygon tests.

The shapes in the timezone data are lists of {x, y} tuples holding boxed floats: nine words per vertex, and a point-in-polygon test that walks every vertex of a ring. Some rings have more than 190,000 vertices, yet a horizontal ray through a point can only be crossed by the handful of edges whose vertical extent contains the point. This module compiles each shape so a test visits little more than those edges.

Representation

A compiled shape is {tzid, polygons}, with the polygons in the shape's own order. Each polygon is {outer, holes}, and each ring is packed as:

• the vertical extent and right-hand side of its bounding box, used to reject points whose ray cannot cross it;

• its vertices, as native 64-bit float pairs in a single binary — 16 bytes a vertex rather than 72;

• its edges indexed by the horizontal bands their vertical extent overlaps, in compressed sparse row form: one binary of 32-bit edge indices laid out band by band, and one binary of per-band start offsets.

The number of bands grows with the ring, so each band holds roughly the same number of edges however large the ring is.

Exactness

Results are identical to ray casting over every vertex of the original shapes. The crossing test is the same even-odd rule, applied to the same translated coordinates in the same arithmetic, and vertices round-trip through the binary unchanged. Only work that cannot change the answer is skipped:

• an edge crosses the ray at y only if its vertical extent contains y, and every such edge is placed in y's band, because assigning bands is monotonic in y;

• a ray from a point above, below or to the right of a ring's bounding box crosses none of its edges. Points to the left are left to the ray cast: rejecting them too would rely on the ring being closed.