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