Convex Hull Algorithms: Domain Explainer#

What This Solves#

Imagine you have a collection of points scattered across a surface, and you need to find the smallest boundary that encloses all of them. The convex hull is that boundary, always drawn as straight edges connecting outer points, with no inward curves or dents.

This problem appears everywhere in computational geometry. Robotics engineers use it to calculate collision boundaries for irregular-shaped objects. Graphics programmers use it to optimize rendering by creating simplified shapes for complex models. Data scientists use it to identify outliers in multi-dimensional datasets. Computer vision systems use it to detect object boundaries in images. Geographic information systems use it to define territory boundaries from scattered GPS points.

The fundamental challenge is efficiency. With just a handful of points, any algorithm works fine. But when you have thousands or millions of points, the difference between a naive approach and an optimized algorithm becomes the difference between instant results and waiting hours for computation to complete.

Accessible Analogies#

The Rubber Band Model: Place pins on a board representing your points. Stretch a rubber band around all the pins and release it. The rubber band will naturally snap to the outermost pins, forming the tightest perimeter that encloses everything. That perimeter is your convex hull. The inner pins don’t touch the rubber band at all - they’re enclosed but not part of the boundary.

Gift Wrapping: Imagine you’re wrapping an oddly-shaped gift. You start at any outer corner, wrap string around it, and pull the string tight to the next corner you encounter. You keep wrapping from corner to corner, always choosing the next point where the string naturally wants to go when pulled tight. Eventually you come back to where you started, and you’ve traced the complete outer boundary.

The Fence Problem: You have scattered fence posts on a property, and you need to build the shortest fence that keeps all posts inside. The convex hull tells you which posts to connect with fence segments, and which posts can be left interior to the fenced area. This fence will have no inward angles - every corner points outward or stays straight.

Sorting by Position: One common approach works like organizing items by their angular position. Stand at the lowest point and imagine looking around in a circle. Sort all other points by the angle you’d need to turn your head to see them. Walk this sorted path, but whenever you’d need to turn right (inward), skip that point - it’s interior. Only left turns (outward) and straight paths define the boundary.

When You Need This#

You need convex hull algorithms when:

• Building collision detection systems where you need simplified boundaries for complex shapes
• Creating geographic territory boundaries from scattered location data
• Identifying the outer boundary of a cluster in data visualization or machine learning
• Optimizing 3D rendering by creating simplified collision meshes for complex models
• Detecting pattern boundaries in computer vision applications
• Finding the outermost points in any multi-dimensional point cloud

Decision criteria:

The primary factor is point count. Under 100 points, algorithm choice barely matters - even naive approaches complete in milliseconds. Between 100 and 10,000 points, algorithm efficiency starts to matter for real-time applications. Above 10,000 points, you need optimized algorithms or users will notice delays.

Dimensionality matters too. Most algorithms are designed for 2D points on a plane. Extending to 3D introduces significant complexity. Beyond 3D, you’re in specialized research territory where few production-ready libraries exist.

You DON’T need this when:

• You can approximate with a simple bounding box or circle (much faster to compute)
• Your shapes are already simple polygons where the boundary is known
• You need the actual outline of a complex shape, not a simplified hull (convex hulls lose concave features)
• You’re working in high dimensions where “convex hull” becomes computationally intractable

If your actual problem is “find nearby points” or “cluster similar points,” you might want spatial indexing or clustering algorithms instead. Convex hull is specifically for finding outer boundaries.

Trade-offs#

The classic trade-off is algorithmic complexity versus implementation simplicity.

Simple algorithms (Gift Wrapping / Jarvis March):

• O(n*h) complexity where n is total points, h is hull points
• Extremely simple to understand and implement (about 50 lines of code)
• Best when the hull includes most points (worst case O(n²))
• Ideal for teaching or quick prototypes

Divide-and-conquer algorithms (QuickHull):

• O(n log n) average case, O(n²) worst case
• Moderate implementation complexity (200-300 lines)
• Good general-purpose choice
• Performs well on typical datasets

Optimal algorithms (Graham Scan, Andrew’s Monotone Chain):

• O(n log n) guaranteed, dominated by sorting step
• Moderate complexity (requires sorting and stack management)
• Standard choice for production systems
• Predictable performance regardless of input distribution

Chan’s Algorithm:

• O(n log h) complexity - optimal when h is small
• High implementation complexity
• Best when you know the hull will be much smaller than the point set
• Rarely implemented outside specialized libraries

Build versus buy:

For 2D convex hulls, don’t implement from scratch unless you’re learning. Mature libraries exist in every major language. Python has scipy.spatial, JavaScript has d3-polygon, Go has github.com/tidwall/pinhole, Rust has geo crate. These implementations are battle-tested and optimized.

For 3D hulls, the landscape is sparser but still covered. Qhull is the dominant C library with wrappers in most languages. It handles arbitrary dimensions but has a steep learning curve.

Only implement your own if:

• You have unusual constraints (embedded systems, WebAssembly size limits)
• You’re working in a language without existing libraries
• You need to optimize for specific data patterns your domain exhibits

Self-hosted versus cloud services:

This is almost entirely self-hosted territory. Convex hull computation is:

• Too fast to benefit from network calls (microseconds to milliseconds)
• Too specialized for generic geometry APIs
• Involves data that may be private or too large to transmit

Cloud services only make sense if convex hull is bundled with heavier processing (like rendering a full 3D scene, or processing large geospatial datasets where the raw data already lives in cloud storage).

Implementation Reality#

Timeline expectations:

Integrating an existing library: 1-2 days for basic use, 1-2 weeks to handle edge cases and optimize for your specific data patterns.

Implementing a standard algorithm (Graham Scan or QuickHull) from scratch: 3-5 days for a working version, 2-3 weeks to make it robust and performant.

Team skill requirements:

Minimum requirement is comfort with coordinate geometry (points, angles, cross products). If your team can work with 2D vectors and understand what “turn left” means mathematically, they can use existing libraries effectively.

Implementing from scratch requires understanding of computational geometry fundamentals and algorithm analysis. Not expert-level, but solid undergraduate CS education or equivalent self-study.

Common pitfalls:

Floating-point precision causes the most issues. Points that should be collinear might not test as perfectly collinear due to rounding errors. This leads to spurious extra points on the hull boundary. Robust implementations use epsilon comparisons, not exact equality tests.

Degenerate cases trip up naive implementations: all points collinear, all points identical, three points forming a straight line, points arranged in already-convex order. Production-quality code handles these explicitly.

Coordinate system confusion is common. Some algorithms assume Y-axis points up, others assume it points down (screen coordinates). This flips the meaning of “clockwise” versus “counter-clockwise” turns. If your hull comes out backwards, this is why.

First 90 days:

Days 1-7: Library integration, basic testing with simple datasets. Verify output matches expectations for known shapes (squares, triangles).

Days 8-30: Feed in real-world data from your application. Discover edge cases where the naive integration breaks or performs poorly. Add proper error handling and input validation.

Days 31-60: Performance tuning. Profile where time is spent. Often the bottleneck is not the hull algorithm itself but preprocessing (removing duplicates, spatial indexing) or postprocessing (simplifying the hull for rendering).

Days 61-90: Production hardening. Add monitoring, handle degraded modes (what happens when computation takes too long?), optimize for your specific data distribution patterns.

The algorithm itself is stable mathematics, but integrating it into a production system involves the same engineering work as any other computational component: error handling, performance tuning, monitoring, and graceful degradation.

Most teams underestimate how much preprocessing matters. Removing duplicate points, handling degenerate cases, and validating input data quality takes more time than the actual hull computation. Budget accordingly.

Convex Hull Libraries - Decision Matrix#

Quick Reference by Language#

Performance Tiers#

Fastest (Native Performance)#

1. Qhull (C/C++) - 3M points in 4.7s (2D)
2. CGAL (C++) - 1M points in 1.63s (3D static)
3. VQhull (2025) - 1.6-16× faster than Qhull

Fast (Interpreted with Native Backend)#

4. scipy.spatial (Python) - ~50% faster than pyhull, uses Qhull
5. geo (Rust) - Near-native performance

Moderate (Pure JavaScript)#

6. quickhull3d - 6,212 ops/sec (100 points, 3D)
7. convex-hull (mikolalysenko) - n-dimensional wrapper
8. convexhull-js - 2,507 ops/sec (100 points, 2D) ⚠️ inactive

Comprehensive (With Performance Cost)#

9. JTS Topology Suite (Java) - Graham Scan O(n log n)
10. Boost.Geometry (C++) - Template-based, strategy pattern

Algorithm Comparison#

Maturity & Maintenance#

Excellent (Active, Mature)#

• scipy - 14.4k stars, 1,393+ contributors, 30+ years ecosystem
• CGAL - 5.7k stars, academic backing, latest release Jan 2026
• JTS - 2.2k stars, Eclipse Foundation, v1.20.0 (Sep 2024)
• geo (Rust) - 12M+ downloads, 90 versions, active

Good (Proven, Some Activity)#

• Qhull - 30+ years old, Qhull 2020.2, widely used as backend
• quickhull3d - 142 stars, incorporated into ThreeJS
• Boost.Geometry - Part of Boost, extensive version history

Concerning (Old or Inactive)#

• convex-hull (mikolalysenko) - 11 years old, 48k weekly downloads but no updates
• convexhull-js - 10 years old, marked inactive ⚠️
• hull.js - DEPRECATED ❌

Ecosystem Integration#

Python Scientific Computing#

scipy.spatial.ConvexHull

• Integrates with: NumPy, Pandas, Matplotlib, scikit-learn
• Use when: Python data science/ML pipeline

C++ CAD/Graphics#

CGAL (correctness) or Qhull (speed)

• CGAL: Academic, exact computation, comprehensive
• Qhull: Lower-level, faster, backend for many tools
• Boost.Geometry: Cross-platform, Boost integration

JavaScript Web/3D Graphics#

quickhull3d (3D) or convex-hull (n-dimensional)

• quickhull3d: ThreeJS integration, fastest JS option
• convex-hull: Dimensional flexibility, convenience

Java GIS/Enterprise#

JTS Topology Suite

• Eclipse LocationTech, GIS-optimized, comprehensive

Rust Systems/Web#

geo crate

• GeoRust ecosystem, memory-safe, performant

Dimensional Support#

Trade-off Priorities#

Choose for SPEED#

1. Qhull (C/C++)
2. VQhull (parallel variant)
3. CGAL static (3D)
4. quickhull3d (JavaScript)

Choose for CORRECTNESS#

1. CGAL (exact computation)
2. Qhull (with thick facets)
3. scipy (Qhull backend)

Choose for SIMPLICITY#

1. scipy.spatial.ConvexHull (Python)
2. quickhull3d (JavaScript 3D)
3. Boost.Geometry (if already using Boost)

Choose for MAINTENANCE#

1. scipy (Python ecosystem)
2. CGAL (academic backing)
3. JTS (Eclipse Foundation)
4. geo (Rust, high downloads)

Choose for ECOSYSTEM#

• Python science: scipy
• C++ CAD: CGAL
• JS 3D graphics: quickhull3d
• Java GIS: JTS
• Rust systems: geo

Common Gotchas#

1. hull.js is deprecated - Don’t use for new projects
2. hull.js computes CONCAVE hulls - Different problem than convex
3. Qhull fails in 9D+ - Use CGAL for high dimensions
4. CGAL has 25-80% overhead - Exact computation cost
5. convexhull-js is inactive - Consider alternatives
6. Qhull doesn’t handle virtual memory well - Memory constraints matter

Decision Flowchart#

What language?
├─ Python → scipy.spatial.ConvexHull
├─ JavaScript
│  ├─ 3D? → quickhull3d
│  └─ 2D/nD? → convex-hull (mikolalysenko)
├─ C++
│  ├─ Need correctness guarantees? → CGAL
│  ├─ Maximum speed? → Qhull
│  └─ Using Boost? → Boost.Geometry
├─ Java → JTS Topology Suite
└─ Rust → geo crate

Sources Summary#

• Algorithm research: Wikipedia, academic papers (Barber et al., Graham, Andrew)
• Library stats: GitHub repositories, npm registry, crates.io, PyPI
• Performance data: Library benchmarks, academic papers, VQhull 2025 paper
• Maintenance: GitHub activity, release dates, contributor counts

S1-rapid: Convex Hull Library Research#

Overview#

Language-agnostic comparison of major convex hull libraries for decision-making. Focus is on WHAT libraries exist, their characteristics, and trade-offs - NOT installation or usage guides.

Files#

Summary Document#

• 00-library-comparison-summary.md - Quick reference matrix, decision flowchart, performance tiers, and trade-off analysis

Individual Library Files#

Python#

• scipy-spatial-convexhull.md - scipy.spatial.ConvexHull (QuickHull via Qhull)

C/C++#

• qhull.md - Qhull (foundational C/C++ library)
• cgal.md - CGAL (comprehensive, exact computation)
• boost-geometry.md - Boost.Geometry (template library)

JavaScript#

• quickhull3d.md - quickhull3d (best JS 3D option, 142 stars, ThreeJS integration)
• convex-hull-mikolalysenko.md - convex-hull (n-dimensional wrapper, 48k weekly downloads)
• convexhull-js.md - convexhull-js (2D, inactive, 10 years old) ⚠️
• hull-js.md - hull.js (DEPRECATED, concave not convex) ❌

Java#

• jts-topology-suite.md - JTS Topology Suite (GIS-focused, Eclipse Foundation)

Rust#

• geo-rust.md - geo crate (GeoRust ecosystem, 12M+ downloads)

What’s Included#

Each library file contains:

• Speed/performance characteristics (benchmarks, complexity)
• Maturity (GitHub stars, age, maintenance status)
• Algorithm used (QuickHull, Graham Scan, etc.)
• Ecosystem fit (language, integrations, use cases)
• Trade-offs (advantages, disadvantages, when to choose/avoid)

What’s Excluded (per S1 scope)#

• Installation instructions (pip install, npm install, etc.)
• Code samples or usage examples
• How-to tutorials
• API documentation

Quick Recommendations#

Status Notes#

• ❌ hull.js - DEPRECATED, no longer maintained
• ⚠️ convexhull-js - Inactive (10 years old)
• ⚠️ convex-hull (mikolalysenko) - Old (11 years) but high usage (48k weekly)

Research Date#

February 5, 2026

S1-Rapid: Approach#

What is S1?#

S1-Rapid is the ecosystem discovery phase of multi-stage research. It answers a single critical question:

WHAT libraries exist for this problem?

S1 is optimized for speed and decision support, not depth. The goal is to map the landscape quickly so you can make informed choices about which libraries warrant deeper investigation.

S1 Methodology#

Scope: Libraries, Not Implementation#

S1 research focuses on:

• Existence & identification - What libraries solve this problem?
• Characteristics - Speed, maturity, algorithms, ecosystem fit
• Trade-offs - When to use each, when to avoid
• Decision support - Quick comparison matrices and flowcharts

S1 research EXCLUDES:

• Installation instructions
• Usage examples and code samples
• API documentation
• How-to tutorials
• Hands-on proof-of-concept implementation

Why This Scope?#

Fast decision-making requires signal, not noise. A developer facing 5-10 library options needs to know:

1. Which libraries exist - Complete inventory
2. What’s special about each - Algorithm, performance tier, maturity
3. When to choose each - Use cases and trade-offs
4. When to dig deeper - Criteria for moving to S2

Detailed API documentation and tutorials are valuable but waste time when you’re trying to narrow options. S1 trades depth for speed.

Convex Hull S1: Research Focus#

For convex hull libraries, S1 identifies:

1. Speed Characteristics#

• Algorithm used (QuickHull, Graham Scan, Monotone Chain, Incremental)
• Time complexity (O(n log n), O(n²) worst case, etc.)
• Benchmark data (where available)
• Performance tier (fastest, fast, moderate)

2. Maturity & Maintenance#

• GitHub stars, age, release recency
• Maintenance status (active, proven, concerning, deprecated)
• Ecosystem backing (academic, corporate, community)
• Contributor count and velocity

3. Dimensional Support#

• 2D, 3D, n-dimensional, high-dimensional (9D+) capabilities
• Algorithms tailored for specific dimensions
• Limitations per dimension

4. Ecosystem Integration#

• Language and platform fit
• Community size and adoption
• Integration with related libraries
• Industry use (GIS, graphics, ML, data science)

5. Trade-offs & Risk#

• Correctness guarantees vs. speed
• Code complexity and maintenance overhead
• Computational overhead (memory, CPU)
• Maintenance risk (deprecated, inactive, niche)

Language-Agnostic Approach#

S1 treats convex hull libraries across languages as comparable alternatives when:

• Problem is language-neutral (computational geometry)
• Trade-offs are architecture-level (speed vs. correctness)
• Decision framework applies universally (when to use each)

Language choice comes AFTER algorithm and maturity assessment. This research helps answer: “For my problem, which language’s ecosystem has the best library?” rather than “How do I use library X in my language?”

When to Use S1 Results#

Use S1 when you need to:

• Choose between multiple libraries for a new project
• Evaluate risk (maintenance, correctness, performance) quickly
• Narrow options before investing time in learning APIs
• Understand trade-offs at a glance

Move to S2 (Detailed Investigation) when:

• S1 identifies 2-3 candidate libraries
• You need API details, integration examples, or performance benchmarks
• Trade-offs require deeper validation
• Decision still unclear after S1 review

S1 Structure for Convex Hull#

Summary Document#

• 00-library-comparison-summary.md - Decision matrices, flowchart, performance tiers, trade-offs at a glance

Per-Library Assessment#

• One file per library (e.g., scipy-spatial-convexhull.md)
• Consistent structure: algorithm, maturity, performance, trade-offs
• Comparable data across libraries
• No code examples, no installation guides

Formats for Scanning#

• Tables for quick comparison
• Performance tiers for sizing
• Ecosystem integration map
• Decision flowchart for routine choices
• Maintenance status labels (active, concerning, deprecated)

Key Principles#

1. Answer “what?” not “how?” - Inventory and compare; don’t teach implementation
2. Speed over perfection - Hand-curated data from public sources (GitHub, benchmarks)
3. Language-agnostic framing - Compare at architectural level
4. Decision support first - Tables, matrices, flowcharts for easy scanning
5. Clear next steps - Flag which libraries warrant S2 investigation

Research Date#

February 5, 2026

Boost.Geometry#

Overview#

C++ template library providing geometric algorithms as part of the Boost C++ Libraries collection. Includes convex hull computation with strategy pattern for algorithm selection.

Algorithm#

Strategy-based: Uses strategy pattern allowing different algorithm implementations.

Common implementations in Boost.Geometry:

• Graham Scan - Often default for 2D
• Andrew’s Monotone Chain - Alternative 2D strategy

Implementation: Free function boost::geometry::convex_hull() with pluggable strategy.

Performance Characteristics#

• Time Complexity: O(n log n) typical for standard strategies
• Specific benchmarks: Not available in search results
• Template optimization: Compile-time optimizations possible
• Strategy selection: Performance depends on chosen strategy

Maturity#

• Part of Boost: Boost C++ Libraries (one of most established C++ library collections)
• Boost Versions: Available since at least v1.48.0, current through v1.67.0+
• Age: Mature, long-established
• Maintenance: Part of actively maintained Boost collection
• Documentation: Extensive documentation across multiple Boost versions

Ecosystem Fit#

• Language: C++
• Integration: Part of Boost ecosystem (portable, cross-platform)
• Template library: Header-only option available for some components
• Compilation: C++ templates (compile-time specialization)
• Use Cases: Computational geometry, GIS applications, CAD, robotics, scientific computing
• Platform: Cross-platform (Windows, Linux, macOS, etc.)

Trade-offs#

Advantages:

• Boost integration: Works seamlessly with other Boost libraries
• Portable: Cross-platform with Boost’s extensive platform support
• Strategy pattern: Flexible algorithm selection
• Template optimization: Compile-time optimizations possible
• Well-documented: Part of Boost’s comprehensive documentation
• Mature: Long history as part of established library collection
• Header-only options: Some components can be used without linking
• Type flexibility: Works with various coordinate types via templates

