kollision in einem polygon finden

Gast #693363
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
... 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.
Gast
Besten Dank erstmal.

Ich habe folgenden Code implementiert:
1
char collision(int x, int y)
2
{
3
  char inside = TRUE;
4
  u08 npoints = 5;
5
  u08 xpoints[npoints];
6
  u08 ypoints[npoints];
7
  xpoints[0]=10;
8
  xpoints[1]=20;
9
  xpoints[2]=26;
10
  xpoints[3]=60;
11
  xpoints[4]=80;
12
  ypoints[0]=40;
13
  ypoints[1]=10;
14
  ypoints[2]=35;
15
  ypoints[3]=5;
16
  ypoints[4]=60;
17

18
 
19
  int x1 = xpoints[npoints-1];
20
  int y1 = ypoints[npoints-1];
21
  int x2 = xpoints[0];
22
  int y2 = ypoints[0];
23
 
24
  char startUeber = y1 >= y? TRUE : FALSE;
25
  for(int i = 1; i<npoints ; i++)
26
  {
27
    char endUeber = y2 >= y? TRUE : FALSE;
28
    if(startUeber != endUeber)
29
    {
30
      if((y2 - y)*(x2 - x1) <= (y2 - y1)*(x2 - x))
31
      {
32
        if(endUeber)
33
        {
34
          inside = !inside;
35
        }
36
      }
37
      else
38
      {
39
        if(!endUeber)
40
        {
41
          inside = !inside;
42
        }
43
      }
44
    }
45
    startUeber = endUeber;
46
    y1 = y2;
47
    x1 = x2;
48
    x2 = xpoints[i];
49
    y2 = ypoints[i];
50
  }
51
  return inside;
52
}

funktioniert fast.

siehe Anhang
Angehängte Dateien:
Nicht sonderlich gut getestet:
1
#include <stdio.h>
2

3
#ifndef TRUE
4
#define TRUE 1
5
#define FALSE 0
6
#endif
7

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

10
typedef unsigned char u08;
11

12
#define npoints  5
13
  u08 xpoints[5];
14
  u08 ypoints[5];
15

16
char collision(int x, int y)
17
{
18
  char inside = FALSE;
19
  int i;
20
  u08 sx;
21

22
  int x1 = xpoints[npoints-1];
23
  int y1 = ypoints[npoints-1];
24
  int x2 = xpoints[0];
25
  int y2 = ypoints[0];
26
 
27
  for( i = 0; i < npoints ; i++)
28
  {
29
    printf( "Checking  %d/%d -> %d/%d\n", x1, y1, x2, y2);
30

31
    if( ( y1 > y && y2 > y ) ||
32
        ( y1 < y && y2 < y ) ||
33
        ( y1 == y2 ) ||
34
        ( x1 < x && x2 < x ) ) {
35
        printf( "trivial reject\n");
36
    }
37

38
    else {
39
        sx = ( y - y1 ) * ( x2 - x1 ) / ( y2 - y1 ) + x1;
40
        printf( "Intersection  %d/%d\n", sx, y );
41
        if( sx >= x ) {
42
            if( y != y2 )
43
                inside = !inside;
44
        }
45
        printf( "new flag %d\n", inside);
46
    }
47

48
    y1 = y2;
49
    x1 = x2;
50
    x2 = xpoints[i+1];
51
    y2 = ypoints[i+1];
52
  }
53
  return inside;
54
}
55

56

57
int main()
58
{
59
  xpoints[0]=10;   ypoints[0]=40;
60
  xpoints[1]=20;   ypoints[1]=10;
61
  xpoints[2]=26;   ypoints[2]=35;
62
  xpoints[3]=60;   ypoints[3]=5;
63
  xpoints[4]=80;   ypoints[4]=60;
64

65
  if( collision( 79, 60))
66
      printf( "inside\n" );
67
  else
68
      printf( "not inside\n" );
69
}
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.
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 :)
1
// testet, ob ein Punkt innerhalb eines Polygons liegt
2
function punktInPolygon(testPunkt: PPunkt; polygon: PPolygon): boolean;
3
var
4
  testLinie,
