2D Geometry
We provide basic functionality for two-dimensional geometry over the rational numbers. This includes distances and angles, Graham scan for computing the convex hull, intersection of lines, and affine halfplanes.
Points
In RationalPolygons.jl, we represent points as static vectors of length two. As the name suggests, these are statically sized, which leads to improved performance and memory management for many common operations. We provide three type aliases LatticePoint, RationalPoint, and Point, the latter being the union of the previous two. Note that everything is stated for an arbitrary subtype T <: Integer, e.g. fixed size machine integers like Int64, or unbounded integer types like BigInt.
RationalPolygons.LatticePoint — TypeLatticePoint{T <: Integer}A lattice point in two-dimensional space. This is an alias for SVector{2, T}.
RationalPolygons.RationalPoint — TypeRationalPoint{T<:Integer}A rational point in two-dimensional space. This is an alias for SVector{2, Rational{T}}.
RationalPolygons.Point — TypePoint{T<:Integer}The union of LatticePoint and RationalPoint.
RationalPolygons.is_k_rational — Methodis_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.
RationalPolygons.is_integral — Functionis_integral(p :: Point{T}) where {T <: Integer}Checks whether a point p is integral.
Base.denominator — Methoddenominator(p :: Point)The smallest integer r such that r*p is integral.
Example
julia> denominator(RationalPoint(1//2,1//3))
6RationalPolygons.is_primitive — Methodis_primitive(p :: Point)Checks whether a point is primitive, i.e. is integral and its coordinates are coprime.
RationalPolygons.multiplicity — Methodmultiplicity(p :: Point)The unique rational number x such that x*p is primitive and integral.
Example
julia> multiplicity(RationalPoint(4//3,2//3))
3//2RationalPolygons.primitivize — Methodprimitivize(p :: Point)Return the unique primitive lattice point on the ray spanned by p.
Example
julia> primitivize(RationalPoint(4//3,2//3))
2-element StaticArraysCore.SVector{2, Int64} with indices SOneTo(2):
2
1RationalPolygons.norm — Functionnorm(p :: Point{T})Return the square of the euclidean norm of p.
Example
julia> norm(RationalPoint(4//3,2//3))
20//9RationalPolygons.distance — Functiondistance(p :: Point{T}, q :: Point{T})Return the square of the euclidean distance between p and q.
RationalPolygons.pseudo_angle — Methodpseudo_angle(p :: Point{T}) where {T <: Integer}Returns a value in the half-open interval $(-2,2]$. A pseudo angle allows comparing vectors by angle, but is faster to compute than the euclidean angle.
Example
julia> pseudo_angle(LatticePoint(1,1))
1//2Graham scan
The Graham scan is a planar convex hull algorithm named after Ronald Graham [1]. With an asymptotic running time of $O(n \cdot \mathrm{log}(n))$, it is a lot quicker than algorithms that work in arbitrary dimension.
RationalPolygons.graham_scan! — Functiongraham_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 and ordering them counterclockwise.
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]RationalPolygons.graham_scan — Functiongraham_scan(points :: Vector{<:Point{T}}) where {T <: Integer}A non-modifying version of graham_scan!.
Lines
We provide basic functionality for lines in the two-dimensional rational plane. A line is encoded as a simple struct consisting of a base point and a direction vector. Two lines can be intersected to produce a value of type IntersectionBehaviour. This is an abstract type with three concrete subtypes NoIntersection, LinesAreEqual and IntersectInPoint, capturing the three intersection scenarios.
RationalPolygons.Line — TypeLine{T <: Integer}A line in 2-dimensional rational space. It has two fields: base_point :: RationalPoint{T} and direction_vector :: RationalPoint{T}.
RationalPolygons.base_point — Methodbase_point(L :: Line{T}) where {T <: Integer}Return a point on the line L.
RationalPolygons.direction_vector — Methoddirection_vector(L :: Line{T}) where {T <: Integer}Return the direction vector of L.
RationalPolygons.line_through_points — Functionline_through_points(A :: Point{T}, B :: Point{T}) where {T <: Integer}Return the line going through the points A and B.
Example:
julia> line_through_points(Point(1,0),Point(2,2))
Line with base point Rational{Int64}[1, 0] and direction vector Rational{Int64}[1, 2]RationalPolygons.horizontal_line — Functionhorizontal_line(y :: Union{T, Rational{T}}) where {T <: Integer}Return the horizontal line at y.
RationalPolygons.vertical_line — Functionvertical_line(x :: Union{T, Rational{T}}) where {T <: Integer}Return the vertical line at x.
Base.in — MethodBase.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))
trueRationalPolygons.normal_vector — Methodnormal_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
1RationalPolygons.IntersectionBehaviour — TypeIntersectionBehaviour{T <: Integer}An abstract supertype for possible intersection behaviours of two lines. There are the three subtypes IntersectInPoint, NoIntersection, and LinesAreEqual.
RationalPolygons.IntersectInPoint — TypeIntersectInPoint{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.
RationalPolygons.NoIntersection — TypeNoIntersection{T <: Integer}The intersection behaviour of parallel lines.
RationalPolygons.LinesAreEqual — TypeLinesAreEqual{T <: Integer}The intersection behaviour of two equal lines.
RationalPolygons.intersection_behaviour — Functionintersection_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.
RationalPolygons.intersection_point — Functionintersection_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.
Affine halfplanes
An affine halfplane is encoded as a struct consisting of a normal vector $v \in \mathbb{Q}^2$ and a translation $b \in \mathbb{Q}^2$, representing the set of points $\{ x \in \mathbb{Q}^2 | \langle v, x \rangle \geq b \}$.
RationalPolygons.AffineHalfplane — TypeAffineHalfplane{T <: Integer}An affine halfplane in two-dimensional rational space. It has two fields normal_vector :: RationalPoint{T} and translation :: Rational{T}.
RationalPolygons.affine_halfplane — Functionaffine_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//1affine_halfplane(L :: Line{T}) where {T <: Integer}Return the affine halfplane associated to a line. 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.
RationalPolygons.normal_vector — Methodnormal_vector(H :: AffineHalfplane{T}) where {T <: Integer}Return the normal vector of H.
RationalPolygons.translation — Functiontranslation(H :: AffineHalfplane{T}) where {T <: Integer}Return the affine translation of H.
Base.in — MethodBase.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)
trueRationalPolygons.contains_in_interior — Methodcontains_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))
falseBase.issubset — MethodBase.issubset(H1 :: AffineHalfplane{T}, H2 :: AffineHalfplane{T}) where {T <: Integer}Check whether H1 is a subset of H2.
RationalPolygons.line — Methodline(H :: AffineHalfplane{T}) where {T <: Integer}Return the line associated to H.