Reference

std/geometry/polygon

std/geometry/src/polygon.trb

Polygon, a closed chain of corners in the plane, with the convex tests written first: a convex polygon is what a collision narrow phase, a view frustum in the plane and a navigation cell all are.

type Polygon

type Polygon<Scalar: Numeric = Float>

A closed chain of corners: the last one is joined back to the first, and there is no repeated corner at the end.

The convex tests - Polygon.containsConvex and Polygon.intersectsConvex - are the ones to reach for, and they are the ones a program can guarantee cheaply with Polygon.isConvex. Polygon.contains works for any polygon, including one with a dent, and costs a walk over every edge.

Examples

const square = Polygon([Vector2(0, 0), Vector2(4, 0), Vector2(4, 4), Vector2(0, 4)])
print "{square.isConvex()} {square.contains(Vector2(2, 2))}"

Pitfalls

  • Fewer than three corners describe no area, and every test answers false for such a polygon rather than panicking.
  • Polygon.contains divides, and over a whole-number scalar that division truncates: where an edge crosses the test line between two cells, the crossing is counted at the cell below it. Polygon.containsConvex multiplies only and is exact for every scalar, which is one more reason to establish convexity once.
  • Polygon.containsConvex answers nonsense for a polygon that is not convex, and it does not check. That is the whole point of it: the caller has already established convexity, once, instead of per query.

Open

  • There is no triangulation and no convex decomposition here. Both are algorithms rather than geometry, they want a scratch buffer, and a mesh library is where they earn their place.

Related

field corners

corners: List<Vector2<Scalar>>

The corners, in order. The last one is joined back to the first.

fn ofTriangle

static fn ofTriangle(triangle: Triangle2<Scalar>): Polygon<Scalar>

The polygon of a triangle's three corners.

fn ofRectangle

static fn ofRectangle(rectangle: Rectangle<Scalar>): Polygon<Scalar>

The polygon of a rectangle's four corners, running from the first axis towards the second.

fn isEmpty

fn isEmpty(): Bool

Whether the chain describes no area at all, which is the case below three corners.

fn edges

fn edges(): List<Segment2<Scalar>>

The edges, in the order the corners are written, with the closing edge last.

fn signedDoubledArea

fn signedDoubledArea(): Scalar

Twice the area, with a sign that says which way the corners run. This is the shoelace sum.

fn bounds

fn bounds(): Rectangle<Scalar>

The smallest rectangle that holds the polygon. Empty where there are no corners.

fn isConvex

fn isConvex(): Bool

Whether every turn goes the same way, which is what makes the cheap tests correct. A polygon with fewer than three corners is not convex.

fn containsConvex

fn containsConvex(point: Vector2<Scalar>): Bool

Whether the point is inside, for a polygon that is convex: it is inside where it is on the same side of every edge. An edge counts as inside.

Nothing checks that the polygon is convex; Polygon.isConvex is what a caller establishes once.

fn contains

fn contains(point: Vector2<Scalar>): Bool

Whether the point is inside, for any polygon: the crossing count of a ray towards the first axis, which is odd exactly inside.

A point exactly on an edge may come out either way, which is what a crossing count answers for one.

fn intersectsConvex

fn intersectsConvex(other: Polygon<Scalar>): Bool

Whether the two convex polygons share a point, by the separating axis test: two convex shapes miss each other exactly where some edge normal of one of them has all of one on one side and all of the other on the other.

fn translated

fn translated(by: Vector2<Scalar>): Polygon<Scalar>

The same polygon moved.

extend Polygon<Scalar>

extend<Scalar: Signed> Polygon<Scalar>

What a sign buys: the area without its sign.

fn doubledArea

fn doubledArea(): Scalar

Twice the area, without a sign.

extend Polygon<Scalar>

extend<Scalar: Real> Polygon<Scalar>

What a halving buys: the area itself.

fn area

fn area(): Scalar

How much of the plane the polygon covers.