iOverlay

Introduction

• The iOverlay is a poly-bool library that supports main operations such as union, intersection, difference, xor, and self-intersection.

Features

• Operations: union, intersection, difference, and exclusion.
• Polygons: with holes, self-intersections, and multiple paths.
• Simplification: removes degenerate vertices and merges collinear edges.
• Buffering: offsets paths and polygons.
• Fill Rules: even-odd, non-zero, positive and negative.

Source Code

• Rust Version: iShape-Rust/iOverlay
• JS Version: iShape-Rust/iShape-js

Demo

This section showcases interactive examples built using iOverlay.

Use the demos below to explore how the library performs boolean operations on 2D shapes in real time.

• Stars Rotation – See overlapping polygons rotate and combine.
• Shapes Editor – Draw and modify shapes live in the browser.
• Stroke – Test stroke generation.
• Outline – Test outline generation.
• Overlay Editor – Wasm interactive editor.

Stars Rotation

Shapes Editor

Stroke

Outline

Overlay Editor

Overlay Editor

Your browser does not support WebGPU.

Please use a WebGPU-supported browser, such as the latest version of Chrome.

Performance Comparison

Benchmark project is here.

For Rust-only solver precision benchmarks, see Rust iOverlay Solver Benchmarks.

All tests were run on a machine with the following specifications:
3 GHz 6-Core Intel Core i5, 40GB 2667 MHz DDR4

All results are presented in seconds.

Solvers:

• iOverlay(Rust) v1.9.0 (multithreading on/off)
• iOverlay(Swift) v1.13.0
• Clipper2(C++) v1.4.0
• Boost(C++) v1.86.0

Checkerboard Test

Not Overlap Test

Lines Net Test

Spiral Test

* There is now boost results for this test

Windows Test

Nested Squares Test

Rust iOverlay Solver Benchmarks

All results were measured on Apple M4, 24 GB. Values are seconds per operation. The benchmark project is in performance/rust_app in the iOverlay repository.

• i16/i32/64 math solvers
• on/off multithreading feature

Average Comparison

Checkerboard Test

Not Overlap Test

Lines Net Test

Spiral Test

Windows Test

Nested Squares Test

Documentation

Filling Rules

Filling rules determine how the interior of a shape is defined. iOverlay supports 4 filling rules:

• Even-Odd: A point is inside the shape if a ray drawn from the point crosses the shape’s edges an odd number of times.
• Non-Zero: A point is inside the shape if the total winding number around the point is non-zero.
• Positive: Only regions with a positive winding number are considered inside.
• Negative: Only regions with a negative winding number are considered inside.

Overlay Rules

Overlay rules define how two shapes interact during Boolean operations:

• Union (A ∪ B): Combines the areas of both shapes.
• Intersection (A ∩ B): Retains only the overlapping area of both shapes.
• Difference (A - B): Subtracts the area of shape B from shape A.
• Exclusion (A ⊕ B): Combines the areas of both shapes but excludes the overlapping region.

Contours

Contours represent the boundaries of shapes and are categorized as:

• Outer Contours: Define the external boundary of a shape, ordered in a counterclockwise direction.
• Inner Contours (Holes): Define holes within a shape, ordered in a clockwise direction.

Overlay Graph

The overlay graph is a data structure that represents the intersections and overlays of two geometric objects. It is constructed by dividing all segments of the object contours into non-intersecting parts, where segments can only touch at their endpoints. Each segment in the graph contains information about its association with the original shapes, facilitating efficient Boolean operations.

Extract Shapes

After applying Boolean operations, the resulting shapes are extracted through a series of steps:

1. Build Contour: Starting from the leftmost node, the algorithm traverses connected segments to form contours, marking each segment as visited to prevent duplication.
2. Define Contour: Determines whether a contour is outer or inner based on its orientation and position.
3. Matching Contours: Associates inner contours with their corresponding outer contours by analyzing spatial relationships.

Filling Rules

Even-Odd

Non-Zero

Positive

Negative

Filling Rules:

• Even-Odd: Only odd numbered sub-regions are filled
• Non-Zero: Only non-zero sub-regions are filled
• Positive: Only positive sub-regions are filled
• Negative: Only negative sub-regions are filled

Overlay Rules

Union, A or B

Intersection, A and B

Difference, A - B

Inverse Difference, B - A

Exclusion, A xor B

Contours

Outer and Inner

In the context of the Overlay Graph, contours are used to represent the boundaries of geometric objects. These contours are classified into two types: outer contours and inner contours.

Outer Contour:

• An outer contour is a sequence of points ordered in a counterclockwise direction.
• The outer contour defines the external boundary of a shape, enclosing the exterior space.