5
  testGleichung: TGleichung;
6
  punkt: PPunkt;
7
  sp: TPunkt;
8
  count: Integer;
9
  i: Integer;
10
  weiterTesten: boolean;
11
  winkel: Double;
12
begin
13
  new(punkt);
14
  punkt^.X := testPunkt^.X;
15
  punkt^.Y := testPunkt^.Y;
16
  testLinie.p1 := testPunkt;
17

18
  new(punkt);
19
  punkt^.X := PPunkt(polygon^.punkte.First)^.X;
20
  punkt^.Y := PPunkt(polygon^.punkte.First)^.Y;
21
  testLinie.p2 := punkt;
22

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

26
  repeat
27
    // noch kein Schnittpunkt gefunden
28
    count := 0;
29
    // von einem Durchgang ohne Sonderfälle ausgehen
30
    weiterTesten := FALSE;
31

32
    // alle Kanten testen
33
    for i := 0 to (polygon^.punkte.Count  - 1) do
34
    begin
35
      testGleichung := macheGleichung(polygon^.punkte.Items[i],
36
                                      polygon^.punkte.Items[(i + 1) mod olygon^.punkte.Count]);
37
      if schnittpunktMoeglich(@testLinie, @testGleichung) then
38
      begin
39
        sp := schnittpunkt(@testLinie, @testGleichung);
40
        // gültiger Schnittpunkt in einer Kante (SP ist _keine_ Ecke)
41
        if (punktInnerhalb(@sp, testGleichung.p1, testGleichung.p2) and
42
            punktInRichtung(@sp, testLinie.p1, testLinie.p2)) then
43
        begin
44
          count := count + 1;
45
        end
46
        else if (punktGleich(@sp, testGleichung.p1) or
47
                 punktGleich(@sp, testGleichung.p2)) then
48
          weiterTesten := TRUE;                 
49
      end;
50
    end;
51
    // wenn es Sonderfälle gab wie Schnittpunkte in Ecken
52
    // dann die Test-Linie anpassen (das Ergebnis wird dadurch _nicht_ falsch!)
53
    if (weiterTesten) then
54
    begin
55
      winkel := punkteWinkel(testLinie.p1, testLinie.p2);
56
      winkel := winkel + ((2*PI) / 3600);  // um 0.1° drehen
57
      testLinie.p2^.X := testLinie.p1^.X + cos(winkel);
58
      testLinie.p2^.Y := testLinie.p1^.Y + sin(winkel);
59

60
      testLinie := macheGleichung(testLinie.p1, testLinie.p2);
61
    end;
62
  until
63
    (weiterTesten = FALSE);
64

65
  result := ((count mod 2) = 1); // Punt in Polygon bei ungerader Anz. SP
66
end;
Gast
Danke Karl heinz, danke Stefan,

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

10
     if (npoints < 3)
11
     {
12
        return(0);
13
     }
14
     xold=poly[npoints-1][0];
15
     yold=poly[npoints-1][1];
16
     for (i=0 ; i < npoints ; i++)
17
     {
18
          xnew=poly[i][0];
19
          ynew=poly[i][1];
20
          if (xnew > xold)
21
          {
22
               x1=xold;
23
               x2=xnew;
24
               y1=yold;
25
               y2=ynew;
26
          }
27
          else
28
          {
29
               x1=xnew;
30
               x2=xold;
31
               y1=ynew;
32
               y2=yold;
33
          }
34
          if ((xnew < x) == (x <= xold)          /* edge "open" at one end */
35
           && ((long) y-(long)y1)*(long)(x2-x1)
36
            < ((long)y2-(long)y1)*(long)(x-x1))
37
          {
38
               inside=!inside;
39
          }
40
          xold=xnew;
41
          yold=ynew;
42
     }
43
     return(inside);
44
}
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?

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 19 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.