Disadvantages:

• Boost dependency: Requires Boost libraries (can be large dependency)
• Compilation time: Template-heavy code increases compile times
• Learning curve: Requires understanding Boost conventions and template patterns
• No specific performance data: Benchmarks not readily available
• Generic approach: May not be as optimized as specialized libraries (CGAL)
• Template errors: Complex template error messages
• Binary size: Template instantiation can increase binary size

When to Choose:

• Already using Boost in your project
• C++ projects requiring cross-platform portability
• Need integration with other Boost.Geometry operations
• Projects valuing Boost’s maturity and support
• When compile-time optimization via templates is beneficial
• Applications requiring strategy pattern flexibility

When to Avoid:

• Maximum performance critical (CGAL or Qhull may be faster)
• Don’t want Boost dependency
• Simple projects where Boost overhead isn’t justified
• Compilation time is critical concern
• Need specific performance guarantees (benchmarks not available)
• Embedded systems with limited resources

Alternatives#

• CGAL - More comprehensive, potentially faster, exact computation
• Qhull - Lower-level, potentially faster for specific cases
• Custom implementation - If avoiding dependencies is critical

Sources#

• Boost.Geometry Documentation (multiple versions)
• convex_hull reference (v1.56.0)
• Boost.Geometry convex_hull header
• Convex Hull of Polygon using Boost.Geometry (Rcpp example)

CGAL (Computational Geometry Algorithms Library)#

Overview#

Comprehensive C++ library for computational geometry providing robust, exact algorithms for 2D and 3D geometric operations including convex hulls.

Algorithm#

Multiple strategies available:

2D:

• Bykat’s Algorithm: Output-sensitive O(nh) - non-recursive version of QuickHull
• Akl-Toussaint Algorithm: O(n log n) worst case

3D:

• Static approach: Best performance for fixed point sets
• Dynamic approach: Supports point insertion/deletion
• Incremental approach: Builds hull incrementally

Performance Characteristics#

• 2D Time Complexity: O(nh) or O(n log n) depending on algorithm choice
• 3D Benchmark (1M random points in unit ball):
  • Static: 1.63s
  • Dynamic: 9.50s
  • Incremental: 11.54s
• Linking Impact: Static linking significantly faster than dynamic (1.63s vs 9.50s for 1M points)
• Exact Computation Overhead: 25-80% slower than fixed-precision algorithms
  • Delaunay triangulation: ~25% overhead
  • Arrangement of segments: ~80% overhead
• High Dimensions: More memory-efficient than Qhull for 64-bit code in higher dimensions

Maturity#

• Repository: CGAL/cgal
• GitHub Stars: 5.7k stars
• Forks: ~1.5k forks
• Age: Long-established project (academic origins)
• Maintenance: Active as of January 2026 (latest release)
• Current Version: 6.1.1 (documentation references)
• Latest Release: January 26, 2026

Ecosystem Fit#

• Language: C++
• Integration: Part of academic/professional computational geometry ecosystem
• Dependencies: C++ standard library, optional boost
• Architecture: Modular package system (e.g., Convex_hull_2, Convex_hull_3 packages)
• Use Cases: CAD/CAM, GIS, scientific visualization, robotics, mesh generation

Trade-offs#

Advantages:

• Robust: Guaranteed correctness through exact computation paradigm
• Flexible: Multiple algorithm choices optimized for different scenarios
• Comprehensive: Full suite of computational geometry algorithms beyond convex hull
• Efficient memory: Better than Qhull in high dimensions (64-bit)
• Static linking: Dramatically faster performance when statically linked
• Well-documented: Extensive academic documentation and research backing

Disadvantages:

• Learning curve: Steep - complex API and concepts (kernel selection, number types)
• Compilation time: Template-heavy C++ leads to slow compilation
• Performance cost: Exact computation 25-80% slower than fixed-precision alternatives
• Complexity: Must choose kernel based on robustness vs speed trade-offs
• Setup overhead: Requires understanding of point-location strategies, number types
• Binary size: Large static binaries if statically linked

When to Choose:

• Correctness is critical (no tolerance for floating-point errors)
• Complex geometric operations beyond just convex hull
• Academic or professional applications requiring proven algorithms
• High-dimensional problems where memory efficiency matters
• Static binaries acceptable for maximum performance

When to Avoid:

• Quick prototyping or simple use cases
• Real-time systems where 25-80% overhead is unacceptable
• Small projects where setup complexity outweighs benefits
• Teams unfamiliar with computational geometry concepts
• Dynamic linking requirements with performance constraints

Sources#

• CGAL 2D Convex Hulls Manual
• CGAL 3D Convex Hulls Manual
• CGAL GitHub Repository
• CGAL FAQ
• The Exact Computation Paradigm

convex-hull (mikolalysenko)#

Overview#

JavaScript wrapper library providing a unified interface for computing convex hulls in any dimension. Simplifies access to specialized convex hull implementations.

Algorithm#

Wrapper over multiple implementations:

• incremental-convex-hull - For general n-dimensional cases
• monotone-convex-hull-2d - Optimized for 2D (Andrew’s Monotone Chain)

Automatic selection: Chooses appropriate underlying algorithm based on dimensionality.

Performance Characteristics#

• Time Complexity: Depends on wrapped algorithm
  • 2D: O(n log n) via monotone-convex-hull-2d
  • nD: Incremental algorithm complexity
• Practical Performance: Not benchmarked directly; inherits from wrapped libraries
• Flexibility: Any dimension supported

Maturity#

• Repository: mikolalysenko/convex-hull
• GitHub Stars: 36 stars
• npm Downloads: ~48,372 weekly downloads
• Latest Version: 1.0.3
• Last Updated: 11 years ago
• Author: Mikola Lysenko
• License: MIT
• Dependents: Used as dependency by other packages

Ecosystem Fit#

• Language: JavaScript
• Platform: Browser and Node.js
• Integration: Part of Mikola Lysenko’s computational geometry suite
• Related Libraries:
  • incremental-convex-hull
  • monotone-convex-hull-2d
  • full-convex-hull (handles lower-dimensional degeneracies)
  • qhull-js (JavaScript port of Qhull)
• Use Cases: General-purpose convex hull computation, research, prototyping

Trade-offs#

Advantages:

• Dimensional flexibility: Any dimension (2D, 3D, 4D+)
• Convenience: Single unified interface across dimensions
• Optimized selection: Automatically uses best algorithm for dimension
• High download count: 48k+ weekly downloads indicates real-world usage
• Ecosystem: Part of larger computational geometry library suite
• Simple API: Abstracts complexity of choosing algorithms

Disadvantages:

• Old: Last updated 11 years ago
• Performance: Slower than specialized implementations (e.g., quickhull3d for 3D)
• Wrapper overhead: Additional abstraction layer
• Limited stars: 36 stars (low visibility/community)
• Maintenance uncertainty: Very old last update
• Generic approach: Not optimized for specific use cases

When to Choose:

• Need dimensional flexibility (2D, 3D, 4D+)
• Prototyping or research where convenience > performance
• Already using Mikola Lysenko’s geometry libraries
• Simple use cases where performance isn’t critical
• Need consistent API across different dimensions

When to Avoid:

• Performance-critical 3D applications (use quickhull3d)
• Production systems requiring active maintenance
• When you need latest JavaScript optimizations
• Projects requiring guaranteed long-term support
• Specialized 2D or 3D scenarios where dedicated libraries are faster

Alternatives#

• quickhull3d - Faster for 3D, actively maintained
• Direct use of wrapped libraries - If you know dimension in advance

Sources#

• GitHub - mikolalysenko/convex-hull
• convex-hull npm package
• incremental-convex-hull npm
• monotone-convex-hull-2d GitHub

convexhull-js#

Overview#

Tiny high-performance JavaScript library for computing 2D convex hulls.

Algorithm#

Not explicitly specified in available documentation, but advertised as high-performance for 2D.

Performance Characteristics#

• Benchmark (100 points): 2,507 ops/sec
• Benchmark (100,000 points): 2.81 ops/sec
• Comparison: Slower than quickhull3d (which is primarily 3D) in direct benchmarks
• Dimensionality: 2D only
• Time Complexity: Not specified

Maturity#

• Repository: indy256/convexhull-js
• npm Package: convexhull-js
• Latest Version: 1.0.0
• Last Published: 10 years ago
• Maintenance Status: INACTIVE - No new versions in past 12 months (as of search date)
• GitHub Stars: Not specified in search results
• Age: Over 10 years old

Ecosystem Fit#

• Language: JavaScript
• Platform: Browser and Node.js
• Use Cases: 2D geometric computations, basic convex hull needs
• Package Size: “Tiny” (advertised as lightweight)

Trade-offs#

Advantages:

• Lightweight/tiny size
• Simple 2D implementation
• Pure JavaScript (no native dependencies)

Disadvantages:

• Inactive maintenance: No updates in 10+ years
• Old: Last published version 10 years old
• Slower performance: 2-3× slower than alternatives (e.g., quickhull3d in benchmarks)
• 2D only: No 3D or higher-dimensional support
• No recent optimization: Hasn’t benefited from modern JavaScript performance improvements
• Maintenance risk: Snyk marks as inactive project
• Limited documentation: Algorithm details not clearly specified

When to Choose:

• Extremely simple 2D use cases where package size matters more than performance
• Legacy projects already using it (but consider migrating)
• When you need absolute minimal dependency footprint

When to Avoid:

• Production systems requiring active maintenance
• Performance-critical applications (3× slower than alternatives)
• Projects needing 3D or higher dimensions
• New projects (prefer actively maintained alternatives)
• When you need guaranteed bug fixes and security updates

Alternatives#

For JavaScript convex hull computation:

• quickhull3d - Faster, actively maintained, 3D capable
• convex-hull (mikolalysenko) - n-dimensional, more flexible
• Modern JavaScript implementations with active maintenance

Sources#

• GitHub - indy256/convexhull-js
• convexhull-js npm package
• convexhull-js Snyk Package Health Analysis
• quickhull3d benchmarks

geo (Rust crate)#

Overview#

Rust geospatial library providing planar geometry primitives and algorithms including convex hull computation. Part of the GeoRust ecosystem.

Algorithm#

QuickHull - Based on the algorithm described in Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (December 1, 1996).

Implementation: ConvexHull trait that returns counter-clockwise oriented hull.

Performance Characteristics#

• Time Complexity: O(n log n) expected (QuickHull)
• Specific benchmarks: Not available in search results
• Rust performance: Near-native C/C++ performance with memory safety
• Output orientation: Always counter-clockwise

Maturity#

• Repository: georust/geo
• Crates.io Downloads: 12,086,311 total downloads
• Published Versions: 90 versions
• Community: Part of GeoRust collective (geospatial computing in Rust)
• Related Crates: geo-types (reexported geometric types)
• Maintenance: Active development
• GitHub Stars: Not specified in search results, but high download count indicates usage

Ecosystem Fit#

• Language: Rust
• Integration: Part of GeoRust ecosystem
• Related Libraries:
  • geo-types: Geometric types
  • rstar: R*-tree spatial index
  • geos: Rust bindings for GEOS
  • geo-index: Packed spatial indexes
• Use Cases: Geospatial computing, GIS, mapping, spatial analysis, web services
• Platform: Cross-platform Rust

Trade-offs#

Advantages:

• Memory safety: Rust’s ownership system prevents memory errors
• Performance: Near-native C/C++ speed
• Modern language: Benefits from Rust’s modern features
• GeoRust ecosystem: Part of comprehensive geospatial toolkit
• High usage: 12M+ downloads indicates production use
• Active development: 90 versions published
• Type safety: Strong type system catches errors at compile time
• Comprehensive: Beyond convex hull - distance, centroid, affine operations, boolean ops
• No runtime: No garbage collection overhead

Disadvantages:

• Rust-only: Not accessible from other languages without FFI
• Learning curve: Requires Rust knowledge (ownership, borrowing)
• Compilation time: Rust compilation can be slow for large projects
• Smaller ecosystem: Less mature than Python/C++ geometry libraries
• No benchmarks: Performance data not readily available
• Newer language: Less historical precedent than C++/Python options

When to Choose:

• Rust projects requiring geometric computation
• Geospatial applications in Rust
• Need memory safety guarantees
• Building high-performance web services in Rust
• Projects valuing modern language features
• When part of larger GeoRust-based application
• Embedded or systems programming requiring safety

When to Avoid:

• Non-Rust projects (Python, JavaScript, C++, Java)
• Teams unfamiliar with Rust
• When you need extensive benchmarks/performance data
• Legacy system integration (FFI complexity)
• Rapid prototyping where compile times matter
• When mature ecosystem (Python/C++) is more important than language benefits

Alternatives#

• CGAL - More comprehensive, exact computation (C++)
• scipy.spatial - Python scientific computing
• JTS - Java GIS applications
• GEOS - C/C++ geospatial library (Rust bindings available)

Sources#

• geo crate on crates.io
• GitHub - georust/geo
• ConvexHull trait documentation
• GeoRust organization
• geo-types crate

hull.js#

Overview#

JavaScript library for building concave hulls (not convex hulls) from a set of 2D points. Note: This library computes CONCAVE hulls, which are different from convex hulls.

Algorithm#

Concave hull algorithm - Implementation details not specified in available documentation.

Performance Characteristics#

• Specific benchmarks: Not available in search results
• Dimensionality: 2D only
• Type: Concave hull (more complex than convex hull)

Maturity#

• Repository: AndriiHeonia/hull
• Status: DEPRECATED AND NO LONGER MAINTAINED (explicitly stated on GitHub)
• npm Package: hull.js
• Latest Version: 1.0.13
• Author: Andrii Heonia
• Dependencies: monotone-convex-hull-2d, robust-segment-intersect
• GitHub Stars: Not specified in search results
• Maintenance: Abandoned - no active development

Ecosystem Fit#

• Language: JavaScript
• Platform: Browser and Node.js
• Use Cases: Geographic data visualization, mapping applications
• npm Package Name: hull.js

Trade-offs#

Advantages:

• Concave hull capability (useful for shape approximation)
• JavaScript-native (no compilation needed)
• Works in browser and Node.js

Disadvantages:

• DEPRECATED: No longer maintained or supported
• Wrong algorithm: Computes concave hulls, not convex hulls (different problem)
• No performance data: Benchmarks not available
• Abandoned: No bug fixes or updates
• Limited dimensionality: 2D only
• Dependency risk: Relies on other packages that may also become outdated

When to Choose:

• DO NOT CHOOSE for new projects - This library is deprecated
• Only consider if maintaining legacy code that already uses it
• If you specifically need concave hulls (not convex), look for maintained alternatives

When to Avoid:

• All new projects (library is deprecated)
• Production systems requiring support
• When you need convex hulls (this library does concave hulls)
• Projects requiring 3D or n-dimensional hulls

Alternatives#

For JavaScript convex hull computation, consider:

• quickhull3d (3D, actively maintained)
• convex-hull by mikolalysenko (n-dimensional)
• convexhull-js (2D, though also old)

Sources#

• GitHub - AndriiHeonia/hull (DEPRECATED)
• hull.js npm package

JTS Topology Suite#

Overview#

Comprehensive Java library for computational geometry and vector-based geomatics, providing extensive geometric operations including convex hull computation.

Algorithm#

Graham Scan - Classic O(n log n) algorithm used for convex hull computation.

Implementation: ConvexHull class works with both Geometry objects and Coordinate arrays, returning the minimal convex hull representation.

Performance Characteristics#

• Time Complexity: O(n log n) - Graham Scan algorithm
• Optimized sorting: O(n) if points already sorted by coordinate or angle
• Output: Minimal number of points needed to represent the convex hull
• Practical Performance: No specific benchmarks in available sources

Maturity#

• Repository: locationtech/jts
• GitHub Stars: ~2.2k stars
• Organization: Eclipse Foundation LocationTech working group
• Latest Version: 1.20.0 (released September 4, 2024)
• Maintenance: Actively maintained - recent 2024 release
• Age: Long-established, mature library
• License: Open source
• Community: Active development team, welcomes contributions

Ecosystem Fit#

• Language: Java
• Primary Use: Vector-based geomatics software, GIS applications
• Integration: Core component for geographic information systems
• Related Capabilities:
  • Concave hull algorithms
  • General planar linear geometry operations
  • Topology operations (union, intersection, etc.)
  • Spatial indexing
• Use Cases: GIS software, mapping applications, spatial databases, CAD systems

Trade-offs#

Advantages:

• Comprehensive: Full geometric toolkit beyond just convex hull
• GIS-optimized: Designed for geographic/geospatial applications
• Mature: Long track record in production GIS systems
• Active maintenance: 2024 release shows ongoing development
• Eclipse backing: Part of established Eclipse Foundation
• Rich functionality: Handles complex geometric operations beyond convex hulls
• Production-proven: Used in major GIS software
• Java ecosystem: Integrates well with enterprise Java applications

Disadvantages:

• JVM requirement: Requires Java runtime
• Java-only: Not accessible from other languages without bindings
• GIS focus: May be overengineered for simple convex hull needs
• Heavyweight: Large library if you only need convex hull
• Performance: Graham Scan not fastest algorithm for all cases
• Learning curve: Complex API designed for comprehensive geometric operations

When to Choose:

• Java/JVM-based projects
• GIS and geospatial applications
• Need comprehensive geometric operations beyond convex hull
• Enterprise applications requiring proven, maintained libraries
• Projects already using Eclipse LocationTech ecosystem
• When you need both convex and concave hull capabilities
• Spatial database integration

When to Avoid:

• Non-JVM languages (Python, JavaScript, C++)
• Simple convex hull-only requirements
• Performance-critical scenarios requiring fastest possible algorithm
• Lightweight applications (library is comprehensive/large)
• Real-time systems where JVM overhead is problematic
• When QuickHull performance benefits matter more than Graham Scan

Alternatives#

• CGAL - For C++ projects requiring more performance
• scipy.spatial - For Python scientific computing
• quickhull3d - For lightweight JavaScript 3D needs

Sources#

• GitHub - locationtech/jts
• JTS Topology Suite Documentation
• ConvexHull JavaDoc
• JTS Topology Suite Wikipedia

Qhull#

Overview#

Low-level C/C++ library implementing the QuickHull algorithm for computing convex hulls, Delaunay triangulations, Voronoi diagrams, and halfspace intersections.

Algorithm#

QuickHull - The algorithm that gives the library its name.

Characteristics:

• Runs faster when input contains non-extreme points
• Uses less memory for non-extreme points
• Adaptively switches to extended precision when needed

Performance Characteristics#

• Time Complexity: O(n log n) average case, O(n²) worst case
• 2D Practical Performance: 3,000,000 evenly spaced cocircular points in 4.7 seconds (1.7 GHz i7)
• High-Dimensional Performance: Does not work well with virtual memory
• Dimensional Scaling: Output size and execution time grow by n^(floor(d/2)) where n=input size, d=dimension (d≥3)
• Medium-Sized 9D+: Does not support medium-sized inputs in 9D and higher
• Recent Optimization (VQhull 2025): Parallel variant shows 1.6-16× sequential improvement, 1.5-11× parallel improvement
• Memory Efficiency: Less efficient than CGAL in high dimensions (64-bit code)

Maturity#

• Repository: Official Qhull site + various GitHub mirrors (e.g., manctl/qhull)
• Age: Established 1992-2012 (v1.0 and v2.0 developed under NSF grants)
• Original Authors: C. Bradford Barber, Hannu Huhdanpaa (v1.0)
• Copyright: 1992-2012 C. B. Barber and The Geometry Center, University of Minnesota
• Latest Referenced Version: Qhull 2020.2
• Maintenance: Active through at least 2020, ongoing community maintenance

Ecosystem Fit#

• Language: C/C++
• Integration:
  • Used as backend for scipy.spatial.ConvexHull (Python)
  • Used as backend for various wrappers (pyhull, etc.)
  • Bindings available for multiple languages (Python, Haskell, etc.)
