How do I choose between convex hull algorithms?

Based on input sorting and required complexity; Andrew's monotone chain is convenient when you can sort points; Graham scan relies on angle sorting; Jarvis is-optimal in theory but slower in practice.

How do I integrate with my codebase?

Copy the algorithm code blocks or include as a module, adapt point/segment types to your project, and test against the provided input/output schemas.

geometry-algorithm-library

Scanned

npx machina-cli add skill a5c-ai/babysitter/geometry-algorithm-library --openclaw

Files (1)

SKILL.md

1.6 KB

Geometry Algorithm Library Skill

Purpose

Implement computational geometry algorithms for competitive programming and algorithmic problems.

Capabilities

Convex hull (Graham scan, Andrew's monotone chain)
Line intersection algorithms
Closest pair of points
Point in polygon tests
Voronoi diagram, Delaunay triangulation
Polygon clipping

Target Processes

computational-geometry

Algorithm Catalog

Convex Hull

Graham scan O(n log n)
Andrew's monotone chain O(n log n)
Jarvis march O(nh)

Intersection Algorithms

Line sweep for segment intersection
Bentley-Ottmann algorithm
Polygon intersection

Distance Problems

Closest pair of points O(n log n)
Farthest pair (rotating calipers)
Point-polygon distance

Triangulation

Ear clipping O(n^2)
Delaunay triangulation
Voronoi diagram

Input Schema

{
  "type": "object",
  "properties": {
    "algorithm": { "type": "string" },
    "variant": { "type": "string" },
    "language": {
      "type": "string",
      "enum": ["cpp", "python", "java"]
    },
    "includeVisualization": { "type": "boolean", "default": false }
  },
  "required": ["algorithm"]
}

Output Schema

{
  "type": "object",
  "properties": {
    "success": { "type": "boolean" },
    "code": { "type": "string" },
    "complexity": { "type": "object" },
    "usage": { "type": "string" }
  },
  "required": ["success", "code"]
}

Source

git clone https://github.com/a5c-ai/babysitter/blob/main/plugins/babysitter/skills/babysit/process/specializations/algorithms-optimization/skills/geometry-algorithm-library/SKILL.md

View on GitHub

Overview

Provides ready-to-use computational geometry implementations for competitive programming. It covers convex hulls (Graham scan, monotone chain), line intersections, closest pairs, point-in-polygon tests, triangulation, Voronoi and Delaunay diagrams, and polygon clipping. These building blocks help you solve geometry problems quickly and reliably.

How This Skill Works

Algorithms are implemented as modular components (e.g., Graham scan, Andrew's monotone chain, Bentley-Ottmann) that you can swap in based on problem constraints. Each component exposes a consistent API and can be consumed from cpp/python/java using the defined input and output schemas in the SKILL. The library focuses on efficiency and robustness for competitive programming.

When to Use It

When you need the convex hull of a point set for geometry tests or collision detection
When determining if two line segments intersect or computing polygon intersections
When solving distance problems like the closest pair of points or farthest pair with rotating calipers
When you must check whether a point lies inside, outside, or on the boundary of a polygon
When generating triangulations, Voronoi diagrams, or Delaunay triangulations for mesh / spatial analysis

Quick Start

Step 1: Choose an algorithm (e.g., Graham scan for hull) and a language (cpp/python/java).
Step 2: Provide input as a JSON object following the Input Schema, specifying algorithm, variant, language, and options.
Step 3: Run the skill and use the Output Schema to read success, code, complexity, and usage.

Best Practices

Choose the right hull or intersection algorithm based on input size and order (e.g., Graham scan for unsorted data, monotone chain for N log N)
Handle collinear points and degenerate cases explicitly to avoid incorrect results
Use robust numeric types or epsilon tolerances for floating-point coordinates
Validate algorithms with randomized and adversarial tests, including boundary cases
Profile memory and runtime across languages (cpp, Python, Java) and optimize data structures accordingly

Example Use Cases

Collision detection in games and robotics using convex hulls and distance queries
Map rendering and GIS tasks that require polygon clipping and intersection
Mesh generation and spatial analysis using Delaunay triangulation and Voronoi diagrams
Proximity queries and nearest-neighbor problems solved with closest-pair tests
Path planning and visibility graphs leveraging line intersection and polygon operations

Frequently Asked Questions

Add this skill to your agents