Identifying the corners of a polygon in 2d space

Answer 1

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?

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.