Question
Write a test program that prompts the user to enter the set size and the points and displays the points that form a convex hull.
Write a test program that prompts the user to enter the set size and the points and displays the points that form a convex hull. Note that when you debug the code, you will discover that the algorithm overlooked two cases (1) when t1 = t0 and (2) when there is a point that is on the same line from t0 to t1. When either case happens, replace t1 by point p if the distance from t0 to p is greater than the distance from t0 to t1. Here is a sample run:
I keep getting event overload errors, thanks in advance.
#include
using namespace std;
struct Point
{ //2D Convex Plot int x;
int y;
}; // 0 --> p, q and r are colinear (mid.point)
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r) //checks point for relation
{
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
}
// Prints convex hull of a set of n points.
void convexHull(Point points[])
{ const int n = 6;
//Let t1 and t2 be the top first and second element in stack H; //if (pi is on the left side of the direct line from t2 to t1)
if (n
return;
// Initialize Result
int next[6];
for (int i = 0; i
next[i] = -1;
// Find the leftmost point
int l = 0;
for (int i = 1; i
if (points[i].x
l = i;
// Start from leftmost point, keep moving counterclockwise
// until reach the start point again
int p = l, q;
do
{
// Search for a point 'q' such that orientation(p, i, q) is
// counterclockwise for all points 'i'
q = (p + 1) % n;
for (int i = 0; i
if (orientation(points[p], points[i], points[q]) == 2)
q = i;
next[p] = q; // Add q to result as a next point of p
p = q; // Set p as q for next iteration
}
while (p != l);
// Print Result
for (int i = 0; i
{
if (next[i] != -1)
cout
}
}
int main()
{
Point points[] = { { 1, 2.4 }, { 2.5, 2 }, { 1.5, 34.5 }, { 5.5, 6 }, { 6, 2.4 },
{ 5.5, 9 }};
cout
int n = sizeof(points) / sizeof(points[0]);
convexHull(points, n);
return 0;
};
18: Developing Efficient Algorithms ho Repeat Step 2: A convex hullis expanded repeatedly (a) ho is the rightmost lowest point in S. (b) Step 2 finds point t. (c) A convex hull is expanded repeatedly. (d) A convex hull is found when t, becomes ho Sample Run for Exercise 18_11 Enter input data for the program (Sample data provided below. You may modify it.) 1 2.4 2.5 2 1.5 34.5 5.5 6 6 2.4 5.5 9 Show the Sample Output Using the Preceeding Input Reset command>Exercise18 11 How many points are in the set? 6 Enter 6 points: 1 2.4 2.5 2 1.5 34.5 5.5 6 6 2.4 5.59 The convex hull is (2.5, 2.0) (6.0, 2.4) (5.5, 9.0) (1.5, 34.5) (1.0, 2.4) command> 18: Developing Efficient Algorithms ho Repeat Step 2: A convex hullis expanded repeatedly (a) ho is the rightmost lowest point in S. (b) Step 2 finds point t. (c) A convex hull is expanded repeatedly. (d) A convex hull is found when t, becomes ho Sample Run for Exercise 18_11 Enter input data for the program (Sample data provided below. You may modify it.) 1 2.4 2.5 2 1.5 34.5 5.5 6 6 2.4 5.5 9 Show the Sample Output Using the Preceeding Input Reset command>Exercise18 11 How many points are in the set? 6 Enter 6 points: 1 2.4 2.5 2 1.5 34.5 5.5 6 6 2.4 5.59 The convex hull is (2.5, 2.0) (6.0, 2.4) (5.5, 9.0) (1.5, 34.5) (1.0, 2.4) command>
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access with AI-Powered Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started