当前课程知识点:计算几何 > 05. Delaunay Triangulation > I. RIC With Example > 05-I-02. Point Location
假设 我们已经立足于
这样一个基本成形的三角剖分
它是由六个点所构成的
现在我们要插入第七个点
那么我们要做的第一项工作
就是point location 点定位
在后面我们还会专门有一章
来介绍这个问题
也就是当你任意的
给定了一个点以后
如何确定
它在背景的那个subdivision中
位于哪个face
或者说三角形内部
那现在呢
我们假设这个是可以做
包括后面我们会看到
我们实际上在这里
用的是一个很简明的一个方法
就能帮助我们做这件事
来确定每一个点
每一个新插入的这个G
到底是落在哪个三角形内部
当然 我们可以明确的是
我们这里所依赖的
依然是基本的DCEL结构
双向链接编表
当然相应的
我们还要再附加一种策略
也就是待会我们会介绍的
分统策略
如果你像我一样
虽然学习数据结构和算法
但实际上非常讨厌
滥用那种所谓高级的玩意
有的时候用简明的方法
实际上效率反而会更高
至少在理论上
介绍的时候会更加思路清晰
我们待会就是这么做的
好 第二个问题就是
我们这样的一个point location
不仅要是可行的
而且本身它作为整个算法中
反复要做的一个基本的步骤
也要足够快才行
它能够足够快吗
表面看是难免会有这种担忧的
但是正像刚才我们引用的
Guibas和Knuth的
那种证明一样
待会我们会通过
另一种简明的方法
来给出一个
足够让你有信心的一个证明
可以说明它确实是足够快的
虽然这个证明本身有些复杂
-Before we start
--html
-Evaluation
--html
-Online Judge
--html
-Lecture notes
--html
-Discussion
--html
-A. History of This Course
--00-A. History of This Course
-B. What's Computational Geometry
--00-B. What's Computational Geometry
-B. What's Computational Geometry--作业
-C. How to Learn CG Better
--00-C. How to Learn CG Better
-C. How to Learn CG Better--作业
-D. Why English
-A. Convexity
-A. Convexity--作业
-B. Extreme Points
-B. Extreme Points--作业
-C. Extreme Edges
-C. Extreme Edges--作业
-D. Incremental Construction
--01-D-01. Decrease and Conquer
--01-D-02. In-Convex-Polygon Test
--01-D-03. Why Not Binary Search
-D. Incremental Construction--作业
-E. Jarvis March
--01-E-06. Lowest-Then-Leftmost
-E. Jarvis March--作业
-F. Lower Bound
--01-F-02. CAO Chong's Methodology
-F. Lower Bound--作业
-G. Graham Scan: Algorithm
-G. Graham Scan: Algorithm--作业
-H. Graham Scan: Example
-H. Graham Scan: Example--作业
-I. Graham Scan: Correctness
-I. Graham Scan: Correctness--作业
-J. Graham Scan: Analysis
-J. Graham Scan: Analysis--作业
-K. Divide-And-Conquer (1)
-K. Divide-And-Conquer (1)--作业
-L. Divide-And-Conquer (2)
--01-L-03. Topmost + Bottommost ?
--01-L-07. More Considerations
-L. Divide-And-Conquer (2)--作业
-M. Wrap-Up
-0. Introduction
-0. Introduction--作业
-A. Preliminary
-A. Preliminary--作业
-B. Interval Intersection Detection
-B. Interval Intersection Detection--作业
-C. Segment Intersection Reporting
-C. Segment Intersection Reporting--作业
-D. BO Algorithm: Strategy
--02-D-01. Proximity & Separability
--02-D-02. Comparability & Ordering
-D. BO Algorithm: Strategy--作业
-E. BO Algorithm: Implementation
--02-E-03. Events & Operations
-E. BO Algorithm: Implementation--作业
-F. BO Algorithm: Analysis
--02-F-04. Complexity of Event Queue
--02-F-05. Complexity of Status Structure
-F. BO Algorithm: Analysis--作业
-G. Convex Polygon Intersection Detection
--02-G-01. Problem Specification
--02-G-02. Monotone Partitioning
--02-G-04. Decrease-And-Conquer
-G. Convex Polygon Intersection Detection--作业
-H. Edge Chasing
--02-H-01. Eliminating Sickles
-H. Edge Chasing--作业
-I. Plane Sweeping
-I. Plane Sweeping--作业
-J. Halfplane Intersection Construction
-J. Halfplane Intersection Construction--作业
-0. Methodology
-0. Methodology--作业
-A. Art Gallery Problem
--03-A-02. Lower & Upper Bounds
--03-A-04. Approximation & Classification
-A. Art Gallery Problem--作业
-B. Art Gallery Theorem
--03-B-01. Necessity of floor(n/3)
--03-B-02. Sufficiency by Fan Decomposition
-B. Art Gallery Theorem--作业
-C. Fisk's Proof
--03-C-04. Pigeon-Hole Principle
-C. Fisk's Proof--作业
-D. Orthogonal Polygons
--03-D-01. Necessity of floor(n/4)
--03-D-02. Sufficiency by Convex Quadrilateralization
-D. Orthogonal Polygons--作业
-E. Triangulation
-E. Triangulation--作业
-F. Triangulating Monotone Polygons
--03-F-02. Monotonicity Testing
--03-F-04. Stack-Chain Consistency
-F. Triangulating Monotone Polygons--作业
-G. Monotone Decomposition
-G. Monotone Decomposition--作业
-I. Tetrahedralization
--03-I-01. Polyhedron Decomposition
--03-I-02. Schonhardt's Polyhedron
-I. Tetrahedralization--作业
-A. Introduction
--04-A-02. Dining Halls on Campus
--04-A-03. More Analogies & Applications
-A. Introduction--作业
-B. Terminologies
--04-B-02. Intersecting Halfspaces
--04-B-04. Planar Voronoi Diagram
-B. Terminologies--作业
-C. Properties
--04-C-03. Nearest = Concyclic
--04-C-04. Number of Nearest Sites = Degree
-C. Properties--作业
-D. Complexity
-D. Complexity--作业
-E. Representation
-E. Representation--作业
-F. DCEL
-F. DCEL--作业
-G. Hardness
--04-G-03. Voronoi Diagram In General Position
-G. Hardness--作业
-H. Sorted Sets
--04-H-01. Convex Hull Made Easier
--04-H-02. Convex Hull As A Combinatorial Structure
--04-H-03. Voronoi Diagram As A Geometric Structure
-H. Sorted Sets--作业
-I. VD_sorted
--04-I-06. Sorting Not Made Easier
-I. VD_sorted--作业
-J. Naive Construction
-J. Naive Construction--作业
-K. Incremental Construction
-K. Incremental Construction--作业
-L. Divide-And-Conquer
--04-L-09. Intersecting with Cells
-L. Divide-And-Conquer--作业
-M. Plane-Sweep
--04-M-09. Circle Event: What, When & Where
-M. Plane-Sweep--作业
-A. Point Set Triangulation
-A. Point Set Triangulation--作业
-B. Delaunay Triangulation
-B. Delaunay Triangulation--作业
-C. Properties
-C. Properties--作业
-D. Proximity Graph
--05-D-02. Relative Neighborhood Graph
-D. Proximity Graph--作业
-E. Euclidean Minimum Spanning Tree
-E. Euclidean Minimum Spanning Tree--作业
-F. Euclidean Traveling Salesman Problem
-G. Minimum Weighted Triangulation
-G. Minimum Weighted Triangulation--作业
-H. Construction
--05-H-03. Maximizing The Minimum Angle
--05-H-04. Evolution By Edge Flipping
-H. Construction--作业
-I. RIC With Example
-I. RIC With Example--作业
-J. Randomized Incremental Construction
--05-J-01. Recursive Implementation
--05-J-02. Iterative Implementation
-J. Randomized Incremental Construction--作业
-K. RIC Analysis
--05-K-04. Types Of Edge Change
--05-K-05. Number Of Edge Changes
--05-K-07. Number Of Rebucketings
--05-K-08. Probability For Rebucketing
--05-K-10. Further Consideration
-0. Online/Offline Algorithms
--06-0. Online/Offline Algorithms
-0. Online/Offline Algorithms--作业
-A. Introduction
--06-A-03. Assumptions For Clarity
--06-A-05. Performance Measurements
-A. Introduction--作业
-B. Slab Method
--06-B-02. Ordering Trapezoids
-B. Slab Method--作业
-C. Persistence
--06-C-01. Ephemeral Structure
--06-C-02. Persistent Structure
-C. Persistence--作业
-D. Path Copying
--06-D-03. Storage Optimization
-D. Path Copying--作业
-E. Node Copying
-E. Node Copying--作业
-F. Limited Node Copying
-G. Kirkpatrick Structure
--06-G-01. Optimal And Simpler
--06-G-06. The More The Better
--06-G-07. The Fewer The Better
--06-G-09. Existence Of Independent Subset
--06-G-10. Construction Of Independent Subset
-G. Kirkpatrick Structure--作业
-H. Trapezoidal Map
--06-H-03. Properties & Complexity
--06-H-04. Search Structure: Example
--06-H-05. Search Structure: Nodes
--06-H-06. Search Structure: Performance
-H. Trapezoidal Map--作业
-I. Constructing Trapezoidal Map
--06-I-04. Case 1: Two Endpoints
--06-I-05. Case 2: One Endpoint
--06-I-06. Case 3: No Endpoints
-J. Performance Of Trapezoidal Map
--06-J-03. Number Of Ray Trimmed
--06-J-04. Number Of Trapezoidals Created (1)
--06-J-05. Number Of Trapezoidals Created (2)
--06-J-06. Time For Point Location
--06-J-07. Size Of Search Structure
--06-J-08. Fixed Query Point + Randomly Created Maps
--06-J-10. Probability Of Enclosing Trapezoid Changed
-A. Range Query
--07-A-01. 1-Dimensional Range Query
-A. Range Query--作业
-B. BBST
--07-B-02. Lowest Common Ancestor
-B. BBST--作业
-C. kd-Tree: Structure
-C. kd-Tree: Structure--作业
-D. kd-Tree: Algorithm
-D. kd-Tree: Algorithm--作业
-E. kd-Tree: Performance
--07-E-01. Preprocessing Time + Storage
-E. kd-Tree: Performance--作业
-F. Range Tree: Structure
--07-F-03. x-Query * y-Queries
-F. Range Tree: Structure--作业
-G. Range Tree: Query
-G. Range Tree: Query--作业
-H. Range Tree: Performance
-H. Range Tree: Performance--作业
-I. Range Tree: Optimization
--07-I-04. Fractional Cascading
-A. Orthogonal Windowing Query
-A. Orthogonal Windowing Query--作业
-B. Stabbing Query
-C. Interval Tree: Construction
-C. Interval Tree: Construction--作业
-D. Interval Tree: Query
-D. Interval Tree: Query--作业
-E. Stabbing With A Segment
--08-E-03. Query Algorithm (1)
--08-E-04. Query Algorithm (2)
-F. Grounded Range Query
--08-F-03. 1D-GRQ Using Range Tree
--08-F-04. 1D-GRQ By Linear Scan
-G. 1D-GRQ Using Heap
-G. 1D-GRQ Using Heap--作业
-H. Priority Search Tree
--08-H-03. Sibling Partitioning
-H. Priority Search Tree--作业
-I. 2D-GRQ Using PST
-I. 2D-GRQ Using PST--作业
-J. Segment Tree
--08-J-01. General Windowing Query
--08-J-02. Elementary Interval
--08-J-06. Solving Stabbing Query
--08-J-11. Constructing A Segment Tree
--08-J-12. Inserting A Segment (1)
--08-J-13. Inserting A Segment (2)
--08-J-14. Inserting A Segment (3)
-K. Vertical Segment Stabbing Query