Computational Geometry Lecture Notes on Point Location and Trapezoidal Maps
Explore the concept of point location and trapezoidal maps in computational geometry. Understand the query for the face containing a point, trapezoidal map construction, geometric complexity, and data structures for efficient search. Follow along with detailed explanations and visual aids.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Lecture Notes for Introduction to Computational Geometry (Com S 418/518) Yan-Bin Jia, Iowa State University Point Location & Trapezoidal Maps Point Outline: I. Query for the face containing a point II. Trapezoidal map III. Geometric complexity of the map IV. Data structure for search Textbook: Computational Geometry: Algorithms and Applications (3rd ed.) by M. de Berg et al., Springer-Verlag, 2008.
I. Query for Containing Face ?: planar subdivision with ? edges Query: Given a point ?, report face ? such that ? ?. ? ?
Simple Data Structure Draw vertical lines through all the vertices. Slab Sort them by ?-coordinate. Determine the slab containing ?. ?(log?)time ?
Slab No vertices inside a slab Slab Bounded by the vertical lines through two adjacent vertices in the sorted list. ?1 Edges don t cross each other. ?1 ?2 ?2 Order them from top to bottom. ?3 - Store edges intersecting a slab in sorted order (e.g., in an array). ? ?3 ?4 - Label each edge with the face immediately above. ?4 ?5 ?5 ?6
Query Algorithm 1. Determine the slab containing ?. Slab Binary search with ?-coordinate of ?. ? log? ?1 2. Binary search within the slab. ?2 Given a segment ? crossing the slab, determine whether ? is above, below, or on ?. ? ?3 ? segments ? log? time. ?4 Query time is ? log? . ?5
Storage An array on ?-coordinate of vertices. ?(?) An array for every slab. ?(?) ?(?2) ?(?) slabs ?/2slabs (?2)storage! ? 4 Over-refinement of ? for query purpose!
II. Trapezoidal Map General position assumption (removable) No two vertices have the same ?-coordinate. Makes point location query easier. Needs ?(?) storage. axis-parallel rectangle ? Draw a rectangle bounding all segments in its interior. From every point draw two vertical extensions (up and down). Stop when they meet another segment or the boundary of ?. ?(?)
Face of a Trapezoidal Map ? ? Trapezoid Triangle Every face in ?(?) has 2 vertical sides and 2 non-vertical sides. A vertical side is one of two cases: ? - a vertical extension, or - a vertical edge of ?.
Top & Bottom Distinguish the two non-vertical sides. top( ) bottom( )
Classification of the Left Side top( ) top( ) bottom( ) (b) Lower vertical extension (a) Degenerating into a point (c) Upper vertical extension (e) Left edge of ? (d) Upper & lower extension
Defining Endpoint leftp( ) left endpoint of top (b) or left endpoint of bottom (c) or both (a) or right endpoint of a 3rd segment (d) or lower left corner of ? (e) rightp( )can be similarly defined.
Face Description A trapezoid is uniquely determined. top( ) leftp( ) rightp( ) bottom( )
III. Complexity of the Trapezoidal Map Lemma 1?(?) contains 6? + 4 vertices. Proof A vertex is one of three types below: a vertex of ? 4 an endpoint of a segment 2? (shared endpoints may exist) the point where the vertical extension line starting in an endpoint reaches another segment or the boundary of ?. 2 2? Every endpoint generates at most two such points. #vertices 4 + 2? + 4? = 6? + 4
Number of Trapezoids Lemma 2?(?) contains 3? + 1 trapezoids. Proof Every trapezoid is represented by leftp . Need only count leftp , including multiplicities (#times for each endpoint). leftp is one of three possible types: lower left corner of ? it is leftp for exactly 1 trapezoid. right endpoint of a segment (? such points) it is leftp for 1 trapezoid. shared endpoint
(contd) left endpoint of a segment (? such points) leftp for 2 trapezoids. shared endpoint # trapezoids 1 + 1 ? + 2 ? = 3? + 1
Adjacency Trapezoids and are adjacent if they share a vertical edge. 4 1 is adjacent to 1, 2, 3, and 4 but not to 5. 3 2 5 1: upper left neighbor 2: lower left neighbor 3: lower right neighbor 4: upper right neighbor
Adjacency (contd) A trapezoid has 4 neighbors under the general position assumptions. adjacent to along the left vertical edge of . 4 1 3 2 5 top = top or bottom = bottom top = top 1 = top 4 bottom = bottom 2 = bottom 3
IV. Point Location Data Structure ? is a directed acyclic graph (DAG) one root one leaf for every trapezoid two types of internal nodes ?-nodes labeled with an endpoint of some segment ?-nodes labeled with a segment ?1 ? ?1 ?1 ? ? ? ?2 ?2 ? ?2 ? ?
DAG ?2 right left ? ?2 ?1 ?2 ?(?) above below ?1 ?1 ? ? ?1 ? ? ?(?) and ? cross-referenced ? ? ? trapezoid leaf of ? pointer
Query ?2 ? ? ?2 ? ?1 ?2 ?1 ?1 ? ? ?1 ? ? ? ? ? ?
