Segment intersection: Given two segments, do they intersect?
Intersection and Orientation
Two segments (p1,q1) and (p2,q2) intersect if and only if
one of the following two conditions is verified
• general case:
- (p1,q1,p2) and (p1,q1,q2) have different
orientations and
- (p2,q2,p1) and (p2,q2,q1) have different
orientations
• special case
- (p1,q1,p2), (p1,q1,q2), (p2,q2,p1), and (p2,q2,q1) are
all collinear and
- the x-projections of (p1,q1) and (p2,q2) intersect
- the y-projections of (p1,q1) and (p2,q2) intersect
• Orientation test
- counterclockwise (left turn): σ < τ
- clockwise (right turn): σ > τ
- collinear (left turn): σ = τ
• The orientation depends on whether the expression (y2−y1) (x3−x2) − (y3−y2) (x2−x1)
is positive, negative, or null.
Point Inclusion
• given a polygon and a point, is the point inside or outside the polygon?
• orientation helps solving this problem in linear time
• Draw a horizontal line to the right of each point and extend it to infinity
• Count the number of times a line intersects the polygon. We have:
- even number ⇒ point is outside
- odd number ⇒ point is inside
• What about points d and g ?? Degeneracy!
• The question is: how do we compute angles?
- We could use trigonometry (e.g., arctan).
- However, the computation would be inefficient since trigonometric functions are not in the normal
instruction set of a computer and need a call to a math-library routine.
- Observation:, we don’t care about the actual
values of the angles. We just want to sort by angle.
- Idea: use the orientation to compare angles
without actually computing them!!
θ(p) < θ(q) ⇔ orientation(a,p,q) = CCW
• We can sort the points by angle by using any
“sorting-by-comparison” algorithm (e.g., heapsort or merge-sort) and replacing angle comparisons with orientation tests
• We obtain an O(N log N)-time algorithm for the simple closed path problem on N points
Graham Scan Algorithm
Algorithm Scan(S, a):
Input: A sequence S of points in the plane beginning
with point a such that:
1) a is a vertex of the convex hull of the points of S
2) the remaining points of S are
counterclockwise around a.
Output: Sequence S from which the points that are
not vertices of the convex hull have been removed.
S.insertLast(a) {add a copy of a at the end of S}
prev ← S.first() {so that prev = a initially}
curr ← S.after(prev) {the next point is on the}
{current convex chain}
repeat
next ← S.after(curr) {advance}
if points (point(prev), point(curr), point(next))
make a left turn then
prev ← curr
else
S.remove(curr) {point curr is on the convex hull}
prev ← S.before(prev)
curr ← S.after(prev)
until curr = S.last()
S.remove(S.last()) {remove the copy of a}
Read full article from GEOMETRIC ALGORITHMS
Intersection and Orientation
Two segments (p1,q1) and (p2,q2) intersect if and only if
one of the following two conditions is verified
• general case:
- (p1,q1,p2) and (p1,q1,q2) have different
orientations and
- (p2,q2,p1) and (p2,q2,q1) have different
orientations
• special case
- (p1,q1,p2), (p1,q1,q2), (p2,q2,p1), and (p2,q2,q1) are
all collinear and
- the x-projections of (p1,q1) and (p2,q2) intersect
- the y-projections of (p1,q1) and (p2,q2) intersect
• Orientation test
- counterclockwise (left turn): σ < τ
- clockwise (right turn): σ > τ
- collinear (left turn): σ = τ
• The orientation depends on whether the expression (y2−y1) (x3−x2) − (y3−y2) (x2−x1)
is positive, negative, or null.
Point Inclusion
• given a polygon and a point, is the point inside or outside the polygon?
• orientation helps solving this problem in linear time
• Draw a horizontal line to the right of each point and extend it to infinity
• Count the number of times a line intersects the polygon. We have:
- even number ⇒ point is outside
- odd number ⇒ point is inside
• What about points d and g ?? Degeneracy!
Simple Closed Path — Part I
• “Connect the dots” without crossings
• Pick the bottommost point a as the anchor point
• For each point p, compute the angle q(p) of the segment (a,p) with respect to the x-axis:
• Traversing the points by increasing angle yields a simple closed path.• The question is: how do we compute angles?
- We could use trigonometry (e.g., arctan).
- However, the computation would be inefficient since trigonometric functions are not in the normal
instruction set of a computer and need a call to a math-library routine.
- Observation:, we don’t care about the actual
values of the angles. We just want to sort by angle.
- Idea: use the orientation to compare angles
without actually computing them!!
θ(p) < θ(q) ⇔ orientation(a,p,q) = CCW
• We can sort the points by angle by using any
“sorting-by-comparison” algorithm (e.g., heapsort or merge-sort) and replacing angle comparisons with orientation tests
• We obtain an O(N log N)-time algorithm for the simple closed path problem on N points
Graham Scan Algorithm
Algorithm Scan(S, a):
Input: A sequence S of points in the plane beginning
with point a such that:
1) a is a vertex of the convex hull of the points of S
2) the remaining points of S are
counterclockwise around a.
Output: Sequence S from which the points that are
not vertices of the convex hull have been removed.
S.insertLast(a) {add a copy of a at the end of S}
prev ← S.first() {so that prev = a initially}
curr ← S.after(prev) {the next point is on the}
{current convex chain}
repeat
next ← S.after(curr) {advance}
if points (point(prev), point(curr), point(next))
make a left turn then
prev ← curr
else
S.remove(curr) {point curr is on the convex hull}
prev ← S.before(prev)
curr ← S.after(prev)
until curr = S.last()
S.remove(S.last()) {remove the copy of a}
Read full article from GEOMETRIC ALGORITHMS