• Input Format: Points in any dimension
• Use Cases: Foundation library for higher-level geometric computing, scientific computing, CAD

Trade-offs#

Advantages:

• Foundational: Core library used by many higher-level tools (scipy, etc.)
• Mature: 30+ years of development and refinement
• Low-level control: Direct C/C++ interface for maximum performance
• Versatile: Beyond convex hull - Delaunay, Voronoi, halfspace intersections
• Well-studied: Extensive academic research and optimization (including recent VQhull parallel variant)
• Adaptive precision: Switches to extended precision only when needed
• Fast for typical cases: Optimized for non-extreme points

Disadvantages:

• High-dimensional limitations: Poor performance in 9D+, doesn’t support medium-sized inputs
• Virtual memory: Does not work well with virtual memory
• Memory efficiency: CGAL more efficient in high dimensions (64-bit)
• “Thick facets”: Returns parallel hyperplanes to account for round-off error - may complicate downstream use
• Raw C API: Steeper learning curve than higher-level wrappers
• Coplanar point issues: High-dimensional problems may drop points due to numerical precision

When to Choose:

• Building low-level geometric libraries or tools
• Need maximum control over algorithm behavior
• C/C++ project with no Python/other language constraints
• 2D-7D problems with moderate complexity
• When you need Delaunay/Voronoi in addition to convex hull

When to Avoid:

• High-dimensional problems (9D+)
• Large datasets requiring virtual memory
• Python/other language projects (use scipy or other wrappers instead)
• Need guaranteed correctness (use CGAL’s exact computation)
• Memory-constrained high-dimensional scenarios (CGAL more efficient)

Sources#

• Qhull Official Website
• Qhull Manual
• The Quickhull Algorithm for Convex Hulls (ACM Paper)
• VQhull: a Fast Planar Quickhull (2025)
• GitHub - manctl/qhull

quickhull3d#

Overview#

JavaScript library for computing 3D convex hulls using the QuickHull algorithm. High-performance implementation ported from John Lloyd’s Java implementation.

Algorithm#

QuickHull - Robust implementation with O(n log n) expected time complexity.

Origin: Ported from John Lloyd’s Java implementation, which is academically validated.

Performance Characteristics#

• Time Complexity: O(n log n) expected
• Benchmark (100 points): 6,212 ops/sec
• Benchmark (100,000 points): 11.90 ops/sec
• Benchmark (200,000 points): 6.00 ops/sec
• Performance comparison: 2-4× faster than convexhull-js across all test sizes
  • 100 points: 6,212 vs 2,507 ops/sec (2.5× faster)
  • 100,000 points: 11.90 vs 2.81 ops/sec (4.2× faster)
• Dimensionality: 3D
• Robustness: Described as “robust” implementation

Maturity#

• Repository: mauriciopoppe/quickhull3d
• GitHub Stars: 142 stars
• npm Package: quickhull3d
• Latest Version: 3.1.1
• Last Published: 1 year ago (as of search date)
• Dependencies: 7 dependencies, 2 dependents
• Total Versions: 24 versions published
• Author: Mauricio Poppe
• Integration: Incorporated into ThreeJS (major validation)

Ecosystem Fit#

• Language: JavaScript
• Platform: Browser and Node.js
• Integration: Used by ThreeJS (major 3D graphics library)
• Use Cases: 3D graphics, computational geometry, mesh generation, collision detection
• Documentation: Well-documented functions

Trade-offs#

Advantages:

• Fastest JavaScript option: 2-4× faster than alternatives in benchmarks
• Robust implementation: Ported from validated Java implementation
• ThreeJS integration: Used in production by major library
• Active maintenance: Published within last year
• Well-documented: Key functions clearly documented
• Academic pedigree: Based on established QuickHull research
• Proven performance: Concrete benchmark data available

Disadvantages:

• 3D only: Not suitable for 2D or higher-dimensional problems
• JavaScript overhead: Still slower than native C/C++ implementations
• Limited ecosystem: 2 dependents (though ThreeJS is significant)
• Specialization: Focused on 3D - need different library for other dimensions

When to Choose:

• 3D convex hull computation in JavaScript
• Browser-based 3D graphics applications
• Node.js geometric processing with 3D data
• Need fastest JavaScript 3D convex hull implementation
• Working with ThreeJS or similar 3D frameworks
• Performance-critical JavaScript applications

When to Avoid:

• 2D problems (use 2D-optimized library)
• Higher-dimensional problems (4D+)
• Native performance requirements (use C/C++ libraries)
• When absolute cutting-edge maintenance is required (1 year since update)

Alternatives#

• convex-hull (mikolalysenko) - n-dimensional but slower
• Native bindings - If JavaScript performance isn’t sufficient

Sources#

• GitHub - mauriciopoppe/quickhull3d
• quickhull3d npm package
• Performance benchmarks from quickhull3d repository

S1-Rapid: Quick Recommendations#

Decision Matrix by Language#

Performance Tiers#

Tier 1: Maximum Speed (Native C/C++)#

• Qhull (C/C++) - 3M points in 4.7s (2D), 30+ years proven
• CGAL (C++ static) - 1M points in 1.63s (3D), exact computation
• VQhull (C/C++ 2025) - 1.6-16× faster than Qhull (emerging)

Use when: Performance is critical, latency matters, dataset size is large (1M+)

Tier 2: Fast (Interpreted with Native Backend)#

• scipy.spatial.ConvexHull (Python) - Delegates to Qhull, ~50% overhead
• geo (Rust) - Near-native performance, memory-safe

Use when: Native code is impractical but speed matters, language ecosystem is important

Tier 3: Moderate (Pure Interpreted)#

• quickhull3d (JavaScript) - 6,212 ops/sec (100 points, 3D)
• convex-hull (JavaScript) - n-dimensional, slightly slower than quickhull3d
• JTS (Java) - Graham Scan, enterprise-grade but not optimized for speed

Use when: Simplicity/integration matters more than raw speed, datasets small-to-medium (1k-100k)

When to Use Each Library#

scipy.spatial.ConvexHull (Python)#

• When: Building Python ML/data science pipeline
• Why: Qhull backend, NumPy integration, minimal setup
• Skip if: Need ultimate speed or non-standard dimensions (9D+)

CGAL (C++)#

• When: Correctness guarantees matter (financial, CAD, scientific computing)
• Why: Exact computation, arbitrary precision, academic backing
• Cost: 25-80% computational overhead vs. Qhull
• Skip if: Speed is primary goal and approximate hulls acceptable

Qhull (C/C++)#

• When: Maximum speed, proven stability, control over algorithm details
• Why: 30+ years, widely used as backend, lower-level access
• Skip if: Need to avoid C/C++ compilation or correctness guarantees required

quickhull3d (JavaScript)#

• When: Building 3D graphics app in JavaScript (ThreeJS integration)
• Why: Only good JS 3D option, built-in engine integration
• Skip if: 2D/nD problem (use convex-hull) or server-side (use Node.js alternatives)

convex-hull / mikolalysenko (JavaScript)#

• When: 2D or n-dimensional problem in JavaScript
• Why: n-dimensional support, 48k weekly downloads, battle-tested
• Risk: Not updated in 11 years; use if stability matters more than new features
• Skip if: 3D (use quickhull3d instead)

JTS Topology Suite (Java)#

• When: GIS/enterprise system in Java (PostgreSQL integration, spatial indexing)
• Why: Industry standard, Eclipse Foundation backing, comprehensive toolkit
• Skip if: Not in Java ecosystem or convex hull is only geometry need

geo (Rust)#

• When: Systems programming or Rust web application
• Why: Memory safety, near-native speed, 12M+ downloads, active maintenance
• Skip if: Convex hull is one-off tool (Rust setup overhead not justified)

Common Scenarios#

“I’m doing Python ML. Quick decision?”#

→ scipy.spatial.ConvexHull. Done. No alternatives needed.

“C++ with strict performance SLA?”#

→ Qhull if approximate hulls acceptable → CGAL if correctness guarantees required → Measure both in your specific use case

“Web app with 3D visualization?”#

→ quickhull3d if you control input dataset → convex-hull (mikolalysenko) if you need fallback to 2D

“GIS or spatial database work?”#

→ JTS (Java) or CGAL (C++)

“Rust systems tool?”#

→ geo crate, no alternatives needed

“High-dimensional data (5D-8D)?”#

→ CGAL (best) or Qhull (near-limit at 8D) → Qhull explicitly fails at 9D+

“Most important: code simplicity?”#

→ scipy (Python) or quickhull3d (JavaScript 3D)

Key Trade-Offs at a Glance#

Maintenance Risk Assessment#

No Risk#

• scipy - Python ecosystem, 30+ years, 1,393+ contributors
• CGAL - Academic backing, latest release Jan 2026
• JTS - Eclipse Foundation, v1.20.0 Sep 2024
• geo - Rust ecosystem, 90+ versions, active

Low Risk#

• Qhull - 30+ years old, stable API, widely used as backend
• quickhull3d - 142 stars, incorporated into ThreeJS

Medium Risk#

• convex-hull (mikolalysenko) - 11 years old, 48k weekly downloads, no recent updates

High Risk#

• convexhull-js - 10 years old, marked inactive ⚠️
• hull.js - DEPRECATED ❌

Next Steps: When to Move to S2#

Investigate S2 if:#

1. Multiple S1 candidates are equally ranked (need API/integration details)
2. Performance benchmark results unclear (build proof-of-concept)
3. Library has maintenance risk and correctness is critical (validate stability)
4. Trade-off between libraries is close (detailed comparison needed)

Skip S2 if:#

• Clear winner from flowchart above
• Ecosystem choice already made (Python → scipy, Java → JTS, etc.)
• Speed/correctness/maintenance decision straightforward

S1 Summary#

S1 provides language-by-language recommendations and decision flowcharts. Use the table above and quick scenarios to pick a library. If still uncertain, S2 can deep-dive into specific candidates with benchmarks, code examples, and integration guides.

Most projects can choose confidently from S1. S2 is for close calls.

scipy.spatial.ConvexHull#

Overview#

Python library providing convex hull computation as part of the SciPy spatial data structures and algorithms suite.

Algorithm#

QuickHull - Uses the Qhull library under the hood for actual computation.

Performance Characteristics#

• Time Complexity: O(n log n) average case, O(n²) worst case (inherits from Qhull)
• Practical Performance: ~50% faster than pyhull (older Python Qhull wrapper) for larger hulls as of scipy 0.12.0
• 2D Performance: Can compute convex hull of 3,000,000 evenly spaced, cocircular points in ~4.7 seconds (1.7 GHz i7, inherited from Qhull)
• High Dimensions: Performance degrades in higher dimensions - not suitable for virtual memory scenarios
• Dimensional Scaling: Output size and execution time grow by n^(floor(d/2)) where n=input size, d=dimension (d≥3)

Maturity#

• Repository: scipy/scipy
• GitHub Stars: 14.2k - 14.4k stars
• Contributors: 1,393+ contributors
• Age: Mature library, actively maintained
• Maintenance: Active as of January 2026, with multiple maintenance branches
• Current Version: 1.17.0 (as of documentation date)

Ecosystem Fit#

• Language: Python
• Integration: Part of the scientific Python ecosystem (NumPy, Pandas, Matplotlib integration)
• Dependencies: Requires Qhull library (C/C++)
• Input Format: ndarray of points
• Output: ConvexHull object with vertices, simplices, neighbors, equations, and other geometric properties
• Use Cases: Scientific computing, data analysis, machine learning pipelines

Trade-offs#

Advantages:

• Mature, well-tested library with extensive community support
• Seamless integration with NumPy arrays and scientific Python stack
• Direct convex hull computation (not via Delaunay triangulation) since v0.12.0
• Optional qhull_options parameter for fine-tuning
• Rich output object with multiple geometric properties

Disadvantages:

• Python overhead compared to pure C/C++ implementations
• Inherits Qhull’s limitations in high dimensions (9D+)
• Inherits Qhull’s poor performance with virtual memory
• Not ideal for real-time or embedded systems
• “Thick facets” approach in high dimensions may cause precision issues with coplanar points

When to Choose:

• Python-based scientific computing workflows
• Integration with existing SciPy/NumPy code
• Need for rich geometric properties (not just hull vertices)
• 2D-7D problems with moderate point counts

When to Avoid:

• High-dimensional problems (≥9D)
• Extremely large datasets requiring virtual memory
• Real-time performance requirements
• Embedded systems or resource-constrained environments

Sources#

• SciPy ConvexHull Documentation
• SciPy GitHub Repository
• Qhull Documentation
• pyhull Documentation

S2 Pass: Technical Analysis Methodology#

What is S2?#

S2 (Technical Analysis) is the second research pass in a multi-stage investigation process. It focuses on deep technical understanding of algorithms, architectures, and implementation details.

Objectives#

Primary Goals#

1. Algorithm understanding: How do the core algorithms work at a detailed level?
2. Complexity analysis: What are the time/space trade-offs?
3. Implementation characteristics: What makes implementations robust or efficient?
4. Performance characteristics: When does each approach excel or fail?
5. Practical considerations: What do developers need to know to use these effectively?

What S2 Is NOT#

• S2 is NOT a tutorial: No step-by-step installation or usage guides
• S2 is NOT beginner-focused: Assumes reader has technical background
• S2 is NOT comprehensive: Selective depth on key topics
• S2 is NOT implementation: No complete working code (only illustrative snippets)

Research Methodology#

Information Gathering#

1. Primary sources:

   • Academic papers (original algorithm descriptions)
   • Reference implementations (scipy, CGAL, Qhull)
   • Textbooks (Computational Geometry, Algorithms)

2. Secondary sources:

   • Technical blog posts
   • Stack Overflow discussions
   • Benchmark studies
   • Documentation

3. Empirical validation:

   • Verify complexity claims
   • Check implementation details
   • Confirm performance characteristics

Analysis Framework#

For each algorithm/library:

1. Conceptual model: What is the core idea?
2. Detailed mechanics: How does it work step-by-step?
3. Complexity analysis: Time and space bounds
4. Trade-offs: Advantages and disadvantages
5. Implementation concerns: Numerical robustness, edge cases
6. Practical performance: Real-world behavior
7. Use cases: When to use this approach

Document Structure#

Individual Algorithm Files#

Each algorithm gets dedicated analysis:

Sections:

• Overview: One-paragraph summary
• Algorithm Description: Core idea, steps, pseudocode
• Complexity Analysis: Time/space with justification
• Advantages/Disadvantages: Honest assessment
• Optimization Techniques: Practical improvements
• Implementation Considerations: Robustness, edge cases
• Performance Characteristics: When it excels/fails
• Applications: Real-world use cases
• Comparison: How it relates to alternatives

Depth: 500-1500 lines per major algorithm

Comparison Files#

Cross-cutting analysis:

• Complexity tables
• Feature matrices
• Performance benchmarks
• Decision frameworks
• Trade-off discussions

Implementation Files#

Library/tool deep-dives:

• Architecture
• API reference
• Integration patterns
• Performance tuning
• Common pitfalls

Quality Standards#

Technical Accuracy#

• Verify claims: Cross-reference multiple sources
• Test complexity: Ensure Big-O analysis is correct
• Check implementations: Refer to actual source code when possible
• Cite appropriately: Reference papers, libraries, documentation

Clarity#

• Define terms: Don’t assume reader knows jargon
• Use examples: Concrete illustrations where helpful
• Structure logically: Flow from overview to details
• Visual aids: Pseudocode, tables, equations

Completeness#

Each document should enable reader to:

• Understand the core algorithm
• Evaluate trade-offs
• Make informed implementation choices
• Avoid common pitfalls

Practicality#

Balance theory and practice:

• Include asymptotic complexity AND real-world performance
• Discuss edge cases and numerical issues
• Provide guidance for tool selection
• Acknowledge limitations honestly

Scope Boundaries#

What to Include#

• Algorithm mechanics and complexity
• Implementation architecture of major libraries
• Performance characteristics (average, worst-case)
• Practical trade-offs
• Minimal illustrative code snippets showing API patterns

What to Exclude#

• Installation instructions
• Complete code examples
• Step-by-step tutorials
• Library version migration guides
• Unrelated algorithms
• Extensive historical background (brief context OK)

Code Snippets#

When including code:

DO include:

• Pseudocode for algorithms
• API signature examples (1-2 lines showing function call pattern)
• Illustrative fragments showing key concepts

DON’T include:

• Complete runnable examples
• Installation commands (pip install, apt-get, etc.)
• Environment setup
• Full implementations

Example of appropriate snippet:

hull = ConvexHull(points)  # API signature
vertices = hull.vertices    # Key attributes

Example of inappropriate (tutorial-style):

# Install scipy first
!pip install scipy

# Now let's build a complete example...
import numpy as np
from scipy.spatial import ConvexHull

points = np.random.rand(30, 2)
hull = ConvexHull(points)

import matplotlib.pyplot as plt
...  # 20 more lines of plotting code

Target Audience#

Assumed Background#

• Programming: Proficiency in at least one language
• Algorithms: Big-O notation, basic data structures
• Mathematics: Calculus, linear algebra basics
• Geometry: Basic computational geometry concepts

Knowledge Level#

S2 documents target:

• Software engineers: Making architectural decisions
• Researchers: Understanding algorithm options
• Technical leads: Evaluating libraries and approaches
• Advanced students: Learning computational geometry

NOT targeting:

• Beginners learning to code
• Users needing copy-paste solutions
• Non-technical stakeholders

Integration with Other Passes#

Research Pipeline#

S1 (Survey)
  ↓
S2 (Technical Analysis) ← You are here
  ↓
S3 (Implementation)
  ↓
S4 (Evaluation)

S1 provides: Broad landscape, key players identified S2 provides: Deep technical understanding S3 uses: S2 analysis to guide implementation S4 validates: S2 performance predictions

Cross-References#

S2 documents may reference:

• S1 survey for context
• S3 implementation notes (forward reference)
• External papers and documentation

Deliverables#

For Convex Hull Research#

Nine primary documents:

1. graham-scan.md: Graham Scan algorithm analysis
2. quickhull.md: Quickhull algorithm analysis
3. jarvis-march.md: Jarvis March (Gift Wrapping) analysis
4. chans-algorithm.md: Chan’s optimal output-sensitive algorithm
5. qhull-architecture.md: Qhull library deep-dive
6. scipy-implementation.md: SciPy ConvexHull implementation details
7. feature-comparison.md: Cross-algorithm comparison
8. approach.md: This methodology document
9. recommendation.md: Technical recommendations and decision framework

Quality Metrics#

Each document should:

• Be 500-2000 lines (appropriate depth)
• Include complexity analysis
• Provide practical guidance
• Reference authoritative sources
• Be technically accurate
• Be clearly written

Maintenance and Updates#

When to Update S2 Documents#

• New algorithms published
• Library versions change significantly
• Errors discovered
• Performance characteristics change (hardware evolution)
• New optimization techniques emerge

Version Control#

S2 documents are living artifacts:

• Date each major revision
• Note sources consulted
• Track significant changes

Ethical Considerations#

Attribution#

• Cite original algorithm authors
• Reference implementations accurately
• Acknowledge library maintainers
• Give credit to benchmark authors

Balanced Reporting#

• Present algorithms fairly
• Don’t oversell favorites
• Acknowledge limitations honestly
• Avoid vendor/library bias

Conclusion#

S2 pass provides the technical foundation for informed decision-making about algorithms and libraries. It balances theoretical rigor with practical considerations, enabling readers to understand not just WHAT works, but WHY and WHEN.

The goal is technical depth without tutorial overhead—empowering skilled practitioners to make their own implementation choices based on deep understanding.

Chan’s Algorithm#

Overview#

Chan’s Algorithm is the optimal output-sensitive algorithm for computing 2D convex hulls, discovered by Timothy Chan in 1996. It achieves O(n log h) time complexity, where h is the number of hull vertices, matching the theoretical lower bound for output-sensitive convex hull computation.

Algorithm Description#

Core Idea#

