AlGeo - Computational Geometry Library

A modern C++20 computational geometry library implementing fundamental 2D geometric algorithms with performance optimizations via SIMD (AVX2) support.

Features

Core Data Structures

• Point: 2D point representation with floating-point coordinates
• Line: Line segment between two points with length calculation
• Contur: Boundary/outline computation for point sets

Algorithms

Convex Hull - Graham Scan

• File: ConvexHull.h/cpp
• Time Complexity: O(n log n)
• Space Complexity: O(n)
• Description: Computes the convex hull of a point set using the Graham scan algorithm
  1. Find the point with minimum y-coordinate
  2. Sort points by polar angle relative to the starting point
  3. Process points in order, maintaining a stack of hull vertices
  4. Remove points that create right turns (non-convex angles)
• Advantages: Simple, efficient, handles collinear points well

Bentley-Ottmann Sweep Line Algorithm

• File: Sweep.h/cpp
• Time Complexity: O((n + k) log n) where k is the number of intersections
• Space Complexity: O(n)
• Description: Finds all intersection points between line segments
• Features:
  • Event-based processing for start/end points and intersections
  • Improved sweep status structure using std::set (O(log n) lookups) instead of std::list (O(n) lookups)
  • Duplicate intersection prevention
  • Automatic segment swap on intersection

Point-in-Polygon Tests

• File: PointInPolygon.h/cpp
• Time Complexity: O(n) where n is the number of polygon vertices
• Description: Multiple algorithms for point-in-polygon detection

Ray Casting Algorithm

• Fast and efficient for most cases
• Casts a horizontal ray from the point to infinity
• Counts edge crossings
• Variants:
  • isPointInPolygon(): Returns true if point is inside or on boundary
  • isPointStrictlyInPolygon(): Returns true only if strictly inside (boundary excluded)

Winding Number Algorithm

• More robust for complex and concave polygons
• Counts how many times the polygon winds around the point
• Returns winding number (0 if outside, non-zero if inside)
• Better for self-intersecting polygons

Geometry Utilities

• File: GeometryUtils.h/cpp
• Description: Common geometric utility functions

Polygon Area (Shoelace Formula)

• Function: polygonArea()
• Complexity: O(n)
• Formula: Area = 0.5 * |Σ(x_i * y_{i+1} - x_{i+1} * y_i)|
• Signed Version: polygonSignedArea() returns negative for clockwise, positive for counter-clockwise

Polygon Perimeter

• Function: polygonPerimeter()
• Complexity: O(n)
• Description: Sums the lengths of all edges

Closest Point on Segment

• Functions:
  • closestPointOnSegment(): Returns the point on segment closest to a given point
  • squaredDistanceToSegment(): Returns squared distance (faster, avoids sqrt)
  • distanceToSegment(): Returns actual distance
• Complexity: O(1)
• Description: Uses parametric representation and clamping to find projection

Basic Predicates

• File: Algorithms2D.h/cpp
• Cross Product: Computes 2D cross product for orientation testing
• Half-Plane Test: Determines if a point is LEFT/RIGHT/COLINEAR to a directed line segment
  • Single point: O(1)
  • Vectorized version: Processes 8 points in parallel using AVX2 (O(1) per 8 points)
• Point-on-Segment: Checks if a point lies on a line segment
• Segment Intersection: Returns intersection point if segments intersect

Performance Optimizations

SIMD Vectorization

• Conditional Compilation: Enable with -DUSE_SIMD=1
• Supported Operations:
  • Half-plane test for 8 points simultaneously
  • Requires compiler flags: -mavx2 -O3 -mfma
• Benefits: 8x speedup for batch geometric tests

Data Structure Improvements

• Sweep status structure upgraded from std::list (O(n)) to std::set (O(log n))
• Reduces Bentley-Ottmann complexity for practical instances

Usage Examples

Convex Hull

#include "ConvexHull.h"

std::vector<Point> points = {
    {2, 4}, {5, 3}, {8, 3}, {9, 2}, {11, 3}
};

std::vector<Point> hull = convexHull(points);
// Returns: {2, 4}, {5, 3}, {9, 2}, {11, 3}

Point in Polygon

#include "PointInPolygon.h"

std::vector<Point> polygon = {
    {0, 0}, {4, 0}, {4, 4}, {0, 4}
};

