mikrocontroller.net

Forum: PC-Programmierung kollision in einem polygon finden


Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

kann mir jemand einen Lösungsvorschlag für folgende Problemstellung 
geben?
(am Besten in C)

Es ist ein Polygon mit verschiedenen Koordinaten definiert.
Z.B. 1.Punkt x10 y5
     2.Punkt x15 y0
     3.Punkt x30 y-4
     4.Punkt x12 y-10
     5.Punkt x5  y-2
diese Punkte werde zu eine Polygon verbunden.
jetzt möchte ich prüfen ob eine neue Koordinate innnerhalb oder 
auserhalb dieses Polygons liegt, wie kann man das prüfen?
Koordinate x12 y-5 = innerhalb
Koordinate x40 y-10 = auserhalb

ich hoffe das war verständlich.

Michael

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du denkst dir eine Verbindung von deinem Testpunkt zu einem Punkt der 
garantiert ausserhalb liegt, und zählst wie oft diese Verbindung die 
Polygon-Begrenzungen schneidet:

Ungerade=>innerhalb,
Gerade=>ausserhalb.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
... und um das weiter auszuführen:
Wenn der Testpunkt dieselbe y Koordinate hat wie dein Testpunkt,
aber in X im unendlichen liegt, dann werden die Tests besonders
einfach.
Im Grunde läuft das dann auf die Bestimmung des Schnittpunktes
2-er Geraden hinaus. Allerdings hast du dann die Möglichkeit
einige Trivialfälle sehr schnell ausscheiden zu können:

Sei P1-P2 eine Kante deines Polygons, und T der zu testende
Punkt, dann fallen folgende Fälle trivialerweise weg:

Sowohl P1.y als auch P2.y sind größer als T.y
Sowohl P1.y als auch P2.y sind kleiner als T.y
Sowohl P1.x als auch P2.x sind kleiner als T.x
Sind P1.y und P2.y gleich, so kann es keinen
Schnittpunkt geben -> P1-P2 ignorieren.

Für die restlichen Fälle bestimmst du den Schnittpunkt
zwischen P1-P2 und einer Geraden die bei T beginnt und
parallel zur X Achse läuft. Über das Prinzip der ähnlichen
Dreiecke ist dies besonders einfach. Nur dann wenn der
Schnittpunkt in Y Richtung zwischen P1.y und P2.y liegt,
dann wird der Schnittpunkt auch gezählt.

Eine Besonderheit gibt es noch, wenn der Testpunkt in der
Y Koordinate exakt auf der Höhe eines Polygonpunktes liegt.
In dem Fall ist eine einfache Lösung die, dass der Schnittpunkt
nur dann gezählt wird, wenn er Y-mässig mit dem kleineren der
beiden Polygonpunkte übereinstimmt.

Du solltest auch noch definieren, wie du mit Punkten umgehen
willst, die exakt an der Aussenkontur des Polygons liegen:
Gehören sie zum Polygon, gehören sie nicht zum Polygon, oder
ist es egal, wie sie gewertet werden.

Autor: Michael (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Besten Dank erstmal.

Ich habe folgenden Code implementiert:
char collision(int x, int y)
{
  char inside = TRUE;
  u08 npoints = 5;
  u08 xpoints[npoints];
  u08 ypoints[npoints];
  xpoints[0]=10;
  xpoints[1]=20;
  xpoints[2]=26;
  xpoints[3]=60;
  xpoints[4]=80;
  ypoints[0]=40;
  ypoints[1]=10;
  ypoints[2]=35;
  ypoints[3]=5;
  ypoints[4]=60;

 
  int x1 = xpoints[npoints-1];
  int y1 = ypoints[npoints-1];
  int x2 = xpoints[0];
  int y2 = ypoints[0];
 
  char startUeber = y1 >= y? TRUE : FALSE;
  for(int i = 1; i<npoints ; i++)
  {
    char endUeber = y2 >= y? TRUE : FALSE;
    if(startUeber != endUeber)
    {
      if((y2 - y)*(x2 - x1) <= (y2 - y1)*(x2 - x))
      {
        if(endUeber)
        {
          inside = !inside;
        }
      }
      else
      {
        if(!endUeber)
        {
          inside = !inside;
        }
      }
    }
    startUeber = endUeber;
    y1 = y2;
    x1 = x2;
    x2 = xpoints[i];
    y2 = ypoints[i];
  }
  return inside;
}

funktioniert fast.

siehe Anhang

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Welchen Fall soll der else Zweig behandeln?

Vorschlag: Lass die Trivialoptimierungen erst mal weg.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie oft wird deine Schleife durchlaufen?

Antwort: 4 mal

Du hast aber 5 Polygonkanten, die du untersuchen musst!

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nicht sonderlich gut getestet:
#include <stdio.h>

#ifndef TRUE
#define TRUE 1
#define FALSE 0
#endif

#define min(a,b)  (a)<(b)?(a):(b)

typedef unsigned char u08;

#define npoints  5
  u08 xpoints[5];
  u08 ypoints[5];

char collision(int x, int y)
{
  char inside = FALSE;
  int i;
  u08 sx;

  int x1 = xpoints[npoints-1];
  int y1 = ypoints[npoints-1];
  int x2 = xpoints[0];
  int y2 = ypoints[0];
 
  for( i = 0; i < npoints ; i++)
  {
    printf( "Checking  %d/%d -> %d/%d\n", x1, y1, x2, y2);

    if( ( y1 > y && y2 > y ) ||
        ( y1 < y && y2 < y ) ||
        ( y1 == y2 ) ||
        ( x1 < x && x2 < x ) ) {
        printf( "trivial reject\n");
    }

    else {
        sx = ( y - y1 ) * ( x2 - x1 ) / ( y2 - y1 ) + x1;
        printf( "Intersection  %d/%d\n", sx, y );
        if( sx >= x ) {
            if( y != y2 )
                inside = !inside;
        }
        printf( "new flag %d\n", inside);
    }

    y1 = y2;
    x1 = x2;
    x2 = xpoints[i+1];
    y2 = ypoints[i+1];
  }
  return inside;
}


int main()
{
  xpoints[0]=10;   ypoints[0]=40;
  xpoints[1]=20;   ypoints[1]=10;
  xpoints[2]=26;   ypoints[2]=35;
  xpoints[3]=60;   ypoints[3]=5;
  xpoints[4]=80;   ypoints[4]=60;

  if( collision( 79, 60))
      printf( "inside\n" );
  else
      printf( "not inside\n" );
}

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das sieht schon viel besser aus!
An den Spitzen wo sich zwei Linien treffen wird ein inside ausgegeben 
obwohl ausserhalb.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael wrote:
> Das sieht schon viel besser aus!
> An den Spitzen wo sich zwei Linien treffen wird ein inside ausgegeben
> obwohl ausserhalb.

Hast du mal ein paar Koordinaten?

Ob ein Polygoneckpunkt inside oder outside ist ist weitgehend
Definitionssache.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Muss leider weg.

Du kannst im Web auch weiter nach deinem Problem suchen.
Das Problem ist bekannt als 'Point in Polygon'

http://www.visibone.com/inpoly/

Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Zunächst muss mal definiert sein was innen und außen von nem Polygon 
ist. Dazu verwendet man im normalfall die "Richtung" Der äußeren Kanten. 
z.B. Linksrum = Polygon, Rechtsrum = "Loch"

Ich hab vor langen Zeiten auch mal ne Punkt in Polygon Funktion 
geschrieben. Die Behandlung von Sonderfällen wie z.b. Testlinie auf 
einer Ecke wird dadurch behoben dass einfach die Testlienie neu gewählt 
wird :)
// testet, ob ein Punkt innerhalb eines Polygons liegt
function punktInPolygon(testPunkt: PPunkt; polygon: PPolygon): boolean;
var
  testLinie,
  testGleichung: TGleichung;
  punkt: PPunkt;
  sp: TPunkt;
  count: Integer;
  i: Integer;
  weiterTesten: boolean;
  winkel: Double;
