AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Multimedia Delphi Algorithmus gesucht: Schnitt Polygon <-> Gerade

Algorithmus gesucht: Schnitt Polygon <-> Gerade

Ein Thema von Codewalker · begonnen am 7. Sep 2008 · letzter Beitrag vom 7. Sep 2008
Antwort Antwort
Seite 1 von 2  1 2   
Benutzerbild von Codewalker
Codewalker

Registriert seit: 18. Nov 2005
Ort: Ratingen
945 Beiträge
 
Delphi XE2 Professional
 
#1

Algorithmus gesucht: Schnitt Polygon <-> Gerade

  Alt 7. Sep 2008, 16:30
Hallo zusammen.

Ich habe eine Problemstellung und weiß nicht, wie ich es genau angehen soll: Ich habe 2 gegebene Punkte sowie eine Menge von Polygonen. Ich möchte nun für ein Polygon testen, ob die Strecke (nicht die Gerade) zwischen diesen beiden Punkten, das Hexagon schneidet.
Wie würdet ihr sowas überprüfen? Ich habe eine Hilfsfunktion, die prüft ob ein Punkt im Polygon liegt - aber das hilft mir nicht wirklich weiter. Ich kann ja nicht alle möglichen Punkte durchprobieren.

Danke und Grüße
Thomas
  Mit Zitat antworten Zitat
kalmi01
(Gast)

n/a Beiträge
 
#2

Re: Algorithmus gesucht: Schnitt Polygon <-> Gerade

  Alt 7. Sep 2008, 16:38
Hallo Codewalker,

eigentlich doch reecht einfach, schneidet Deine Strecke AB eine der Polygonlinien, dann schneidet AB auch Dein Polygon.
Algo's dafür findest Du zB. hier.
  Mit Zitat antworten Zitat
Benutzerbild von idontwantaname
idontwantaname

Registriert seit: 31. Aug 2004
Ort: Traiskirchen
575 Beiträge
 
Turbo Delphi für Win32
 
#3

Re: Algorithmus gesucht: Schnitt Polygon <-> Gerade

  Alt 7. Sep 2008, 16:38
Also ich würde das so lösen: mache aus dem Polygon eine Ebene und schneide die Gerade bzw. erweiterte Strecke mit dieser. Nun prüfst du, ob der Schnittpunkt im Polygon liegt - wenn ja, dann prüfst du noch, ob der Schnittpunkt auch auf der Strecke liegt
Oliver Hanappi
Besucht meine neue Homepage: http://oli.hux.de
  Mit Zitat antworten Zitat
Benutzerbild von Nikolas
Nikolas

Registriert seit: 28. Jul 2003
1.528 Beiträge
 
Delphi 2005 Personal
 
#4

Re: Algorithmus gesucht: Schnitt Polygon <-> Gerade

  Alt 7. Sep 2008, 17:01
Wenn du nur mit Hexagonen arbeitest, solltest du vorher noch eine kleine Abfrage mit einer BoundingBox (circle) vorschalten. Die Eckpunkt deines Polygons liegen auf einem Kreis, so dass eine Gerade sicher diesen Kreis schneiden muss, wenn sie das Polygon schneidet. Die Abfrage, ob der Kreis geschnitten wird, ist eine einfache quadratische Gleichung, damit kannst du dir die ausfwändige Lösung mit dem Schnitt mit allen Polygonstrecken sparen.
Erwarte das Beste und bereite dich auf das Schlimmste vor.
  Mit Zitat antworten Zitat
Benutzerbild von Codewalker
Codewalker

Registriert seit: 18. Nov 2005
Ort: Ratingen
945 Beiträge
 
Delphi XE2 Professional
 
#5

Re: Algorithmus gesucht: Schnitt Polygon <-> Gerade

  Alt 7. Sep 2008, 17:20