Chan’s algorithm brilliantly combines two simpler algorithms—Graham Scan (O(n log n)) and Jarvis March (O(nh))—to achieve the best of both worlds. It uses Graham Scan to build “mini-hulls” and Jarvis March to merge them, with a clever iterative guess-and-verify strategy for the unknown hull size h.

The Key Insight#

We don’t know h in advance, but if we guess a value m ≈ h, we can:

1. Partition points into n/m groups
2. Compute hull of each group: O((n/m) log(n/m)) per group = O(n log m) total
3. Merge mini-hulls using Jarvis March: O(m log m) per hull vertex = O(h m log m) total
4. If we guess m = h correctly, total time is O(n log h)

Since we don’t know h, we try increasing values of m until we succeed.

Steps#

1. Guess m: Start with m = 4, double each iteration (m = 4, 8, 16, 32, …)

2. Partition: Divide n points into ⌈n/m⌉ groups of size ≤ m

3. Mini-hulls: Compute convex hull of each group using Graham Scan

   • Each group hull has ≤ m vertices
   • Total time: O(n log m)

4. Merge with Jarvis March variant:

   • Start from leftmost point among all mini-hulls
   • For each hull vertex to find:
     • For each mini-hull, find the point that would be next in Jarvis March from current position
     • This uses binary search on the mini-hull (since it’s sorted by angle)
     • Take the “most counter-clockwise” candidate across all mini-hulls
   • Continue until wrapping back to start or exceeding m vertices

5. Check termination:

   • If found complete hull with ≤ m vertices: Done! Return hull.
   • If exceeded m vertices: m was too small. Double m and restart.

6. Correctness: Eventually m ≥ h, algorithm completes successfully

Binary Search on Mini-Hull#

Key optimization: Each mini-hull is a convex polygon with vertices sorted by angle from a reference point. Finding the “next point” from current edge direction uses binary search:

Find point on mini-hull with minimum counter-clockwise angle from direction d:
- Binary search to find tangent point
- O(log m) time instead of O(m) linear search
- Repeat for each of O(n/m) mini-hulls: O((n/m) log m)
- Total per hull vertex: O(n/m · log m)

Time Complexity#

Let h = actual number of hull vertices, and assume we reach m ≥ h in iteration k.

Iteration i (where m = 2^i):

• Mini-hull computation: O(n log m)
• Jarvis March phase: O(h · (n/m) · log m) = O(nh log m / m)
• Total: O(n log m + nh log m / m)

Summing over iterations: We try m = 4, 8, 16, …, up to first m ≥ h. This is O(log h) iterations.

For final iteration (m ≈ h):

• Mini-hulls: O(n log h)
• Merge: O(h · (n/h) · log h) = O(n log h)
• Total: O(n log h)

Earlier iterations do less work (smaller m), contributing at most O(n log h).

Result: O(n log h) total time

Space Complexity#

O(n) - for storing points and mini-hulls

Advantages#

1. Optimal output-sensitive: Matches theoretical lower bound O(n log h)
2. No worst case degradation: Unlike Quickhull, always achieves optimal complexity
3. Adaptive to output: Automatically adjusts to hull size
4. Practical efficiency: Constants are reasonable, not just theoretically optimal
5. Combines best of both worlds: Robustness of Graham Scan + output-sensitivity of Jarvis March

Disadvantages#

1. Implementation complexity: More intricate than Graham Scan or Jarvis March alone
2. Constant factors: Higher constants than pure Graham Scan for large h
3. Not cache-optimal: Random access to multiple mini-hulls
4. Overhead for tiny hulls: More complex than Jarvis March when h is very small
5. 2D only: No natural extension to higher dimensions
6. Requires guess-and-verify: Iterative doubling adds bookkeeping

Optimization Techniques#

Initial Guess for m#

Heuristic estimation: Use statistical properties of point distribution to guess h

• Standard deviation of angles
• Ratio of bounding box to point spread
• Sample-based estimation

Better initial guess reduces iterations.

Mini-Hull Representation#

Implicit ordering: Store mini-hull as sorted array by angle from centroid Lazy evaluation: Compute mini-hulls only when needed in merge phase Caching: Store binary search results for repeated queries

Merge Phase Optimization#

Pruning mini-hulls: Eliminate mini-hulls entirely enclosed by others Spatial indexing: Use angular sectors to limit mini-hull candidates Parallel mini-hull computation: Independent subproblems

Memory Layout#

Contiguous storage: Pack all mini-hulls in single array for cache locality Index-based references: Avoid pointer chasing between mini-hulls

Pseudocode#

chans_algorithm(points):
    n = len(points)

    # Try increasing values of m
    for t = 2 to ceil(log log n):
        m = 2^(2^t)  # m = 4, 16, 256, 65536, ...

        # Partition and compute mini-hulls
        groups = partition(points, m)
        mini_hulls = [graham_scan(group) for group in groups]

        # Merge using modified Jarvis March
        hull = []
        current = leftmost_point(mini_hulls)
        hull.append(current)

        for i = 0 to m:
            # Find next hull point across all mini-hulls
            candidates = []
            for mini_hull in mini_hulls:
                # Binary search for tangent point
                candidate = find_tangent(mini_hull, current, direction)
                candidates.append(candidate)

            # Take most counter-clockwise candidate
            next = most_ccw(candidates, current)

            # Check if wrapped around to start
            if next == hull[0]:
                return hull

            hull.append(next)
            current = next

        # Exceeded m vertices, need larger m

    # Should never reach here if m grows sufficiently
    return graham_scan(points)  # Fallback

Implementation Variants#

Simplified Chan#

Skip the guess-and-verify: compute full Graham Scan (O(n log n)), then use result size as m. Two-pass algorithm sacrifices some optimization but simpler to implement.

Adaptive Chan#

Adjust m based on observed hull growth rate in Jarvis phase, rather than strict doubling.

Parallel Chan#

Compute mini-hulls in parallel, merge sequentially. Natural data parallelism.

Performance Characteristics#

When Chan’s Beats Graham Scan#

Chan’s algorithm becomes faster when h << n / log n.

Example: n = 1,000,000 points, h = 100 vertices

• Graham Scan: O(n log n) ≈ 20M operations
• Chan’s: O(n log h) ≈ 6.6M operations
• Speedup: ~3x

When Graham Scan Beats Chan’s#

Small inputs or large h:

• n < 10,000: Setup overhead dominates
• h > n / 10: Comparable to Graham Scan, higher constants

Empirical Performance#

Measurements on random uniform distributions:

Speedup increases with n when h remains small.

Comparison with Other Algorithms#

Applications#

1. Large-scale GIS: Process millions of points with sparse boundaries
2. Computer vision: Extract object boundaries from point clouds
3. Collision detection: Quick bounding shapes for complex objects
4. Data analysis: Outlier detection in high-volume datasets
5. Scientific computing: Boundary extraction from simulation results

When to Use Chan’s Algorithm#

Choose Chan’s when:

• n is large (> 100k points)
• h is expected to be small relative to n
• Need guaranteed optimal output-sensitive performance
• Avoiding worst-case quadratic behavior is critical

Avoid Chan’s when:

• Simple implementation preferred
• Small datasets (< 10k points)
• Hull size unknown and potentially large
• Need 3D or higher dimensions

Implementation Considerations#

Numerical Robustness#

Consistent predicates: Use same geometric primitives across mini-hulls and merge Binary search stability: Handle collinear points in tangent finding Overflow protection: Cross products on large coordinate values

Degenerate Cases#

Single mini-hull: Falls back to Graham Scan result All points on hull: m grows until covering entire hull Collinear points: Mini-hulls may be line segments

Practical Enhancements#

Hybrid approach: Switch to pure Graham Scan if m exceeds threshold Incremental m growth: Use smaller steps than doubling if h estimate available Preprocessing: Remove obvious interior points before partitioning

Theoretical Significance#

Chan’s algorithm is a landmark result in computational geometry:

1. Matches lower bound: First practical algorithm to achieve optimal O(n log h)
2. Algorithmic technique: Guess-and-verify with doubling is now standard
3. Combining algorithms: Shows how merging different approaches can beat either alone
4. Output-sensitive paradigm: Inspired similar techniques in other geometric problems

Extensions and Variants#

Three-Dimensional Analog#

No direct extension to 3D. The binary search on mini-hulls doesn’t generalize cleanly to 3D facets. 3D output-sensitive algorithms exist but use different techniques.

Dynamic Chan’s#

Maintain convex hull under point insertions/deletions:

• Recompute affected mini-hulls
• Rerun merge phase
• Amortized performance better than full recomputation

Approximate Hull#

Relax correctness for speed:

• Terminate Jarvis phase early
• Accept hull with ≈ h vertices (within factor)
• Useful for visualization or rough boundaries

Historical Context#

Timothy Chan’s 1996 paper “Optimal output-sensitive convex hull algorithms in two and three dimensions” resolved a long-standing open problem. The 2D result (this algorithm) was particularly elegant, while the 3D result was more technically involved. The algorithm is taught in advanced algorithms courses as an example of sophisticated algorithm design.

Further Reading#

The core insight—using guess-and-verify with exponential search on parameter space—has been applied to numerous other problems:

• 3D convex hull (Chan’s 3D algorithm)
• Diameter computation
• Closest pair
• Voronoi diagram construction

Chan’s technique of combining algorithms through adaptive parameter selection remains influential in algorithm design.

Convex Hull Algorithms: Technical Comparison#

Overview#

This document provides a comprehensive technical comparison of major convex hull algorithms, focusing on computational complexity, implementation characteristics, and practical performance trade-offs.

Complexity Analysis#

Time Complexity Summary#

Legend:

• n = number of input points
• h = number of convex hull vertices
• Output-sensitive = complexity depends on output size

Space Complexity#

Dimensional Applicability#

Notes:

• “-” indicates not applicable or no standard implementation
• “Fair/Poor” indicates significant performance degradation

Implementation Characteristics#

Code Complexity#

Numerical Robustness#

Robustness rating:

• Excellent: Handles nearly all inputs reliably
• Good: Works with careful implementation
• Moderate: Requires attention to edge cases

Performance Characteristics#

Input Distribution Sensitivity#

Random Uniform Points#

Gaussian Clusters (many interior points)#

Circular/Boundary Distribution (most points on hull)#

Dataset Size Scaling#

Small Datasets (n < 1,000)#

Best: Jarvis March or Graham Scan

• Overhead minimal
• Simple implementations fast
• Constant factors matter most

Medium Datasets (1,000 < n < 100,000)#

Best: Graham Scan or Quickhull

• Algorithms mature into asymptotic behavior
• Implementation quality matters
• Cache effects visible

Large Datasets (n > 100,000)#

Best: Chan’s Algorithm or Quickhull

• Output sensitivity valuable
• Parallelization potential important
• Memory hierarchy critical

Hardware Considerations#

Cache Efficiency#

Parallelization Potential#

SIMD Utilization#

Best: Operations on batches of points

• Distance computations (Quickhull)
• Cross products (all algorithms)
• Min/max finding (initialization)

Implementation note: Requires careful data layout and explicit vectorization

Practical Decision Matrix#

When to Use Each Algorithm#

Graham Scan#

Use when:

• General-purpose 2D hull
• Need predictable O(n log n) performance
• Simple, maintainable code desired
• Hull size unknown

Avoid when:

• Hull known to be tiny (h << log n)
• Need output-sensitive guarantees
• Working in 3D+

Quickhull#

Use when:

• 3D or higher dimensions
• Many interior points expected
• Want production-ready library (Qhull)
• Need Delaunay/Voronoi as well

Avoid when:

• Worst-case guarantees critical
• Points likely on circular boundary
• Need simplest possible code

Jarvis March#

Use when:

• Hull known to be very small
• Memory extremely constrained
• Simplest implementation needed
• Educational/teaching context

Avoid when:

• Hull size unknown
• Performance critical
• Processing large batches

Chan’s Algorithm#

Use when:

• Large datasets (n > 100k)
• Hull expected to be small relative to n
• Need optimal output-sensitive performance
• Can handle implementation complexity

Avoid when:

• Small datasets (n < 10k)
• Simple implementation preferred
• Hull size comparable to n
• Need 3D+ algorithm

Library and Tool Comparison#

Available Implementations#

Production-Ready Options#

Python#

scipy.spatial.ConvexHull  # Best choice for most use cases

• Mature, well-tested
• Excellent documentation
• NumPy integration
• Qhull backend

C/C++#

Qhull library  // Production standard
CGAL  // When exact arithmetic needed

JavaScript#

hull.js  // 2D, simple
d3-delaunay  // Delaunay with hull

R#

geometry::convhulln  # Qhull wrapper
chull  # Base R, 2D only

Benchmarking Methodology#

Standard Test Cases#

Synthetic Distributions#

1. Uniform random: Points uniform in unit square/cube
2. Gaussian cluster: N(0, 1) distribution
3. Circle/sphere: Points on boundary
4. Grid: Regular lattice points
5. Star: Radial rays from center

Real-World Datasets#

1. GIS coordinates: Geographic point clouds
2. Image keypoints: Computer vision features
3. Scientific data: Simulation outputs, measurements
4. Graphics: Mesh vertices, particle systems

Performance Metrics#

Time Metrics#

• Total time: End-to-end execution
• Setup time: Preprocessing, initialization
• Core algorithm time: Main loop only
• Postprocessing time: Output formatting

Memory Metrics#

• Peak memory: Maximum allocation during execution
• Working set: Average memory in use
• Allocations: Number of malloc/free calls

Quality Metrics#

• Correctness: All hull vertices found
• Completeness: No extra vertices
• Numerical stability: Consistent results on perturbed inputs

Summary Recommendations#

For Different Scenarios#

Quick Selection Guide#

Ask yourself:

1. Dimension?

   • 2D → Graham Scan, Jarvis March, Chan’s
   • 3D+ → Qhull

2. Dataset size?

   • Small (< 1k) → Graham Scan or Jarvis March
   • Large (> 100k) → Chan’s or Quickhull

3. Hull size known?

   • Small → Jarvis March or Chan’s
   • Unknown → Graham Scan

4. Implementation time budget?

   • Hours → Use library (scipy, Qhull)
   • Days → Implement Graham Scan
   • Weeks+ → Consider Chan’s

5. Performance critical?

   • Yes → Benchmark multiple algorithms on your data
   • No → Use scipy.ConvexHull

Theoretical Bounds#

Lower Bounds#

2D Convex Hull: Ω(n log n) in comparison model

• Sorting reduces to convex hull
• Any comparison-based algorithm must be Ω(n log n)

Output-Sensitive: Ω(n log h) optimal

• Chan’s algorithm achieves this bound

3D Convex Hull: Ω(n log n)

• Same reduction from sorting

Upper Bounds Achieved#

Open Problems and Research Directions#

Unresolved Questions#

1. Optimal output-sensitive 3D: No O(n log h) algorithm known
2. Parallel algorithms: Best parallel bounds still open
3. Approximate hulls: Trade-off curves not fully characterized
4. Streaming algorithms: Space-efficient online hulls

Recent Advances#

• GPU acceleration: CUDA implementations for large-scale problems
• Approximate hulls: Epsilon-approximations with better constants
• Distributed computing: MapReduce-style convex hull algorithms
• Numerical robustness: Exact predicates with adaptive precision

Conclusion#

The “best” convex hull algorithm depends entirely on context:

• scipy.ConvexHull (Qhull): Default choice for most practical applications
• Graham Scan: Best for understanding, teaching, or simple 2D implementations
• Chan’s Algorithm: Optimal for large datasets with small hulls
• Jarvis March: Simplest algorithm, good for tiny hulls

When in doubt, use a well-tested library (scipy, CGAL, Qhull) rather than implementing from scratch. Convex hull is a solved problem with excellent production-ready tools.

Graham Scan Algorithm#

Overview#

Graham Scan is one of the most widely used algorithms for computing 2D convex hulls, discovered by Ronald Graham in 1972. It achieves optimal O(n log n) time complexity in all cases.

Algorithm Description#

Core Idea#

The algorithm works by sorting points and then making a single pass through them, maintaining a stack that represents the convex hull vertices. It uses a “left turn test” to determine which points to keep.

Steps#

1. Find the anchor point: Select the point with the lowest y-coordinate (bottommost). If there’s a tie, choose the leftmost among them. This point is guaranteed to be on the convex hull.

2. Sort by polar angle: Sort all other points by the angle they make with the anchor point. Points with the same angle are sorted by distance from the anchor.

3. Build the hull: Process sorted points in order:

   • Start with anchor and first two points on stack
   • For each subsequent point:
     • While the last three points make a right turn (or are collinear), pop the middle point
     • Push the current point onto the stack
   • The stack contains the hull vertices in counter-clockwise order

Left Turn Test#

The algorithm uses the cross product to determine turn direction:

For three points P1(x1,y1), P2(x2,y2), P3(x3,y3):
cross_product = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)

cross_product > 0  → left turn (counter-clockwise)
cross_product < 0  → right turn (clockwise)
cross_product = 0  → collinear

Time Complexity#

• Sorting: O(n log n) - dominant operation
• Anchor selection: O(n)
• Hull construction: O(n) - each point pushed/popped at most once
• Total: O(n log n)

Space Complexity#

O(n) - for storing sorted points and the stack

Advantages#

1. Optimal complexity: Matches the lower bound for comparison-based convex hull algorithms
2. Simple to implement: Clean conceptual model with straightforward logic
3. In-place operation: Can modify input array for space efficiency
4. Deterministic: No worst-case degradation unlike Quickhull
5. Stable: Well-studied with proven correctness

Disadvantages#

1. Not output-sensitive: Always O(n log n) even when hull has few vertices
2. 2D only: Does not generalize to higher dimensions
3. Sorting overhead: Full sort required even for nearly-convex inputs
4. Numerical precision: Angle computation can be sensitive to floating-point errors

Optimization Techniques#

Collinear Point Handling#

Keep boundary points: Include collinear points on hull edges Remove boundary points: Keep only corner vertices (more common)

Implementation affects the equality check in the left turn test.

Sorting Optimization#

Avoid trigonometry: Use cross product for angle comparison instead of atan2()

compare_angle(p1, p2, anchor):
    return cross_product(anchor, p1, p2) > 0

Preprocessing: Remove interior points before sorting if many points are known to be internal

Stack Implementation#

Array-based: Use index pointer instead of actual stack operations Deque: Python collections.deque for O(1) push/pop at both ends

Pseudocode#

graham_scan(points):
    # Find anchor
    anchor = point with min y (break ties by min x)

    # Sort by polar angle
    sorted_points = sort(points - anchor, key=polar_angle_from_anchor)

    # Initialize stack
    stack = [anchor, sorted_points[0], sorted_points[1]]

    # Process remaining points
    for i = 2 to len(sorted_points)-1:
        # Remove points that make right turn
        while len(stack) >= 2 and ccw(stack[-2], stack[-1], sorted_points[i]) <= 0:
            stack.pop()
        stack.push(sorted_points[i])

    return stack

Variant: Modified Graham Scan#

Some implementations start from the rightmost point instead of bottommost, or process points in different orders. The fundamental approach remains the same.

Applications Beyond Convex Hull#

1. Polygon simplification: Remove redundant vertices
2. Collision detection: Quick separation tests
3. Computational geometry: Foundation for many geometric algorithms
4. Computer graphics: Silhouette computation

Comparison with Other O(n log n) Algorithms#

vs Merge Hull: Graham Scan is simpler but doesn’t parallelize as well

vs Divide and Conquer: Graham Scan has better constants and simpler implementation

vs Monotone Chain: Very similar approach; Monotone Chain avoids angle computation

Implementation Considerations#

Numerical Robustness#

Use exact predicates or robust geometric primitives to handle:

• Collinear points
• Nearly collinear points
• Points very close together
• Extreme coordinate ranges

Degenerate Cases#

• All points collinear: Returns line segment
• Fewer than 3 points: Returns all points
• Duplicate points: Remove in preprocessing

Coordinate Systems#

Works in any 2D coordinate system. For geographic data, project to plane first.

Performance Characteristics#

