Generating Realistic Roofs over a Rectilinear Polygon
作者： Hee-Kap Ahn , Sang Won Bae , Christian Knauer , Mira Lee , Chan-Su Shin
DOI: 10.1007/978-3-642-25591-5_8
关键词:
摘要: Given a simple rectilinear polygon P in the xy-plane, roof over is terrain whose faces are supported by planes through edges of that make dihedral angle π/4 with xy-plane. In this paper, we introduce realistic roofs imposing few additional constraints. We investigate geometric and combinatorial properties roofs, show connection straight skeleton P. maximum possible number distinct $(n-4)/2 \choose \lfloor(n-4)/4\rfloor$ when has n vertices. present an algorithm enumerates representation each such O(1) time per without repetition, after O(n4) preprocessing time. also O(n5)-time for computing minimum height or volume.
springer.com
springerlink.com
acm.org 参考文章(18)
Feifeng Zheng, Stanley P. Y. Fung, Wun-Tat Chan, Francis Y. L. Chin, Chung Keung Poon, Prudence W. H. Wong, Improved on-line broadcast scheduling with deadlines computing and combinatorics conference. pp. 320- 329 ,(2006) , 10.1007/11809678_34
Peter Reinartz, Manfred Lehner, Thomas Krauß, Generation of coarse 3D models of urban areas from high resolution stereo satellite images International Society of Photogrammetry and Remote Sensing. ,(2008)
Oswin Aichholzer, Franz Aurenhammer, David Alberts, Bernd Gärtner, A Novel Type of Skeleton for Polygons Journal of Universal Computer Science. ,vol. 1, pp. 752- 761 ,(1996) , 10.1007/978-3-642-80350-5_65
Niklaus Wirth, Algorithms and data structures 288 p. : ill. Englewood, New Jersey: Prentice-Hall Inc., 1986. includes bibliography and index. ,(1986)
Oswin Aichholzer, Franz Aurenhammer, Straight skeletons for general polygonal figures in the plane Lecture Notes in Computer Science. pp. 117- 126 ,(1996) , 10.1007/3-540-61332-3_144
J-M. Oliva, M. Perrin, S. Coquillart, 3D Reconstruction of Complex Polyhedral Shapes from Contours using a Simplified Generalized Voronoi Diagram Computer Graphics Forum. ,vol. 15, pp. 397- 408 ,(1996) , 10.1111/1467-8659.1530397
R. G. Laycock, A. M. Day, Automatically generating large urban environments based on the footprint data of buildings acm symposium on solid modeling and applications. pp. 346- 351 ,(2003) , 10.1145/781606.781663
Stefan Huber, Martin Held, Theoretical and practical results on straight skeletons of planar straight-line graphs symposium on computational geometry. pp. 171- 178 ,(2011) , 10.1145/1998196.1998223
D. Eppstein, J. Erickson, Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions Discrete and Computational Geometry. ,vol. 22, pp. 569- 592 ,(1999) , 10.1007/PL00009479
Mirela Tanase, Remco C. Veltkamp, Polygon decomposition based on the straight line skeleton symposium on computational geometry. pp. 58- 67 ,(2003) , 10.1145/777792.777802