Identifizieren der Ecken eines Polygons im 2D-Raum

Question

Da vier (x, y) Paare, die die vier Ecken eines beliebigen Polygons (Viereck) im 2D-Raum darstellen, würde Ich mag identifizieren:

1. Ob das Polygon konvex
2. Wenn es konvex ist, der die oben links, oben rechts, unten links und unten rechts

ich tue dies als Teil eines Bildverarbeitungsprogramms, insbesondere Punkt stellt so Angenommen, die Y-Achse wird umgedreht (dh positive Werte bewegen sich von oben nach unten).

---

Mein erster Gedanke war, den Begrenzungsrahmen des Polygons zu bekommen, dann messen Sie den Abstand von jedem Scheitel von den Ecken des Begrenzungsrahmens. Bestimmen Sie dann für jeden Eckpunkt des Polygons, welcher Ecke des Begrenzungsrahmens dieser am nächsten ist, und kennzeichnen Sie ihn entsprechend. Das gilt nicht für Polygone funktionieren wie:

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

Die linke obere Ecke des Vielecks ist am nächsten an der rechten oberen Ecke des Begrenzungsrahmens. Außerdem ist es nicht der nächstgelegene Stützpunkt zur oberen linken Ecke der Begrenzungsbox.

Answer 1

Um zu bestimmen, ob das Polygon konvex ist, könnten Sie etwas Ähnliches wie in einer Graham scan verwenden und durch die Punkte gehen und prüfen, ob Sie jedes Mal eine Rechts- (oder Links) -Richtung erhalten.

Um zu bestimmen, welche Ecken wo sind, können Sie sehen, welche Punkte am wenigsten x und y haben; und wähle einen davon aus, der links unten sein soll. Sie könnten zusammen incide, was gut ist, aber wenn nicht, na ja, nicht immer leicht zu sagen, was unten links sein sollte, wie hier:

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

Sobald Sie auf die man Ihren Boden entschieden haben, links, man kann einfach durch die Ecken gehen und sie entsprechend beschriften. Um herauszufinden, in welcher Reihenfolge sie sich befinden, überprüfe einfach, ob du mit dem oben genannten Check alles richtig gemacht hast.

Answer 2

Nun, da ich das Problem festgestellt habe kurz und bündig eine andere Lösung zu mir kam:

1. Zeichnen von Linien zwischen jedem der Scheitel
2. Bestimmen Sie, welche Linien die Diagonale durch Prüfen, ob die verbleibenden zwei Punkte auf liegen gegenüberliegende Seiten der Linie oder die gleiche Seite
3. Wenn genau zwei Diagonalen mit dieser Methode gefunden werden, ist das Polygon konvex.
4. Die Diagonale mit negativer Neigung verbindet die untere linke Ecke mit der oberen rechten Ecke und die Diagonale mit positiver Neigung verbindet die obere linke Ecke mit der unteren rechten Ecke.

Gibt es einen einfacheren Weg?

Answer 3

Das Viereck ist konvex, wenn beide Diagonalen innerhalb des Vierecks liegen und sich somit schneiden. Die untere linke Ecke ist der Punkt, der sich unterhalb und links vom Schnittpunkt befindet. Analoge Bedingungen gelten für die anderen drei Ecken.

Wenn Sie die Reihenfolge der Punkte nicht im Voraus kennen, kennen Sie keine gegenüberliegenden Ecken, daher die Diagonalen. In diesem Fall müssen Sie den Schnittpunkt aller möglichen sechs Segmente berechnen. Wenn das Polygon konvex ist, erhalten Sie genau einen Schnittpunkt und Sie können damit die vier Ecken bestimmen. Wenn das Polygon nicht konvex ist, gibt es keinen Schnittpunkt.

UPDATE

habe ich ein Programm kleines C# meinen Vorschlag zu prüfen. Konvex-konkav-Erkennung funktioniert wie erwartet, aber es gibt immer noch Fälle, in denen die Eckenerkennung fehlschlägt (siehe Testfall 3 im Code). Aber es sollte ziemlich einfach sein, dieses Problem zu lösen.

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.