Выявление углов многоугольника в 2d пространстве

Question

Учитывая четыре (x, y) пары, которые представляют четыре угла произвольного многоугольника (четырехугольника) в 2-мерном пространстве, я хотел бы определить:

1. Является ли многоугольник выпуклым
2. Если оно выпуклое, какая конкретная точка представляет верхний левый, верхний правый, нижний левый и нижний правый угол

Я делаю это как часть программы обработки изображений, поэтому предположим, что ось Y перевернута (т.е. положительные значения перемещаются сверху вниз).

---

Моей первой мыслью было получить ограничивающий прямоугольник многоугольника, а затем измерить расстояние каждой вершины от углов ограничивающего прямоугольника. Затем для каждой вершины многоугольника определите, к какому углу ограничивающего прямоугольника он ближе всего, и пометьте его соответствующим образом. Это не работает для полигонов, таких как:

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

Верхняя левая вершина многоугольника находится ближе всего к верхнему правому углу ограничительной рамки. Также это не ближайшая вершина к верхнему левому углу ограничительной рамки.

Answer 1

Чтобы определить, является ли многоугольник выпуклым, вы можете использовать что-то похожее на то, что использовалось в сканировании Грэма , и пройтись по точкам, проверяя, получаете ли вы право (или налево) поворот каждый раз.

Для определения того, какие углы находятся, вы можете посмотреть, какие точки имеют наименьшие значения x и y; и выберите один из них внизу слева. Они могут совпасть, что хорошо, но если нет, то не всегда легко сказать, что должно быть слева внизу, например:

"Нижний левый угол" весьма неоднозначен http://a.imagehost.org/0894/bottomleftiswhich.png

Как только вы определились с тем, какой из них ваш нижний левый, вы можете просто пройти по углам по порядку и соответствующим образом пометить их. Чтобы выяснить, в каком порядке они находятся, просто проверьте, выполнили ли вы все правые или левые повороты с помощью вышеуказанной проверки.

Answer 2

Четырехугольник выпуклый, если обе диагонали находятся внутри четырехугольника и, следовательно, пересекаются. Левый нижний угол - это точка, расположенная ниже и слева от точки пересечения. Аналоговые условия выполняются для остальных трех углов.

Если вы не знаете порядок точек заранее, вы не знаете противоположных углов, отсюда и диагонали. В этом случае вы должны рассчитать точку пересечения всех шести возможных отрезков. Если многоугольник выпуклый, вы получите ровно одну точку пересечения и можете использовать ее для определения четырех углов. Если многоугольник не является выпуклым, точка пересечения не будет.

UPDATE

Я создал небольшую программу на C #, чтобы проверить мое предложение. Выпукло-вогнутое обнаружение работает, как и ожидалось, но все еще есть случаи, когда обнаружение угла не удается (см. Контрольный пример 3 в коде). Но решить эту проблему должно быть довольно просто.

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

Теперь, когда я кратко изложил проблему, ко мне пришло другое решение:

1. Нарисуйте линии между каждой из вершин
2. Определите, какие линии имеют диагональ, проверив, лежат ли две оставшиеся точки на противоположных сторонах линии или на той же стороне
3. Если при использовании этого метода найдено ровно две диагонали, полигон выпуклый.
4. Диагональ с отрицательным наклоном соединяет левый нижний угол с верхним правым углом, а диагональ с положительным наклоном соединяет верхний левый угол с нижним правым углом.

Есть ли более простой способ?