begin
  new(punkt);
  punkt^.X := testPunkt^.X;
  punkt^.Y := testPunkt^.Y;
  testLinie.p1 := testPunkt;

  new(punkt);
  punkt^.X := PPunkt(polygon^.punkte.First)^.X;
  punkt^.Y := PPunkt(polygon^.punkte.First)^.Y;
  testLinie.p2 := punkt;

  // Gleichung durch diese 2 Punkte machen
  testLinie := macheGleichung(testLinie.p1, testLinie.p2);

  repeat
    // noch kein Schnittpunkt gefunden
    count := 0;
    // von einem Durchgang ohne Sonderfälle ausgehen
    weiterTesten := FALSE;

    // alle Kanten testen
    for i := 0 to (polygon^.punkte.Count  - 1) do
    begin
      testGleichung := macheGleichung(polygon^.punkte.Items[i],
                                      polygon^.punkte.Items[(i + 1) mod olygon^.punkte.Count]);
      if schnittpunktMoeglich(@testLinie, @testGleichung) then
      begin
        sp := schnittpunkt(@testLinie, @testGleichung);
        // gültiger Schnittpunkt in einer Kante (SP ist _keine_ Ecke)
        if (punktInnerhalb(@sp, testGleichung.p1, testGleichung.p2) and
            punktInRichtung(@sp, testLinie.p1, testLinie.p2)) then
        begin
          count := count + 1;
        end
        else if (punktGleich(@sp, testGleichung.p1) or
                 punktGleich(@sp, testGleichung.p2)) then
          weiterTesten := TRUE;                 
      end;
    end;
    // wenn es Sonderfälle gab wie Schnittpunkte in Ecken
    // dann die Test-Linie anpassen (das Ergebnis wird dadurch _nicht_ falsch!)
    if (weiterTesten) then
    begin
      winkel := punkteWinkel(testLinie.p1, testLinie.p2);
      winkel := winkel + ((2*PI) / 3600);  // um 0.1° drehen
      testLinie.p2^.X := testLinie.p1^.X + cos(winkel);
      testLinie.p2^.Y := testLinie.p1^.Y + sin(winkel);

      testLinie := macheGleichung(testLinie.p1, testLinie.p2);
    end;
  until
    (weiterTesten = FALSE);

  result := ((count mod 2) = 1); // Punt in Polygon bei ungerader Anz. SP
end;

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke Karl heinz, danke Stefan,

diese Funktion erfüllt jetzt den Zweck:
char collision(u08 x, u08 y, u08 poly[5][2], u08 npoints)
{
     u08 xnew,ynew;
     u08 xold,yold;
     u08 x1,y1;
     u08 x2,y2;
     u08 i;
     char inside=0;

     if (npoints < 3)
     {
        return(0);
     }
     xold=poly[npoints-1][0];
     yold=poly[npoints-1][1];
     for (i=0 ; i < npoints ; i++)
     {
          xnew=poly[i][0];
          ynew=poly[i][1];
          if (xnew > xold)
          {
               x1=xold;
               x2=xnew;
               y1=yold;
               y2=ynew;
          }
          else
          {
               x1=xnew;
               x2=xold;
               y1=ynew;
               y2=yold;
          }
          if ((xnew < x) == (x <= xold)          /* edge "open" at one end */
           && ((long) y-(long)y1)*(long)(x2-x1)
            < ((long)y2-(long)y1)*(long)(x-x1))
          {
               inside=!inside;
          }
          xold=xnew;
          yold=ynew;
     }
     return(inside);
}

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

die Funktion läuft. Jetzt suche ich noch eine Möglichkeit den Abstand 
von einem sich außerhalb befindlichen Punkt zu einem Polygon zu 
errechnen.

Hat da jemand Hilfe oder Info darüber?

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.