Overview
Weiler-Atherton clipping can preserve separate output contours and holes by classifying entry and exit intersections.
ExtendedSource checked
Weiler-Atherton Polygon Clipping
Clips complex polygons by walking between subject and clipping polygon boundaries at intersections.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Advanced
- Family
- Polygon Clipping
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 3
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
boundary traversalentry-exit pointpolygon intersectioncontour assembly
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n m)
Average
O(n m)
Worst
O(n m)
Space
O(n + m + intersections)
When to Use
- Use when collision and intersection tests needs boundary traversal.
- Use when the input matches the assumptions behind polygon Clipping.
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
- Clips complex polygons by walking between subject and clipping polygon boundaries at intersections
- Uses boundary traversal and entry-exit point 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
Pseudocode
- 1.Prepare the inputs and state needed for Weiler-Atherton Polygon Clipping.
- 2.Apply the boundary traversal 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
- Weiler-Atherton Polygon Clipping input with a small representative case
- Output
- Geometric relation, simplified shape, or constructed geometry
- Explanation
- Weiler-Atherton Polygon Clipping applies boundary traversal to produce geometric relation, simplified shape, or constructed geometry.
Implementation Notes
- Use robust orientation and tolerance checks for boundary cases.
- Keep the boundary traversal 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 Weiler-Atherton Polygon Clipping 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 Weiler-Atherton Polygon Clipping.
geometry-mechanismNotes
Weiler-Atherton Polygon Clipping should be used with the assumptions and tradeoffs of polygon Clipping in mind.
Sources (3)
What each reference supports for this entry.
Computational Geometry: Algorithms and Applications
BookComputational geometry textbook support for Weiler-Atherton Polygon Clipping's geometric model, data structures, and robustness concerns.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Weiler-Atherton Polygon Clipping's problem context, known alternatives, and practical selection tradeoffs.
Open sourceWeiler-Atherton Polygon Clipping
PaperOriginal reference for clipping concave polygons with holes as part of polygon area sorting.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageIt inserts intersection points between polygon and clipping boundaries.
Alternative toSutherland-Hodgman Polygon Clipping
Weiler-Atherton handles more general polygon clipping cases.
Tags
Computational GeometryPolygon ClippingPolygonsGeometry