Identifying polygon corners in 2d space
Given the four (x, y) pairs that represent the four corners of an arbitrary polygon (quad) in 2d space, I would like to define:
- Is the polygon convex
- If it is convex, what particular point represents the top-left, top-right, bottom-left, and bottom-right corners.
I'm doing this as part of an imaging program, so let's assume the Y-axis is inverted (i.e. positive values move downward).
My first thought was to get the bounding box of the polygon and 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 is closest and label it accordingly. This doesn't work for polygons like:
http://matt.bridges.name/polygon.png
The top-left vertex of the polygon is closest to the top-right corner of the bounding rectangle. Also, it is not the closest vertex to the top-left corner of the bounding box.
source to share
To determine if a polygon is convex, you can use something similar to the one used in Graham scan and step through the points, checking if you get right (or left) correctly each time.
To determine which angles are where, you can look at which points have the smallest x and y; and select one of them to be at the bottom left. They can be joint, which is good, but if not, it is not always easy to say what should be at the bottom left, for example here:
"Bottom left corner" is rather ambiguous http://a.imagehost.org/0894/bottomleftiswhich.png
Once you've determined on what basis you left it, you can simply go through the corners in order and mark them accordingly. To find out what order they are in, just check if you do all right or all left turns with the above check.
source to share
Now that I've summarized the problem, I got another solution:
- Draw lines between each of the vertices
- Determine which lines are diagonal by checking if the other two points are on opposite sides of the line or on the same side
- If this method finds exactly two diagonals, the polygon is convex.
- A negative slope diagonal connects the bottom left corner to the upper right corner, and a positive slope diagonal connects the upper left corner to the lower right corner.
Is there an easier way?
source to share
A quadrilateral is convex if both diagonals are inside the quadrilateral and therefore intersect. The bottom left corner is the point below and to the left of the intersection. The analogue conditions hold for the other three corners.
If you do not know the order of the points in advance, you do not know the opposite angles, hence the diagonals. In this case, you need 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 define four corners. If the polygon is not convex, then there will be no intersection point.
UPDATE
I created a small C # program to test my suggestion. Convex-concave-detection works as expected, but there are still cases where corner detection fails (see Test Case 3 in code). But solving this problem is quite simple.
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.
source to share