iOverlay

Introduction

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

Features

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

Source Code

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

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.

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

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 clockwise 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 counterclockwise 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 counterclockwise direction 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 clockwise direction, while inner contours are extracted in a counterclockwise 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

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_{0}\) 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 $$