2

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.

4
  • Do you know the order of the points or are the points unordered? Aug 22, 2009 at 13:54
  • The order of points must be known; there are multiple polygons with 4 given corners. Aug 22, 2009 at 13:56
  • There are the following cases. 1. Three points form a triangle and the last point is inside this triangle. In this case there are three possible quadrilaterals and they are all non-convex. 2. In all other cases there three possible quadrilaterals, too. One is convex and the other two are self-intersecting. Hence the questions can also be answered if the order is not know (and self-intersecting quadrilaterals are not considered). Aug 22, 2009 at 14:15
  • The points are unordered, selected arbitrarily by the user. I want to detect the case (1) above, and report an error. In case 2, I want to find the one convex non-self-intersecting polygon and identify each corner as top-left, top-right, etc. Aug 22, 2009 at 15:53

3 Answers 3

4

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.

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?

0
1

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.
3
  • This is OK for a dart-like concave quad but for a bowtie-like concave shape (e.g. (0,0) (0,2) (2,0) (2,2) ) there is still one intersection so it will be detected as convex.
    – danio
    Aug 26, 2009 at 10:46
  • The points are unordered and self-intersecting polygons are not considered as the opener stated in a comment. Hence your example would be detected as the convex polygon (0,0)(2,0)(2,2)(0,2). Aug 26, 2009 at 11:47
  • OK missed the fact that the points are unordered in the comments. I think it would be worth clarifying that assumptions in your answer. Currently the way it is stated doesn't make it 100% clear IMO.
    – danio
    Aug 26, 2009 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.