Punkt-in-Polygon-Test nach Jordan funktioniert nicht

  • C#
  • .NET (FX) 4.0

Es gibt 14 Antworten in diesem Thema. Der letzte Beitrag () ist von Trade.

    Punkt-in-Polygon-Test nach Jordan funktioniert nicht

    Moin,

    zusammen mit @Gonger96 habe ich gestern in SharpMath noch einen kleinen Bug gefunden, der bei mir beim Testen nicht vorkam.
    Dazu haben wir eine Testanwendung erstellt und einfach eine Form hinzugefügt:

    C#-Quellcode

    1. using System.Drawing;
    2. using System.Windows.Forms;
    3. using SharpMath.Geometry;
    5. namespace PolygonTest
    6. {
    7. public partial class Form1 : Form
    8. {
    9. private readonly Polygon _p;
    10. private readonly PointF[] _pts =
    11. {
    12. new PointF(0, 0), new PointF(200, 80), new PointF(400, 200),
    13. new PointF(100, 60)
    14. };
    15. private bool _b;
    17. public Form1()
    18. {
    19. InitializeComponent();
    20. _p =
    21. new Polygon(new Point2D(0, 0), new Point2D(200, 80), new Point2D(400, 200), new Point2D(100, 60));
    22. }
    24. private void Form1_Paint(object sender, PaintEventArgs e)
    25. {
    26. e.Graphics.FillRectangle(Brushes.Black, ClientRectangle);
    27. e.Graphics.FillPolygon(_b ? Brushes.AliceBlue : Brushes.Red, _pts);
    28. }
    30. private void Form1_MouseMove(object sender, MouseEventArgs e)
    31. {
    32. bool bOld = _b;
    33. _b = _p.ContainsPoint(new Point2D(e.X, e.Y));
    34. if (_b != bOld)
    35. Invalidate();
    36. Text = e.Location.ToString();
    37. }
    38. }
    39. }


    Simpel, aber erledigt seine Arbeit. Es wird einfach ein entsprechendes Polygon gezeichnet und wenn sich die Maus innerhalb des Polygons befindet, dann soll dieses weiß gefüllt werden (normal ist es rot).
    Die Methode dazu habe ich geschrieben und dazu den Punkt-in-Polygon-Test nach Jordan implementiert. Das Ganze sieht so aus:

    C#-Quellcode

    1. /// <summary>
    2. /// Determines whether this <see cref="Polygon" /> contains the specified <see cref="Point" />.
    3. /// </summary>
    4. /// <param name="point">The <see cref="Point" /> to check.</param>
    5. /// <returns>
    6. /// <c>true</c> if this <see cref="Polygon" /> contains the specified <see cref="Point" />; otherwise <c>false</c>
    7. /// .
    8. /// </returns>
    9. public bool ContainsPoint(Point2D point)
    10. {
    11. double t = -1;
    12. var points = Points;
    13. //points[0] = points[points.Count - 1];
    14. int j = 1;
    15. for (int i = 0; i < points.Count; ++i)
    16. {
    17. t = t*ContainsPointInternal(point, points[i], points[j]);
    18. j++;
    19. if (j == points.Count)
    20. j = 0;
    21. }
    23. return t >= 0;
    24. }
    26. private int ContainsPointInternal(Point2D q, Point2D p1, Point2D p2)
    27. {
    28. Debug.Print($"From: {p1} to {p2}");
    29. if (FloatingNumber.AreApproximatelyEqual(q.Y, p1.Y) && FloatingNumber.AreApproximatelyEqual(p1.Y, p2.Y))
    30. {
    31. if ((p1.X <= q.X && q.X <= p2.X) || (p2.X <= q.X && q.X <= p1.X))
    32. return 0;
    33. return 1;
    34. }
    35. if (p1.Y > p2.Y)
    36. {
    37. var currentP1 = p1;
    38. p1 = p2;
    39. p2 = currentP1;
    40. }
    41. else if (FloatingNumber.AreApproximatelyEqual(q.Y, p1.Y) && FloatingNumber.AreApproximatelyEqual(q.X, p1.X))
    42. return 0;
    43. else if (q.Y <= p1.Y || q.Y > p2.Y)
    44. return 1;
    46. var delta = (p1.X - q.X)*(p2.Y - q.Y) - (p1.Y - q.Y)*(p2.X - q.X);
    47. if (delta > 0)
    48. return -1;
    49. return delta < 0 ? 1 : 0;
    50. }


    Das mit dem j ist im Pseudocode von Wikipedia nicht so gemacht, allerdings habe ich das so implementiert und so oder so funktioniert es nicht. Die auskommentierte Zeile verursachte außerdem, dass die Verbindung des letzten Punkts von ​100, 60 aus nicht mit ​0, 0, sondern eben ​200, 80 stattfand, sodass über dieser Strecke sowieso keine Punkte entdeckt wurden.
    Dennoch klappt das nicht und ich glaube, es ist am Einfachsten, das Problem visuell zu zeigen:



    Man sieht, es klappt auch mit der Erkennung, wenn ich im Polygon bin, allerdings macht er das tw. auch, wenn ich weiter unten bin. Ich tippe darauf, dass das mit einer entsprechenden Linie durch den einen Punkt ​100, 60 dort zusammenhängt, denn das wird ja auch geprüft, aber ich komme einfach nicht drauf, warum das so ist.
    Könnt Ihr mir da helfen?

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    @Trade SharpMath.Geometry und Polygon ist dabei was?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Wie gesagt, meine Bibliothek.
    github.com/ProgTrade/SharpMath…pMath/Geometry/Polygon.cs

    Die zwei Methoden von oben sind aber auf GitHub noch anders. Es geht nun um das oben.

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    Naja, aber das wäre zu umständlich, denn das sollte alles durch diesen Algorithmus bereits getan sein. Auf diese Weise würde ja das Grundproblem nicht behoben werden. ^^

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    @Trade Kannst Du mal einen compilierbaren Code / Projekt posten?
    =======
    Ich hab mal leere Hülsen für alle nicht vorhandenen Klassen / Methoden / Properties generiert und kann den Effekt reproduzieren.
    Ohne in den Code gesehen zu haben würde ich meinen, dass da ein Richtungsvektor eine übergroße / unendliche Länge hat, an der sich der Zustand scheidet.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „RodFromGermany“ ()

    @Gonger96 Habe Deinen Edit jetzt gesehen. Danke, wenn alles nicht klappt, dann werde ich das so implementieren. Das lässt sich ja relativ angenehm übersetzen.
    @RodFromGermany Im Anhang. Die Anwendung ist "PolygonTest".

    Grüße
    Dateien

    • SharpMath.zip

      (4,07 MB, 266 mal heruntergeladen, zuletzt: )
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    @Trade Ich hab mal alle Pixel entsprechend ihrer Antwort eingefärbt. Erst mal ohne Kommentar.

    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    @Trade Gelöst. Deine Methoden ContainsPoint() und ContainsPointInternal() waren nicht ganz korrekt, ich hab sie noch mal neu implementiert:
    Spoiler anzeigen

    C#-Quellcode

    1. public bool ContainsPoint(Point2D point)
    2. {
    3. double t = -1;
    4. List<Point2D> points = new List<Point2D>();
    5. points.AddRange(Points);
    6. points.Add(points[0]); // Dies insbesondere
    8. for (int i = 0; i < points.Count - 1; i++)
    9. {
    10. t = t * this.ContainsPointInternal(point, points[i], points[i + 1]);
    11. }
    13. return t >= 0;
    14. }
    16. /// <summary>
    17. /// −1, wenn der Strahl von A nach rechts die Kante [BC] schneidet (außer im unteren Endpunkt);
    18. /// 0, wenn A auf [BC] liegt;
    19. /// sonst +1
    20. /// </summary>
    21. /// <param name="A"></param>
    22. /// <param name="B"></param>
    23. /// <param name="C"></param>
    24. /// <returns></returns>
    25. private int ContainsPointInternal(Point2D A, Point2D B, Point2D C)
    26. {
    27. // Wenn y_A = y_B = y_C
    28. if (FloatingNumber.AreApproximatelyEqual(A.Y, B.Y) &&
    29. FloatingNumber.AreApproximatelyEqual(A.Y, C.Y))
    30. {
    31. // Wenn x_B ≤ x_A ≤ x_C oder x_C ≤ x_A ≤ x_B
    32. if ((B.X <= A.X && A.X <= C.X) ||
    33. (C.X <= A.X && A.X <= B.X))
    34. {
    35. return 0;
    36. }
    38. return 1;
    39. }
    41. // Wenn y_B > y_C
    42. if (B.Y > C.Y)
    43. {
    44. // Vertausche B und C
    45. var currentB = B;
    46. B = C;
    47. C = currentB;
    48. }
    50. // Wenn y_A = y_B und x_A = x_B
    51. if (FloatingNumber.AreApproximatelyEqual(A.Y, B.Y) &&
    52. FloatingNumber.AreApproximatelyEqual(A.X, B.X))
    53. {
    54. return 0;
    55. }
    57. // Wenn y_A ≤ y_B oder y_A > y_C
    58. if (A.Y <= B.Y || A.Y > C.Y)
    59. {
    60. return 1;
    61. }
    63. // Delta = (x_B−x_A) * (y_C−y_A) − (y_B−y_A) * (x_C−x_A)
    64. double Delta = (B.X - A.X) * (C.Y - A.Y) - (B.Y - A.Y) * (C.X - A.X);
    66. if (Delta > 0)
    67. {
    68. // Wenn Delta > 0
    69. return -1;
    70. }
    71. else if (Delta < 0)
    72. {
    73. // wenn Delta < 0
    74. return 1;
    75. }
    77. // sonst
    78. return 0;
    79. }

    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Danke, das klappt. :)
    Jetzt sehe ich den Fehler in Zeile 6, da hatte ich den Algorithmus falsch verstanden. n ist ja der Count, folglich hätte ich noch ein weiteres Item hinzufügen müssen, um auf diesen Index zu kommen. Was genau war bei ContainsPointInternal falsch?

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    Dein ContainsPointInternal() mit dem richtigen ContainsPoint() bringt dieses Bild, algorithmisch hab ich das nicht untersucht:

    =====
    @Trade Ich merke, Du hast noch nix von Fortran & Co hehört.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „RodFromGermany“ ()

    Musste das erstmal googlen. Was ist damit im Kontext bzw. was willst Du mir damit sagen?

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    @Trade Der Pseudo-Code bei Wiki ist mit Kenntnis der alten Programmiersprache Fortran ganz easy zu lesen.
    Indices fangen dort z.B. bei 1 an.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Ah okay, das ist gut zu wissen. Kannte ich wirklich nicht.

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

Facebook
Telefonspende