1
Student Name: __________________
Class and Section __________________
Total Points (20 pts) __________________
Due: Feb 22, 2019 before the class
Project: Convex Hull
CSCI 3230 Data Structures
Georgia Southern University
Problem Description:
Given a set of points, a convex hull is a smallest convex polygon that
encloses all these points, as shown in Figure 22.8a. A polygon is
convex if every line connecting two vertices is inside the polygon. For
example, the vertices v0, v1, v2, v3, v4, and v5 in Figure 23.5a form a
convex polygon, but not in Figure 22.8b, because the line that connects
v3 and v1 is not inside the polygon.
Figure 22.8
A convex hull is a smallest convex polygon that
contains a set of points.
Convex hull has many applications in game programming, pattern
recognition, and image processing. Before we introduce the algorithms,
it is helpful to get acquainted with the concept using an interactive
Step 1: Given a list of points S, let the points in S be labeled s0, s1,
…, sk. Select the rightmost lowest point h0 in S. As shown in Figure
22.9a, h0 is such a point. Add h0 to the convex hull H. H is a list
initially being empty. Let t0 be h0.
Step 2: Let t1 be s0.
For every point p in S
if p is on the right side of the direct line from t0 to t1 then
let t1 be p.
2
Step 3: If t1 is h0 (see Figure 22.9d), the points in H form a convex
hull for S. Otherwise, add t1 to H, let t0 be t1, and go to Step 2 (see
Figure 22.9c).
s
t1
Figure 22.9
(a) h0 is the rightmost lowest point in S. (b) Step 2
finds point t1. (c) A convex hull is expanded
repeatedly. (d) A convex hull is found when t1 becomes
h0.
A console-based program for finding the convex is given to you (mailed separately).
Develop a GUI program as shown in Figure 22.5. Name the program Exercise22_13
Screen shots:
What to submit?
1. Complete and submit the hardcopy of this document.
2. Compile and Submit to LiveLab (you must submit the program regardless whether it is
complete or incomplete, correct or incorrect)
h0
t0
3
3. Fill in self-evaluation:
1. Can your program add a point?
2. Can your program remove a point?
FYR:
*3.32 (Geometry: point position) Given a directed line from point p0(x0, y0) to p1(x1, y1), you can use
the following condition to decide whether a point p2(x2, y2) is on the left of the line, on the right,
or on the same line (see Figure 3.13):
Figure 3.13
(a) p2 is on the left of the line. (b) p2 is on the right of the line. (c) p2 is on the same line.
p0
p2
p1
p0
p2
p1
p0
p2
p1
(a) (b) (c)
Write a program that prompts the user to enter the three points for p0, p1, and p2 and displays
whether p2 is on the left of the line from p0 to p1, to the right, or on the same line. Here are some
sample runs:
<output>
Enter three points for p0, p1, and p2: 4.4 2 6.5 9.5 –
5 4 <enter icon>
p2 is on the left side of the line
4
<end output>
<output>
Enter three points for p0, p1, and p2: 3.4 2 6.5 9.5 5
2.5 <enter icon>
p2 is on the right side of the line