How to implement the GRAHAM\'S SCAN algorithm using JSXGraph using a Code: Conve

Question

How to implement the GRAHAM'S SCAN algorithm using JSXGraph using a Code: ConvexHull.html

I have this code to implement a Graham's Scan algorithm using JSXGraph and this part of the code to draw a polygon on a board using a set of points. I need help with implementing this part of the code:

/* The Graham's scan function */

function findConvexHull(board) {

var N = 0, P = {};

for(var el in board.objects)

if(board.objects[el].elType == 'point') {

P[N] = board.objects[el];

N++;

}

// sort the point set P; to obtain the x-coordinate of 'p', simply use 'p.X()' and similarly you can use 'p.Y()' for the y-coordinate

function p.X()

function p.Y()

// run Graham's scan to obtain the convex hull points in some order (clockwise/anticlokwise)

What to implement here?

/* draw line segments between the convex hull points to obtain the final convex polygon; to draw line segment you can simply use --> board.create('segment',[p1,p2],{fillColor: 'green',strokeColor:'green'}); where p1,p2 are the two end-points */

board.create('segment',[p1,p2],{fillColor: 'green',strokeColor:'green'});(How to implement the function)

}

Thanks for the help

Explanation / Answer

As per your requirement for this :-

/* The Graham's scan function */

function findConvexHull(board) {

var N = 0, P = {};

for(var el in board.objects)

if(board.objects[el].elType == 'point') {

P[N] = board.objects[el];

N++;

}

ANSWER :

/ sort the point set P; to obtain the x-coordinate of 'p', simply use 'p.X()' and similarly you can use 'p.Y()' for the y-coordinate
function p.X() min_x = 1, max_x = 1;
for (int i=1; i<n; i++)
{
   if (a[i].first < a[min_x].first)
      min_x = i;
    if (a[i].first > a[max_x].first)
     max_x = i;
}
function p.Y() min_x = 1, max_x = 1;
for (int i=1; i&lt;n; i++)
{
   if (a[i].first &lt; a[min_x].first)
      min_x = i;
    if (a[i].first &gt; a[max_x].first)
     max_x = i;
}

/* I think you might got according to particular part of your dought .Now you can implement the fuction*/

And for below two requirements you can use the given below code
// run Graham's scan to obtain the convex hull points in some order (clockwise/anticlokwise)
What to implement here?
/* draw line segments between the convex hull points to obtain the final convex polygon; to draw line segment you can simply use --> board.create('segment',[p1,p2],{fillColor: 'green',strokeColor:'green'}); where p1,p2 are the two end-points */
board.create('segment',[p1,p2],
{fillColor: 'green',strokeColor:'green'});

(How to implement the function)

}

ANSWER:

  // for explanation of orientation() as clockwise or anticlockwise
#include <iostream>
#include <stack>
#include <stdlib.h>
using namespace std;

struct Point
{
        int x;
        int y;
};

Point p0;

// A utility function to find next to top in a stack
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 dist(Point p1, Point p2)
{
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}

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 (dist(p0, *p2) >= dist(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);

    // 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 < n; 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, 3 }, { 1, 1 }, { 2, 2 }, { 4, 4 }, { 0, 0 },
            { 1, 2 }, { 3, 1 }, { 3, 3 } };
    int n = sizeof(points) / sizeof(points[0]);
    cout << "The points in the convex hull are: ";
    convexHull(points, n);
    return 0;
}

//************ HAPPY TO HELP *************//

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.