Nim-ACL

Polygon

polygon provides basic operations on two-dimensional polygons.

It supports convexity checks, convex hulls, point containment, area, and diameter of a convex polygon.

Import

import atcoder/extra/geometry/geometry_template
import atcoder/extra/geometry/polygon

Polygon

type Polygon[Real] = seq[Point[Real]]

A polygon is represented as a sequence of points.

area

import atcoder/extra/geometry/geometry_template
import atcoder/extra/geometry/polygon

let square: Polygon[float] = @[
  initPoint[float](0.0, 0.0),
  initPoint[float](2.0, 0.0),
  initPoint[float](2.0, 2.0),
  initPoint[float](0.0, 2.0),
]

doAssert area(square) == 4.0

area(p) returns the signed area. It is positive for counterclockwise order and negative for clockwise order.

contains

contains(poly, point)

Returns whether a point is inside, on the boundary of, or outside the polygon.

The return value is State:

doAssert contains(square, initPoint[float](1.0, 1.0)) == State.IN
doAssert contains(square, initPoint[float](2.0, 1.0)) == State.ON
doAssert contains(square, initPoint[float](3.0, 1.0)) == State.OUT

convexHull

let h = convexHull(points)

Returns the convex hull of a point set.

let points: Polygon[float] = @[
  initPoint[float](0.0, 0.0),
  initPoint[float](2.0, 0.0),
  initPoint[float](2.0, 2.0),
  initPoint[float](0.0, 2.0),
  initPoint[float](1.0, 1.0),
]

let h = convexHull(points)

doAssert h.len == 4

isConvex

isConvex(poly)

Returns true if the polygon is convex.

convex_diameter

convex_diameter(poly)

Returns the diameter of a convex polygon: the maximum distance between two vertices.

Complexity