Implement the Divide and Conquer based 2D Convex Hull computing algorithm discus
ID: 3885686 • Letter: I
Question
Implement the Divide and Conquer based 2D Convex Hull computing algorithm discussed in
class. Use the LeftOf test during the merge process.
The input to your program should be a plain ASCII file containing (x, y) coordinates of one point
per line. The first line of the file will contain the number of points. For instance,
5
0 0
1 1
2 3
3 4
4 5
The output will consist of the vertices (extreme points) comprising the convex hull, in clockwise
order. Each line will contain the (x, y) coordinates of the vertex. The first line of the line will
contain the number of vertices in the convex hull. For instance,
4
0 0
2 3
4 5
1 1
Submission consists of
1. A five-page report containing (i) pseudo-code of the algorithm implemented, (ii) five
example cases, some of which should include some special case conditions, of convex
hull computed by the code, (iii) a plot of the time taken to execute the code versus the
number of input points. Vary the number of points until your code takes about a minute
to compute. Plot the best fitting polynomial to the points. Comment on the shape.
2. Your source code
3. A demo of your code on sample inputs. You will setup demo time with the TA during his
office to demo the code. He will share a signup schedule.
Explanation / Answer
#include <iostream>
#include <stack>
#include <stdlib.h>
using namespace std;
struct Point
{
int x, y;
};
Point p0;
Point nextToTop(stack<Point> &S)
{
Point p = S.top();
S.pop();
Point res = S.top();
S.push(p);
return res;
}
// A utility function to swap two points
int swap(Point &p1, Point &p2)
{
Point temp = p1;
p1 = p2;
p2 = temp;
}
// A utility function to return square of distance
// between p1 and p2
int distSq(Point p1, Point p2)
{
return (p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y);
}
// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; // colinear
return (val > 0)? 1: 2; // clock or counterclock wise
}
// A function used by library function qsort() to sort an array of
// points with respect to the first point
int compare(const void *vp1, const void *vp2)
{
Point *p1 = (Point *)vp1;
Point *p2 = (Point *)vp2;
// Find orientation
int o = orientation(p0, *p1, *p2);
if (o == 0)
return (distSq(p0, *p2) >= distSq(p0, *p1))? -1 : 1;
return (o == 2)? -1: 1;
}
// Prints convex hull of a set of n points.
void convexHull(Point points[], int n)
{
// Find the bottommost point
int ymin = points[0].y, min = 0;
for (int i = 1; i < n; i++)
{
int y = points[i].y;
// Pick the bottom-most or chose the left
// most point in case of tie
if ((y < ymin) || (ymin == y &&
points[i].x < points[min].x))
ymin = points[i].y, min = i;
}
// Place the bottom-most point at first position
swap(points[0], points[min]);
// Sort n-1 points with respect to the first point.
// A point p1 comes before p2 in sorted ouput if p2
// has larger polar angle (in counterclockwise
// direction) than p1
p0 = points[0];
qsort(&points[1], n-1, sizeof(Point), compare);
// If two or more points make same angle with p0,
// Remove all but the one that is farthest from p0
// Remember that, in above sorting, our criteria was
// to keep the farthest point at the end when more than
// one points have same angle.
int m = 1; // Initialize size of modified array
for (int i=1; i<n; i++)
{
// Keep removing i while angle of i and i+1 is same
// with respect to p0
while (i < n-1 && orientation(p0, points[i],
points[i+1]) == 0)
i++;
points[m] = points[i];
m++; // Update size of modified array
}
// If modified array of points has less than 3 points,
// convex hull is not possible
if (m < 3) return;
// Create an empty stack and push first three points
// to it.
stack<Point> S;
S.push(points[0]);
S.push(points[1]);
S.push(points[2]);
// Process remaining n-3 points
for (int i = 3; i < m; i++)
{
// Keep removing top while the angle formed by
// points next-to-top, top, and points[i] makes
// a non-left turn
while (orientation(nextToTop(S), S.top(), points[i]) != 2)
S.pop();
S.push(points[i]);
}
// Now stack has the output points, print contents of stack
while (!S.empty())
{
Point p = S.top();
cout << "(" << p.x << ", " << p.y <<")" << endl;
S.pop();
}
}
// Driver program to test above functions
int main()
{
Point points[] = {{0, 0}, {1, 1}, {2, 3}, {3, 4},{4, 5}};
int n = sizeof(points)/sizeof(points[0]);
convexHull(points, n);
return 0;
}
output