#1 22.04.2010 20:37:26

artzuk
GodlikeMember
Ort: Leipzig
Registriert: 24.01.2005
Beiträge: 1164

2D Intersection

Hallo auch,

ich habe ein Polygon mit ca. 4000 Eckpunken. Nun muss ich herausfinden, ob ein Punkt in diesen geschlossenen Polygon liegt, oder außerhalb. Das ganze, wie der Titel schon sagt, in 2D.

Prüfen tu ich das ganze, in dem ich zwischen 2 anliegenden Punkten eine Gerade bilde und schau, ob bei allen Geraden (= Kanten des Polygons) der Abstand zum Punkt negativ ist. Bei einer Abweichung, liegt der Punkt außerhalb. Sollte stimmen, oder? Oder gibt es andere Herangehensweisen?

Nun die Hauptfrage: Wie optimier ich das ganze? Habe gerade kein Ansatz, wie ich zuverlässig vielleicht eine Art LOD implementieren kann. Habt ihr einen Denkanstoß für mich?


Mein kleiner .NET Blog: http://artzuk-interactive.de/

Offline

 

#2 22.04.2010 20:53:37

Gnietschow
ProMember
Ort: Berlin
Registriert: 20.06.2007
Beiträge: 237

Re: 2D Intersection

DfoG und ich hatten im Softwarepraktikum an der Uni das Thema Pseudotriangulierung in 2D. Es ging darum Bälle (Punkte) in ein Polygon zu legen und umherfliegen zu lassen mit abprallen an den Kanten und das ganze Effizient ohne Brute-Force. Da brauchten wir auch eine Funktion die testet ob wir in einem Polygon sind. Allerdings darf das Polygon keine Löcher oder Kantenüberschneidungen haben. Der Ansatz den wir genutzt hatten, war das man vom Punkt eine Gerade nach rechts zieht und zählt, wie oft Außenkanten von unten nach oben oder von oben nach unten geschnitten wurden. Wenn für den einen Fall rechnet man eine Variable +1 und für den anderen Fall -1. Wenn schlussendlich etwas ungleich 0 rauskommt ist man im Polygon. Wir hatten aber nur Polygone mit maximal 500 Kanten, ging aber effizient.

Mal unser Codeschnipsel dafür:

Code: delphi

//Knoten ist ein array of TD3DXVector2
function tpolygonimplementierung.punktimpolygon(
  punkt: td3dxvector2): boolean;
var wn,i:integer;
    p1,p2:td3dxvector2;
    startueber,endeueber:boolean;
begin
  result:=false;
  if not geschlossen then exit;

  wn:=0;
  p1:= knoten[internanzahlknoten-1];
  p2:= knoten[0];

  startueber:= p1.y >= punkt.y;
  for i:=1 to internanzahlknoten do
  begin
    endeueber:= p2.y >= punkt.y;
    if (startueber <> endeueber) then
    begin
      if ((p2.y - punkt.y)*(p2.x - p1.x) <= (p2.y - p1.y)*(p2.x - punkt.x)) then
      begin
        if(endeueber) then inc(wn);
      end
      else if(not endeueber) then dec(wn);
    end;
    if i=internanzahlknoten then break;
    startueber:= endeueber;
    p1:= p2;
    p2:= knoten[i];
  end;
  result:=wn<>0;
end;


Vielleicht hilft dir das etwas smile Mit der Pseudotriangulierung mit geodätischen Dreicken, konnte man recht gut auch immer rausfinden wo die Bälle gegenflogen. Vielleicht kann man darüber auch einen LOD erreichen, bin mir da aber nicht sicher (wenn du mehr Infos zu dem Thema brauchst, kann ich dir unsere Ausarbeitung zukommen lassen).

MfGnietschow


Es gibt 10 Gruppen von Menschen - die die das Binärsystem verstehen und die anderen.  :-)
Vegetarier essen meinem Essen das Essen weg ;)
-------------------------------------------------------------------------------------------------------------------
Der Community-Hub für Videospiele: gameloop.io

Offline

 

#3 23.04.2010 09:59:46

artzuk
GodlikeMember
Ort: Leipzig
Registriert: 24.01.2005
Beiträge: 1164

Re: 2D Intersection

Ah stimmt, über den Ansatz hatte ich auch schon mal nachgedacht, hatte ihn aber abgewählt, da ich dachte, er sei für komplexe Polygone nicht geeignet. Aber an das Zählen von Intersections habe ich gar nicht gedacht. Super, den Ansatz werde ich verfolgen.
Und eine Vorselektierung brauch ich nicht unbedingt, da in 2D diese Abfrage ziemlich einfach ist und wenig Rechenaufwand benötigt smile

Vielen Dank!


Mein kleiner .NET Blog: http://artzuk-interactive.de/

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson