TypeScript library for polygon boolean operations
npm install @avdl/martinezA TypeScript implementation of the Martinez-Rueda-Feito polygon clipping algorithm for Boolean operations on polygons.
- Boolean Operations: Union, intersection, difference, and XOR operations on polygons
- Multi-contour Support: Handles polygons with holes and multiple boundaries
- TypeScript: Full type safety with modern ES modules
- Direct Translation: Based on the C++ reference implementation
- Sweep Line Algorithm: Efficient O(n log n) performance
``bash`
npm install @avdl/martinez
`typescript
import { Martinez, Polygon, BooleanOperationType } from '@avdl/martinez';
// Create polygons
const polygon1 = new Polygon([
[{ x: 0, y: 0 }, { x: 4, y: 0 }, { x: 4, y: 4 }, { x: 0, y: 4 }]
]);
const polygon2 = new Polygon([
[{ x: 2, y: 2 }, { x: 6, y: 2 }, { x: 6, y: 6 }, { x: 2, y: 6 }]
]);
// Perform Boolean operations
const martinez = new Martinez();
const result = martinez.compute(polygon1, polygon2, BooleanOperationType.UNION);
`
- UNION - Combines both polygonsINTERSECTION
- - Returns overlapping areasDIFFERENCE
- - Subtracts second polygon from firstXOR
- - Returns non-overlapping areas
The library generates detailed SVG visualizations for testing complex polygon operations:
Example showing XOR operation between two complex polygons with multiple holes and contours
- Martinez - Main algorithm implementation
- Polygon - Container for polygon contours
- Point - 2D coordinate { x: number, y: number }Segment
- - Line segment between two points
`typescript
type Point = { x: number; y: number };
type Contour = Point[];
type Polygon = { contours: Contour[] };
enum BooleanOperationType {
INTERSECTION,
UNION,
DIFFERENCE,
XOR
}
`
`bashBuild the library
npm run build
Testing
The library includes comprehensive test suites with visual SVG output for debugging complex polygon operations. Test results are generated in the
svg-results/` directory.This library implements the Martinez-Rueda-Feito sweep line algorithm:
1. Event Queue: Processes polygon vertices and intersections in sorted order
2. Sweep Line: Maintains active edge segments during the sweep
3. Intersection Detection: Finds and handles edge crossings
4. Result Construction: Assembles output polygons from processed segments
MIT License - see package.json for details.
- Node.js >= 16.0.0
- TypeScript support for development