22: computer graphics algorithms

Line-Line Intersection | Multiple Line Intersection | Closest Pair of Points
Point in Polygon | Convex Hull | Flood Fill

Line-Line Intersection [1]

A naive approach to solving this problem is to take two line segments, use the y=mx+b equation and solve where the lines intersect.
  • This requires a division of floating point numbers and if the segments are nearly parallel, round-off errors can degrade the accuracy
A more accurate version uses cross-products.

Cross Product

The cross product of points p1 and p2 is the signed area of the parallelogram formed by the points:
  • 0,0
  • p1 = (p1.x, p1.y)
  • p2 = (p2.x, p2.y)
  • p1 + p2 = (p1.x + p2.x, p1.y + p2.y)
If the cross product is positive, then p2 is clockwise from p1 and the origin. If it is negative, then p2 is counter-clockwise from p1 and the origin.

The cross product can be expressed at the determinate of a matrix:
p1 X p2 = x1y2 - x2y1;

To include a third point that is not the origin, we offset everything by a value p0:
(p1 - p0) X (p2 - p0) = (x1 - x0)*(y2 - y0) - (x2 - x0)*(y1 - y0);

We then use the directions to determine if two lines intersect.
1:  
algorithm
 
segmentsIntersect(
Point 
p1, 
Point 
p2, 
Point 
p3, 
Point 
p4)

2:  
 
 
d1 
direction(
p3, 
p4, 
p1)
;

3:  
 
 
d2 
direction(
p3, 
p4, 
p2)
;

4:  
 
 
d3 
direction(
p1, 
p2, 
p3)
;

5:  
 
 
d4 
direction(
p1, 
p2, 
p4)
;

6:  

7:  
 
 
if
(
 
(
 
(
d1 
>
 
and 
d2 
<
 
0)
 
or

8:  
 
 
 
 
 
 
 
 
(
d1 
<
 
and 
d2 
>
 
0)
 
)

9:  
 
 
 
 
 
 

10: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
and

11: 

12: 
 
 
 
 
 
 
(
 
(
d3 
>
 
and 
d4 
<
 
0)
 
or

13: 
 
 
 
 
 
 
 
 
(
d3 
<
 
and 
d4 
>
 
0)
 
)
 
 
 
)

14: 
 
 
{
 
 
 
 

15: 
 
 
 
 
return
 
true;
 
 

16: 
 
 
}
 

17: 
 
 
if
(
 
d1 
== 
and 
onSegment(
p3, 
p4, 
p1)
 
)

18: 
 
 
 
 
return
 
true;

19: 
 
 
if
(
 
d2 
== 
and 
onSegment(
p3, 
p4, 
p2)
 
)

20: 
 
 
 
 
return
 
true;

21: 
 
 
if
(
 
d3 
== 
and 
onSegment(
p1, 
p2, 
p3)
 
)

22: 
 
 
 
 
return
 
true;

23: 
 
 
if
(
 
d4 
== 
and 
onSegment(
p1, 
p2, 
p4)
 
)

24: 
 
 
 
 
return
 
true;

25: 
 
 

26: 
 
 
return
 
false;

27: 

28: 
algorithm
 
direction(
Point 
p_i, 
Point 
p_j, 
Point 
p_k)

29: 
 
 
return
 
(
(
p_k.x 
p_i.x)
*(
p_j.y 
p_i.y)
)
 
(
(
p_j.x 
p_i.x)
*(
p_k.y 
p_i.y)
)
;

30: 

31: 
algorithm
 
onSegment(
Point 
p_i, 
Point 
p_j, 
Point 
p_k)

32: 
 
 
if
(
 
min(
p_i.x, 
p_j.x)
 
<= 
p_k.x 
<= 
max(
p_i.x, 
p_j.x)
 
and

33: 
 
 
 
 
 
 
min(
p_i.y, 
p_j.y)
 
<= 
p_k.y 
<= 
max(
p_i.y, 
p_j.y)
)
{

34: 
 
 
 
 
return
 
true;

35: 
 
 
}

36: 
 
 
return
 
false;

Cases:
  1. Neither conditions cross:
    SegmentsIntersect
  2. One condition crosses:
    SegmentsIntersect
  3. Both conditions cross:
    SegmentsIntersect

Multiple Line Intersection [1]

A naive algorithm for multiple line intersection takes O(n^2) time.

