|
|||||
|
|
Decomposition and intersection of simple splinegons |
|
| Authors: | David P Dobkin Diane L Souvaine and Christopher J Van Wyk |
| Affiliation: | (1) Department of Computer Science, Princeton University, 08544 Princeton, NJ, USA;(2) Present address: Department of Computer Science, Rutgers University, 08903 New Brunswick, NJ, USA;(3) AT&T Bell Laboratories, 07974 Murray Hill, NJ, USA |
| 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.Work on this paper by David A. Dobkin and Diane L. Souvaine was partially supported by National Science Foundation Grants MCS 83-03926 and DCR 85-05517. Diane L. Souvaine was also partially supported by an Exxon Foundation Fellowship. |
| Keywords: | Computational geometry Curves Simplicity testing Intersection detection Monotone decomposition Convex decomposition |
| 本文献已被 SpringerLink 等数据库收录！ | |