Danke für die Tipps. Ich denke mit dem Test auf BoundingBox, ein paar generelle Ausschlüsse durch X/Y-Koordinaten (was zu weit weg liegt, muss ich nicht prüfen) lässt sich die Zahl der Hexagons so weit reduzieren, dass der Test mit den 6 Seiten performancemäßig nicht groß auffallen sollte.
Das ganze soll ein Line-of-Sight - Algorithmus werden - bin mir noch nicht sicher, ob ich das sauber hinbekomme, weil ich ja noch bedenken muss, welche Felder im Verlauf der Strecke durch andere bereits geblockt werden.
Thomas
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.679 Beiträge
 
Delphi 2007 Enterprise
 
#6

Re: Algorithmus gesucht: Schnitt Polygon <-> Gerade

  Alt 7. Sep 2008, 18:07
Reden wir eigentlich über 2D oder 3D? Bei 2D reicht es die Schnitte mit den Kanten zu prüfen, in 3D kannst du immer noch die Fläche treffen, ohne eine Kante zu schneiden.
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
  Mit Zitat antworten Zitat
Benutzerbild von Codewalker
Codewalker

Registriert seit: 18. Nov 2005
Ort: Ratingen
945 Beiträge
 
Delphi XE2 Professional
 
#7

Re: Algorithmus gesucht: Schnitt Polygon <-> Gerade

  Alt 7. Sep 2008, 18:36
Nein, ist alles nur 2D
Thomas
  Mit Zitat antworten Zitat
Benutzerbild von Nikolas
Nikolas

Registriert seit: 28. Jul 2003
1.528 Beiträge
 
Delphi 2005 Personal
 
#8

Re: Algorithmus gesucht: Schnitt Polygon <-> Gerade

  Alt 7. Sep 2008, 20:15
Wie viele Sechsecke hast du denn und wie oft musst du diese Suche durchführen.
Mach dir am Besten erst mal keine Gedanken über die Geschwindigkeit, sondern schreib erst eine kleine Testversion.
Vielleicht ist die Rechenzeit überhaupt kein Problem und du hast duir zu viele Gedanken gemacht.
Worüber du dir auf jeden Fall Gedanken machen solltest, ist die Repräsentation von Geraden. f(x)=mx+c zum Beispiel gibt größere Probleme bei steilen Geraden, der Ansatz (x,f(x))=(v,w)+r*(a,b) ist da vielleicht passender, da kannst du auch schnell sehen, ob ein Schnittpunkt innerhalb deiner Strecke liegt.
Erwarte das Beste und bereite dich auf das Schlimmste vor.
  Mit Zitat antworten Zitat
Benutzerbild von Codewalker
Codewalker

Registriert seit: 18. Nov 2005
Ort: Ratingen
945 Beiträge
 
Delphi XE2 Professional
 
#9

Re: Algorithmus gesucht: Schnitt Polygon <-> Gerade

  Alt 7. Sep 2008, 20:19
Nun, es sind derzeit 30x30 = 900 Sechsecke. Aufruf bei jeder Bewegung einer Figur (Sichtlinienberechnung), also sagen wir mal im Schnitt alle paar Sekunden einmal zum aktualisieren des Fog of War.
Ich muss da erstmal drüber schlafen - hilft meistens
Thomas
  Mit Zitat antworten Zitat
Benutzerbild von Nikolas
Nikolas

Registriert seit: 28. Jul 2003
1.528 Beiträge
 
Delphi 2005 Personal
 
#10

Re: Algorithmus gesucht: Schnitt Polygon <-> Gerade

  Alt 7. Sep 2008, 20:29
Fog of War? Das heisst doch Nebel des Krieges, oder? Also nicht: exakte Grenze des Krieges.
Bei dieser Aufgabe könntest du einfach nur den BoundingCircle benutzen und gut ist.

Vorschlag: Nimm dir den Mittelpunkt einer der Strecken, die das Sechseck umschließen und rechne den Abstand zur Mitte aus. Wenn der Abstand deiner Gerade zum Mittelpunkt kleiner ist, wird das Sechseck getroffen, ansonsten nicht.

In den meisten Fällen solltest du damit sehr gute Ergebnisse erzielen und einen minimalen Programmieraufwand haben.
Erwarte das Beste und bereite dich auf das Schlimmste vor.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 14:10 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz