0

0

0

1

# SeparatingAxisTheorem2D.jl

This package implements collision detection for 2D shapes based on the separating axis theorem. Shape representations leverage StaticArrays.jl for computational efficiency; this package targets applications potentially requiring millions of collision checks, e.g., robot motion planning.

## Shapes

This package exports the abstract type `Shape2D` and the following concrete types for collision checking:

• `Point` (alias for `AbstractVector{<:Number}`)
• `AxisAlignedBoundingBox <: Shape2D` (equivalently, `AABB`)
• `AABB((xl, xu), (yl, yu))`: constructs an instance corresponding to the set [`xl`, `xu`] × [`yl`, `yu`].
• `AABB(Δx, Δy)`: constructs an instance corresponding to the set [-`Δx/2`, `Δx/2`] × [-`Δy/2`, `Δy/2`].
• `LineSegment <: Shape2D`
• `LineSegment(v, w)` constructs a line segment connecting `v` and `w`.
• `Polygon <: Shape2D`
• `Polygon(points...)`: constructs a convex polygon with vertices `points`. `points` must be supplied in counter-clockwise order.
• `Triangle(p1, p2, p3)`: convenience constructor that reorders three points into CCW order before calling `Polygon`.
• `Circle <: Shape2D`
• `Circle(c, r)`: constructs a circle centered at `c` with radius `r`.
• `Circle(r)`: constructs a circle centered at the origin with radius `r`.
• `CompoundShape <: Shape2D`
• `CompoundShape(parts...)`: groups a list of other `Shape2D`s into a single (possible non-convex) collision object.

This package also exports a few methods for transforming/creating new shapes from others.

• `Transformation`s from CoordinateTranformations.jl may be applied to shapes to produce the expected output; some care must be taken, however, to ensure that only rigid transformations are applied to `Circle`s as there is currently no `Ellipse` shape implemented.
• `inflate(X, ε; round_corners=true)`: inflates a shape `X` by a buffer `ε` > 0. The `round_corners` keyword argument may be set to `false` to ensure that inflating an `AABB`, `LineSegment`, or `Polygon` yields just a single `Polygon` (performing an approximate inflation) instead of a `CompoundShape` consisting of a `Polygon` and `Circle`s.
• `sweep`: this function is used internally to facilitate continuous (i.e., "swept") collision detection.
• `sweep(X1, X2)`: yields a shape corresponding to the area swept out by moving shape `X1` to shape `X2` (if sweeping `X1` to `X2` involves a rotation, this rotation should be "reasonably small" or this will probably produce junk).
• `sweep(X, f1, f2)`: equivalent to `sweep(f1(X), f2(X))`.

## Collision Checking

SeparatingAxisTheorem2D.jl defines the following functions for collision checking:

• `intersecting` for discrete collision detection.
• `intersecting(X, Y)`: true iff `X` and `Y` are in collision.
• `intersecting(X, Y, f)`: true iff `X` and `f(Y)` are in collision.
• `sweep_intersecting` for continuous collision detection.
• `X` static and `Y` dynamic
• `sweep_intersecting(X, Y1, Y2)`: true iff `X` and `sweep(Y1, Y2)` are in collision.
• `sweep_intersecting(X, Y, f1, f2)`: true iff `X1` and `sweep(f1(X), f2(X))` are in collision.
• `X` and `Y` both dynamic
• `sweep_intersecting(X, fX1, fX2, Y, fY1, fY2)`: supposing that `X` is getting swept from transformation `fX1` to `fX2` and `Y` is simultaneously getting swept from transformation `fY1` to `fY2`, returns true iff the shapes are ever in collision.

10/10/2018

5 months ago

9 commits