© 2004 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
Building Footprint Simplification Techniques and Their Effects on Radio Propagation Predictions
1 Department of Computer & Information Science, Polytechnic University, Brooklyn, NY 11201, USA 2 Department of Informatics & Telecommunications, The University of Athens, 15771, Athens, Greece 3 Department of Electrical & Computer Engineering, Polytechnic University, Brooklyn, NY 11201, USA
Building footprint simplification is of critical importance to radio propagation predictions in wireless communication systems as the prediction time is closely related to the number of both buildings and vertices involved. Intuitively, if the complexity of footprints (i.e. the number of vertices in the footprints) is reduced, predictions can be generated more quickly. However, such reductions often affect the accuracy of results as the simplification error constrains the efficiency that can be achieved. To achieve a good vertex reduction rate for the footprints involved and at the same time preserve the shapes of footprints in terms of their areas, orientations and centroids, we propose a number of efficient single-pass methods to simplify building footprints. To satisfy constraints on edges, areas and centroids of simplified footprints, multi-pass methods are suggested. Hybrid methods take advantage of complementary properties exhibited by different footprint simplification methods. We assess the baseline effectiveness of our proposed techniques, and carry out an extensive comparative evaluation with real geographic information system data from different municipalities. Through experimentation, we find that hybrid methods deliver the best performance in both vertex reduction rate and simplification error. We examine the effects that these footprint simplification methods have on the ray-tracing based radio propagation prediction systems in terms of processing time and prediction accuracy. Our experiments show that footprint simplification methods indeed reduce prediction time up to three-fold, and maintain prediction accuracy with high confidence as well. We also investigate the relationship between footprint simplification error and the prediction accuracy. We find that the prediction accuracy is sensitive to the distortion (i.e. change of shape) of building footprints. This helps us to better understand the trade-off between precision of the building database and the accuracy of predictions generated by ray-tracing based radio propagation prediction systems.
Received 24 September 2002. Revised 29 May 2003.
* Email: zchen{at}milos.poly.edu
Email: