识别二维空间中多边形的角点

要确定多边形是否为凸多边形,可以使用类似于 Graham scan ,然后通过各点,检查每次是否右转(或左转)。

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

一旦你决定了哪一个是你的左下角,你可以简单地按顺序穿过各个角落,并相应地贴上标签。要找出它们的顺序,只需用上面的检查来检查你是全部右转还是全部左转。

既然我已经简明扼要地说明了这个问题,我又想到了另一个解决办法:

2. 通过检查其余两点是否位于直线的相对侧或同一侧,确定哪些直线是对角线
3. 如果使用此方法正好找到两条对角线,则多边形是凸的。
4. 具有负坡度的对角线连接左下角和右上角,具有正坡度的对角线连接左上角和右下角。

有没有更简单的方法?

如果您事先不知道点的顺序,您就不知道对角点,因此也不知道对角线。在这种情况下,必须计算所有可能的六条线段的交点。如果多边形是凸的,您将得到一个交点,您可以使用它来确定四个角。如果多边形不是凸的,则没有交点。

使现代化

我创建了一个小型C#程序来测试我的建议。凸凹检测的工作原理与exspected相同,但仍然存在拐角检测失败的情况(请参见代码中的测试用例3)。但解决这个问题应该很简单。

密码

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));
        }
    }
}

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.