Best for:

• Medium-sized datasets (10³ to 10⁶ points)
• General-purpose 2D convex hull computation
• When output size is unknown

Avoid when:

• Need output-sensitive algorithm (use Chan’s algorithm)
• Working in 3D+ (use QuickHull or divide-and-conquer)
• Have highly convex point sets (sorting overhead not justified)

Historical Note#

Graham’s original 1972 paper “An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set” laid the groundwork for modern computational geometry. The algorithm remains one of the most taught in algorithms courses due to its elegance and practical efficiency.

Jarvis March Algorithm (Gift Wrapping)#

Overview#

Jarvis March, also known as Gift Wrapping, is an output-sensitive algorithm for computing 2D convex hulls. Discovered by R.A. Jarvis in 1973, it achieves O(nh) time complexity where h is the number of hull vertices. This makes it optimal for point sets where the hull is small relative to the total number of points.

Algorithm Description#

Core Idea#

The algorithm “wraps” a string around the point set by repeatedly finding the next hull vertex. Starting from a known hull point, it selects the point that makes the smallest counter-clockwise angle with the current edge.

Metaphor#

Imagine wrapping a gift with a ribbon. You start at one corner, pull the ribbon tight to the next corner, and continue around the perimeter. The ribbon naturally finds the convex boundary.

Steps#

1. Find starting point: Select leftmost point (minimum x-coordinate). This is guaranteed to be on the hull.

2. Initialize: Set current point to starting point, set previous direction to “downward” or undefined.

3. Find next point: For each iteration:

   • Consider all other points as candidates
   • Find the point that makes the smallest counter-clockwise angle from the current edge direction
   • This point is the next hull vertex
   • Add it to the hull

4. Termination: When the next point equals the starting point, the hull is complete.

Angle Selection#

For current point P and candidate point Q, compute the angle from the previous edge direction to edge PQ. Select the point with minimum angle (most counter-clockwise).

Can be computed without trigonometry using cross product:

For points prev, current, candidate:
cross = (current.x - prev.x) * (candidate.y - current.y) -
        (current.y - prev.y) * (candidate.x - current.x)

cross > 0: candidate is counter-clockwise from prev→current
cross < 0: candidate is clockwise
cross = 0: collinear

Time Complexity#

• Per iteration: O(n) - examine all points to find next hull vertex
• Number of iterations: O(h) - one per hull vertex
• Total: O(nh)

Where:

• n = total number of points
• h = number of convex hull vertices

Best Case#

O(n) when h = O(1) - very few hull vertices (e.g., all points in small cluster)

Worst Case#

O(n²) when h = O(n) - all or most points on hull

Average Case#

Depends on point distribution. For random uniform in square/circle, expected h = O(log n), giving O(n log n) expected time.

Space Complexity#

O(h) - only store hull vertices

Can be O(1) if computing hull perimeter rather than storing vertices.

Advantages#

1. True output-sensitive: Time proportional to output size
2. Simple implementation: Extremely easy to understand and code
3. Minimal memory: Only stores hull vertices, not all points
4. Online capable: Can add points incrementally (with modifications)
5. Natural extension to 3D: Gift wrapping generalizes to higher dimensions
6. Early termination: Can stop when finding specific hull features
7. Numerically stable: Simple angle comparisons, fewer edge cases

Disadvantages#

1. Quadratic worst case: O(n²) when all points on hull
2. Repeated point scanning: Examines all points at each iteration
3. Not cache-friendly: Random access pattern across all points
4. Poor for dense hulls: Slower than O(n log n) algorithms when h is large
5. No parallelization: Sequential nature of “next point” selection
6. Redundant work: No information reuse between iterations

Optimization Techniques#

Point Elimination#

Mark used points: Skip points already on hull in subsequent iterations

Spatial indexing: Use quadtree or grid to limit candidate search region

Convex layers: After finding hull, remove hull points and repeat for inner layers

Angle Computation#

Avoid trigonometry: Use cross product or dot product instead of atan2()

Vector arithmetic: Compute relative angles without absolute angle calculation

Integer arithmetic: For integer coordinates, maintain exact precision

Early Termination#

Partial hull: Stop after finding k vertices if only portion needed

Sector search: Limit search to angular sector around expected next point

Data Structure#

Linked list for candidates: Remove hull points efficiently

Spatial partitioning: Organize points by polar angle from current point

Pseudocode#

jarvis_march(points):
    # Find leftmost point
    start = point with min x-coordinate
    hull = [start]
    current = start

    # Initialize direction (arbitrary for first step)
    prev_direction = vector(0, -1)  # downward

    while True:
        # Find point with smallest counter-clockwise angle
        next_point = None
        min_cross = -infinity

        for candidate in points:
            if candidate == current:
                continue

            cross = cross_product(prev_direction,
                                 vector(current, candidate))

            if next_point is None or cross > min_cross:
                min_cross = cross
                next_point = candidate

        # Check if we've wrapped around to start
        if next_point == start:
            break

        # Add to hull and advance
        hull.append(next_point)
        prev_direction = vector(current, next_point)
        current = next_point

    return hull

Implementation Variants#

Right-Turn Variant#

Instead of finding minimum angle, find the point where all other points are to the right of the edge from current to that point:

for each candidate:
    is_hull_point = True
    for each other_point:
        if other_point is left of edge(current, candidate):
            is_hull_point = False
            break
    if is_hull_point:
        next = candidate
        break

Conceptually clearer but same O(n²) worst case.

3D Gift Wrapping#

Extends naturally to 3D:

• Start with an edge known to be on hull
• Find face containing that edge
• Move to next unprocessed edge on that face
• Repeat until all faces found

Incremental Variant#

Add points one at a time:

• Maintain current hull
• Insert new point by finding edges it makes visible
• Reconnect edges around new point

Useful for dynamic point sets.

Performance Characteristics#

Optimal For#

Small hulls: When h << n

• Points in tight clusters
• Points in convex position (h = O(log n) expected)
• Outlier detection (only need a few hull vertices)

Memory-constrained: Minimal space overhead

Streaming data: When points arrive incrementally

Poor For#

Large hulls: When h approaches n

• Points on circle/ellipse boundary
• Nearly uniform distribution on boundary
• Grid corners

Dense convex hulls: O(n log n) algorithms much faster

Empirical Performance#

• n=1000, h=10: Jarvis ~0.5x time of Graham Scan (faster)
• n=1000, h=100: Jarvis ~2x time of Graham Scan (slower)
• n=1000, h=500: Jarvis ~5x time of Graham Scan (much slower)

Comparison with Other Algorithms#

Applications#

1. Outlier detection: Find boundary points in clusters
2. Collision detection: Quick bounding shape for sparse objects
3. Path planning: Compute navigation boundaries
4. Visible surface determination: 3D variant for graphics
5. Convex layers: Repeatedly peel outer hulls

When to Use Jarvis March#

Choose Jarvis March when:

• Hull size known to be small (h << n/log n)
• Extreme memory constraints
• Need simple, maintainable code
• Only need partial hull (first k vertices)
• Points arrive incrementally

Avoid Jarvis March when:

• Hull size unknown or potentially large
• Processing batch datasets
• Need guaranteed O(n log n) performance
• Working with dense point distributions

Implementation Considerations#

Numerical Robustness#

Collinear points: Decide whether to include or skip

• Include: Keep all boundary points
• Skip: Keep only corner vertices

Tie-breaking: When multiple points have same angle

• Use distance as tiebreaker
• Consistent tie-breaking prevents infinite loops

Floating-point precision: Use robust predicates for angle comparison

Degenerate Cases#

All collinear: Returns line segment or two endpoints Fewer than 3 points: Returns all points Duplicates: Remove or handle in point comparison

Optimization for Practical Use#

Spatial filtering: Use bounding box to limit candidates per iteration

Adaptive switching: If h grows large, switch to Graham Scan mid-computation

Parallel candidate search: While algorithm is sequential in hull vertices, finding next vertex can be parallelized

Historical Context#

Jarvis March was one of the first output-sensitive algorithms in computational geometry. Its simplicity and intuitive “wrapping” metaphor made it popular for teaching. However, its O(nh) complexity limited practical use until Chan (1996) showed how to combine it with Graham Scan to achieve optimal O(n log h) complexity.

The algorithm remains relevant for:

• Educational purposes (clearest convex hull algorithm)
• Small hull applications
• Basis for Chan’s algorithm
• Incremental/online hull computation

Qhull Architecture and Implementation#

Overview#

Qhull is the de facto standard library for computing convex hulls, Delaunay triangulations, Voronoi diagrams, and halfspace intersections in arbitrary dimensions. Developed by Brad Barber and David Dobkin (1993-present), it implements the Quickhull algorithm extended to n-dimensional space with extensive optimizations and robustness enhancements.

Core Architecture#

High-Level Structure#

Qhull System
├── Geometric Engine
│   ├── Quickhull algorithm (divide-and-conquer)
│   ├── Facet management
│   ├── Ridge tracking (shared edges between facets)
│   └── Vertex-facet connectivity
├── Numerical Core
│   ├── Robust geometric predicates
│   ├── Determinant computation
│   ├── Distance calculations
│   └── Precision management
├── Data Structures
│   ├── Facet lists
│   ├── Vertex sets
│   ├── Ridge structures
│   └── Point arrays
└── Output Formatting
    ├── Hull vertices
    ├── Facets (oriented simplices)
    ├── Normals and offsets
    └── Adjacency information

Quickhull in Higher Dimensions#

2D vs 3D vs nD#

2D: Line segments connect hull vertices 3D: Triangular facets form hull surface (most common use case) 4D+: Simplicial facets (tetrahedra in 4D, etc.)

Generalization Strategy#

1. Initial simplex: Instead of leftmost/rightmost points (2D), find d+1 affinely independent points to form initial d-simplex

2. Partitioning: Instead of “above/below line”, partition points by which side of a hyperplane (facet) they lie on

3. Furthest point: Find point furthest from a facet (hyperplane), not line

4. Recursive processing: Create new facets by connecting furthest point to visible horizon ridges

Key Concepts#

Facet: A (d-1)-dimensional face of the convex hull

• In 3D: triangular face
• In 4D: tetrahedral face
• Represented by hyperplane equation: n·x + offset = 0

Ridge: A (d-2)-dimensional face shared by two facets

• In 3D: edge between two triangular faces
• Critical for tracking adjacency

Horizon: Set of ridges visible from a point being added

• Forms boundary between visible and invisible facets
• New facets created by connecting point to horizon ridges

Visible facet: Facet whose outside half-space contains the point being added

Data Structures#

Facet Structure#

facet {
    hyperplane normal[d]      // Unit normal vector
    double offset              // Distance from origin

    set<vertex*> vertices      // Vertices of this facet
    set<ridge*> ridges         // Bounding ridges
    set<facet*> neighbors      // Adjacent facets

    set<point*> outside_set    // Points outside this facet
    point* furthest            // Furthest outside point

    bool seen                  // Processing flag
    bool tested                // Visibility flag
    int id                     // Unique identifier
}

Vertex Structure#

vertex {
    double point[d]            // Coordinates
    set<facet*> neighbors      // Incident facets
    int id
}

Ridge Structure#

ridge {
    set<vertex*> vertices      // d-1 vertices defining ridge
    facet* top                 // Facet on one side
    facet* bottom              // Facet on other side
}

Quickhull Algorithm in Detail#

Initialization#

1. Find initial simplex:

   • Find d+1 affinely independent points
   • Compute centroid
   • Build initial d-simplex with correct orientation
   • Partition remaining points to facet outside sets

2. Orient facets:

   • Ensure normals point outward
   • Check orientation using centroid or interior point

Main Loop#

while exists facet with non-empty outside_set:
    # Select facet to process (various heuristics)
    facet = select_facet_with_outside_points()

    # Find furthest point from this facet
    apex = furthest_point(facet.outside_set)

    # Find all facets visible from apex
    visible_facets = find_visible_facets(apex, facet)

    # Compute horizon ridges
    horizon = compute_horizon(visible_facets)

    # Create new facets
    for ridge in horizon:
        new_facet = create_facet(apex, ridge)
        add_to_hull(new_facet)

    # Partition remaining points to new facets
    for old_facet in visible_facets:
        redistribute_points(old_facet.outside_set, new_facets)

    # Delete visible facets
    delete(visible_facets)

Facet Selection Heuristics#

Best facet: Facet with furthest point (maximizes progress) Breadth-first: Process facets in order encountered Depth-first: Process newly created facets immediately Hybrid: Switch strategies based on recursion depth

Qhull uses adaptive selection based on dimension and point distribution.

Visible Facet Detection#

Starting from facet known to be visible, do breadth-first search:

visible = [initial_facet]
queue = [initial_facet]

while queue not empty:
    facet = queue.pop()
    for neighbor in facet.neighbors:
        if not neighbor.tested:
            neighbor.tested = true
            if is_visible(apex, neighbor):
                visible.add(neighbor)
                queue.append(neighbor)

is_visible(point, facet): point is on positive side of facet’s hyperplane

Horizon Computation#

Horizon is the boundary between visible and invisible regions:

horizon = []
for facet in visible_facets:
    for ridge in facet.ridges:
        # Ridge is on horizon if one neighbor visible, other not
        if (ridge.top in visible_facets) XOR (ridge.bottom in visible_facets):
            horizon.append(ridge)

Point Redistribution#

After creating new facets, reassign points from deleted facets:

for point in old_facet.outside_set:
    # Find which new facet point is outside of
    for new_facet in new_facets:
        if is_outside(point, new_facet):
            new_facet.outside_set.add(point)
            break
    # If point not outside any new facet, it's interior (discard)

Numerical Robustness#

Precision Issues#

Challenge: Geometric predicates (orientation, distance) use floating-point arithmetic, leading to:

• Roundoff errors
• Inconsistent predicate results
• Non-robustness (crashes or incorrect output)

Solutions in Qhull#

1. Joggle Input#

Idea: Add small random perturbation to input points to avoid degeneracies

for each point p:
    p[i] += random() * joggle_factor

Effect: Makes collinear points slightly non-collinear, coplanar points slightly non-coplanar

Trade-off: Output is approximate, not exact

2. Thick Facets#

Idea: Treat facets as thick slabs, not infinitesimal planes

facet is visible from point if:
    distance(point, facet) > epsilon

Effect: Absorbs small numerical errors, provides stability

3. Merging#

Idea: When precision issues create invalid geometry, merge nearby facets

• Detect small angles between facets
• Merge facets that violate convexity by small amount
• Smooth out numerical artifacts

4. Exact Arithmetic (Optional)#

Use rational arithmetic or exact predicates library (e.g., CGAL):

• Slower but guaranteed correct
• Not default in Qhull (performance penalty)

User Controls#

qh_option("QJ")      // Joggle input
qh_option("Q0")      // No merging (may fail on degenerate inputs)
qh_option("C0")      // Set centrum radius (controls thick facets)
qh_option("Qx")      // Exact merges

Performance Optimizations#

Memory Management#

Facet pools: Pre-allocate blocks of facet structures Point recycling: Reuse point structures when redistributing Lazy deletion: Mark facets deleted, batch free later

Cache Optimization#

Contiguous arrays: Store points in array, reference by index Locality: Process nearby facets together when possible Prefetching: Hint processor about upcoming memory accesses

Parallelization#

Limited: Quickhull’s recursive structure is inherently sequential Opportunities:

• Parallelize initial simplex construction
• Parallel point-to-facet assignment
• Multi-threaded distance computations

Qhull itself is single-threaded; parallel wrappers exist.

Dimensionality Considerations#

Computational Complexity#

Time:

• 2D: O(n log n) to O(n²)
• 3D: O(n log n) to O(n²)
• d-dimensional: O(n⌈d/2⌉) worst case

Space: O(n) for d ≤ 3, O(n⌊d/2⌋) for general d

Curse of Dimensionality#

Problem: In high dimensions (d > 10), most points tend to be on the convex hull

• Expected hull vertices ≈ n for d = 20+
• Quickhull degenerates to O(n²) behavior
• Memory explodes (facets, ridges grow exponentially)

Practical limit: Qhull works well up to d ≈ 8-10

High-Dimensional Strategies#

Dimension reduction: Project to lower-dimensional subspace Approximate hulls: Relax convexity requirements Alternative algorithms: Incremental or beneath-beyond for d > 10

Applications and Variants#

Delaunay Triangulation#

Key insight: Delaunay triangulation in d-dimensions = Convex hull in (d+1)-dimensions

Transformation:

1. Lift each point (x₁, …, xₐ) to paraboloid: (x₁, …, xₐ, x₁² + … + xₐ²)
2. Compute convex hull of lifted points
3. Project lower hull back to d-dimensions

Qhull implements this via qdelaunay.

Voronoi Diagrams#

Duality: Voronoi diagram = Delaunay triangulation dual

Computation:

1. Compute Delaunay triangulation
2. Construct dual graph (facet centroids become Voronoi vertices)

Qhull provides via qvoronoi.

Halfspace Intersection#

Problem: Given halfspaces H₁, …, Hₙ, find their common intersection

Solution via duality:

1. Transform each halfspace to dual point
2. Compute convex hull of dual points
3. Transform hull facets to intersection vertices

Qhull implements via qhalf.

API and Usage Patterns#

C Library Interface#

// Basic usage
coordT points[n*dim];  // Input points
int exitcode;
FILE *errfile = stderr;

// Initialize
qh_init_A(stdin, stdout, errfile, 0, NULL);

// Set options
qh_option("qhull");  // Basic convex hull

// Compute
qh_initflags(qh_option("qhull"));
qh_init_B(points, n, dim, True);
qh_qhull();

// Access results
facetT *facet;
vertexT *vertex;
FORALLfacets {
    // Process each facet
}

// Cleanup
qh_freeqhull(True);

Python Wrapper (scipy.spatial.Qhull)#

from scipy.spatial import ConvexHull

points = np.random.rand(100, 3)
hull = ConvexHull(points)

# Access results
vertices = hull.vertices
simplices = hull.simplices
volume = hull.volume

See scipy-implementation.md for details.

C++ Wrappers#

libqhullcpp: Modern C++ interface CGAL: Uses Qhull backend with higher-level abstractions

Output Formats#

Vertices#

List of hull vertex indices (into original point array)

Facets#

Each facet as:

• List of vertex indices
• Normal vector
• Offset from origin
• Adjacent facet indices

Oriented Simplices#

For triangulation: each simplex with consistent orientation

Summary Statistics#

• Number of facets
• Number of vertices
• Number of ridges
• Volume (3D+)
• Surface area

Limitations and Gotchas#

Degeneracies#

Coplanar points: Can cause precision issues

• Use joggling or merging
• Or preprocess to remove exact coplanarities

Duplicate points: Must be removed beforehand

• Qhull may not handle gracefully

Near-duplicate points: Can cause merging/joggling

• Increases output complexity

Precision Settings#

Too loose: Incorrect hull (missing vertices or extra facets) Too tight: Crashes due to failed merges or infinite loops

Default settings work for most cases; tune for extreme inputs.

Memory Consumption#

Large d or n: Memory grows quickly

• Facet count can be exponential in d
• Monitor memory usage, use sampling if needed

Performance Surprises#

Nearly convex inputs: Fastest (few interior points) Circular/spherical inputs: Slowest (all points on hull)

Comparison with Other 3D+ Algorithms#

When to Use Qhull#

Choose Qhull when:

• Need 3D or higher-dimensional hulls
• Want Delaunay/Voronoi capabilities
• Require well-tested, production-ready code
• Can tolerate approximate output (joggling)

Avoid Qhull when:

• 2D only (simpler algorithms faster)
• Need exact arithmetic (use CGAL)
• High dimensions d > 10 (consider alternatives)
• Embedded systems (library footprint large)

Historical Impact#

Qhull has been the standard for convex hull computation since 1995:

• Used in countless scientific applications
• Basis for scipy.spatial, MATLAB’s convhull
• Reference implementation for Quickhull
• Extensive testing and robustness hardening

The library’s longevity and ubiquity make it the practical choice for most convex hull needs despite newer algorithms.

