Module functions

Source

Expand description

Auto-generated module

🤖 Generated with SplitRS

Functions§

alpha_complex_ty: AlphaComplex : List Point2D -> Real -> Type The alpha complex at parameter alpha: a subcomplex of the Delaunay triangulation
alpha_shape_filtration_ty: AlphaShapeFiltration : List Point2D -> List (Real × AlphaComplex) The full filtration from alpha = 0 to alpha = infinity
any_segments_intersect_ty: AnySegmentsIntersect : (List Segment2D) -> Prop Shamos-Hoey: at least one pair of segments intersects
app
app2
app3
arrangement_face_count_ty: ArrangementFaceCount : Nat -> Nat -> Nat f(n, d) = number of faces (cells, facets, …) in a simple arrangement of n hyperplanes in ℝ^d
arrow
bentley_ottmann_correctness_ty: BentleyOttmannCorrectness : BentleyOttmannOutput s = AllIntersections s Correctness theorem for Bentley-Ottmann
bentley_ottmann_output_ty: BentleyOttmannOutput : List Segment2D -> List Point2D Reports all k intersection points of n segments in O((n+k) log n) time
bool_ty
brute_force_closest
build_computational_geometry_env: Build the computational geometry kernel environment.
build_kd_tree: Build a k-d tree from a slice of points.
build_kd_tree_rec
build_range_tree_1d: Build a 1D range tree (BST by key) from a sorted slice.
cech_complex_ty: CechComplex : List Point2D -> Real -> Type The Čech complex at radius r: nerve of the union of balls of radius r
cell_of_arrangement_ty: CellOfArrangement : HyperplaneArrangement -> Point -> Nat Returns the index of the cell containing a given point
circumcenter: Compute the circumcenter of three points.
circumcircle_center_ty: CircumcircleCenter : Point2D -> Point2D -> Point2D -> Point2D The circumcenter of three points
closest_pair: Find the closest pair of points in O(n log n) time. Returns (distance, point_a, point_b).
closest_pair_fn_ty: ClosestPair : (List Point2D) -> (Point2D × Point2D) Returns the closest pair of distinct points
closest_pair_rec
cole_parallel_binary_search_ty: ColeParallelBinarySearch : (Real -> Prop) -> Real Cole’s parametric search: find the critical lambda in O(T_seq * log n) time
compute_persistence_ty: ComputePersistence : (Real -> Type) -> PersistenceDiagram Compute persistent homology from a filtration
configuration_space_ty: ConfigurationSpace : Type -> Type The configuration space C-space of a robot: maps robot description to its C-space
convex_hull_fn_ty: ConvexHull : List Point2D -> List Point2D The convex hull function mapping a point set to its extremal vertices
convex_layer_depth_ty: ConvexLayerDepth : List Point2D -> Point2D -> Nat The convex layer (depth) of a point: 0 = outermost hull
convex_layers_ty: ConvexLayers : List Point2D -> List (List Point2D) Onion peeling: peel successive convex hulls until the set is exhausted
cross: 2D cross product of vectors (p1-p0) × (p2-p0) Positive: p2 is to the left of p0→p1 (counter-clockwise) Negative: p2 is to the right (clockwise) Zero: collinear
cross_2d
cst
delaunay_refinement_ty: DelaunayRefinement : List Point2D -> Real -> List Point2D Ruppert/Chew Delaunay refinement: insert Steiner points until all angles >= min_angle (typically 20.7 degrees)
delaunay_triangulation: Bowyer-Watson incremental Delaunay triangulation. Returns a list of triangles (index triples) for the input point set.
delaunay_triangulation_ty: DelaunayTriangulation : List Point2D -> List (Nat × Nat × Nat) Delaunay triangulation: maximises minimum angle, empty circumcircle property
directed_hausdorff_ty: DirectedHausdorff : List Point2D -> List Point2D -> Real Directed Hausdorff distance from A to B: max_{a in A} min_{b in B} d(a,b)
discrete_frechet_distance_ty: DiscreteFrechetDistance : List Point2D -> List Point2D -> Real Discrete Fréchet distance (dog-leash metric on vertices)
dual_arrangement_ty: DualArrangement : HyperplaneArrangement -> List Point2D Convert a hyperplane arrangement to its dual point set
epsilon_net_bound_ty: EpsilonNetBound : Nat -> Real -> Nat Upper bound on epsilon-net size: O((d/eps) log (d/eps)) for VC-dim d
epsilon_net_ty: EpsilonNet : List Point2D -> Real -> List Point2D An epsilon-net: a subset R such that every heavy range contains a point of R
event_queue_ty: EventQueue : Type -> Type A priority queue of future events ordered by event time
facility_location_ty: FacilityLocation : List Point2D -> Real -> List Point2D Metric facility location: open facilities to minimise opening cost + assignment cost
fractional_cascading_ty: FractionalCascading : List (List Real) -> Real -> List Nat Fractional cascading: simultaneously search k sorted arrays in O(k + log n) time
frechet_distance_ty: FrechetDistance : List Point2D -> List Point2D -> Real Fréchet distance between two polygonal curves
free_space_ty: FreeSpace : Type -> (Type -> Prop) The free configuration space: obstacle-free subset of C-space
gale_transform_ty: GaleTransform : List Point2D -> List Point2D The Gale transform of a point configuration in general position
graham_scan: Compute the convex hull of a set of points using Graham scan. Returns vertices in counter-clockwise order.
hausdorff_distance_ty: HausdorffDistance : List Point2D -> List Point2D -> Real Hausdorff distance: max of directed Hausdorff distances
haussler_packing_lemma_ty: HausslerPackingLemma : Nat -> Nat -> Nat Haussler packing lemma: upper bound on number of distinct projections
hyperplane_arrangement_ty: HyperplaneArrangement : List (Hyperplane d) -> Type A finite collection of hyperplanes inducing a cell decomposition
hyperplane_ty: Hyperplane : Nat -> Type — a hyperplane in ℝ^d defined by a normal vector and offset
in_circumcircle: Test if point p is inside or on the circumcircle of triangle (pa, pb, pc). Assumes the triangle is in CCW order.
interval_intersection_query_ty: IntervalIntersectionQuery : SegmentTree -> (Real × Real) -> List (Real × Real) Report all intervals overlapping a query interval
is_convex_polygon: Test if a polygon (given as CCW ordered vertices) is convex.
is_convex_ty: IsConvex : List Point2D -> Prop — polygon is convex
is_delaunay_ty: IsDelaunay : List Point2D -> List (Nat × Nat × Nat) -> Prop Predicate: the triangulation satisfies the Delaunay condition
is_on_convex_hull_ty: IsOnConvexHull : Point2D -> List Point2D -> Prop A point is on the convex hull of the set
jarvis_march: Compute the convex hull using the Jarvis march (gift wrapping) algorithm. O(nh) where h is the hull size.
k_center_approx_ratio_ty: KCenterApproxRatio : Nat Best known approximation ratio for k-center: 2 (Gonzalez 1985)
k_center_clustering_ty: KCenterClustering : List Point2D -> Nat -> List Point2D k-center clustering: find k centers minimising the maximum cluster radius
k_median_clustering_ty: KMedianClustering : List Point2D -> Nat -> List Point2D k-median clustering: find k centers minimising sum of distances
kd_nearest: Find the nearest neighbour in a k-d tree to a query point.
kd_nearest_rec
kd_range_query: Range query: find all points within distance r of the query in the k-d tree.
kd_range_rec
kd_tree_query_ty: KdTreeQuery : KdTree -> Point2D -> Real -> List Point2D Range query: return all points within distance r of the query point
kd_tree_ty: KdTree : Nat -> Type — a k-d tree for points in ℝ^k
kinetic_certificate_ty: KineticCertificate : Type A combinatorial predicate on moving objects that holds over a time interval
kinetic_convex_hull_ty: KineticConvexHull : Nat -> Type Maintains the convex hull of n moving points in the plane
kinetic_heap_ty: KineticHeap : Nat -> Type A kinetic heap maintains the max of n objects with trajectories
kinetic_tournament_ty: KineticTournament : Nat -> Type A kinetic tournament on n moving points maintains the maximum
list_nat_ty
list_point2d_ty
list_ty
min_angle_guarantee_ty: MinAngleGuarantee : List Point2D -> Real -> Prop All triangles in the refined mesh have minimum angle >= threshold
motion_planning_completeness_ty: MotionPlanningCompleteness : Type -> Prop Completeness of a motion planner: finds a path iff one exists
nat_ty
nearest_neighbour_ty: NearestNeighbour : (List Point2D) -> Point2D -> Point2D Returns the point in the set closest to the query
on_segment: Check if point r lies on segment (p, q) given collinearity.
orientation: Compute the orientation of three points
orthogonal_range_searching_ty: OrthogonalRangeSearching : List Point2D -> (Real × Real) -> (Real × Real) -> List Point2D 2D orthogonal range searching using a range tree
pair_ty
parallel_binary_search_ty: ParallelBinarySearch : List (Real × Real) -> List Real Simultaneous binary search over k sorted arrays
parametric_search_problem_ty: ParametricSearchProblem : Type A decision problem parameterised by a real value lambda, monotone in lambda (used by Cole’s technique)
persistence_diagram_ty: PersistenceDiagram : Type A persistence diagram: multiset of (birth, death) pairs encoding homology lifetimes
pi
point2d_kernel_ty: Point2D : Type — a 2D point (x, y) ∈ ℝ²
point2d_ty
point3d_kernel_ty: Point3D : Type — a 3D point (x, y, z) ∈ ℝ³
point_hyperplane_dual_ty: PointHyperplaneDual : Point2D -> (Real -> Prop) Point-hyperplane duality: maps point (a,b) to the hyperplane y = ax - b
point_in_polygon: Test if a point is strictly inside a simple polygon using ray casting.
point_in_polygon_ty: PointInPolygon : Point2D -> List Point2D -> Prop Ray casting: point is strictly inside the polygon
point_location_ty: PointLocation : (List Point2D) -> Point2D -> Nat Returns the index of the region containing the query point
polygon2d_ty: Polygon2D : List Point2D -> Type — polygon given as an ordered vertex list
polygon_area: Compute the (positive) area of a simple polygon.
polygon_area_ty: PolygonArea : List Point2D -> Real Signed area of a simple polygon (shoelace formula)
polygon_centroid: Compute the centroid of a simple polygon.
polygon_centroid_ty: PolygonCentroid : List Point2D -> Point2D Centroid (centre of mass) of a simple polygon
polygon_perimeter: Compute the perimeter of a polygon.
polygon_perimeter_ty: PolygonPerimeter : List Point2D -> Real
polygon_signed_area: Compute the signed area of a simple polygon using the shoelace formula. Positive for CCW, negative for CW.
probabilistic_roadmap_ty: ProbabilisticRoadmap : Type -> Nat -> Type A probabilistic roadmap: random samples in free C-space connected by a graph
prop
query_range_tree_1d: Query a 1D range tree for all points with key in [lo, hi].
range_tree_query_ty: RangeTreeQuery : RangeTree -> (Real × Real) -> (Real × Real) -> List Point2D Orthogonal range query: report all points in axis-aligned box [x1,x2] × [y1,y2]
range_tree_ty: RangeTree : Nat -> Type A range tree for d-dimensional orthogonal range searching
real_ty
rrt_path_ty: RRTPath : Type -> Point2D -> Point2D -> List Point2D Rapidly-exploring random tree path from start to goal in free space
segment2d_ty: Segment2D : Type — a line segment in ℝ² defined by two endpoints
segment_intersection: Compute the intersection point of two segments (if they intersect). Returns None if they are parallel or do not intersect.
segment_intersection_point_ty: SegmentIntersectionPoint : Segment2D -> Segment2D -> Point2D The intersection point of two segments (if it exists)
segment_tree_ty: SegmentTree : Type A segment tree storing intervals for stabbing/window queries
segments_intersect: Test if two line segments (p1,p2) and (p3,p4) intersect. Uses orientation-based predicates.
segments_intersect_ty: SegmentsIntersect : Segment2D -> Segment2D -> Prop Predicate: two line segments share a common point
shamos_hoey_algorithm_ty: ShamosHoeyAlgorithm : List Segment2D -> Bool Returns true iff any two segments intersect — O(n log n)
shape_matching_optimal_ty: ShapeMatchingOptimal : List Point2D -> List Point2D -> Real Minimum-cost shape matching under rigid motions
spatial_hash_insert_ty: SpatialHashInsert : SpatialHash -> Point2D -> SpatialHash
spatial_hash_ty: SpatialHash : Nat -> Type — spatial hash map with grid resolution n
stabbing_query_ty: StabbingQuery : SegmentTree -> Real -> List (Real × Real) Report all intervals containing the query point
steiner_point_ty: SteinerPoint : List Point2D -> Point2D A Steiner point inserted to improve mesh quality
sweep_line_state_ty: SweepLineState : Type The ordered sequence of segments active at the current sweep-line position
triangle2d_ty: Triangle2D : Type — a triangle in ℝ² defined by three vertices
triangulation_quality_ty: TriangulationQuality : List Point2D -> Real The minimum angle over all triangles in a triangulation
triangulation_ty: Triangulation : List Point2D -> List (Nat × Nat × Nat) A triangulation maps a point set to a list of triangles (vertex index triples)
tukey_depth_ty: TukeyDepth : List Point2D -> Point2D -> Nat Tukey (halfspace) depth of a point with respect to a point set
type0
vc_dimension_ty: VCDimension : (Point2D -> Prop) -> Nat VC dimension of a set system (concept class) on ℝ²
voronoi_cell_ty: VoronoiCell : List Point2D -> Nat -> (Point2D -> Prop) The i-th Voronoi cell: set of points closest to site i
voronoi_diagram_ty: VoronoiDiagram : List Point2D -> List (List Point2D) Maps sites to their Voronoi cell boundary polygon vertices
zone_theorem_bound_ty: ZoneTheoremBound : Nat -> Nat Zone theorem: for a hyperplane h in an arrangement of n hyperplanes in ℝ^d, the complexity of the zone of h is O(n^{d-1})

Module functions

Module functions Copy item path

Functions§

Module functions