Inner Contour (Hole or Cave):

• An inner contour is a sequence of points ordered in a clockwise direction.
• Inner contours represent enclosed areas within an outer contour, often referred to as “holes” or “caves.”

Both outer and inner contours must be simple, meaning they must not self-intersect and must not share edges with other contours.

Overlay Graph

An Overlay Graph is a data structure representing the intersections and overlays of two geometric objects (A and B) defined by closed contours in 2D space.

The graph is constructed by dividing all the segments of the object contours into non-intersecting parts, where segments can only touch at their endpoints. Each segment in the graph contains the following properties:

• For each side of the segment, it stores information about its membership to object A and object B
• Segments do not intersect each other, but they may touch at their endpoints.

for more Overlay Graph examples see Shape Editor

Filter Segments

Difference, C = A - B

The resulting segments of C must not be inside body B and must belong to body A on one side.
The side associated solely with body A will represent the inner part of the resulting shape.

Difference, C = B - A

The resulting segments of C must not be inside body A and must belong to body B on one side.
The side associated solely with body B will represent the inner part of the resulting shape.

Union, C = A or B

The resulting segments of C must belong to either body A or body B, or to both. The opposite side of each segment must not belong to anybody.
The side associated with one of the bodies will represent the inner part of the resulting shape.

Intersection, C = A and B

The resulting segments of C must belong to both bodies A and B. The opposite side of each segment must not belong to both bodies simultaneously.
The side associated with both bodies A and B will represent the inner part of the resulting shape.

Exclusion, C = A xor B

The resulting segments of C must belong to either body A or body B, but not to both simultaneously. The opposite side of each segment must either belong to both bodies or to neither.
The side associated with one of the bodies (A or B) will represent the inner part of the resulting shape.

Extract Shapes

Once we apply boolean filter to Overlay Graph, we can begin extract contours.

Build Contour

Outer Contour

Inner Contour

The algorithm starts by selecting the leftmost node and proceeds by choosing the topmost segment connected to that node. The process continues by traversing to the next node along the selected segment.

At each node, the algorithm selects the next segment by rotating around the current node in a clockwise/counterclockwise direction for outer/inner contours and taking the first nearest segment.

To prevent segments from being visited twice, each segment is marked as visited upon traversal.

This process continues until the contour is complete, forming either an outer or inner contour.

By following this approach, outer contours are extracted in a counter-clockwise direction, while inner contours are extracted in a clockwise direction.

Define Contour

To define a contour, the algorithm begins by identifying the leftmost and topmost segment in the contour. The classification of the contour is determined as follows:

• If the left-top side of the segment is classified as the outer side, then the contour is an outer contour.
• If the left-top side of the segment is classified as the inner side, then the contour is an inner contour.

This method ensures each contour is correctly classified based on its orientation in 2D space.

Define Shape

A shape is defined as a group of contours, where the first contour is always an outer contour, and the subsequent contours (if any) are inner contours.

Matching Contours

To match inner contours to their corresponding outer contours:

1. Draw a line downward from any point on the inner (target) contour.
2. Identify the first segment encountered along the line that does not belong to the target contour.

• If the segment belongs to an outer contour, that contour is the container for the target contour.
• If the segment belongs to another inner contour, the container of that inner contour is also the container for the target contour.

Define Segment under Point

Segment under Point

To determine whether a segment AB is below a point P, one may be tempted to compute the value of y_m at the point of intersection M, where a vertical line is dropped from P onto AB (i.e., x_p = x_m):

$$ y_{m} = \frac{y_{a} - y_{b}}{x_{a} - x_{b}}\cdot(x_{m} - x_{a}) + y_{a} $$

However, this approach can introduce precision issues due to the division involved.

A more reliable method involves using the order of traversal around the vertices of the triangle APB. If segment AB is below point P, the vertices A, P, and B will appear in a clockwise order.

This method uses the cross product of vectors PA and PB:

$$ a \times b = a_x b_y - a_y b_x $$

Since this method avoids division, it eliminates precision issues, making it stable for determining whether a segment is below a point.

Selecting the Closest Segment under Point

When multiple segments are positioned below point P, we need to determine which segment is the closest to P. This scenario can be divided into three distinct cases based on the configuration of the segments relative to P.

Left Case

When both segments share a common left vertex A, we check the positions of their right endpoints. If the vertices B₀, B₁, and A form a clockwise pattern, then AB₀ is closer to P than AB₁.

Right Case

When both segments share a common right vertex B, we check the positions of their left endpoints. If the vertices A₀, A₁, and B form a clockwise pattern, then A₁B is closer to P than A₀B.

