2D Geometry

LatticePoint{T <: Integer}

A lattice point in two-dimensional space. This is an alias for SVector{2, T}.

RationalPoint{T<:Integer}

A rational point in two-dimensional space. This is an alias for SVector{2, Rational{T}}.

Point{T<:Integer}

The union of LatticePoint and RationalPoint.

is_k_rational(k :: T, p :: Point{T}) where {T <: Integer}

Checks whether a point p is k-rational, i.e. its coordinates have denominator at most k.

is_integral(p :: Point{T}) where {T <: Integer}

Checks whether a point p is integral.

rationality(p :: Point)

The smallest integer r such that r*p is integral.

Example

julia> rationality(RationalPoint(1//2,1//3))
6

is_primitive(p :: Point)

Checks whether a point is primitive, i.e. is integral and its coordinates are coprime.

norm(p :: Point{T})

Return the square of the euclidian norm of p.

Example

julia> norm(RationalPoint(4//3,2//3))
20//9

distance(p :: Point{T}, q :: Point{T})

Return the square of the euclidian distance between p and q.

pseudo_angle(p :: Point{T}) where {T <: Integer}

A quick implementation of a pseudo_angle of two-dimensional vectors. It returns values in the half-open interval (-2,2].

Example

julia> pseudo_angle(LatticePoint(1,1))
1//2

pseudo_angle(H :: AffineHalfplane{T}) where {T <: Integer}

Return the pseudo angle of the normal vector of H.

graham_scan!(points :: Vector{<:Point{T}}) where {T <: Integer}

Perform a graham scan on the given points, removing all points that are not vertices of their convex hull.

Example

julia> points = LatticePoint{Int}[(0,0),(1,0),(1,1),(0,1),(-1,1),(0,-1),(-1,-1),(0,-1)];

julia> graham_scan!(points)
5-element Vector{StaticArraysCore.SVector{2, Int64}}:
 [-1, -1]
 [0, -1]
 [1, 0]
 [1, 1]
 [-1, 1]

graham_scan(points :: Vector{<:Point{T}}) where {T <: Integer}

A non-modifying version of graham_scan!.

Line{T <: Integer}

A line in 2-dimensional rational space. It has two fields: base_point :: RationalPoint{T} and direction_vector :: RationalPoint{T}.

base_point(L :: Line{T}) where {T <: Integer}

Return a point on the line L.

base_point(H :: AffineHalfplane{T}) where {T <: Integer}

Return a point on the line associated to H.

direction_vector(L :: Line{T}) where {T <: Integer}

Return the direction vector of L.

direction_vector(H :: AffineHalfplane{T}) where {T <: Integer}

Return the direction vector of the line associated to H.

line_through_points(A :: Point{T}, B :: Point{T}) where {T <: Integer}

Return the line going through the points A and B.

horizontal_line(y :: Union{T, Rational{T}}) where {T <: Integer}

Return the horizontal line at y.

vertical_line(x :: Union{T, Rational{T}}) where {T <: Integer}

Return the vertical line at x.

Base.in(x :: Point{T}, L :: Line{T}) where {T <: Integer}

Check whether a point x lies on a line L.

Example

julia> RationalPoint(3//2,1) ∈ line_through_points(Point(1,0),Point(2,2))
true

normal_vector(L :: Line{T}) where {T <: Integer}

Return a primitive vector orthogonal to the direction vector of L.

Example

julia> normal_vector(line_through_points(Point(1,0),Point(2,2)))
2-element StaticArraysCore.SVector{2, Int64} with indices SOneTo(2):
 -2
  1

IntersectionBehaviour{T <: Integer}

An abstract supertype for possible intersection behaviours of two lines. There are the three subtypes IntersectInPoint, NoIntersection and LinesAreEqual.

IntersectInPoint{T <: Integer}

The intersection behaviour of two lines intersecting in a unique point. This struct has a single field p, which is the intersection point.

NoIntersection{T <: Integer}

The intersection behaviour of parallel lines.

LinesAreEqual{T <: Integer}

The intersection behaviour of two equal lines.

intersection_behaviour(L1 :: Line{T}, L2 :: Line{T}) where {T <: Integer}

Given two lines in 2D rational space, return the intersection behaviour of the two lines: Possible values are LinesAreEqual(), NoIntersection() and IntersectInPoint(p) where p is the unique intersection point.

intersection_point(L1 :: Line{T}, L2 :: Line{T}) where {T <: RationalUnion}

Return the intersection point of two lines in 2D rational space. Throws an error if the lines do not intersect uniquely.

AffineHalfplane{T <: Integer}

An affine halfplane in two-dimensional rational space. It has two fields normal_vector :: RationalPoint{T} and translation :: Rational{T}.

affine_halfplane(nv :: Point{T}, b :: Union{T, Rational{T}}) where {T <: Integer}

Return the affine halfplane given by the equation nv[1] * x[1] + nv[2] * x[2] ≥ b.

Example

julia> affine_halfplane(Point(-2,1),1)
Affine halfplane given by -2//1 x + 1//1 y ≥ 1//1

affine_halfplane(L :: Line{T}) where {T <: Integer}

Return the affine halfplane associated to a line in 2D space. The halfplane is understood to consist of those points to the left of the line L, looking in the direction given by direction_vector(L).

affine_halfplane(p :: Point{T}, q :: Point{T}) where {T <: Integer}

Return the affine halfplane associated to the line going through the points p and q.

affine_halfplane(P :: RationalPolygon, i :: Int)

Return the i-th describing halfplane of P.

normal_vector(H :: AffineHalfplane{T}) where {T <: Integer}

Return the normal vector of the H.

translation(H :: AffineHalfplane{T}) where {T <: Integer}

Return the affine translation of H.

Base.in(x :: Point{T}, H :: AffineHalfplane{T}) where {T <: Integer}

Check whether a point x lies in the halfplane H.

Example

julia> Point(0,1) ∈ affine_halfplane(Point(-2,1),1)
true

contains_in_interior(x :: Point{T}, H :: AffineHalfplane{T}) where {T <: Integer}

Check whether a point x lies in the interior of H.

Example

julia> contains_in_interior(Point(0,1), affine_halfplane(Point(-2,1),1))
false

Base.issubset(H1 :: AffineHalfplane{T}, H2 :: AffineHalfplane{T}) where {T <: Integer}

Check whether H1 is a subset of H2.

line(H :: AffineHalfplane{T}) where {T <: Integer}

Return the line associated to H.