Abstract
A splinegon is a polygon whose edges have been replaced by "well-behaved" curves. We show how to decompose a simple splinegon into a union of monotone pieces and into a union of differences of unions of convex pieces. We also show how to use a fast triangulation algorithm to test whether two given simple splinegons intersect. We conclude with examples of splinegons that make the extension of algorithms from polygons to splinegons difficult.
Original language | English (US) |
---|---|
Pages (from-to) | 473-485 |
Number of pages | 13 |
Journal | Algorithmica |
Volume | 3 |
Issue number | 1 |
DOIs | |
State | Published - Mar 1 1988 |
All Science Journal Classification (ASJC) codes
- Computer Science(all)
- Computer Science Applications
- Applied Mathematics
Keywords
- Computational geometry
- Convex decomposition
- Curves
- Intersection detection
- Monotone decomposition
- Simplicity testing