Intersection of Nonconvex Polygons Using the Alternate Hierarchical Decomposition.
In: Geospatial Thinking; 2010, p1-23, 23p
Buch
Zugriff:
Intersection computation is one of the fundamental operations of computational geometry. This paper presents an algorithm for intersection computation between two polygons (convex/nonconvex, with nonintersecting edges, and with or without holes). The approach is based on the decomposed representation of polygons, alternate hierarchical decomposition (AHD), that decomposes the nonconvex polygon into its convex components (convex hulls) arranged hierarchically in a tree data structure called convex hull tree (CHT). The overall approach involves three operations (1) intersection between two convex objects (2) intersection between a convex and a CHT (nonconvex object) and, (3) intersection between two CHTs (two nonconvex objects). This gives for (1) the basic operation of intersection computation between two convex hulls, for (2) the CHT traversal with basic operation in (1) and, for (3) the CHT traversal with operation in (2). Only the basic operation of intersection of two convex hulls is geometric (for which well known algorithms exist) and the other operations are repeated application of this by traversing tree structures. [ABSTRACT FROM AUTHOR]
Copyright of Geospatial Thinking is the property of Springer Nature / Books and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Titel: |
Intersection of Nonconvex Polygons Using the Alternate Hierarchical Decomposition.
|
---|---|
Autor/in / Beteiligte Person: | Bulbul, Rizwan ; Frank, Andrew U. |
Quelle: | Geospatial Thinking; 2010, p1-23, 23p |
Veröffentlichung: | 2010 |
Medientyp: | Buch |
ISBN: | 978-3-642-12325-2 (print) |
DOI: | 10.1007/978-3-642-12326-9_1 |
Sonstiges: |
|