Java Reference
In-Depth Information
t
1
t
0
t
1
t
0
h
0
t
0
t
1
=
h
0
(a) Step 1
(b) Step 2
(c) Repeat Step 2
(d)
H
is found
F
IGURE
22.9
(a)
h
0
is the rightmost lowest point in S. (b) Step 2 finds point
t
1
. (c) A convex hull is expanded repeatedly.
(d) A convex hull is found when
t
1
becomes
h
0
.
Step 2: Let t
1
be s
0
.
For every point p in
S
,
if
p
is on the right side of the direct line from t
0
to t
1
, then
let t
1
be
p
.
(After Step 2, no points lie on the right side of the direct line from t
0
to t
1
, as shown in Figure 22.9b.)
Step 3: If t
1
is h
0
(see Figure 22.9d), the points in
H
form a convex
hull for
S
. Otherwise, add t
1
to
H
, let t
0
be t
1
, and go back to Step 2
(see Figure 22.9c).
The convex hull is expanded incrementally. The correctness is supported by the fact that no
points lie on the right side of the direct line from
t
0
to
t
1
after Step 2. This ensures that every
line segment with two points in
S
falls inside the polygon.
Finding the rightmost lowest point in Step 1 can be done in
O
(
n
) time. Whether a point is
on the left side of a line, right side, or on the line can be determined in
O
(1) time (see Program-
ming Exercise 3.32). Thus, it takes
O
(
n
) time to find a new point
t
1
in Step 2. Step 2 is repeated
h
times, where
h
is the size of the convex hull. Therefore, the algorithm takes
O
(
hn
) time. In
the worst-case,
h
is
n
.
The implementation of this algorithm is left as an exercise (see Programming Exercise 22.9).
correctness of the algorithm
time complexity of the
algorithm
22.10.2 Graham's Algorithm
A more efficient algorithm was developed by Ronald Graham in 1972, as shown in Listing 22.13.
L
ISTING
22.13
Finding a Convex Hull Using Graham's
Algorithm
Step 1: Given a list of points
S
, select the rightmost lowest point and
name it p
0
. As shown in Figure 22.10a, p
0
is such a point.
p
2
p
1
p
2
p
3
p
3
p
2
p
1
p
1
X
X
p
0
p
0
x
-axis
p
0
x
-axis
p
0
x
-axis
(a) Step 1
(b) Step 2
(c)
p
3
into
H
(d)
p
2
off
H
F
IGURE
22.10
(a)
p
0
is the rightmost lowest point in S. (b) Points are sorted by their angles. (c-d) A convex hull is
discovered incrementally.
Step 2: Sort the points in
S
angularly along the x-axis with p
0
as the
center, as shown in Figure 22.10b. If there is a tie and two points have
the same angle, discard the one that is closer to p
0
. The points in
S
are
now sorted as p
0
, p
1
, p
2
, ..., p
n-1
.
Search WWH ::
Custom Search