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

Sounds like you want the convex hull.

Do you have some pictures?
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".
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?

Originally Posted by nonoob

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).

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.

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

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

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.

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

Originally Posted by phantomotap

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

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.

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