If we sort the endpoints by the x coordinate and use a sweep line, it takes O(nlgn) time.

MultLineIntersect


Algorithm:
1:  
algorithm
 
anySegmentsIntersect(
S)

2:  
 
 
{
 
}

3:  
 
 
sort 
the 
endpoints 
in 
from 
left 
to 
right;

4:  
 
 
for
 
each 
point 
in 
the 
sorted 
list 
of 
endpoints

5:  
 
 
 
 
if
(
is 
the 
left 
endpoint 
of 
segment 
s)

6:  
 
 
 
 
 
 
insert(
T, 
s)
;

7:  
 
 
 
 
 
 
if
(
above(
T, 
s)
 
exists 
and 
intersects 
or

8:  
 
 
 
 
 
 
 
 
 
below(
T, 
s)
 
exists 
and 
intersects 
s)

9:  
 
 
 
 
 
 
 
 
return
 
true;

10: 
 
 
 
 
if
(
is 
the 
right 
endpoint 
of 
segment 
s)

11: 
 
 
 
 
 
 
if
(
both 
above(
T, 
s)
 
and 
below(
T, 
s)
 
exist 
and

12: 
 
 
 
 
 
 
 
 
 
above(
T, 
s)
 
intersects 
below(
T, 
s)
)

13: 
 
 
 
 
 
 
 
 
return
 
true;

14: 
 
 
 
 
 
 
delete
(
T, 
s)

15: 
 
 
return
 
false;
 
 
 

Finding the closest pair of points [1]

Here we are trying to find the closes pair of points in a set of points.

A naive algorithm checks all the points with each other and takes O(n^2) time.

The divide-and-conquer algorithm presented here takes O(nlgn) time.

1:  
algorithm
 
closestPair(
vector<
Point>
 
P)

2:  
 
 
create 
vector<
Point>
 
sorted 
by 
ascending 
coordinate

3:  
 
 
create 
vector<
Point>
 
sorted 
by 
ascending 
coordinate

4:  
 
 
return
 
executeClosestPair(
X, 
Y)

5:  

6:  
algorithm
 
executeClosestPair(
X, 
Y)

7:  
 
 
if
(
|X| 
<= 
3)
{

8:  
 
 
 
 
find 
the 
closest_pair 
with 
brute 
force;

9:  
 
 
 
 
return
 
the 
closet_pair

10: 
 
 
}

11: 

12: 
 
 
divide 
into 
X_L 
and 
X_R 
of 
equal 
sizes;

13: 
 
 
while
(
traversal 
of 
in 
ascending 
order 
is 
not 
complete)
{

14: 
 
 
 
 
if
(
curr_point 
is 
in 
X_L)
{

15: 
 
 
 
 
 
 
place 
curr_point 
in 
Y_L;

16: 
 
 
 
 
}
 
else
 
{

17: 
 
 
 
 
 
 
place 
curr_point 
in 
Y_R;

18: 
 
 
 
 
}

19: 
 
 
}

20: 

21: 
 
 
closest_pair_L 
executeClosestPair(
X_L, 
Y_L)
;

22: 
 
 
closest_pair_R 
executeClosestPair(
X_R, 
Y_R)
;

23: 

24: 
 
 
closest 
closest_pair(
closest_pair_L, 
closest_pair_R)
;

25: 
 
 

26: 
 
 
create 
Y_prime 
by 
choosing 
the 
points 
from 
that 
are 
min_dist 
away 
from 
the 
divide.

27: 

28: 
 
 
foreach(
point 
in 
Y_prime)
{

29: 
 
 
 
 
foreach(
points 
following 
p)
{

30: 
 
 
 
 
 
 
if
(
new_pair 
is 
closer 
than 
closest)
{

31: 
 
 
 
 
 
 
 
 
closest 
dist(
new_pair)
;

32: 
 
 
 
 
 
 
}

33: 
 
 
 
 
}
 
 
 
 

34: 
 
 
}

35: 

36: 
 
 
return
 
closest;

37: 
}

Finding the closest pair with each of the points in P_L and P_R takes O(n^2) naively. It can be shown that only 4 points on each side of Y_L and Y_R need to be checked because of the min property.

Point in polygon [2]

Point in polygon is very useful for mouse hit code inside a graphical editor with arbirtary shapes to be selected with the mouse. The shape is the polygon and the point is the mouse coordinate.