Further Reading#

Qhull documentation: http://www.qhull.org/html/index.htm Original paper: Barber, Dobkin, Huhdanpaa (1996) “The Quickhull Algorithm for Convex Hulls” Robustness: Papers on joggling, merging, and thick facets Alternatives: CGAL documentation for exact methods

Quickhull Algorithm#

Overview#

Quickhull is a divide-and-conquer algorithm for computing convex hulls, inspired by the Quicksort algorithm. Discovered independently by Eddy (1977) and Bykat (1978), it exhibits excellent average-case performance and often outperforms Graham Scan in practice.

Algorithm Description#

Core Idea#

Quickhull recursively partitions points using a “furthest point” strategy, similar to how Quicksort uses pivots. It identifies points definitely on the hull and recursively processes subsets of remaining points.

Steps#

1. Find extreme points: Identify leftmost and rightmost points (min/max x-coordinates). These are guaranteed to be on the hull.

2. Divide points: The line connecting these extremes divides the point set into two subsets:

   • Points above the line (left side)
   • Points below the line (right side)

3. Recursive hull construction: For each subset:

   • Find the point furthest from the dividing line
   • This point is on the convex hull
   • Recursively process points outside the triangle formed by:
     • The line segment endpoints
     • The furthest point
   • Points inside the triangle are interior and discarded

4. Termination: When no points remain outside a line segment, that segment is part of the hull.

Distance Calculation#

Distance from point P(x,y) to line through A(x₁,y₁) and B(x₂,y₂):

signed_distance = (y-y₁)*(x₂-x₁) - (x-x₁)*(y₂-y₁)

Positive: point on left side of directed line A→B
Negative: point on right side
Zero: collinear with line

Actual distance not needed; signed value sufficient for comparison.

Time Complexity#

• Average case: O(n log n)

  • Each level processes all points: O(n)
  • Expected recursion depth: O(log n)
  • Similar analysis to Quicksort

• Worst case: O(n²)

  • Occurs when points form a circle or semi-circle
  • Each recursion removes only one point
  • Depth becomes O(n)

• Best case: O(n)

  • When all points are on or near the hull
  • Few points discarded at each level

Space Complexity#

• Recursion stack: O(log n) average, O(n) worst case
• Point storage: O(n)
• In-place variants: Possible with careful bookkeeping

Advantages#

1. Excellent average performance: Often faster than Graham Scan in practice
2. Output-sensitive behavior: Tends toward O(n) when many points are interior
3. Intuitive: Easy to understand divide-and-conquer approach
4. Adaptable: Can be modified for specific point distributions
5. Cache-friendly: Good locality of reference during point partitioning
6. Parallelizable: Natural divide-and-conquer structure

Disadvantages#

1. Quadratic worst case: Poor performance on circular or semi-circular point sets
2. Unpredictable performance: Depends heavily on point distribution
3. Not truly output-sensitive: Doesn’t achieve optimal O(n log h) like Chan’s
4. Implementation complexity: More bookkeeping than Graham Scan
5. 2D limitation: 3D extension (Qhull) has different characteristics

Optimization Techniques#

Furthest Point Selection#

Exact distance: Compute actual perpendicular distance

distance = |ax + by + c| / sqrt(a² + b²)

Signed distance: Skip square root (sufficient for comparison)

signed_dist = ax + by + c

Cross product: Equivalent to signed distance, often faster

cross = (x-x₁)(y₂-y₁) - (y-y₁)(x₂-x₁)

Point Filtering#

Triangle test: Use triangle inequality to quickly eliminate interior points

Bounding box: Discard points obviously inside current hull segments

Batch processing: Find multiple hull points per recursion level

Data Structure Optimization#

Linked lists: For efficient point removal during partitioning

Arrays with indices: Better cache performance than pointer-based structures

Bucket structures: For spatial locality when partitioning points

Pseudocode#

quickhull(points):
    # Find extreme points
    leftmost = point with min x
    rightmost = point with max x
    hull = [leftmost, rightmost]

    # Partition points
    above = points above line(leftmost, rightmost)
    below = points below line(leftmost, rightmost)

    # Recursively build hull
    find_hull(above, leftmost, rightmost, hull)
    find_hull(below, rightmost, leftmost, hull)

    return hull

find_hull(points, p1, p2, hull):
    if points is empty:
        return

    # Find furthest point
    furthest = point with max distance from line(p1, p2)

    # Add to hull
    hull.insert_between(p1, p2, furthest)

    # Partition remaining points
    left_set = points left of line(p1, furthest)
    right_set = points right of line(furthest, p2)

    # Discard points inside triangle(p1, furthest, p2)

    # Recurse
    find_hull(left_set, p1, furthest, hull)
    find_hull(right_set, furthest, p2, hull)

Implementation Variants#

Iterative Quickhull#

Replace recursion with explicit stack:

• Better memory control
• Avoids stack overflow on degenerate inputs
• Slightly more complex code

Hybrid Approaches#

Switch to insertion: When subset size < threshold, use simpler algorithm

Multiple pivots: Select k furthest points per iteration to reduce depth

Preprocessing: Remove obvious interior points before main algorithm

Performance Characteristics#

Best Input Distributions#

• Gaussian clusters: Most points interior, quickly discarded
• Grid patterns: Regular structure aids partitioning
• Random uniform: Average-case performance

Worst Input Distributions#

• Circle/ellipse: Every point on boundary, no pruning
• Semi-circle: Repeated partitions with minimal pruning
• Star pattern: Poor pivot selection at each level

Empirical Performance#

On random uniform distributions:

• Small datasets (n < 1000): Comparable to Graham Scan
• Medium datasets (1000 < n < 100k): Often 20-40% faster than Graham Scan
• Large datasets (n > 100k): Advantage increases with more interior points

3D Extension: Qhull#

Quickhull generalizes to higher dimensions as Qhull:

• Same divide-and-conquer principle
• Uses facets instead of line segments
• Industry-standard implementation available
• More complex geometry but same conceptual approach

See qhull-architecture.md for detailed 3D implementation.

Comparison with Graham Scan#

Applications#

1. Large random datasets: Excels when most points are interior
2. Parallel processing: Divide-and-conquer structure maps to parallel algorithms
3. Adaptive requirements: Performance scales with hull complexity
4. 3D convex hulls: Via Qhull library

Implementation Considerations#

Numerical Stability#

Integer coordinates: Exact arithmetic possible for small ranges

Floating-point: Use robust predicates:

• Adaptive precision methods
• Error bounds on distance calculations
• Consistent tie-breaking for collinear points

Degenerate Cases#

All collinear: Return line segment or all points Duplicates: Remove in preprocessing or handle in distance calculation Fewer than 3 points: Return input

Memory Management#

Recursive overhead: Monitor stack depth on large inputs Point copying: Avoid if possible; use indices into original array Dynamic allocation: Pre-allocate buffers if recursion depth estimable

When to Use Quickhull#

Choose Quickhull when:

• Point distribution has many interior points
• Need parallelizable algorithm
• Working with 3D or higher dimensions (via Qhull)
• Average-case performance critical

Avoid Quickhull when:

• Worst-case guarantees required (use Graham Scan)
• Points nearly all on hull (sorting overhead less than repeated partitioning)
• Need output-sensitive guarantees (use Chan’s algorithm)
• Simple implementation preferred

Historical Context#

Quickhull emerged in the late 1970s as computational geometry matured. Its connection to Quicksort made it immediately accessible to algorithm designers. The Qhull library (1993) established Quickhull as the de facto standard for practical convex hull computation in 3D and higher dimensions.

Convex Hull: Technical Recommendations#

Executive Summary#

For most practical applications, use scipy.spatial.ConvexHull (Python) or Qhull (C/C++). These provide production-ready implementations of the Quickhull algorithm with excellent robustness, performance, and features.

For specialized needs or educational purposes, consider implementing Graham Scan (2D, predictable performance), Jarvis March (very small hulls), or Chan’s Algorithm (large datasets with small hulls).

Decision Framework#

Quick Selection Guide#

START: Need convex hull algorithm
    │
    ├─ Working in Python?
    │   ├─ Yes → Use scipy.spatial.ConvexHull
    │   └─ No → Continue
    │
    ├─ Need 3D or higher?
    │   ├─ Yes → Use Qhull library
    │   └─ No (2D only) → Continue
    │
    ├─ Hull size known to be tiny (< 10 vertices)?
    │   ├─ Yes → Implement Jarvis March
    │   └─ No → Continue
    │
    ├─ Dataset very large (> 100k points) with small expected hull?
    │   ├─ Yes → Consider Chan's Algorithm
    │   └─ No → Implement Graham Scan
    │
    └─ END

Recommended Approaches by Context#

1. Production Applications (Most Common)#

Recommendation: scipy.spatial.ConvexHull (Python) or Qhull (C/C++)

Rationale:

• Battle-tested over decades
• Handles edge cases and degeneracies
• Excellent performance across input distributions
• Well-documented with active maintenance
• Supports 2D through ~10D
• Includes Delaunay/Voronoi capabilities

Example use case:

• Scientific computing
• Data analysis
• Computer graphics
• GIS applications

Implementation note: No need to write your own algorithm; use the library.

2. Educational/Learning Context#

Recommendation: Implement Graham Scan or Jarvis March

Rationale:

• Graham Scan: Optimal complexity, clean conceptual model
• Jarvis March: Simplest algorithm, intuitive “gift wrapping” metaphor

Learning path:

1. Start with Jarvis March (50 lines of code)
2. Understand output-sensitivity concept
3. Implement Graham Scan (100 lines)
4. Compare performance empirically
5. Read about Chan’s Algorithm (combine both approaches)

Do NOT use library as black box when learning—implement yourself.

3. Performance-Critical 2D Applications#

Recommendation: Benchmark Graham Scan vs Quickhull vs Chan’s on your data

Rationale:

• “Best” algorithm depends on point distribution
• Small constant-factor differences matter at scale
• Implementation quality varies

Testing methodology:

# Pseudocode for benchmarking
algorithms = [graham_scan, quickhull_2d, chans_algorithm]
test_distributions = [uniform_random, gaussian_cluster, circular_boundary]

for algo in algorithms:
    for dist in test_distributions:
        points = generate_points(dist, n=100000)
        time = benchmark(algo, points, iterations=100)
        print(f"{algo.__name__} on {dist}: {time}ms")

Expected results:

• Uniform random: Quickhull ≈ Chan’s < Graham Scan
• Gaussian cluster: Quickhull < Chan’s < Graham Scan
• Circular boundary: Graham Scan < Chan’s << Quickhull

Recommendation: Profile on YOUR data, not synthetic benchmarks.

4. Very Small Hulls (h < 10)#

Recommendation: Implement Jarvis March

Rationale:

• O(nh) complexity optimal when h is tiny
• Simplest implementation (~50 lines)
• Minimal memory overhead
• No sorting overhead

Use cases:

• Outlier detection in tight clusters
• Bounding shapes for sparse objects
• Convex layers (repeated hull peeling)

When NOT to use: Hull size unknown or potentially large.

5. Large Datasets (n > 100k) with Small Hulls#

Recommendation: Implement or use Chan’s Algorithm

Rationale:

• Optimal O(n log h) complexity
• Adapts automatically to output size
• Predictable worst-case performance

Trade-off: Implementation complexity (~300 lines vs 100 for Graham Scan)

Alternative: Use scipy.ConvexHull (Quickhull averages O(n log n), good enough in practice)

6. 3D and Higher Dimensions#

Recommendation: Use Qhull library exclusively

Rationale:

• No simpler alternatives with comparable robustness
• Extending 2D algorithms to 3D+ is non-trivial
• Qhull is industry standard (used by scipy, MATLAB, etc.)
• Handles degeneracies via joggling and merging

DO NOT attempt to implement your own 3D+ hull algorithm unless:

• Research project on new algorithm
• Specific needs Qhull doesn’t address
• Willing to invest weeks debugging geometry edge cases

7. Exact Arithmetic Required#

Recommendation: Use CGAL library

Rationale:

• Supports exact predicates (rational arithmetic)
• Guaranteed correctness even with degeneracies
• Well-tested robustness

Trade-off: 2-10x slower than Qhull with floating-point

Use cases:

• Geometric algorithms research
• Applications where incorrect hull is unacceptable
• Legal/safety-critical systems

8. Embedded/Resource-Constrained Systems#

Recommendation: Implement Graham Scan (2D) or use minimal Qhull build

Rationale:

• Graham Scan: <1KB code size, minimal dependencies
• Qhull: Can strip to core functionality (~100KB)

Avoid:

• Full scipy (massive dependencies)
• Chan’s Algorithm (complexity not justified for small n)
• Floating-point heavy algorithms if FPU unavailable

9. Real-Time Applications (Graphics, Robotics)#

Recommendation: Precompute when possible; otherwise Graham Scan or incremental algorithms

Rationale:

• Precomputation: O(1) lookup beats any O(n log n) algorithm
• Graham Scan: Predictable worst-case for live computation
• Incremental: Update existing hull as points move (O(log n) per update)

Techniques:

• Spatial hashing to limit point set
• Incremental hull updates
• Approximate hulls with bounded error

10. Parallel/Distributed Computing#

Recommendation: Use Quickhull variant or Divide-and-Conquer

Rationale:

• Quickhull: Natural divide-and-conquer structure
• Divide-and-Conquer: Explicit parallel subproblems

Avoid:

• Graham Scan (sorting is main bottleneck, limited parallelism)
• Jarvis March (inherently sequential)

Frameworks:

• OpenMP for shared-memory parallelism
• MPI for distributed computing
• GPU acceleration (CUDA) for massive point clouds

Implementation Guidelines#

If Using a Library#

Python: scipy.spatial.ConvexHull#

from scipy.spatial import ConvexHull
import numpy as np

# Standard usage
points = np.array([[...], [...], ...])
hull = ConvexHull(points)

# Access results
vertices = points[hull.vertices]
volume = hull.volume

Tips:

• Use qhull_options="QJ" for precision issues
• Enable incremental=True for dynamic point sets
• Check hull.good to identify interior points

C/C++: Qhull#

#include "qhull_a.h"

// Initialize and compute
qh_init_A(...);
qh_initflags("qhull");
qh_init_B(points, numpoints, dim, True);
qh_qhull();

// Access results via facetT and vertexT structures

Tips:

• Read Qhull documentation thoroughly (complex API)
• Use Qhull error handling (qh_errexit)
• Consider C++ wrapper (libqhullcpp) for RAII

If Implementing Your Own#

Priority Order#

1. First choice (2D): Graham Scan

   • Optimal O(n log n) guaranteed
   • ~100 lines of code
   • Well-understood edge cases

2. Second choice (2D, small hull): Jarvis March

   • Simplest implementation
   • Good for learning
   • Only if hull size known to be small

3. Advanced (2D, large n): Chan’s Algorithm

   • Optimal output-sensitive
   • Complex implementation
   • Only if Graham Scan measured as bottleneck

4. 3D+: Don’t implement; use Qhull

Implementation Checklist#

• Use cross product for turn detection (avoid atan2())
• Handle collinear points consistently
• Remove duplicate points in preprocessing
• Test on degenerate cases (all collinear, < 3 points, etc.)
• Use robust geometric predicates (epsilon-based comparisons)
• Validate output (every point on or inside hull)

Numerical Robustness#

Key principle: Use integer arithmetic when possible, robust predicates when not.

For integer coordinates:

def cross_product(o, a, b):
    # Exact arithmetic for int32 coordinates
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

For floating-point:

