Определение углов многоугольника в 2d пространстве

Question

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

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

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

---

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

UPDATE

Я создал небольшой C# программу, чтобы проверить мое предложение. Выпуклый-вогнутый-детектирование работает как ожидалось, но все же есть случаи, когда обнаружение углов не удается (см. Тестовый пример 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.