Identifying the corners of a polygon in 2d space

Question

Given four (x,y) pairs that represent the four corners of an arbitrary polygon (quadrilateral) in 2d space, I'd like to identify:

1. Whether the polygon is convex
2. If it is convex, Which particular point represents the top left, top right, bottom left, and bottom right corner

I'm doing this as part of an image processing program, so assume the Y-axis is flipped (i.e., positive values move down from the top).

---

My first thought was to get the bounding box of the polygon, then measure the distance of each vertex from the corners of the bounding box. Then for each vertex of the polygon, determine which corner of the bounding box it is closest to and label it accordingly. That does not work for polygons such as:

http://matt.bridges.name/polygon.png

The top-left vertex of the polygon is closest to the top-right corner of the bounding box. Also it is not the closest vertex to the top-left corner of the bounding box.

Answer 1

For determining if the polygon is convex, you could use something similar to what's used in a Graham scan, and go through the points, checking if you get a right (or left) turn every time.

For determining which corners are where, you can look at which points have the least x and y; and pick one of those to be the bottom left. They might co-incide, which is good, but if not, well, not always easy to tell what should be bottom left, such as here:

"Bottom left corner" is quite ambiguous http://a.imagehost.org/0894/bottomleftiswhich.png

Once you've decided on which one's your bottom left one, you can simply go through the corners in order and label them accordingly. To find out which order they're in, simply check if you make all right or all left turns with the above check.

Answer 2

The quadrilateral is convex if both diagonal are inside the quadrilateral and hence intersect. The bottom left corner is the point located below and to the left of the intersection point. Analog conditions hold for the other three corners.

If you don't know the order of the points in advance, you don't know opposite corners, hence the diagonals. In this case you have to calculate the intersection point of all possible six segments. If the polygon is convex, you will get exactly one intersection point and you can use it to determine the four corners. If the polygon is not convex, there will be no intersection point.

UPDATE

I created a small C# program to test my suggestion. Convex-concave-detection works as exspected, but there are still cases where the corner detection fails (see test case 3 in the code). But it should be quite simple to solve this issue.

CODE

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Globalization;
using System.Linq;
using System.Text;
using System.Threading;

namespace Quadrilaterals
{
    public class Program
    {
        public static void Main()
        {
            Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;

            Int32[,] tests = { { 0, 1, 2, 3 }, { 0, 2, 1, 3 }, { 0, 3, 1, 2 } };

            PointF[] points = { new PointF(4, -2), new PointF(2, 5), new PointF(8, -6), new PointF(10, 7) };
            //PointF[] points = { new PointF(0, 0), new PointF(10, 0), new PointF(5, 10), new PointF(5, 3) };
            //PointF[] points = { new PointF(4, -2), new PointF(3, -1), new PointF(0, 0), new PointF(1, 0) };

            PointF? p = null;

            for (Int32 i = 0; i < 3; i++)
            {
                Console.WriteLine("Intersecting segments ({0}|{1}) and ({2}|{3}).", tests[i, 0], tests[i, 1], tests[i, 2], tests[i, 3]);

                Single? f1 = IntersectLines(points[tests[i, 0]], points[tests[i, 1]], points[tests[i, 2]], points[tests[i, 3]]);
                Single? f2 = IntersectLines(points[tests[i, 2]], points[tests[i, 3]], points[tests[i, 0]], points[tests[i, 1]]);

                if ((f1 != null) && (f2 != null))
                {
                    PointF pp = PointOnLine(points[tests[i, 0]], points[tests[i, 1]], f1.Value);

                    Console.WriteLine("  Lines intersect at ({0}|{1}) with factors {2} and {3}.", pp.X, pp.Y, f1, f2);

                    if ((f1 > 0) && (f1 < 1) && (f2 > 0) && (f2 < 1))
                    {
                        Console.WriteLine("  Segments intersect.");

                        p = pp;
                    }
                    else
                    {
                        Console.WriteLine("  Segments do not intersect.");
                    }
                }
                else
                {
                    Console.WriteLine("  Lines are parallel.");
                }
            }

            if (p == null)
            {
                Console.WriteLine("The quadrilateral is concave.");
            }
            else
            {
                Console.WriteLine("The quadrilateral is convex.");

                for (Int32 j = 0; j < 4; j++)
                {
                    Console.WriteLine("   Point {0} ({3}|{4}) is the {1} {2} corner.", j, (points[j].Y < p.Value.Y) ? "bottom" : "top", (points[j].X < p.Value.X) ? "left" : "right", points[j].X, points[j].Y);
                }
            }

            Console.ReadLine();
        }

        private static Single? IntersectLines(PointF a1, PointF a2, PointF b1, PointF b2)
        {
            PointF r = Difference(a1, b1);
            PointF a = Difference(a2, a1);
            PointF b = Difference(b2, b1);

            Single p = r.X * b.Y - r.Y * b.X;
            Single q = a.Y * b.X - a.X * b.Y;

            return (Math.Abs(q) > Single.Epsilon) ? (p / q) : (Single?)null;
        }

        private static PointF Difference(PointF a, PointF b)
        {
            return new PointF(a.X - b.X, a.Y - b.Y);
        }

        private static PointF PointOnLine(PointF a, PointF b, Single f)
        {
            return new PointF(a.X + f * (b.X - a.X), a.Y + f * (b.Y - a.Y));
        }
    }
}

OUTPUT

Intersecting segments (0|1) and (2|3).
  Lines intersect at (7|-12.5) with factors -1.5 and -0.5.
  Segments do not intersect.
Intersecting segments (0|2) and (1|3).
  Lines intersect at (-2|4) with factors -1.5 and -0.5.
  Segments do not intersect.
Intersecting segments (0|3) and (1|2).
  Lines intersect at (5|-0.4999999) with factors 0.1666667 and 0.5.
  Segments intersect.
The quadrilateral is convex.
   Point 0 (4|-2) is the bottom left corner.
   Point 1 (2|5) is the top left corner.
   Point 2 (8|-6) is the bottom right corner.
   Point 3 (10|7) is the top right corner.

Answer 3

Now that I've stated the problem succinctly another solution came to me:

1. Draw lines between each of the vertices
2. Determine which lines are the diagonal by checking if the remaining two points lie on opposite sides of the line or the same side
3. If exactly two diagonals are found using this method, the polygon is convex.
4. The diagonal with negative slope connexts the bottom-left corner with the top-right corner, and the diagonal with positive slope connects the top-left corner with the bottom-right corner.

Is there an easier way?