How to write points in this algorithm

This is a discussion on How to write points in this algorithm within the C++ Programming forums, part of the General Programming Boards category; Hi all! I have found Andrew's monotone convex hull algorithm implemented on the net: Algorithm Implementation/Geometry/Convex hull/Monotone chain - Wikibooks, ...

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    19

    Question How to write points in this algorithm

    Hi all!

    I have found Andrew's monotone convex hull algorithm implemented on the net:
    Algorithm Implementation/Geometry/Convex hull/Monotone chain - Wikibooks, open books for an open world

    This is perfect for me, but I have an irritating problem... I just can't figure out how to use the stuct Point. Here's the implementation:
    Code:
    // Implementation of Andrew's monotone chain 2D convex hull algorithm.
    // Asymptotic complexity: O(n log n).
    // Practical performance: 0.5-1.0 seconds for n=1000000 on a 1GHz machine.
    #include <algorithm>
    #include <vector>
    using namespace std;
     
    typedef int coord_t;         // coordinate type
    typedef long long coord2_t;  // must be big enough to hold 2*max(|coordinate|)^2
     
    struct Point {
            coord_t x, y;
     
            bool operator <(const Point &p) const {
                    return x < p.x || (x == p.x && y < p.y);
            }
    };
     
    // 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
    // Returns a positive value, if OAB makes a counter-clockwise turn,
    // negative for clockwise turn, and zero if the points are collinear.
    coord2_t cross(const Point &O, const Point &A, const Point &B)
    {
            return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
    }
     
    // Returns a list of points on the convex hull in counter-clockwise order.
    // Note: the last point in the returned list is the same as the first one.
    vector<Point> convex_hull(vector<Point> P)
    {
            int n = P.size(), k = 0;
            vector<Point> H(2*n);
     
            // Sort points lexicographically
            sort(P.begin(), P.end());
     
            // Build lower hull
            for (int i = 0; i < n; i++) {
                    while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
                    H[k++] = P[i];
            }
     
            // Build upper hull
            for (int i = n-2, t = k+1; i >= 0; i--) {
                    while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
                    H[k++] = P[i];
            }
     
            H.resize(k);
            return H;
    }
    If i for example want to use the method cross(), then what do I write? This seems the most logical: cross(1.1, 3.9, 11.0), but this is read as doubles.

    I don't want to use the cross method of cause, just to understand how Points are written, so I can supply the convex_hull method with a vector containing these Points.

    Best regards
    Jannick
    Last edited by animation; 06-17-2011 at 06:38 AM.

  2. #2
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    839
    the function accepts Points, a pair of x and y values, not single numbers. you need to declare instances of Points, assign values to their members, and pass them into the function.

  3. #3
    Registered User
    Join Date
    Mar 2011
    Posts
    19
    Quote Originally Posted by m37h0d View Post
    the function accepts Points, a pair of x and y values, not single numbers. you need to declare instances of Points, assign values to their members, and pass them into the function.
    Cool!
    Code:
    Point a = {2,5};

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Points on circle
    By Suchy in forum C++ Programming
    Replies: 2
    Last Post: 11-16-2008, 03:08 PM
  2. problem with fout.write: cannot write 0x0A (10 dec)
    By yvesdefrenne in forum C++ Programming
    Replies: 7
    Last Post: 05-23-2005, 01:53 PM
  3. +/- Rep Points
    By jrahhali in forum A Brief History of Cprogramming.com
    Replies: 42
    Last Post: 01-01-2005, 01:16 PM
  4. Decimal Points and Binary Points
    By Shadow12345 in forum A Brief History of Cprogramming.com
    Replies: 9
    Last Post: 11-07-2002, 01:06 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21