Find corners in array of points

This is a discussion on Find corners in array of points within the C Programming forums, part of the General Programming Boards category; Hi! I have an array of points, describing a rectangular shaped polygon. And I am looking for a function to ...

  1. #1
    Registered User
    Join Date
    May 2011
    Location
    Sweden
    Posts
    24

    Find corners in array of points

    Hi!

    I have an array of points, describing a rectangular shaped polygon. And I am looking for a function to extract the four corners of that polygon.

    The difficulty I am facing is that the top-left corner is not necessarily the point where x & y are the closest to 0.
    Y can be higher on the middle if the polygon is bent. And X isn't n necessarily the same on both right corners if the polygon is a parallelogram.

    What i need is an algorithm that detects the two bends furthest out on both sides of the polygon, and I have no idea how to do this.

    Has anyone done something similar?

    //John Erlandsson

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Sounds like you want the convex hull.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,418
    Do you have some pictures?
    Apart from the 4 points which make up the corners, how are the rest of the points distributed?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    I don't understand how a rectangular shaped polygon can be "bent".
    The points you have are not just the corners, but are coordinates all along the polygon's four segments? If so, how much of an error do they have?

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by nonoob View Post
    I don't understand how a rectangular shaped polygon can be "bent".
    I think he means it could be oriented like a ♦ (a diamond if I've messed up the typing).

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,427
    I think by bent he means bulging sides, though he does mention that the corners aren't right angles (a la diamond, parallelogram). Googling "corner detection" came up with a handful of algorithms, most of which look somewhat complex, and are geared toward image processing, not dealing simply with points.

    Is your array of points "in order". That is, are they in the order you would encounter them if you walked around the shape? If so, you could walk around the image, looking at the angle from the previous point to the current point, and from the current point to the next point. If the difference between those two angles is more than some threshold (say 15 degrees)*, you have yourself a corner. Depending on the closeness of your points, and what they're measured in, you may need to use points farther from your current point, like say 10 spaces back and 10 spaces forward. It's crude, but might work for your purposes.

    * EDIT: The threshold really should check if you're more than X degrees from a straight line, i.e. for a 15 degree threshold, the difference should be less than 165 degrees, or more than 195. Also, there may be some slicker way to get the angle between those 3 points, but I'm not feeling like digging up any of my trig knowledge right now.
    Last edited by anduril462; 05-20-2011 at 11:34 AM.

  7. #7
    Registered User
    Join Date
    May 2011
    Location
    Sweden
    Posts
    24
    Sounds like you want the convex hull.
    I tried the convex hull algorithm included in opencv. But i could not find a way to limit it to only four points.

    Apart from the 4 points which make up the corners, how are the rest of the points distributed?
    I don't understand how a rectangular shaped polygon can be "bent".
    Here is an extreme example of my polygon. (This polygon is filled, but my array consists of the points describing its contour)

    Googling "corner detection" came up with a handful of algorithms, most of which look somewhat complex, and are geared toward image processing, not dealing simply with points.
    My application is in fact an image processing application. My first...
    There are opencv functions for corner detection from the pixels of the image. But I need the contour points anyway, and thought there might be som clever way of sorting the array.

    I will look in to the "stepping through the array looking for extreme angle" idea right away, but other ideas are also very much appreciated.

    Thank you all for helping

    //John

  8. #8
    Registered User
    Join Date
    May 2011
    Location
    Sweden
    Posts
    24
    Ok.. Here is what I came up with:

    First I'll explain the opencv specific variables:
    CvSeq = A struct containing my contour, from which i can extract CvPoint objects
    CvPoint = A struct containing int x and int y

    Prototype of function for extracting CvPoints from CvSeq:
    CVAPI(schar*) cvGetSeqElem( const CvSeq* seq, int index );

    Here is my function:
    Code:
    CvPoint *findCorners( CvSeq *contour, int max_corners, int min_angle, int min_distance )
    {
        CvPoint *ret = malloc( sizeof( CvPoint ) * max_corners );
        CvPoint *p1, *p2, *p3;
        double prevAngle = 0;
        double distance = 0;
    
        int cc = 0;
    
        for( int i = 0; i < (contour->total + 3); i++ )
        {
            if( i > 2 )
            {
                if( i - contour->total < 0 ) //Handle the overlapping steps of the loop
                {
                    p1 = (CvPoint *)cvGetSeqElem( contour, i - 2 );
                    p2 = (CvPoint *)cvGetSeqElem( contour, i - 1 );
                    p3 = (CvPoint *)cvGetSeqElem( contour, i );
                }
                else if( i - contour->total == 0 )
                {
                    p1 = (CvPoint *)cvGetSeqElem( contour, i - 2 );
                    p2 = (CvPoint *)cvGetSeqElem( contour, i - 1 );
                    p3 = (CvPoint *)cvGetSeqElem( contour, 0 );
                }
                else if( i - contour->total == 1 )
                {
                    p1 = (CvPoint *)cvGetSeqElem( contour, i - 2 );
                    p2 = (CvPoint *)cvGetSeqElem( contour, 0 );
                    p3 = (CvPoint *)cvGetSeqElem( contour, 1 );
                }
                else
                {
                    p1 = (CvPoint *)cvGetSeqElem( contour, i - contour->total - 2 );
                    p2 = (CvPoint *)cvGetSeqElem( contour, i - contour->total - 1 );
                    p3 = (CvPoint *)cvGetSeqElem( contour, i - contour->total );
                }
    
                //Calculate angle between points 1 and 3
                double currAngle = atan2( p1->y - p3->y, p1->x - p3->x ) * 180 / PI;
                if( currAngle < 0 )
                    currAngle = (currAngle * -1);
    
                if( i > 3 )
                {
                    //calculate the difference between this angle and the previous one
                    double diffAngle = prevAngle - currAngle;
    
                    if( diffAngle < 0 ) //Make sure sign is positive
                        diffAngle = (diffAngle * -1);
    
    
                    //Add point to return array if angle diff is above threshold
                    if( diffAngle > min_angle )
                    {
                        //Ignore points that are closer than "min_distance pixels" to the previous point
                        if( cc > 0 )
                        {
                            double dx;
                            if(p1->x > ret[cc - 1].x)
                                dx = (double)(p1->x - ret[cc - 1].x);
                            else
                                dx = (double)(ret[cc - 1].x - p1->x);
    
                            double dy;
                            if(p1->y > ret[cc - 1].y)
                                dy = p1->y - ret[cc - 1].y;
                            else
                                dy = ret[cc - 1].y - p1->y;
    
                            distance = sqrtf( (dx * dx) + (dy * dy) );
    
                            if( distance >= min_distance )
                            {
                                ret[cc] = *p1;
                                cc++;
                            }
                        }
                        else
                        {
                            ret[cc] = *p1;
                            cc++;
                        }
    
                        if( cc > max_corners )
                            break;
    
                    }
                }
    
                prevAngle = currAngle;
            }
    
        }
        
        if( cc < max_corners )
            fprintf( stderr, "Find corners: found %d of %d corners\n", cc, max_corners );
            
        return ret;
    }
    I would appreciate any feedback on this function. Not only on its functionality, but also general mistakes or bad behaviors in my coding.

    Thanks

    //John
    Last edited by John Erlandsson; 05-20-2011 at 08:26 PM. Reason: spelling error

  9. #9
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,230
    Code:
    double currAngle = atan2( p1->y - p3->y, p1->x - p3->x ) * 180 / PI;
                if( currAngle < 0 )
                    currAngle = (currAngle * -1);
    1. It's a bit odd to scale the angles to degrees instead of radians. When dealing with angles, you usually will eventually feed that angle back into a trig function, and those functions want angles in radians.
    2. Negating the angle is incorrect -- this produces a mirror of the true angle. You just want to add 2*Pi to it. EDIT: Ahh, you're just trying to get the size of the angle, not its correct sign. Guess you're okay then.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #10
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,147
    I'm having a real difficult time figuring out why words like "rectangular", "parallelogram", and to be honest even "polygon" was used to describe this object.

    This looks to me more like the curve points you'd get from processing a Bézier curve.

    Anyway, I'm concerned by what seems to be conflicting information here. Do you only have four points? Do you have every point along the curve? Do you operate on only four points to generate the others? Do you process all the points in any order? Is the order randomized? Or is the order in some fixed format?

    Soma

  11. #11
    Registered User
    Join Date
    May 2011
    Location
    Sweden
    Posts
    24
    Quote Originally Posted by phantomotap View Post
    I'm having a real difficult time figuring out why words like "rectangular", "parallelogram", and to be honest even "polygon" was used to describe this object.

    This looks to me more like the curve points you'd get from processing a Bézier curve.

    Anyway, I'm concerned by what seems to be conflicting information here. Do you only have four points? Do you have every point along the curve? Do you operate on only four points to generate the others? Do you process all the points in any order? Is the order randomized? Or is the order in some fixed format?

    Soma
    Sorry about the poor description. English is not my primary language...

    I have every point along the objects contour.
    The points are extracted from the image using a function called "cvFindContours", which seem to return the points in order from start-end going clockwise.
    Only the startingpoint differs if I rotate/move the object.

    Thanks for taking an interest

    //John

  12. #12
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,427
    This looks more or less like what I was thinking. Some general comments:
    Code:
    double diffAngle = prevAngle - currAngle;
    
    if( diffAngle < 0 ) //Make sure sign is positive
        diffAngle = (diffAngle * -1);
    fabs give absolute value of a double, so you can just use diffAngle = fabs(prevAngle - currAngle);

    Your distance calc could be simplified. You don't need the if-else, or even an fabs since the squaring will get rid of the negatives.
    Code:
    dx = ret[cc - 1].x - p1->x;  // no need for if-else or fabs
    dy = ret[cc - 1].y - p1->x;
    distance = sqrtf( (dx * dx) + (dy * dy) );  // dx*dx will always be positive
    ret only has room for max_corners elements, which means valid values for cc are 0 to max_corners-1. That makes ret[cc] = *p1; an array overflow when cc equals max_corners. You need to fix the error handling near the bottom of your function so you break out on cc >= max_corners, and probably fix your error printing, since I would assume finding too many corners is also an error.

  13. #13
    Registered User
    Join Date
    May 2011
    Location
    Sweden
    Posts
    24
    Hello again!

    This is actually turning in to something good... I am still working on the function, making it find the center of a rounded corner and such. I also prepare the contour before calling the function, removing everything but the points 10 pixels in from the rightmost and leftmost points.

    I think we can call this one solved, thanks for helping.

    //John

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Collisions does not take affect on the corners
    By bijan311 in forum C++ Programming
    Replies: 4
    Last Post: 05-21-2010, 08:34 PM
  2. Replies: 12
    Last Post: 11-20-2007, 08:35 AM
  3. find the outer polygon enclosing a set of points
    By itachi in forum C Programming
    Replies: 1
    Last Post: 02-18-2006, 02:38 AM
  4. Decimal Points and Binary Points
    By Shadow12345 in forum A Brief History of Cprogramming.com
    Replies: 9
    Last Post: 11-07-2002, 12:06 AM
  5. Round Corners/Holey Windows batman!
    By LuckY in forum Windows Programming
    Replies: 5
    Last Post: 07-25-2002, 12:30 AM

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