Middle Case

In this case, one of the vertices (e.g., A₁ or B₀) lies inside the opposite segment. We use the point-segment comparison method to determine which of the segments is closer to P.

iTriangle

Introduction

• Easy way to get your triangulation!

Features

• Delaunay triangulation
• Break into convex polygons
• Support any kind of polygons
• Self-Intersection Resolving

Source Code

• Swift Version: iShape-Swift/iTriangle
• Rust Version: iShape-Rust/iTriangle

Demo

This section contains interactive examples that demonstrate how iTriangle performs triangulation and tessellation.

• Triangulation – Basic polygon triangulation.
• Tessellation – Subdivision of polygons into smaller.

Triangulation

Tessellation

Performance Comparison

Benchmark projects are:

• rust
• cpp

All benchmarks were executed on the following machine:
3 GHz 6-Core Intel Core i5, 40GB 2667 MHz DDR4

All results are presented in microseconds (10⁻⁶ sec).

Each test was repeated multiple times, and the average result is shown.

All input shapes are clean (non-self-intersecting), and the logic was optimized to achieve maximum performance.

Solvers

• iTriangle (Earcut64, Rust) v0.36.3 — raw triangulation, no holes, limited to ≤64 points, validation disabled
• iTriangle (Monotone, Rust) v0.36.3 — raw triangulation, validation disabled
• iTriangle (Delaunay, Rust) v0.36.3 — Delaunay triangulation, validation disabled
• MapBox (Earcut Rust) v0.5.0 – Rust port – raw triangulation, validation disabled
• MapBox (Earcut C++) v2.2.4 – C++ official – raw triangulation, validation disabled
• Triangle (Delaunay C) v1.6 – C official - constrained Delaunay triangulation, validation disabled

Star Test

Raw

Delaunay

Spiral Test

Raw

Delaunay

Star with Hole Test

Raw

Delaunay

Star with 8 holes Test

Raw

Delaunay

Delaunay

Delaunay

Click on the canvas to drag the points

What is the Delaunay Condition?

When creating a triangulation network, the Delaunay condition aims to form triangles such that their circumscribed circles do not contain any other points from the dataset. In simpler terms, it ensures that triangles are “well-shaped” rather than “skinny,” making the network more balanced and useful for various applications.

If the condition \(\alpha + \beta < \pi\) holds, it implies that the point \(P\) will lie outside the circumscribed circle. This confirms that a pair of triangles satisfies the Delaunay condition.

$$ \alpha + \beta < \pi \Rightarrow \sin(\alpha + \beta) > 0 $$

$$ \sin(\alpha + \beta) = \sin(\alpha)\cos(\beta) + \cos(\alpha)\sin(\beta) $$

Calculating \(\cos(\alpha)\) and \(\sin(\alpha)\):

$$ \cos(\alpha) = \frac{\vec{a} \cdot \vec{b}}{|a||b|} = \frac{a_{x}b_{x} + a_{y}b_{y}}{|a||b|} $$

$$ \sin(\alpha) = \sqrt{1- \cos^2(\alpha)} = … = \frac{|a_{x}b_{y} - b_{x}a_{y}|}{|a||b|} = \frac{|\vec{a} \times \vec{b}|}{|a||b|} $$

Calculating \(\cos(\beta)\) and \(\sin(\beta)\):

$$ \cos(\beta) = \frac{\vec{c} \cdot \vec{d}}{|c||d|} = \frac{c_{x}d_{x} + c_{y}d_{y}}{|c||d|} $$

$$ \sin(\beta) = \frac{|\vec{c} \times \vec{d}|}{|c||d|} = \frac{|c_{x}d_{y} - d_{x}c_{y}|}{|c||d|} $$

Final Equation:

$$ \sin(\alpha + \beta) = \frac{|a_{x}b_{y} - b_{x}a_{y}|\cdot(c_{x}d_{x} + c_{y}d_{y}) + (a_{x}b_{x} + a_{y}b_{y})\cdot|c_{x}d_{y} - c_{x}d_{y}|}{|a||b||c||d|} > 0 $$

$$ |a_{x}b_{y} - b_{x}a_{y}|\cdot(c_{x}d_{x} + c_{y}d_{y}) + (a_{x}b_{x} + a_{y}b_{y})\cdot|c_{x}d_{y} - d_{x}c_{y}| > 0 $$

Or in vector form:

$$ |\vec{a} \times \vec{b}|(\vec{c} \cdot \vec{d}) + (\vec{a} \cdot \vec{b})|\vec{c} \times \vec{d}| > 0 $$