# `TzWorld.PackedGeometry`
[🔗](https://github.com/kipcole9/tz_world/blob/v2.5.0/lib/tz_world/packed_geometry.ex#L1)

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.

# `polygon`

```elixir
@type polygon() :: {ring(), [ring()]}
```

A compiled polygon: its outer ring and any holes.

# `ring`

```elixir
@type ring() ::
  {number(), number(), number(), float(), pos_integer(), binary(), binary(),
   binary()}
```

A compiled ring: bounds, band scaling, and three binaries.

# `compile`

```elixir
@spec compile(Geo.MultiPolygon.t() | Geo.Polygon.t()) :: {String.t(), [polygon()]}
```

Compiles a time zone shape.

### Arguments

* `shape` is a `Geo.MultiPolygon` or `Geo.Polygon` whose properties carry the
  `:tzid`.

### Returns

* `{tzid, polygons}`, with the polygons in the same order as the shape's.

### Examples

    iex> square = %Geo.Polygon{
    ...>   coordinates: [[{0.0, 0.0}, {4.0, 0.0}, {4.0, 4.0}, {0.0, 4.0}, {0.0, 0.0}]],
    ...>   properties: %{tzid: "Etc/Square"}
    ...> }
    iex> {tzid, [{_outer, holes}]} = TzWorld.PackedGeometry.compile(square)
    iex> {tzid, holes}
    {"Etc/Square", []}

# `contains?`

```elixir
@spec contains?([polygon()], number(), number()) :: boolean()
```

Returns whether any of a compiled shape's polygons contains a point.

A polygon contains the point when its outer ring does and none of its holes
do. Polygons are tried in order and the first to contain the point ends the
search.

### Arguments

* `polygons` is the polygon list of a compiled shape.

* `x` and `y` are the point's longitude and latitude.

### Returns

* `true` or `false`.

### Examples

    iex> square_with_hole = %Geo.Polygon{
    ...>   coordinates: [
    ...>     [{0.0, 0.0}, {4.0, 0.0}, {4.0, 4.0}, {0.0, 4.0}, {0.0, 0.0}],
    ...>     [{1.0, 1.0}, {2.0, 1.0}, {2.0, 2.0}, {1.0, 2.0}, {1.0, 1.0}]
    ...>   ],
    ...>   properties: %{tzid: "Etc/Square"}
    ...> }
    iex> {_tzid, polygons} = TzWorld.PackedGeometry.compile(square_with_hole)
    iex> TzWorld.PackedGeometry.contains?(polygons, 3.0, 3.0)
    true
    iex> TzWorld.PackedGeometry.contains?(polygons, 1.5, 1.5)
    false

---

*Consult [api-reference.md](api-reference.md) for complete listing*