def cross_product(o, a, b, epsilon=1e-10):
    cp = (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
    if abs(cp) < epsilon:
        return 0  # Treat as collinear
    return cp

Epsilon selection: Depends on coordinate scale; typically 1e-10 for normalized coordinates.

Performance Optimization#

Regardless of Algorithm#

1. Preprocess:

   • Remove duplicate points: O(n log n) with sorting or O(n) with hashing
   • Remove obvious interior points (inside bounding box by large margin)
   • Scale coordinates to similar magnitude

2. Data structures:

   • Use contiguous arrays (not linked lists) for cache efficiency
   • Index into original array rather than copying points
   • Pre-allocate buffers when possible

3. Memory layout:

   • Structure-of-arrays (SoA) for SIMD: x[], y[] not point[].x, point[].y
   • Align data structures to cache line boundaries

Algorithm-Specific#

Graham Scan#

• Use cross product for angle comparison (not atan2)
• Sort indices, not points themselves
• In-place stack via array index pointer

Quickhull#

• Use spatial indexing (quadtree) to limit candidate searches
• Cache distance calculations
• Switch to insertion sort for small subproblems

Jarvis March#

• Eliminate hull points from subsequent searches (mark as used)
• Use spatial partitioning to limit candidate set per iteration

Chan’s Algorithm#

• Choose initial m based on heuristic (not blind doubling)
• Parallelize mini-hull computation
• Cache binary search results within Jarvis phase

Testing and Validation#

Test Cases#

Minimal set (every implementation must pass):

1. Degenerate:

   • 0 points → empty hull
   • 1 point → single point
   • 2 points → line segment
   • 3 collinear points → line segment
   • 3 non-collinear → triangle

2. Small:

   • 4 points forming square
   • 5 points (4 corners + 1 interior)
   • 10 random points

3. Large:

   • 1000 uniform random
   • 1000 Gaussian cluster (few hull vertices)
   • 100 points on circle (all hull vertices)

4. Precision:

   • Nearly collinear points
   • Points with large coordinate values
   • Points very close together

Correctness Checks#

def validate_hull(points, hull_vertices):
    """Verify convex hull is correct."""
    hull_points = points[hull_vertices]

    # Check 1: All hull vertices are input points
    assert all(v < len(points) for v in hull_vertices)

    # Check 2: At least 3 vertices (unless degenerate)
    assert len(hull_vertices) >= 3 or len(points) < 3

    # Check 3: All input points inside or on hull
    for point in points:
        assert point_in_or_on_hull(point, hull_points)

    # Check 4: All hull edges make left turns
    for i in range(len(hull_vertices)):
        a, b, c = hull_points[i-1], hull_points[i], hull_points[(i+1)%len(hull_points)]
        assert cross_product(a, b, c) >= 0  # Left turn or collinear

    return True

Benchmarking#

Compare against scipy.spatial.ConvexHull on your data:

import time
import numpy as np
from scipy.spatial import ConvexHull

def benchmark(algorithm, points, iterations=100):
    times = []
    for _ in range(iterations):
        start = time.perf_counter()
        hull = algorithm(points)
        times.append(time.perf_counter() - start)
    return np.median(times), np.std(times)

# Your implementation
median_time, std_time = benchmark(my_convex_hull, test_points)
print(f"My algorithm: {median_time*1000:.2f} ± {std_time*1000:.2f} ms")

# Reference
median_time, std_time = benchmark(lambda p: ConvexHull(p), test_points)
print(f"SciPy (Qhull): {median_time*1000:.2f} ± {std_time*1000:.2f} ms")

Common Pitfalls and Solutions#

Pitfall 1: Using atan2() for Angle Comparison#

Problem: Trigonometric functions are slow and introduce floating-point error.

Solution: Use cross product for orientation test:

# Bad
angle_a = atan2(a.y - origin.y, a.x - origin.x)
angle_b = atan2(b.y - origin.y, b.x - origin.x)
if angle_a < angle_b: ...

# Good
cross = cross_product(origin, a, b)
if cross > 0: ...  # a is counter-clockwise from b

Pitfall 2: Ignoring Collinear Points#

Problem: Inconsistent handling leads to incorrect hull or infinite loops.

Solution: Decide on policy (include or exclude) and implement consistently:

# Include collinear points on boundary
if cross_product(a, b, c) >= 0: ...

# Exclude collinear points (only keep corners)
if cross_product(a, b, c) > 0: ...

Pitfall 3: Not Removing Duplicates#

Problem: Duplicate points cause zero-length edges and division by zero.

Solution: Preprocess to remove duplicates:

unique_points = np.unique(points, axis=0)

Pitfall 4: Assuming Normalized Coordinates#

Problem: Epsilon comparisons fail on large or small coordinate values.

Solution: Scale epsilon with coordinate magnitude:

# Bad
if abs(cross_product) < 1e-10: ...

# Good
scale = max(abs(coord) for point in [a, b, c] for coord in point)
epsilon = 1e-10 * scale
if abs(cross_product) < epsilon: ...

Pitfall 5: Inefficient Data Structures#

Problem: Using linked lists or dynamic arrays with many allocations.

Solution: Use pre-allocated arrays and index-based access:

# Bad
hull = []
for point in points:
    hull.append(point)  # Repeated allocations

# Good
hull = np.empty(len(points), dtype=int)
hull_size = 0
for i, point in enumerate(points):
    hull[hull_size] = i
    hull_size += 1
hull = hull[:hull_size]  # Trim to actual size once

Summary: The Recommendation#

For 95% of Use Cases#

Use scipy.spatial.ConvexHull (Python) or Qhull (C/C++).

These libraries are:

• Correct and robust
• Fast across diverse inputs
• Well-maintained
• Feature-complete

Do not reinvent the wheel unless you have specific needs (learning, embedded systems, extreme performance tuning).

For Specialized Needs#

Final Advice#

1. Start simple: Use scipy.spatial.ConvexHull unless you have a compelling reason not to.

2. Profile before optimizing: Measure whether convex hull is actually your bottleneck.

3. Test thoroughly: Especially degenerate and numerical edge cases.

4. Understand trade-offs: No algorithm is best for all inputs; choose based on your data distribution.

5. Read the literature: The algorithms in this research are well-studied; stand on the shoulders of giants.

Further Resources#

Essential Reading#

• Computational Geometry: Algorithms and Applications (de Berg et al.) - Comprehensive textbook
• Introduction to Algorithms (CRLS) - Graham Scan and complexity analysis
• Qhull documentation - http://www.qhull.org/ - Implementation details

Papers#

• Graham (1972): Original Graham Scan paper
• Eddy (1977): Quickhull algorithm
• Chan (1996): Optimal output-sensitive algorithm
• Barber, Dobkin, Huhdanpaa (1996): Qhull and robustness techniques

Online Resources#

• SciPy documentation: https://docs.scipy.org/doc/scipy/reference/spatial.html
• CGAL documentation: https://www.cgal.org/
• Wikipedia: Convex hull algorithms (good overview with references)

Implementation Examples#

• scipy/scipy GitHub repository (Cython wrappers)
• Qhull source code (C implementation)
• CGAL examples (C++ with exact arithmetic)

Bottom line: For convex hulls, the problem is solved. Use battle-tested libraries unless you have specific constraints. If implementing yourself, start with Graham Scan for 2D or Qhull for 3D+, and only optimize if profiling shows it’s necessary.

SciPy ConvexHull Implementation#

Overview#

scipy.spatial.ConvexHull is Python’s de facto standard for convex hull computation, providing a high-level interface to the Qhull library. It offers clean NumPy integration, comprehensive output attributes, and excellent performance for scientific computing workflows.

Architecture#

Layered Structure#

scipy.spatial.ConvexHull (Python)
    ↓
scipy.spatial.qhull (Cython wrapper)
    ↓
Qhull C library (underlying engine)

Python layer: High-level API, NumPy array handling, documentation Cython layer: Low-level bindings, memory management, error handling C library: Actual computation via Quickhull algorithm

Core API#

Basic Usage#

from scipy.spatial import ConvexHull
import numpy as np

# Create point array
points = np.array([[0, 0], [1, 0], [1, 1], [0, 1], [0.5, 0.5]])

# Compute hull
hull = ConvexHull(points)

Constructor Signature#

ConvexHull(points, incremental=False, qhull_options=None)

Parameters:

• points: (n, d) array of n points in d-dimensional space
• incremental: Enable incremental mode for adding points later
• qhull_options: String of Qhull command-line options (e.g., “QJ” for joggling)

Output Attributes#

Essential Attributes#

vertices#

hull.vertices  # (nvertices,) array

Indices of points forming the convex hull. Indices reference the original points array.

Example:

hull_points = points[hull.vertices]

simplices#

hull.simplices  # (nsimplex, d) array

Indices of points forming simplicial facets. Each row is one facet.

2D: Each simplex is an edge (2 vertex indices) 3D: Each simplex is a triangle (3 vertex indices) 4D+: Each simplex is a d-dimensional simplex

Example (3D):

# Each row is a triangular facet
for simplex in hull.simplices:
    triangle = points[simplex]  # 3 points forming triangle

equations#

hull.equations  # (nsimplex, d+1) array

Hyperplane equations for each facet: [n₁, n₂, …, nₐ, offset]

For facet i: n·x + offset = 0 defines the hyperplane Points on hull satisfy this equation, interior points have negative value.

Example:

normal = hull.equations[i, :-1]
offset = hull.equations[i, -1]
# Point x is outside facet if: normal @ x + offset > 0

Topological Attributes#

neighbors#

hull.neighbors  # (nsimplex, d) array

Indices of neighboring facets for each facet. -1 indicates no neighbor (boundary in lower-dimensional hull).

Example:

facet_i = 5
adjacent_facets = hull.neighbors[5]  # Facets sharing edge with facet 5

coplanar#

hull.coplanar  # (ncoplanar, 3) array

Points that are coplanar with facets but not vertices. Each row: [point_index, facet_index, distance].

Only populated with certain Qhull options (e.g., “Qc”).

Geometric Attributes#

volume#

hull.volume  # float

Volume of convex hull.

2D: Area 3D: Volume 4D+: Hypervolume

Example:

area = ConvexHull(points_2d).volume  # 2D area
volume = ConvexHull(points_3d).volume  # 3D volume

area#

hull.area  # float

Surface area of convex hull (facets total area).

2D: Perimeter 3D: Surface area 4D+: (d-1)-dimensional measure

Diagnostic Attributes#

ndim#

hull.ndim  # int

Dimension of space (d).

npoints#

hull.npoints  # int

Number of input points (n).

nsimplex#

hull.nsimplex  # int

Number of simplicial facets.

good#

hull.good  # (npoints,) bool array

Boolean mask of points on the hull (True) vs interior (False).

Only populated with option “Qg” (good facets).

Advanced Features#

Incremental Mode#

Add points to existing hull without full recomputation:

# Initial hull
hull = ConvexHull(points, incremental=True)

# Add more points
new_points = np.array([[2, 2], [3, 3]])
hull.add_points(new_points)

# Access updated hull
updated_vertices = hull.vertices

Use cases:

• Streaming data
• Interactive applications
• Dynamic point sets

Performance: O(k log n) per batch of k new points (amortized)

Note: Incremental mode has some memory overhead

Qhull Options#

Pass Qhull command-line options for fine-grained control:

# Joggle input to avoid precision issues
hull = ConvexHull(points, qhull_options="QJ")

# Include coplanar points
hull = ConvexHull(points, qhull_options="Qc")

# Multiple options
hull = ConvexHull(points, qhull_options="QJ Pp")

Common options:

• QJ: Joggle input (add random noise to avoid degeneracies)
• Qt: Triangulated output (always triangular facets in 3D+)
• Qc: Keep coplanar points
• Pp: Don’t report precision problems
• A-0.99: Compute all facets with cosine < 0.99 (nearly flat)

Full reference: http://www.qhull.org/html/qh-quick.htm#options

Point-in-Hull Testing#

No built-in method, but can be implemented via equations:

def point_in_hull(point, hull):
    """
    Check if point is inside convex hull.
    Uses hyperplane equations: point inside if on negative side of all facets.
    """
    # Add tolerance for numerical precision
    tolerance = 1e-12
    return np.all(hull.equations @ np.append(point, 1) <= tolerance)

For many queries, use scipy.spatial.Delaunay (faster point-in-simplex tests).

Performance Characteristics#

Time Complexity#

Inherits from Qhull (Quickhull algorithm):

• Average: O(n log n)
• Worst: O(n²) for circular/spherical distributions
• Best: O(n) when few points on hull

Space Complexity#

O(n) for input and output

Additional overhead:

• NumPy array allocations
• Cython wrapper bookkeeping
• Qhull internal structures

Benchmarks#

Measured on random uniform distributions (3D):

Performance scales well with n for typical distributions.

Memory Usage#

Approximate memory footprint:

Base: 8n bytes (float64 coordinates)
Simplices: 8h bytes (h = hull vertices)
Equations: 8(d+1)h bytes
Total: ~20-50 MB for n=10⁶ points in 3D

Comparison with Alternatives#

ConvexHull vs Delaunay#

from scipy.spatial import Delaunay

tri = Delaunay(points)

Delaunay provides:

• Triangulation of interior (not just boundary)
• Fast point location (find_simplex)
• Neighbor queries

Use Delaunay when:

• Need interior triangulation
• Frequent point-in-hull queries
• Building meshes

Use ConvexHull when:

• Only need boundary
• Want volume/area
• Simpler output structure

ConvexHull vs QHull Direct#

Can call Qhull directly via scipy.spatial.qhull.Qhull:

from scipy.spatial.qhull import Qhull

qhull = Qhull(points, qhull_options="Qt")
# Lower-level access to Qhull internals

ConvexHull advantages:

• Higher-level, easier API
• Standard output format
• Better documentation

Qhull direct advantages:

• More Qhull features exposed
• Finer control
• Advanced use cases

ConvexHull vs Pure Python#

Pure Python implementations (e.g., Graham Scan):

• 10-100x slower than SciPy
• Useful for education or no-dependency scenarios
• Not recommended for production

Common Patterns and Recipes#

Extract Hull Boundary (2D)#

# Points on hull, in order
hull_points = points[hull.vertices]

# Close the loop
hull_boundary = np.vstack([hull_points, hull_points[0]])

Visualize 2D Hull#

import matplotlib.pyplot as plt

plt.plot(points[:, 0], points[:, 1], 'o')
for simplex in hull.simplices:
    plt.plot(points[simplex, 0], points[simplex, 1], 'k-')
plt.show()

Visualize 3D Hull#

from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt

fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.plot_trisurf(points[:, 0], points[:, 1], points[:, 2],
                triangles=hull.simplices, alpha=0.3)
plt.show()

Compute Hull Volume Ratio#

# Ratio of hull volume to bounding box volume
bbox_volume = np.prod(points.max(axis=0) - points.min(axis=0))
fill_ratio = hull.volume / bbox_volume

Filter Points to Hull#

# Keep only hull vertices
hull_points = points[hull.vertices]

# Remove interior points from dataset
mask = np.isin(np.arange(len(points)), hull.vertices)
filtered = points[mask]

Compute Distance to Hull#

def distance_to_hull(point, hull):
    """
    Compute signed distance to hull.
    Negative = inside, positive = outside.
    """
    # Distance to each facet
    distances = hull.equations @ np.append(point, 1)
    # Maximum distance (most violated constraint)
    return distances.max()

Error Handling#

Common Errors#

QhullError: Precision Issues#

from scipy.spatial.qhull import QhullError

try:
    hull = ConvexHull(points)
except QhullError:
    # Retry with joggling
    hull = ConvexHull(points, qhull_options="QJ")

Causes:

• Nearly collinear/coplanar points
• Extreme coordinate values
• Duplicate points

Solutions:

• Use “QJ” option (joggle)
• Preprocess: remove duplicates, scale coordinates
• Increase precision tolerance with “C” option

ValueError: Not Enough Points#

# Need at least d+1 points in d dimensions
if len(points) < points.shape[1] + 1:
    raise ValueError("Insufficient points for convex hull")

MemoryError: Too Many Points/Dimensions#

# Downsample or reduce dimensions
from sklearn.decomposition import PCA

pca = PCA(n_components=3)
reduced_points = pca.fit_transform(points)
hull = ConvexHull(reduced_points)

Integration with NumPy Ecosystem#

Input Flexibility#

# Lists converted to arrays automatically
hull = ConvexHull([[0, 0], [1, 0], [0, 1]])

# Any array-like works
hull = ConvexHull(pd.DataFrame({'x': [...], 'y': [...]}))

Output Integration#

# Slice with hull vertices
hull_coords = points[hull.vertices]

# Boolean indexing
is_on_hull = np.isin(np.arange(len(points)), hull.vertices)
interior = points[~is_on_hull]

# Advanced indexing
facet_points = points[hull.simplices[0]]  # Points of first facet

Vectorized Operations#

# Compute centroid of each facet
facet_centroids = points[hull.simplices].mean(axis=1)

# Check multiple points against hull
def points_in_hull(test_points, hull):
    return np.all(test_points @ hull.equations[:, :-1].T +
                  hull.equations[:, -1] <= 1e-12, axis=1)

Performance Optimization Tips#

Preprocessing#

# Remove duplicate points
unique_points, inverse = np.unique(points, axis=0, return_inverse=True)
hull = ConvexHull(unique_points)
# Map back to original indices if needed
original_vertices = inverse[hull.vertices]

Dimensionality Reduction#

# Project to lower dimension if points are nearly planar
from sklearn.decomposition import PCA

pca = PCA(n_components=3)
reduced = pca.fit_transform(high_d_points)
hull = ConvexHull(reduced)

Batching#

# For very large datasets, sample first
sample_size = 10000
sample_indices = np.random.choice(len(points), sample_size, replace=False)
hull = ConvexHull(points[sample_indices])

Incremental for Streaming#

# Process data in chunks
hull = ConvexHull(initial_batch, incremental=True)
for batch in data_stream:
    hull.add_points(batch)

Limitations and Workarounds#

No Axis-Aligned Bounding Box#

ConvexHull computes general convex hull, not AABB:

# Compute AABB separately
mins = points.min(axis=0)
maxs = points.max(axis=0)

No Oriented Bounding Box#

Use scipy.spatial.distance.cdist with PCA for OBB:

from sklearn.decomposition import PCA

pca = PCA()
pca.fit(points)
rotated = pca.transform(points)
obb_mins = rotated.min(axis=0)
obb_maxs = rotated.max(axis=0)

No Concave Hull#

ConvexHull only computes convex hull. For concave/alpha shapes:

# Use shapely for 2D alpha shapes (not in scipy)
from shapely.ops import cascaded_union
from shapely.geometry import Point

# Create buffer around each point, merge
alpha = 0.1
shapes = [Point(p).buffer(alpha) for p in points]
concave = cascaded_union(shapes).exterior

When to Use SciPy ConvexHull#

Choose SciPy ConvexHull when:

• Working in Python scientific stack (NumPy/SciPy/pandas)
• Need simple, well-documented API
• Want proven, production-ready implementation
• Dimensions 2-8 (Qhull sweet spot)

Consider alternatives when:

• 2D only and want simplest possible code (implement Graham Scan)
• Need exact arithmetic (use CGAL Python bindings)
• High dimensions (d > 10) with specific needs
• Embedded/low-memory environment (use specialized library)

Further Reading#

SciPy documentation: https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html Qhull manual: http://www.qhull.org/html/ Source code: https://github.com/scipy/scipy/blob/main/scipy/spatial/qhull.pyx Examples: SciPy gallery and Stack Overflow convex-hull tag

S3 Need-Driven Research Approach#

Methodology#

The S3 pass focuses on user personas and their needs rather than technical implementation. The goal is to understand who would use convex hull algorithms and why they matter to real-world problems.

Structure#

Each use case file follows a consistent structure:

1. Who Needs This#

Identifies the specific user persona: their role, domain, and context.

2. Problem Context#

Describes the real-world problem the user faces, without assuming they know what a convex hull is. Focuses on:

• The domain-specific challenge
• Why current approaches fall short
• What constraints exist (time, resources, accuracy)

3. Why Convex Hull Matters#

Connects the abstract mathematical concept to concrete user value. Explains:

• What specific property of convex hulls addresses the problem
• How this translates to practical benefit
• What makes this approach better than alternatives

4. Real-World Impact#

Two-part analysis:

• Without: What limitations or failures occur when convex hulls aren’t used
• With: What capabilities or improvements convex hulls enable

This section makes the value proposition explicit and measurable.

5. Decision Factors#

Provides checklist criteria for when this use case applies. Helps users self-identify whether convex hulls are relevant to their specific situation.

Design Principles#

1. User-centric language: Avoid jargon; explain concepts in domain-specific terms
2. Problem-first: Start with the pain point, not the solution
3. Value-focused: Emphasize outcomes over mechanisms
4. No implementation details: FORBIDDEN per S3 requirements
5. Persona specificity: Each use case targets a distinct user role with distinct needs

Coverage Strategy#

The five use cases selected provide:

• Spatial domains: Robotics, GIS (physical space navigation and analysis)
• Visual domains: Computer graphics, Computer vision (rendering and perception)
• Data domains: Data science (abstract multidimensional spaces)

This ensures coverage across the three primary application categories while keeping the set focused and actionable.

Relationship to Other Passes#

• S1 (Rapid): Provides quick implementation examples; S3 provides the “why bother”
• S2 (Comprehensive): Exhaustive algorithmic catalog; S3 provides user context for selection
• S4 (Strategic): High-level architectural guidance; S3 provides ground-level user needs

S3 serves as the bridge between abstract algorithms and concrete user value.

Use Case Recommendations#

Primary Use Cases (High Value, Clear Fit)#

1. Robotics Path Planning#

Strength: Collision detection is a solved problem with convex hulls; well-established theory and implementations.

When to prioritize:

• Real-time constraints are strict
• Safety-critical applications
• Embedded systems with limited computational resources

Key insight: Convex hulls provide the mathematical foundation for configuration space obstacles, enabling provably safe path planning. This isn’t just an optimization—it’s the standard approach.

2. Computer Graphics#

Strength: Rendering pipeline optimizations have decades of refinement; convex hull techniques are battle-tested.

When to prioritize:

• Frame rate is below target (< 60 fps for games)
• Scene complexity increasing (more objects, higher polygon counts)
• Power consumption matters (mobile, VR)

Key insight: LOD systems and occlusion culling via convex hulls are industry standard. Not using them means fighting GPU performance limits.

3. GIS Spatial Analysis#

Strength: Minimum convex polygon is a standardized metric in ecological and geographic research.

When to prioritize:

• Need reproducible boundary definitions
• Comparing spatial extents across studies or time periods
• Working with point data that implies area coverage

Key insight: The convex hull provides the baseline for all other boundary estimation techniques. Even when using more sophisticated methods (alpha shapes, concave hulls), understanding the convex hull baseline is essential.

Secondary Use Cases (Situational Value)#

4. Data Science / ML#

Strength: Non-parametric outlier detection and model boundary analysis.

Caution: High-dimensional data suffers from curse of dimensionality. Convex hulls work well in 2-10 dimensions; beyond that, the hull becomes increasingly meaningless.

When to prioritize:

• Outlier detection on moderate-dimensional data
• Model diagnostics for production ML systems
• Feature space visualization and understanding

Key insight: More valuable for understanding and diagnostics than for production algorithms. Use for insight, not as your primary anomaly detection method.

5. Computer Vision#

Strength: Bridge between low-level pixels and high-level object understanding.

Caution: Modern deep learning approaches often bypass explicit geometric representations. Convex hulls remain relevant for:

• Classical vision pipelines (contour-based)
• Hybrid systems (learning + geometry)
• Resource-constrained systems (embedded vision)

When to prioritize:

• Shape-based recognition is appropriate for the domain
• Real-time performance on limited hardware
• Manufacturing/inspection where geometric priors exist

Key insight: Deep learning has displaced convex hull methods in many vision tasks, but geometric approaches remain relevant for interpretability, efficiency, and domains with strong shape priors.

Selection Guide#

Start here if you are:#

• Robotics engineer: Use case 1 (Path Planning)
• Game developer: Use case 2 (Computer Graphics)
• GIS analyst / Urban planner: Use case 4 (GIS Analysis)
• Data scientist: Use case 3 (Data Science) if working with moderate-dimensional data
• Computer vision engineer: Use case 5 (Computer Vision) if using classical CV pipelines

Critical success factors:#

Rule of thumb: If dimensionality > 10, convex hulls lose effectiveness. If real-time performance isn’t critical, more sophisticated (slower) methods may be preferable.

Common Anti-Patterns#

Don’t use convex hulls when:#

1. The shape is inherently concave: If the object or region you’re modeling has significant concave features that matter for your application, convex hulls will over-approximate unacceptably. (Example: tracking a C-shaped object—the convex hull fills in the gap.)

2. You need exact boundaries: Convex hulls are approximations. If you need pixel-perfect or polygon-exact boundaries, you need different techniques.

3. Dimensionality is very high: In 20+ dimensions, convex hulls of random points approach the entire space. They lose discriminative power.

4. Computational complexity is no concern: If you have unlimited processing time and accuracy is paramount, exact methods are preferable to convex hull approximations.

Next Steps After Reading Use Cases#

1. Identify your persona: Which use case matches your role and problem?
2. Verify decision factors: Do the listed criteria apply to your situation?
3. Consult S2 (Comprehensive): Find specific algorithms for your dimensionality and performance needs
4. Check S1 (Rapid): Get starter implementations for quick prototyping
5. Review S4 (Strategic): Understand architectural implications if building a system

The use cases provide the “why”; the other passes provide the “how” and “what”.

Who Needs This#

Game developers, 3D rendering engineers, and visual effects artists who need to render complex 3D scenes efficiently while maintaining visual quality.

Problem Context#

Modern 3D graphics involve rendering scenes with millions of polygons, often in real-time at 60+ frames per second. Every additional polygon requires computational resources—vertex processing, rasterization, shading. The challenge: maintain visual fidelity while keeping frame rates high and power consumption reasonable.

Furthermore, rendering hidden geometry (objects behind other objects) wastes GPU cycles. Engines must quickly determine which objects are visible to the camera and which can be culled from the rendering pipeline.

Why Convex Hull Matters#

Convex hulls enable critical graphics optimizations:

1. Mesh simplification and LOD: High-detail models are expensive to render at distance or in peripheral vision. The convex hull provides a simplified boundary that can serve as a level-of-detail (LOD) representation. When an object is far away, rendering its convex hull instead of full geometry saves GPU resources without visible quality loss.

2. Occlusion culling: To determine if object A blocks object B from the camera’s view, graphics engines can use convex hull intersection tests. This is far faster than per-polygon occlusion queries. Objects whose convex hulls are entirely behind other solid convex hulls can be skipped entirely.

3. Bounding volume hierarchies: Many rendering optimizations rely on bounding volumes—simple shapes that fully contain complex geometry. Convex hulls provide tighter bounding volumes than axis-aligned boxes or spheres, reducing false positives in intersection tests while still being computationally efficient.

4. Collision detection for physics: Game engines integrate physics simulation. Convex hulls enable fast collision detection between game objects, supporting destructible environments, ragdoll physics, and particle systems.

5. Shadow volume generation: For certain shadow rendering techniques, the convex hull defines the outer boundary from which shadow volumes are projected, simplifying the geometry processing pipeline.

Real-World Impact#

Without convex hull optimizations:

• Frame rates drop, especially in complex scenes
• Draw distance must be reduced (pop-in artifacts)
• Player counts in multiplayer games must be limited
• Visual effects budgets become constrained
• Power consumption increases (battery life for mobile games)

With convex hull-based rendering optimizations:

• Higher polygon counts become feasible
• Larger, more detailed game worlds are possible
• More objects can be rendered simultaneously
• Better frame rate stability
• Improved battery life for mobile and handheld gaming

Decision Factors#

This use case is relevant when:

• Rendering performance is a bottleneck
• Scenes contain many objects with varying levels of detail
• Real-time rendering is required (games, interactive visualization)
• Power consumption is a concern (mobile, VR headsets)
• Visual fidelity must be maintained while reducing computational load

Who Needs This#

Computer vision engineers, image processing specialists, and robotics perception developers who extract meaningful structure from visual data.

Problem Context#

Computer vision systems must convert raw pixel data into understanding: Is that object a car or a pedestrian? Where are its boundaries? What direction is it facing? How is it shaped?

Images provide enormous amounts of data (megapixels), but most of it is redundant or irrelevant. The challenge: extract compact, meaningful representations of object shape and position from noisy, high-dimensional pixel data. These representations must be:

• Invariant to irrelevant changes (lighting, minor viewpoint shifts)
• Sensitive to meaningful changes (object deformation, occlusion)
• Computationally efficient (real-time processing for robotics, autonomous vehicles)

Why Convex Hull Matters#

Convex hulls bridge low-level pixels and high-level understanding:

1. Contour-based object recognition: Vision systems often begin by detecting edges and extracting contours. The convex hull of a contour provides a canonical shape representation—simplified but preserving essential geometry. This enables shape matching, object classification, and pose estimation without getting lost in pixel-level noise.

2. Defect detection in manufacturing: Industrial vision systems inspect products for defects. For many objects (circuit boards, machined parts, packages), the ideal shape is convex or approximately so. Computing the convex hull of the detected object and comparing it to the actual contour reveals concavities that may indicate defects—dents, missing material, improper assembly.

3. Hand gesture recognition: For human-computer interaction, vision systems track hand position and shape. The convex hull of finger contours provides a gesture representation that’s robust to small finger movements. Analyzing hull vertices and their angles enables gesture classification (pointing, grabbing, open palm, etc.).

4. Bounding polygon for object tracking: Object trackers maintain a representation of the tracked object’s position and extent. Convex hulls provide tighter bounding regions than rectangles or ellipses while remaining computationally cheap to update frame-by-frame. This reduces false positives in occlusion detection and improves tracking accuracy.

5. Foreground segmentation: Separating objects from backgrounds often starts with identifying regions of interest. The convex hull of detected foreground pixels provides a consistent, stable region definition that’s less sensitive to noise than raw pixel classifications.

6. 3D reconstruction from silhouettes: Reconstructing 3D shape from multiple 2D images (multi-view geometry) often uses silhouette-based methods. The 3D convex hull consistent with all silhouettes provides a coarse 3D model—a starting point for refinement or a sufficient representation for many applications (grasping, collision avoidance).

Real-World Impact#

Without convex hull analysis:

• Object representations remain pixel-level (noisy, computationally expensive)
• Shape-based recognition less robust to viewpoint and lighting changes
• Defect detection requires pixel-perfect templates (brittle)
• Gesture recognition sensitive to minor finger position variations
• Object tracking bounding boxes too loose (false occlusions) or too tight (tracking loss)

With convex hull-based vision:

• Robust shape representation at intermediate abstraction level
• Efficient shape matching and recognition
• Reliable defect detection with geometric priors
• Stable gesture recognition for interaction systems
• Improved tracking accuracy with better bounding regions
• Faster processing (fewer points to process than raw pixels)

Decision Factors#

This use case is relevant when:

• Processing contour or silhouette data (edge-detected images)
• Shape-based object recognition is required
• Object shape is approximately convex or should be (defect detection)
• Real-time performance is critical (robotics, autonomous systems)
• Intermediate representation needed between pixels and high-level features
• Working with 2D images or 2.5D depth data (not volumetric data)
• Robustness to noise and minor variations is important

Who Needs This#

Data scientists and machine learning engineers who analyze multidimensional datasets to identify patterns, anomalies, and decision boundaries.

Problem Context#

Real-world datasets often contain outliers—data points that don’t fit the expected pattern. These outliers might represent errors (sensor malfunctions, data entry mistakes) or genuine anomalies (fraud, rare diseases, novel phenomena). Identifying which is which is critical for:

• Training machine learning models (outliers can skew learning)
• Quality control (detecting defective products or processes)
• Fraud detection (identifying suspicious transactions)
• Scientific discovery (finding genuinely novel observations)

The challenge: In high-dimensional spaces, “distance from the majority” becomes ambiguous. Traditional metrics like Euclidean distance break down, and visual inspection is impossible beyond 3 dimensions.

Why Convex Hull Matters#

Convex hulls provide a geometric framework for understanding data distribution:

1. Outlier detection: The convex hull defines the minimal boundary containing all data points. Points far outside this boundary, or points that extend the hull disproportionately, are candidate outliers. This provides a non-parametric approach that doesn’t assume any particular distribution shape (unlike Gaussian assumptions).

2. Feature space analysis: In machine learning, features define a multidimensional space. The convex hull of training data in feature space reveals the “coverage” of the training set. New data points outside this hull are extrapolations, not interpolations—the model is being asked to predict beyond its training experience.

3. Clustering and segmentation: Multiple convex hulls can represent distinct clusters in data. The “Peeling” algorithm (iteratively computing and removing outer convex hulls) reveals layered data structure, helping identify cluster cores and boundaries without assuming cluster shape.

4. Support vector machines foundation: SVMs find decision boundaries between classes. The foundational theory relies on separating convex hulls of different classes with maximum-margin hyperplanes. Understanding convex hulls provides intuition for when SVMs will work well.

5. Dimensionality reduction guidance: Techniques like PCA aim to preserve data structure while reducing dimensions. Comparing the convex hull before and after reduction quantifies how much structural information is preserved.

Real-World Impact#

Without convex hull analysis:

• Outlier detection relies on parametric assumptions (may miss non-Gaussian anomalies)
• Model reliability in production is harder to assess
• Cluster analysis limited to spherical or elliptical cluster shapes
• Feature engineering lacks geometric intuition
• Model behavior on edge cases remains opaque

With convex hull-based analysis:

• Non-parametric outlier detection catches distribution-free anomalies
• Clear “in-distribution” vs “out-of-distribution” boundaries for model inputs
• More flexible cluster identification
• Better understanding of feature space coverage
• Improved model diagnostics and failure prediction

Decision Factors#

This use case is relevant when:

• Dataset contains suspected outliers or anomalies
• Model will be deployed in production with unknown input distributions
• Data distribution shape is unknown or non-Gaussian
• Feature engineering requires geometric insight
• Model interpretability and reliability are critical (medical, financial, safety domains)
• Working with 2-10 dimensional data (very high dimensions suffer from curse of dimensionality)

Who Needs This#

Geographic Information Systems (GIS) specialists, urban planners, and cartographers who analyze spatial relationships, service areas, and territorial boundaries.

Problem Context#

Spatial analysis involves questions like:

• What area does a delivery service cover given its depot locations?
• Which territories should emergency response units be assigned to for optimal coverage?
• What is the boundary of a wildlife habitat based on observation points?
• How can we define market areas for competing retail locations?

These questions require converting discrete point locations into meaningful regional boundaries. The boundaries must be:

• Mathematically well-defined (reproducible, not arbitrary)
• Geographically intuitive (reasonable approximations of actual coverage)
• Computationally efficient (large datasets, frequent recalculation)

Why Convex Hull Matters#

Convex hulls provide foundational spatial boundary definitions:

1. Service area approximation: Given customer locations or service request points, the convex hull defines the outer boundary of the served area. This provides a “maximum extent” estimate for service planning, infrastructure placement, and logistics optimization.

2. Territory definition: For administrative or planning purposes, territories often need defined boundaries. Convex hulls of constituent points (e.g., addresses, landmarks, observation sites) provide consistent, reproducible boundary definitions that avoid arbitrary line-drawing.

3. Habitat and range mapping: Wildlife biologists collect observation points (animal sightings, GPS collar data). The convex hull of these points defines the “minimum convex polygon” (MCP)—a standard metric in habitat analysis. While not perfect (it may include unsuitable habitat), it provides a consistent, comparable measure of range size.

4. Site selection and coverage: When planning infrastructure (cell towers, fire stations, distribution centers), the convex hull of existing facility locations reveals coverage gaps. Areas far outside the hull may be underserved.

5. Geometric set operations: Many GIS queries involve set operations on regions (union, intersection, difference). When regions are represented as convex hulls, these operations have efficient geometric algorithms. This enables fast spatial queries like “what areas are served by A but not B?”

6. Data validation: GPS data often contains errors (signal noise, spoofing, multipath errors). Convex hulls of valid historical locations provide a geometric filter—points far outside the expected hull are suspect and warrant closer inspection.

Real-World Impact#

Without convex hull analysis:

• Service areas defined arbitrarily or manually (inconsistent, time-consuming)
• Habitat range estimates vary wildly between studies (not comparable)
• Coverage gap analysis requires expensive manual boundary definition
• Spatial queries rely on approximations (bounding boxes) with poor fit
• Data quality issues harder to detect

With convex hull-based spatial analysis:

• Consistent, reproducible territorial boundaries
• Standardized habitat metrics enable comparative studies
• Automated coverage analysis at scale
• Efficient geometric queries on large datasets
• Built-in data quality checks for outlier points

Decision Factors#

This use case is relevant when:

• Point data represents locations that imply an area (service locations, observations, samples)
• Boundary definition must be reproducible and mathematically justified
• Comparing extents across different datasets or time periods
• Coverage analysis for service planning or resource allocation
• Data quality validation for spatial datasets
• Working with moderate-sized datasets (thousands to millions of points)

Note: For concave or irregular boundaries, convex hulls provide initial estimates. More sophisticated techniques (alpha shapes, concave hulls) may follow for refinement.

Who Needs This#

Robotics engineers and autonomous vehicle developers who design systems that must navigate safely through physical spaces while avoiding obstacles.

Problem Context#

Mobile robots, drones, and autonomous vehicles operate in environments filled with obstacles—walls, furniture, other vehicles, pedestrians. These systems need to compute safe paths that guarantee collision-free movement.

The fundamental challenge: Given the robot’s shape and a set of obstacle locations, determine whether a proposed path would result in a collision. This calculation must happen repeatedly, often in real-time, as the robot moves and the environment changes.

Why Convex Hull Matters#

Convex hulls provide a mathematically rigorous way to represent the outer boundary of an object or obstacle field. For collision detection:

1. Simplified boundary representation: Instead of checking every point on a complex robot shape against every obstacle point, the convex hull reduces this to checking against a minimal set of boundary vertices.

2. Configuration space obstacles: When planning paths, engineers transform physical obstacles into “configuration space” where they represent forbidden positions for the robot’s reference point. Convex hulls of obstacles in this space enable efficient path validity checking.

3. Minkowski sum collision checking: To determine if two objects collide, engineers compute the Minkowski sum of their shapes. When both shapes are convex hulls, this operation is computationally tractable and produces exact collision boundaries.

4. Safety margins: A convex hull naturally provides a conservative approximation—if a path avoids the convex hull, it definitely avoids the actual object. This “safe overestimation” is valuable for safety-critical systems.

Real-World Impact#

Without efficient collision detection via convex hulls:

• Path planning algorithms become prohibitively slow
• Robots must move more slowly to compensate for computational lag
• Safety margins must be increased, reducing operational efficiency
• Complex environments become impractical to navigate

With convex hull-based collision detection:

• Real-time path replanning becomes feasible
• Robots can operate at higher speeds safely
• More complex environments become navigable
• Computational resources can be allocated to other tasks (perception, decision-making)

Decision Factors#

This use case is relevant when:

• The robot/vehicle has a well-defined physical footprint
• The environment contains discrete obstacles or can be discretized
• Real-time or near-real-time path planning is required
• Safety-critical collision avoidance is mandatory
• Computational resources are limited (embedded systems)

S4 Strategic Pass: Methodology#

Purpose#

The S4-strategic pass analyzes long-term viability of libraries over a 5-10 year horizon, evaluating not just current functionality but sustainability, ecosystem health, and strategic fit for production systems.

Evaluation Framework#

1. Maintenance Trajectory#

• Commit frequency: Active development vs maintenance-only vs dormant
• Contributor growth: Growing, stable, or declining community
• Release cadence: Regular releases indicate active stewardship
• Issue/PR management: Responsiveness to bugs and contributions

2. Ecosystem Health#

• Dependency risk: Stable foundations vs rapidly evolving dependencies
• Breaking changes: API stability and semantic versioning practices
• Adoption metrics: Stars, forks, dependents as proxy for usage
• Community size: Support channels, documentation, educational resources

3. Long-term Risks#

• Abandonment risk: Single maintainer vs institutional backing
• Fork potential: License, complexity, community willing to fork
• Technology obsolescence: Language/platform evolution trajectory
• Alternative emergence: Competitive landscape and displacement risk

4. Strategic Fit#

• Language ecosystem trends: Growing, stable, or declining platforms
• Industry adoption: Enterprise use, critical infrastructure, niche tool
• Technical debt: Legacy code burden vs modern practices
• Integration costs: Ease of adoption and migration paths

Analysis Scope#

For each library, we examine:

1. Historical context: Age, origin, major milestones
2. Current state: Recent activity, community health, usage
3. Future outlook: Trajectory, risks, opportunities
4. Recommendation: Production readiness, risk level, strategic considerations

Time Horizon#

This analysis targets decisions with 5-10 year consequences:

• Production systems with multi-year lifespans
• Technical debt accumulation over time
• Migration costs if replacement becomes necessary
• Strategic alignment with platform evolution

Sources#

Analysis draws from:

• GitHub repository metrics (commits, contributors, issues, stars)
• Package registry data (npm, crates.io, PyPI)
• Industry trend analysis and adoption surveys
• Academic and institutional backing
• Developer community sentiment

Risk Categories#

Low Risk: Active development, institutional backing, growing ecosystem Medium Risk: Stable but aging, dependent on broader ecosystem health High Risk: Dormant maintenance, single point of failure, declining ecosystem Critical Risk: Abandoned, security concerns, no migration path

CGAL Long-term Viability Analysis#

Library Overview#

Name: CGAL (Computational Geometry Algorithms Library) Language: C++ Age: 30 years (founded 1996) Purpose: Comprehensive computational geometry (convex hulls, triangulations, boolean operations, mesh processing, etc.) License: Dual (GPL/commercial)

Maintenance Trajectory#

Current State (2026)#

• Repository: github.com/CGAL/cgal
• Latest release: CGAL 6.1.1 (January 26, 2026) - 10 days old
• Commits: 114,989 total
• Contributors: 189 core + 175 additional = 364 total
• Releases: 94 total, released twice per year
• Open issues: 506
• Open PRs: 151

Activity Analysis#

Excellent health indicators:

• Consistent biannual release schedule
• Large, active contributor base
• Continuous development since 1996
• Modern C++ adoption (CGAL 6.0 mandated C++17 in 2024)
• Regular compiler compatibility updates
• Participating in Google Summer of Code 2025

Development Philosophy#

• Robustness: Exact arithmetic, degeneracy handling
• Genericity: Template-based, algorithm customization
• Efficiency: Competitive performance with robustness guarantees

Verdict: ACTIVELY DEVELOPED, EXCELLENT HEALTH#

Ecosystem Health#

Adoption Metrics#

• Stars: 5.7k
• Forks: 1.5k
• Open issues: 506 (high but reflects active usage)
• Open PRs: 151 (community engagement)

Industry Position#

CGAL occupies a unique position as:

• Most comprehensive computational geometry library
• Academic research foundation (papers implement in CGAL)
• Industry standard for robust geometry processing
• Used in CAD, mesh processing, GIS, robotics, graphics

Community Engagement#

• Active discussion forums
• Comprehensive documentation (auto-updated weekly)
• Daily testsuite results published
• Academic integration (cited in thousands of papers)

C++ Ecosystem Fit#

• Modern C++17/C++20 adoption ongoing
• Header-only components for ease of use
• CMake build system (modern practices)
• Conan/vcpkg package manager support

Verdict: STRONG ECOSYSTEM, NICHE DOMINANCE#

Long-term Risks#

Risk 1: Abandonment (LOW)#

Mitigation factors:

• Institutional backing: Joint effort of academic institutions
• Commercial partner: GeometryFactory (founded 2003)
• Multi-stakeholder governance
• Funded by INRIA (French national research institute)
• Historical precedent: 30 years of continuous development

Governance model:

• Academic research groups provide algorithms and theory
• GeometryFactory provides maintenance, support, distribution
• Dual licensing ensures revenue stream

Verdict: Strong structure prevents single-point-of-failure

Risk 2: Technology Obsolescence (MEDIUM)#