代写 C algorithm Lecture notes GGS 650 GIS Algorithms

Lecture notes GGS 650 GIS Algorithms
Fall 2018
Module 5: More Geometric Algorithms Submodule 1: Point in Polygon Test
Lecture: Dr. Andreas Züfle

Section Overview
2. Geometric Algorithms
1. Preliminaries:
2. Right‐Hand‐Rule
3. LineSegmentCrossingTest 4. Point‐in‐PolygonTest
5. LineSetCrossing
GGS 650: Module 5: More Geometric Algorithms

Section Overview
2. Geometric Algorithms
1. Preliminaries:
2. Right‐Hand‐Rule
3. LineSegmentCrossingTest
4. Point‐in‐PolygonTest
1. Convex Polygons: Simple Test
2. Simple Polygons: Ray Casting Algorithm
3. Filter‐Refinement Algorithms: Motivation
5. LineSetCrossing
GGS 650: Module 5: More Geometric Algorithms

Section Overview
2. Geometric Algorithms
1. Preliminaries:
2. Right‐Hand‐Rule
3. LineSegmentCrossingTest
4. Point‐in‐PolygonTest
1. Convex Polygons: Simple Test
2. Simple Polygons: Ray Casting Algorithm
3. Filter‐Refinement Algorithms: Motivation
5. LineSetCrossing
GGS 650: Module 5: More Geometric Algorithms

Point in Convex Polygon test
Problem: Given a convex polygon P 􏰀 􏰁􏰂􏰃, 􏰂􏰄, … , 􏰂􏰅, 􏰂􏰃􏰆 andapoint􏰇.Decideif􏰇 ∈ 􏰈.
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰃
􏰂􏰄
􏰂􏰉
􏰂􏰋
􏰂􏰊
q

Point in Convex Polygon test
Problem: Given a convex polygon P 􏰀 􏰁􏰂􏰃, 􏰂􏰄, … , 􏰂􏰅, 􏰂􏰃􏰆 andapoint􏰇.Decideif􏰇 ∈ 􏰈.
Idea: Walk around the polygon, counter‐clock wise. If 􏰇 is
always on your left, then you 􏰂􏰃 must have walked around it!
q
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰋
􏰂􏰊
􏰂􏰉 􏰂􏰄

Point in Convex Polygon test
Problem: Given a convex polygon P 􏰀 􏰁􏰂􏰃, 􏰂􏰄, … , 􏰂􏰅, 􏰂􏰃􏰆 andapoint􏰇.Decideif􏰇 ∈ 􏰈.
Idea: Walk around the polygon, counter‐clock wise. If 􏰇 is
always on your left, then you 􏰂􏰃 must have walked around it!
q
Implementation:
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰋
􏰂􏰊
􏰂􏰉 􏰂􏰄

Point in Convex Polygon test
Problem: Given a convex polygon P 􏰀 􏰁􏰂􏰃, 􏰂􏰄, … , 􏰂􏰅, 􏰂􏰃􏰆 andapoint􏰇.Decideif􏰇 ∈ 􏰈.
Idea: Walk around the polygon, counter‐clock wise. If 􏰇 is
always on your left, then you 􏰂􏰃 must have walked around it!
q
Implementation:
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰋
􏰂􏰊
􏰂􏰉 􏰂􏰄

Iff.
Point in Convex Polygon test
Problem: Given a convex polygon P 􏰀 􏰁􏰂􏰃, 􏰂􏰄, … , 􏰂􏰅, 􏰂􏰃􏰆 andapoint􏰇.Decideif􏰇 ∈ 􏰈.
􏰌􏰍􏰎􏰂􏰃,􏰂􏰄,􏰇 􏰀􏰏1∧
􏰌􏰍􏰎􏰂􏰄,􏰂􏰉,􏰇 􏰀􏰏1∧ 􏰂􏰃 …∧
􏰌􏰍􏰎􏰂􏰅,􏰂􏰃,􏰇 􏰀􏰏1
q
Then 􏰇 ∈ 􏰈
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰋
􏰂􏰊
􏰂􏰉 􏰂􏰄

