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
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.
... 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.
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
Welchen Fall soll der else Zweig behandeln? Vorschlag: Lass die Trivialoptimierungen erst mal weg.
Wie oft wird deine Schleife durchlaufen? Antwort: 4 mal Du hast aber 5 Polygonkanten, die du untersuchen musst!
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 | }
|
Das sieht schon viel besser aus! An den Spitzen wo sich zwei Linien treffen wird ein inside ausgegeben obwohl ausserhalb.
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.
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/
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; |
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 | }
|
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?
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.