1
Student Name: __________________
Class and Section __________________
Total Points (20 pts) __________________
Due: September 28, 2016 before the class
Project: Convex Hull
CSCI 2410 Data Structures and Algorithms
Armstrong Atlantic State 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,
Many algorithms have been developed to find a convex hull. An intuitive
approach, called the gift–wrapping algorithm, works as follows:
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.
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).
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
(Hint: Do it incrementally. Can you add a point? Can you remove a point? Can you find a
convex hull? Can you display a convex hull?)
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)
3. Fill in self-evaluation:
3
1. Can your program add a point?
2. Can your program remove a point?
3. Can your program display a polygon that connects some points?
4. Can your program display a convex hull correctly?
}
static class MyPoint {
double x, y;
MyPoint(double x, double y) {
this.x = x; this.y = y;
}
}
ArrayList<MyPoint> H = new ArrayList<MyPoint>();
H.add(h0);
MyPoint t0 = h0;
// Step 2 and Step 3
while (true) {
MyPoint t1 = myPoints[0];
for (int i = 1; i < myPoints.length; i++) {
double status = whichSide(t0.x, t0.y, t1.x, t1.y, myPoints[i].x, myPoints[i].y);
if (t1.x == h0.x && t1.y == h0.y)
break; // A convex hull is found
else {
H.add(t1);
t0 = t1;
}
}
return H;
}
/** Return the rightmost lowest point in S */
private static MyPoint getRightmostLowestPoint(MyPoint[] p) {
int rightMostIndex = 0;
double rightMostX = p[0].x;
double rightMostY = p[0].y;
5
return p[rightMostIndex];
}
public static double distance(double x1, double y1, double x2, double y2) {
return Math.sqrt((x1 – x2) * (x1 – x2) + (y1 – y2) * (y1 – y2));
}
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)
(x1-x0)*(y2-y0) – (x2-x0)*(y1-y0)
>0 p2 is on the left side of the line
=0 p2 is on the same line
<0 p2 is on the right side of the line
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:
6
<output>