Iff.
􏰅􏰓􏰃
Point in Convex Polygon test
Problem: Given a convex polygon P 􏰀 􏰁􏰂􏰃, 􏰂􏰄, … , 􏰂􏰅, 􏰂􏰃􏰆 andapoint􏰇.Decideif􏰇 ∈ 􏰈.
􏰐􏰌􏰍􏰎􏰂􏰑,􏰂􏰑􏰒􏰃,􏰇 􏰀􏰏1∧ 􏰂􏰃 􏰑􏰔􏰃
q
􏰌􏰍􏰎􏰂􏰅,􏰂􏰃,􏰇 􏰀􏰏1 Then 􏰇 ∈ 􏰈
􏰂􏰉 􏰂􏰄
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰋
􏰂􏰊

Only works for convex polygons!
Point in Polygon test
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰃
􏰂􏰄
􏰂􏰋
􏰂􏰊 􏰂􏰉
q

Only works for convex polygons!
Point in Polygon test
Example:􏰌􏰍􏰎 􏰂􏰉,􏰂􏰊,􏰇 􏰀1 But 􏰇 ∈ 􏰈, which contradicts
􏰂􏰋
􏰂􏰊 􏰂􏰉
the previous equivalence.
q
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰃
􏰂􏰄

Ray Casting Algorithm
Idea: Have 􏰇 fire a laser in one direction, and see how many line segments it crosses!
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰃
􏰂􏰄
􏰂􏰋
􏰂􏰊 􏰂􏰉
q

Ray Casting Algorithm
Idea: Have 􏰇 fire a laser in one direction, and see how many line segments it crosses!
Odd number of hits: 􏰇 ∈ 􏰈 Even number of hits: 􏰇 ∉ 􏰈
q
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰃
􏰂􏰄
􏰂􏰋
􏰂􏰊 􏰂􏰉

Ray Casting Algorithm
Idea: Have 􏰇 fire a laser in one direction, and see how many line segments it crosses!
Odd number of hits: 􏰇 ∈ 􏰈 Even number of hits: 􏰇 ∉ 􏰈
q
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰃
􏰂􏰄
􏰂􏰋
􏰂􏰊 􏰂􏰉

Ray Casting Algorithm
Idea: Have 􏰇 fire a laser in one direction, and see how many line segments it crosses!
Odd number of hits: 􏰇 ∈ 􏰈 Even number of hits: 􏰇 ∉ 􏰈
q
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰃
􏰂􏰄
􏰂􏰋
􏰂􏰊 􏰂􏰉

Ray Casting Algorithm
Idea: Have 􏰇 fire a laser in one direction, and see how many line segments it crosses!
Odd number of hits: 􏰇 ∈ 􏰈 Even number of hits: 􏰇 ∉ 􏰈
q
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰃
􏰂􏰄
􏰂􏰋
􏰂􏰊 􏰂􏰉

Ray Casting Algorithm
Idea:
Let the ray go east, until the end of the MBR of the polygon.
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰃
􏰂􏰄
􏰂􏰋
􏰂􏰊 􏰂􏰉
q

Ray Casting Algorithm
Idea:
Let the ray go east, until the end of the MBR of the polygon.
L e t 􏰕 􏰖 􏰗 􏰘􏰙 􏰚 􏰘 : 􏰀 m a x 􏰂 . 􏰝 , 􏰞 􏰙􏰚􏰘 􏰛∈􏰜
􏰇 ≔􏰁􏰕􏰖􏰗􏰘 ,􏰇.􏰟􏰆,
Count the number of crossings
q
between 􏰇􏰇′ and 􏰂􏰑􏰂􏰠 ∈ 􏰈
GGS 650: Module 5: More Geometric Algorithms
􏰂􏰃
􏰂􏰄
q’
􏰂􏰋
􏰂􏰊 􏰂􏰉

Ray Casting Algorithm
Idea:
Let the ray go east, until the end of the MBR of the polygon.
􏰡􏰢􏰣􏰤􏰥􏰢􏰡􏰦:􏰀 􏰅􏰓􏰃
􏰂􏰋
q 􏰂􏰉
􏰂􏰊
􏰧􏰨 􏰩􏰌􏰥􏰎􏰎 􏰂􏰑,􏰂􏰑􏰒􏰃,􏰇,􏰇􏰞 􏰂􏰃
􏰑􏰔􏰃􏰞 q’
􏰪􏰨 􏰩􏰌􏰥􏰎􏰎 􏰂􏰅,􏰂􏰃,􏰇,􏰇
Where 􏰨􏰁. 􏰆 is an indicator function which maps true to one, and false to zero.
􏰂􏰄
GGS 650: Module 5: More Geometric Algorithms

