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. This algorithm is based on Vatti clipping ideas but is an original implementation.
Features
- Supports all basic operations union, intersection, difference, exclusion and self-intersection.
- Support any kind of polygons
- Remove removing unnecessary vertices and merging parallel edges
- Deterministic
Source Code
- Swift Version: iShape-Swift/iOverlay
- Rust Version: iShape-Rust/iOverlay
- JS Version: iShape-Rust/iShape-js
Filling Rules
Even-Odd
Non-Zero
Filling Rules:
- Even-Odd: Only odd numbered sub-regions are filled
- Non-Zero: Only non-zero sub-regions are filled
Overlay Rules
Union, A or B
Intersection, A and B
Difference, B - A
Exclusion, A xor B
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
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 $$