# Intersection of Nonconvex Polygons Using the Alternate Hierarchical Decomposition

Rizwan Bulbul*, Andrew U. Frank

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

## Abstract

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.
Original language English Geospatial Thinking Marco Painho Berlin Springer Verlag 1 1-23 978-3-642-12326-9 978-3-642-12325-2 https://doi.org/10.1007/978-3-642-12326-9_1 Published - 31 Mar 2010 Yes 13th AGILE International Conference on Geographic Information Science - Guimarães, PortugalDuration: 10 May 2010 → 14 May 2010

### Publication series

Name Lecture Notes in Geoinformation and Cartography

### Conference

Conference 13th AGILE International Conference on Geographic Information Science AGILE 2010 Portugal Guimarães 10/05/10 → 14/05/10

## Fingerprint

Dive into the research topics of 'Intersection of Nonconvex Polygons Using the Alternate Hierarchical Decomposition'. Together they form a unique fingerprint.