Overview
Ear clipping finds a convex vertex whose triangle contains no other polygon vertices, emits that triangle, and removes the vertex.
CoreSource checked
Ear Clipping Triangulation
Triangulates a simple polygon by repeatedly removing valid ears.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Intermediate
- Family
- Triangulation
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
simple polygonconvex vertexear triangletriangulation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n^2)
Average
O(n^2)
Worst
O(n^3)
Space
O(n)
When to Use
- Use when collision and intersection tests needs simple polygon.
- Use when the input matches the assumptions behind triangulation.
When Not to Use
- Avoid when floating-point robustness is critical and no tolerance strategy is defined.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Triangulates a simple polygon by repeatedly removing valid ears
- Uses simple polygon and convex vertex to guide the work.
- Produces geometric relation, simplified shape, or constructed geometry.
Use Cases
- Collision and intersection tests
- Shape analysis
- Geometry processing
Inputs
- Points, segments, polygons, or meshes
- Query shape or tolerance
Outputs
- Geometric relation, simplified shape, or constructed geometry
Key Formulas (1)
Ear validity
isconvex(v) and no polygon vertex lies inside triangle(prev, v, next)
is_convex(v) and no polygon vertex lies inside triangle(prev, v, next)Determines whether a vertex can be clipped safely.
Pseudocode
- 1.Prepare the inputs and state needed for Ear Clipping Triangulation.
- 2.Apply the simple polygon step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return geometric relation, simplified shape, or constructed geometry.
Canonical Example
- Input
- Ear Clipping Triangulation with a minimal inspectable input
- Output
- Geometric relation, simplified shape, or constructed geometry
- Explanation
- Ear Clipping Triangulation applies simple polygon to produce geometric relation, simplified shape, or constructed geometry.
Implementation Notes
- Use robust orientation and tolerance checks for boundary cases.
- Keep the simple polygon step separate enough to test independently.
Common Pitfalls
- Degenerate cases such as collinear points or shared edges often need explicit handling.
- Forgetting to check edge cases can make Ear Clipping Triangulation look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasDraw the input shapes, active tests, and generated geometric result.
Step 1 of 4: Prepare the inputs and state needed for Ear Clipping Triangulation.
geometry-mechanismNotes
Ear Clipping Triangulation should be used with the assumptions and tradeoffs of triangulation in mind.
Sources (2)
What each reference supports for this entry.
Computational Geometry: Algorithms and Applications
BookComputational geometry textbook support for Ear Clipping Triangulation's geometric model, data structures, and robustness concerns.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Ear Clipping Triangulation's problem context, known alternatives, and practical selection tradeoffs.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toDelaunay Triangulation
Ear clipping triangulates polygons without optimizing Delaunay criteria.
UsesPoint in Polygon
Ear clipping checks whether candidate ears contain other polygon vertices.
Related Algorithms
Tags
Computational GeometryTriangulationPolygonsGeometry