Pick's theorem, checked by counting rather than assumed

\(A = I + B/2 - 1\) for a simple lattice polygon. The three quantities are computed independently – area by integer shoelace, boundary by \(\sum \gcd(|\Delta x|, |\Delta y|)\), interior by testing every lattice point of the bounding box with exact integer ray casting – and the theorem is then CHECKED. A check that derives one side from the other two would be a tautology.

Usage

morie_pick_theorem(
  vertices,
  verify_by_enumeration = TRUE,
  enumeration_cap = 1e+06
)

Arguments

vertices

Two-column matrix of integer (x, y) in traversal order.

verify_by_enumeration

Count interior points directly.

enumeration_cap

Largest bounding box enumerated.

Value

A list with area, twice_area, boundary, interior, interior_enumerated, verified, pick_holds, warnings.

Details

Enumeration over a huge bounding box is refused rather than silently skipped: verified comes back NA with a warning, so a cap never masquerades as a pass. A self-intersecting polygon shows up as a disagreement between the formula and the count, which is the detection, not a defect.

References

Pick G (1899) Lotos 19:311-319.

Examples

D <- data.frame(x = c(1, 2, 3, 4), y = c(2, 4, 5, 9))
morie_pick_theorem(D)
#> $area
#> [1] 2
#> 
#> $twice_area
#> [1] 4
#> 
#> $boundary
#> [1] 4
#> 
#> $interior
#> [1] 1
#> 
#> $interior_enumerated
#> [1] 1
#> 
#> $verified
#> [1] TRUE
#> 
#> $pick_holds
#> [1] TRUE
#> 
#> $estimate
#> [1] 2
#> 
#> $n
#> [1] 4
#> 
#> $warnings
#> character(0)
#> 
#> $method
#> [1] "Pick's theorem (Pick 1899), checked by enumeration"
#>