Point test(2, 2);
bool inside = isPointInPolygon(test, polygon);  // true
bool strict = isPointStrictlyInPolygon(test, polygon);  // true

Point boundary(2, 0);
inside = isPointInPolygon(boundary, polygon);  // true
strict = isPointStrictlyInPolygon(boundary, polygon);  // false

Polygon Properties

#include "GeometryUtils.h"

std::vector<Point> polygon = {
    {0, 0}, {3, 0}, {3, 4}, {0, 4}
};

fbase area = polygonArea(polygon);  // 12.0
fbase perimeter = polygonPerimeter(polygon);  // 14.0

Closest Point on Segment

#include "GeometryUtils.h"

Line segment({0, 0}, {4, 0});
Point query(2, 3);

Point closest = closestPointOnSegment(query, segment);  // (2, 0)
fbase dist = distanceToSegment(query, segment);  // 3.0

Building the Project

Prerequisites

• C++20 compatible compiler (GCC 10+, Clang 12+, MSVC 2019+)
• CMake 3.15+
• GoogleTest (automatically downloaded via FetchContent)

Build Steps

mkdir build
cd build
cmake ..
cmake --build .

Enable SIMD Optimization

cmake -DUSE_SIMD=1 ..
cmake --build .

Running Tests

./build/test/UnitTest

Code Quality & Testing

Test Coverage

• Comprehensive unit tests for all algorithms
• Edge case testing:
  • Degenerate cases (collinear points, zero-length segments)
  • Boundary conditions (points on edges/vertices)
  • Duplicate points
  • Empty/minimal inputs
• Uses GoogleTest framework for robust test infrastructure

Improvements Made

1. ✅ Fixed Line::length() bug: Changed subtraction to addition in distance formula
2. ✅ Upgraded Convex Hull: Implemented Graham scan algorithm (simpler, more efficient)
3. ✅ Added Point-in-Polygon: Implemented both ray-casting and winding number algorithms
4. ✅ Added Geometry Utilities: Polygon area, perimeter, closest point calculations
5. ✅ Optimized Sweep Status: Replaced O(n) list with O(log n) balanced BST (std::set)
6. ✅ Enhanced Testing: Added comprehensive test suites for new algorithms
7. ✅ Improved Documentation: Added Doxygen-style comments throughout

Architecture

AlGeo/
├── src/
│   ├── Core Data Structures
│   │   ├── Point.h/cpp
│   │   ├── Line.h/cpp
│   │   └── Contur.h/cpp
│   ├── Algorithms
│   │   ├── ConvexHull.h/cpp
│   │   ├── Sweep.h/cpp
│   │   ├── PointInPolygon.h/cpp
│   │   ├── GeometryUtils.h/cpp
│   │   └── Algorithms2D.h/cpp
│   ├── Utilities
│   │   ├── Definitions.h
│   │   └── AlGeoCommon.h
│   └── Tests (*_test.cpp)
├── test/
│   ├── CMakeLists.txt
│   └── main.cpp
├── CMakeLists.txt
└── README.md

Complexity Summary

Algorithm	Time	Space	Notes
Convex Hull (Graham)	O(n log n)	O(n)	Optimal for general case
Sweep Line (Bentley-Ottmann)	O((n+k) log n)	O(n)	k = intersections
Point in Polygon	O(n)	O(1)	Works for any polygon
Polygon Area (Shoelace)	O(n)	O(1)	Signed area available
Closest Point (Segment)	O(1)	O(1)	Constant time projection
Half-Plane Test	O(1)	O(1)	Single point
Half-Plane Test (Vectorized)	O(1) per 8	O(8)	With AVX2

Future Enhancements

Planned Features

• Delaunay triangulation
• Voronoi diagram computation
• KD-tree spatial indexing
• Polygon clipping (Sutherland-Hodgman)
• AVX2 optimization for more algorithms

References

Algorithm Papers & Resources

• Graham Scan: R. L. Graham, "An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set" (1972)
• Bentley-Ottmann: J. L. Bentley & T. A. Ottmann, "Algorithms for Reporting and Counting Geometric Intersections" (1979)
• Ray Casting: Various computational geometry texts
• Shoelace Formula: A. M. Bruckstein & J. L. Poreda (1991)
• Fernuni Hagen Algorithmic Geometry

---

Last Updated: January 2025 Version: 1.0