kollision in einem polygon finden

[Michael (Gast)]

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

[Εrnst B. (ernst)]

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.

[Karl H. (kbuchegg)]

... 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.

[Michael (Gast)]

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

[Karl H. (kbuchegg)]

Welchen Fall soll der else Zweig behandeln?

Vorschlag: Lass die Trivialoptimierungen erst mal weg.

[Karl H. (kbuchegg)]

Wie oft wird deine Schleife durchlaufen?

Antwort: 4 mal

Du hast aber 5 Polygonkanten, die du untersuchen musst!

[Karl H. (kbuchegg)]

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" );
}

[Michael (Gast)]

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

[Karl H. (kbuchegg)]

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.

[Karl H. (kbuchegg)]

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/

[Stefan (Gast)]

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;

[Michael (Gast)]

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);
}

[Michael (Gast)]

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?