It is easy to figure out point inside a square or rectangle. Points inside a arbitrary polygon need a more complicated algorithm.

PointInPolygon
PointInPolygon

The crossing number algorithm determines the number of times a ray crosses the polygon borders. If the crossing number is even, the point is outside the polygon, if it is odd, it is inside.
1:  
algorithm
 
crossingNumber(
Polygon 
p, 
Point 
mouse_click)

2:  
 
 
int
 
cn 
0;

3:  
 
 

4:  
 
 
for
 
each 
edge 
in 
p

5:  
 
 
 
 
if
(
crossesUpward(
edge, 
mouse_click)
 
|| 
crossesDownward(
edge, 
mouse_click)
)

6:  
 
 
 
 
 
 
if
(
edge 
is 
to 
the 
right 
of 
mouse_click)

7:  
 
 
 
 
 
 
 
 
++cn

8:  

9:  
 
 
return
 
cn 
1;

10: 

11: 
algorithm
 
crossesUpward(
Edge 
edge, 
Point 
p)

12: 
 
 
if
(
edge.p1.y 
<
p.y 
&& 
edge.p2.y 
>
 
p.y)

13: 
 
 
 
 
return
 
true;

14: 
 
 
return
 
false;

15: 

16: 
algorithm
 
crossesDownward(
Edge 
edge, 
Point 
p)

17: 
 
 
if
(
edge.p2.y 
<
p.y 
&& 
edge.p1.y 
>
 
p.y)

18: 
 
 
 
 
return
 
true;

19: 
 
 
return
 
false;

20: 

Convex Hull [1]

Graham's-scan takes O(nlgn) time
1:  
algorithm
 
grahamsScan(
Points 
q)

2:  
 
 
p0 
the 
point 
in 
with 
the 
min 
coordinate

3:  
 
 
p1, 
p2, 
pm 
are 
the 
remaining 
points 
in 
q, 
sorted 
by 
polar 
angle 
in 
counterclockwise 
order 
around 
p0

4:  

5:  
 
 
push(
p0, 
S)

6:  
 
 
push(
p1, 
S)

7:  
 
 
push(
p2, 
S)

8:  
 
 
for
(
to 
m)

9:  
 
 
 
 
while
(
the 
angle 
formed 
by 
points 
NextToTop(
S)
Top(
S)
 
and 
p_i 
make 
nonleft 
turn)

10: 
 
 
 
 
 
 
pop(
S)
;

11: 
 
 
 
 
push(
p_i, 
S)
;

12: 
 
 
return
 
S;

Flood Fill

Flood Fill is an algorithm used to fill in an area in a image that has similar colors to a seed point.
1:  
algorithm
 
floodFill(
bitmap 
bmp, 
point 
seed)

2:  
 
 
enqueue 
seed;

3:  
 
 
while
 
queue 
is 
not 
empty

4:  
 
 
 
 
curr 
dequeue(
)
;

5:  
 
 
 
 
if
 
curr 
is 
visited

6:  
 
 
 
 
 
 
continue;

7:  
 
 
 
 
visit 
curr 
and 
mark 
curr 
visited;

8:  

9:  
 
 
 
 
enqueue(
curr.x 
1, 
curr.y 
1)
;

10: 
 
 
 
 
enqueue(
curr.x 
0, 
curr.y 
1)
;

11: 
 
 
 
 
enqueue(
curr.x 
1, 
curr.y 
1)
;

12: 
 
 
 
 

13: 
 
 
 
 
enqueue(
curr.x 
1, 
curr.y 
0)
;

14: 
 
 
 
 
enqueue(
curr.x 
1, 
curr.y 
0)
;

15: 

16: 
 
 
 
 
enqueue(
curr.x 
1, 
curr.y 
1)
;

17: 
 
 
 
 
enqueue(
curr.x 
0, 
curr.y 
1)
;

18: 
 
 
 
 
enqueue(
curr.x 
1, 
curr.y 
1)
;

FloodFill FloodFill

References

  1. Introduction to Algorithms, Cormen, Leiserson, Rivest and Stein. Chapter 33.
  2. http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm
  3. http://en.wikipedia.org/wiki/Line-line_intersection
  4. http://en.wikipedia.org/wiki/Closest_pair_of_points_problem
  5. http://en.wikipedia.org/wiki/Delaunay_triangulation