Back to Search
Start Over
DETERMINING A SET OF MAXIMUM INSCRIBED RECTANGLES FOR LABEL PLACEMENT IN A REGION.
- Source :
- International Journal of Computational Geometry & Applications; Aug2009, Vol. 19 Issue 4, p341-356, 16p, 14 Diagrams, 1 Chart, 2 Graphs, 1 Map
- Publication Year :
- 2009
-
Abstract
- Driven by the industrial challenge of labeling maps for GIS applications, we investigate the problem of computing a map region P such that a rectangular axis-parallel label L of a given size can be placed in it. The map region to be labeled is in general a non-convex n-gon which may contain holes. We first derive a new practical algorithm based on the sweep-line technique that determines the com set of Maximum Inscribed Rectangles (MIRs) in P in O(nk), where k is the size of the output, for the case when the polygon sides have an axis-parallel orientation. After the set of MIRs has been found, any subsequent query on label L placement runs in only O(logn) time. We then provide an algorithm to convert the general case to the axis-parallel case. Extensive experimentation in both laboratory and industrial settings confirms that the developed method is practical and highly efficient for processing large GIS data sets. [ABSTRACT FROM AUTHOR]
- Subjects :
- ALGORITHMS
GEOMETRY
ALGEBRA
MATHEMATICS
NUMERICAL analysis
Subjects
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 19
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 43919806
- Full Text :
- https://doi.org/10.1142/S021819590900299X