Problem:
Point in Convex Polygon test
What if we have a many polygons? Millions? Billions?
q
Do we have to rhs‐test all edges of all polygons?
Can we discard some polygons without having to completely check them?
Can we prune any computation? GGS 650: Module 5: More Geometric Algorithms

Multi‐Step Query Processing
Idea: Use a simple check to discard candidate results.
q
Example: Conservatively approximate polygons, using minimum bounding rectangles (MBRs).
GGS 650: Module 5: More Geometric Algorithms

Multi‐Step Query Processing
Idea: Use a simple check to discard candidate results.
q
Example: Conservatively approximate polygons P, using minimum bounding rectangles MBR(P).
Ifq∉􏰕􏰖􏰗 􏰈 →􏰇∉􏰈
The counter‐implication does
not hold!
GGS 650: Module 5: More Geometric Algorithms

Multi‐Step Query Processing
Problem: Still so many MRBs!
We still need to check each and everyone of them! Linear run‐ time!
q
Apply the same idea: Conseratively approximate sets of MBRs.
GGS 650: Module 5: More Geometric Algorithms

Multi‐Step Query Processing
Problem: Still so many MRBs!
We still need to check each and everyone of them! Linear run‐ time!
q
Apply the same idea: Conseratively approximate sets of MBRs.
GGS 650: Module 5: More Geometric Algorithms

Multi‐Step Query Processing
Problem: Still so many MRBs!
We still need to check each and everyone of them! Linear run‐ time!
q
Apply the same idea: Conseratively approximate sets of MBRs.
And again!
GGS 650: Module 5: More Geometric Algorithms

Multi‐Step Query Processing
Problem: Still so many MRBs!
We still need to check each and everyone of them! Linear run‐ time!
q
Apply the same idea: Conseratively approximate sets of MBRs.
And again!
GGS 650: Module 5: More Geometric Algorithms

Multi‐Step Query Processing
Problem: Still so many MRBs!
We still need to check each and everyone of them! Linear run‐ time!
q
Apply the same idea: Conseratively approximate sets of MBRs.
And again! And again!
GGS 650: Module 5: More Geometric Algorithms

Multi‐Step Query Processing
Problem: Still so many MRBs!
q
We still need to check each and everyone of them! Linear run‐ time!
Apply the same idea: Conseratively approximate sets of MBRs.
And again! And again!
Best case: One MBR check for trillions of rectangles!
GGS 650: Module 5: More Geometric Algorithms

Multi‐Step Query Processing
Multi‐Step Query Processing:
q
• The idea behind spatial index structures
• This specific idea using MBRs is the idea of the R‐tree
• More details on index structures like the R‐tree soon!
GGS 650: Module 5: More Geometric Algorithms

Section Overview
2. Geometric Algorithms
1. Preliminaries:
2. Right‐Hand‐Rule
3. LineSegmentCrossingTest 4. Point‐in‐PolygonTest
5. LineSetCrossing
GGS 650: Module 5: More Geometric Algorithms

Line Segment Set Crossing
GGS 650: Module 5: More Geometric Algorithms

Line Segment Set Crossing
Problem: Find all crossings of a set of 􏰡 line segments
GGS 650: Module 5: More Geometric Algorithms

Line Segment Set Crossing
Problem: Find all crossings of a set of 􏰡 line segments 􏰄 Quadratic Problem Complexity: The number of crossings m may be in 􏰫􏰁􏰡 􏰆
GGS 650: Module 5: More Geometric Algorithms

Line Segment Set Crossing
Problem: Find all crossings of a set of 􏰡 line segments 􏰄 Quadratic Problem Complexity: The number of crossings may be in 􏰫􏰁􏰡 􏰆
Output Sensitive Algorithm: Since usually 􏰣 ≪ 􏰡􏰄, we aim to find an algorithm that scales well in 􏰣.
GGS 650: Module 5: More Geometric Algorithms

Line Segment Set Crossing
Algorithm (Naïve):
Input: Set of Line Segments S
􏰌􏰬􏰎􏰢􏰭􏰦 􏰀 ∅
For each Line Segment x 􏰀 􏰁a, b􏰆 ∈ 􏰮:
return 􏰌􏰬􏰎􏰢􏰭􏰦
GGS 650: Module 5: More Geometric Algorithms
For each Line Segment y 􏰀 􏰁c, d􏰆 ∈ 􏰮 ∖ 􏰎: If (cross(a,b,c,d)):
􏰌􏰬􏰎􏰢􏰭􏰦 􏰀 􏰌􏰬􏰎􏰢􏰭􏰦 ∪ 􏰁􏰝, 􏰟􏰆

return 􏰌􏰬􏰎􏰢􏰭􏰦 size 􏰣.
Line Segment Set Crossing
Algorithm (Naïve):
Input: Set of Line Segments S
􏰌􏰬􏰎􏰢􏰭􏰦 􏰀 ∅
For each Line Segment x 􏰀 􏰁a, b􏰆 ∈ 􏰮:
GGS 650: Module 5: More Geometric Algorithms
For each Line Segment y 􏰀 􏰁c, d􏰆 ∈ 􏰮 ∖ 􏰎: If (cross(a,b,c,d)):
􏰌􏰬􏰎􏰢􏰭􏰦 􏰀 􏰌􏰬􏰎􏰢􏰭􏰦 ∪ 􏰁􏰝, 􏰟􏰆
Number of cross‐tests is always 􏰡 ∗ 􏰡 􏰏 1 ∈ 􏰫􏰁􏰡􏰄􏰆 regardless of the result

Line Sweep Algorithm: Idea
Line Segment Set Crossing
• Take a vertical line, and move it from west to east
• At each time:
• track the set of active line segments
• sort these line segment by their leftmost y‐value
• Observation: Only vertically adjacent line segments need to be checked for
crossing
􏰯
􏰰
GGS 650: Module 5: More Geometric Algorithms
􏰯
􏰰
􏰰 􏰯

􏰯
􏰰
Line Segment Set Crossing
For each line segment (a,b), use a.x and b.x as stop points (“events”)
GGS 650: Module 5: More Geometric Algorithms
􏰯
􏰰
􏰰 􏰯

􏰯
􏰰
Line Segment Set Crossing
GGS 650: Module 5: More Geometric Algorithms
􏰯
􏰱􏰩􏰦􏰲􏰳􏰬􏰮􏰬􏰴􏰣􏰬􏰡􏰦􏰎 􏰀 ∅
􏰰 􏰯
􏰰
Initially:
No Line segments have been seen

􏰯
􏰰
Line Segment Set Crossing
GGS 650: Module 5: More Geometric Algorithms
􏰯
􏰰
Stop point 􏰱􏰵:
􏰱 is added to the active set. No other segments have been seen, so nothing to check. 􏰱􏰩􏰦􏰲􏰳􏰬􏰮􏰬􏰴􏰣􏰬􏰡􏰦􏰎 􏰀 􏰶􏰱􏰷
􏰰 􏰯

􏰯
􏰰
Line Segment Set Crossing
GGS 650: Module 5: More Geometric Algorithms
􏰯 􏰰
􏰱􏰩􏰦􏰲􏰳􏰬􏰮􏰬􏰴􏰣􏰬􏰡􏰦􏰎 􏰀􏰶􏰱,􏰖􏰷
􏰰 􏰯
Ok!
Stop point 􏰖􏰵:
􏰖 is added to the active set.
Neighbors of B are checked for crossings:
􏰩􏰌􏰥􏰎􏰎 􏰱􏰵,􏰱􏰸,􏰖􏰵,􏰖􏰸
􏰀􏰹􏰺􏰭􏰎􏰬

Line Segment Set Crossing
􏰯 􏰯
􏰰 Add a new event at the crossing 􏰰
GGS 650: Module 5: More Geometric Algorithms
􏰯
􏰰
􏰱􏰩􏰦􏰲􏰳􏰬􏰮􏰬􏰴􏰣􏰬􏰡􏰦􏰎 􏰀􏰶􏰱,􏰤,􏰖􏰷
Stop point 􏰤􏰵:
􏰤 is added to the active set.
Neighbors of C are checked for crossing:
Ok!
􏰩􏰌􏰥􏰎􏰎 􏰱􏰵,􏰱􏰸,􏰤􏰵,􏰤􏰸 􏰀􏰹􏰺􏰭􏰎􏰬
􏰩􏰌􏰥􏰎􏰎 􏰖􏰵,􏰖􏰸,􏰤􏰵,􏰤􏰸 􏰀􏰦􏰌􏰢􏰬 Report 􏰁􏰖, 􏰤􏰆 as a partial result and

Line Segment Set Crossing
􏰯 􏰯
􏰰 Add a new event at the crossing 􏰰
GGS 650: Module 5: More Geometric Algorithms
􏰯
􏰰
􏰱􏰩􏰦􏰲􏰳􏰬􏰮􏰬􏰴􏰣􏰬􏰡􏰦􏰎 􏰀􏰶􏰱,􏰤,􏰖􏰷
Stop point 􏰤􏰵:
􏰤 is added to the active set.
Neighbors of C are checked for crossing:
Ok!
􏰩􏰌􏰥􏰎􏰎 􏰱􏰵,􏰱􏰸,􏰤􏰵,􏰤􏰸 􏰀􏰹􏰺􏰭􏰎􏰬
􏰩􏰌􏰥􏰎􏰎 􏰖􏰵,􏰖􏰸,􏰤􏰵,􏰤􏰸 􏰀􏰦􏰌􏰢􏰬 Report 􏰁􏰖, 􏰤􏰆 as a partial result and

􏰯
􏰰
Line Segment Set Crossing
GGS 650: Module 5: More Geometric Algorithms
􏰯
􏰰
􏰱􏰩􏰦􏰲􏰳􏰬􏰮􏰬􏰴􏰣􏰬􏰡􏰦􏰎 􏰀􏰶􏰱,􏰖,􏰤􏰷
􏰰 􏰯
Ok!
The next event is an crossing point of B and C. So B and C switch sides in the list.
Neighbors of B and C are checked for crossing. C has no other neighbor than B,
We check
􏰩􏰌􏰥􏰎􏰎 􏰱􏰵,􏰱􏰸,􏰖􏰵,􏰖􏰸
􏰀􏰹􏰺􏰭􏰎􏰬

􏰯
􏰰
Line Segment Set Crossing
GGS 650: Module 5: More Geometric Algorithms
􏰯
􏰰
􏰱􏰩􏰦􏰲􏰳􏰬􏰮􏰬􏰴􏰣􏰬􏰡􏰦􏰎 􏰀􏰶􏰱,􏰖􏰷
􏰰 􏰯
The next event is at the end point of 􏰤 Remove 􏰤 from the list

􏰯
􏰰
Line Segment Set Crossing
For each line segment (a,b), use a.x and b.x as stop points
GGS 650: Module 5: More Geometric Algorithms
􏰯
􏰰
􏰱􏰩􏰦􏰲􏰳􏰬􏰮􏰬􏰴􏰣􏰬􏰡􏰦􏰎 􏰀 􏰶􏰱􏰷
􏰰 􏰯
The next event is at the end point of 􏰖 Remove 􏰖 from the list

􏰯
􏰰
Line Segment Set Crossing
For each line segment (a,b), use a.x and b.x as stop points
GGS 650: Module 5: More Geometric Algorithms
􏰯
􏰰
􏰱􏰩􏰦􏰲􏰳􏰬􏰮􏰬􏰴􏰣􏰬􏰡􏰦􏰎 􏰀
􏰰 􏰯
The next event is at the end point of 􏰱 Remove 􏰱 from the list
No more events. Return the current result.

Line Segment Set Crossing
How does this algorithm scale for large data sets?
• Two events per line segment
• One event per Crossing
• Re‐sorting the active edge list at each event, can be done in 􏰫􏰁log 􏰡􏰆
exploiting a binary tree to represent the list. • Total complexity 􏰫 􏰡 ⋅ log􏰡 􏰪 􏰣 ⋅ log􏰡
(n is the number of line segments, m is the number of intersections)
• Note: That’s in 􏰫􏰁􏰡􏰄 ⋅ log 􏰡 􏰆 in the case where 􏰣 ∈ 􏰡􏰄. That’s Slower than the naïve algorithm!
• Butthat’sin􏰫 􏰡⋅log􏰡 inthecasewhere􏰣∈􏰫 1 . (e.g. 􏰣 􏰻 1000􏰆
• Alsoin􏰫 􏰡⋅log􏰡 inthecasewhere􏰣∈􏰫􏰁􏰡􏰆,thecasewherethe number of crossings per edge is bounded by a constant.
GGS 650: Module 5: More Geometric Algorithms