AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Flächenüberschneidung suchen

Ein Thema von blablab · begonnen am 28. Jan 2011 · letzter Beitrag vom 28. Jan 2011
Antwort Antwort
blablab

Registriert seit: 3. Jan 2006
509 Beiträge
 
Delphi 7 Enterprise
 
#1

AW: Flächenüberschneidung suchen

  Alt 28. Jan 2011, 08:19
Vielleicht hab ich das etwas blöd formuliert. Ich will nicht alle Flächen mit allen vergleichen.
Ich habe eine Menge von Rects, das nenn ich jetzt mal die Flächenliste. Ich bin mir nicht sicher ob das einen Unterschied macht, aber diese Flächenliste hat als besondere Eigenschaft, dass sich die einzelnen Flächen darin nicht überschneiden.

Und jetzt hab ich 2 Probleme:
1) Ich bekomme als Eingabe einen Punkt P.
Hier würde ich gerne ausrechnen ob dieser Punkt P eine Fläche der Flächenliste schneidet und wenn ja welche.

2) Ich bekomme als Eingabe eine Fläche F.
Hier möchte ich herausfinden welche und wie viele Flächen der Flächenliste die Fläche F schneiden.
Fläche Fläche Fläche
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.666 Beiträge
 
Delphi 12 Athens
 
#2

AW: Flächenüberschneidung suchen

  Alt 28. Jan 2011, 08:23
Achso, Du suchst ein geeignetes Ausschlussverfahren. Da muss ich mal drüber nachdenken.

[edit] Wenn man nach mit CustomSort nach den Kriterien Left, Width, Top und Height sortiert, müsste sich doch eine binäre Suche realisieren lassen, oder täusche ich mich? [/edit]
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen

Geändert von DeddyH (28. Jan 2011 um 08:30 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Bummi
Bummi

Registriert seit: 15. Jun 2010
Ort: Augsburg Bayern Süddeutschland
3.470 Beiträge
 
Delphi XE3 Enterprise
 
#3

AW: Flächenüberschneidung suchen

  Alt 28. Jan 2011, 08:42
Iterierien mit PtInRect bzw. InsersectRect ?
Thomas Wassermann H₂♂
Das Problem steckt meistens zwischen den Ohren
DRY DRY KISS
H₂ (wenn bei meinen Snipplets nichts anderes angegeben ist Lizenz: WTFPL)
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.666 Beiträge
 
Delphi 12 Athens
 
#4

AW: Flächenüberschneidung suchen

  Alt 28. Jan 2011, 08:44
Bummi, darum geht es ja nicht, das hatte ich auch erst falsch verstanden. Er sucht ein geeignetes Ausschlussverfahren, damit er nicht jedes Rect einzeln prüfen muss.
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
blablab

Registriert seit: 3. Jan 2006
509 Beiträge
 
Delphi 7 Enterprise
 
#5

AW: Flächenüberschneidung suchen

  Alt 28. Jan 2011, 09:22
Kann es sein dass das mit dem sortieren sogar noch aufwändiger ist?
Ich muss ja dann in jeder Liste die binäre Suche anwenden (das ist noch nicht aufwändig). Als Ergebnis hab ich dann jeweils eine Position wo dann zum Beispiel oberhalb alle Rects in Frage kommen und unterhalb nicht. Um diese 4 Listen zusammenzufügen würde ich dann einen Boolean-Array mit der Länge n machen und dann alle Listen durchgehen und die Rects die nicht in Frage kommen im Boolean-Array markieren. Und dann müsste ich nochmal den Boolean-Array durchegehen und mir die die übriggebliebenen Rects rausschreiben.

Das wäre dann:
4*Binäre Suche = 4* log(n)
Boolean-Array initialisieren = n
Falsche Rects rausstreichen ~ 4* 1/2n
Übriggebliebenen Rects rausschreiben = n

Insgesamt sind das dann ganz grob >4n Operationen.
Das ist ja eigentlich nicht viel, aber wenn ich die n Rects einfach alle durchgehe, dann muss ich ja auch nur jeweils 4 Vergleiche pro Rect machen. Und wenn einer der 4 Vergleiche false ergibt, dann müssen die restlichen nicht verglichen werden. Das bedeutet es sind sogar eher weniger als 4n Operationen...
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.666 Beiträge
 
Delphi 12 Athens
 
#6

AW: Flächenüberschneidung suchen

  Alt 28. Jan 2011, 09:37
Wie kommst Du auf 4 Listen? Ich meinte eine einzige, aber nach 4 Kriterien sortiert. Solange sich die Rects nicht ändern, muss diese Sortierung ja nur einmalig vorgenommen werden.
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
Benutzerbild von Bummi
Bummi

Registriert seit: 15. Jun 2010
Ort: Augsburg Bayern Süddeutschland
3.470 Beiträge
 
Delphi XE3 Enterprise
 
#7

AW: Flächenüberschneidung suchen

  Alt 28. Jan 2011, 09:43
mein Bauch meint iterieren wird die schnellst Methode bleiben....
Thomas Wassermann H₂♂
Das Problem steckt meistens zwischen den Ohren
DRY DRY KISS
H₂ (wenn bei meinen Snipplets nichts anderes angegeben ist Lizenz: WTFPL)
  Mit Zitat antworten Zitat
blablab

Registriert seit: 3. Jan 2006
509 Beiträge
 
Delphi 7 Enterprise
 
#8

AW: Flächenüberschneidung suchen

  Alt 28. Jan 2011, 09:47
Das verstehe ich jetzt nicht...
Meinst du dass z.B. zuerst nach Left sortiert wird und wenn Left bei beiden gleich ist wird nach Right sortiert usw. ? Weil dann weiß ich nicht wie ich diese Liste beim Ausschlussverfahren benutzen kann.
Ich kann dann zwar die Sortierung nach Left benutzen um alle Rects auszuschließen, die sich rechts vom Punkt befinden, aber bei den restlichen Rects wird es dann schwer und bringt nicht mehr viel....

@Bummi
Das glaube ich langsam auch...
Wahrscheinlich läuft es darauf hinaus, dass der Code maximal 10% schneller und dafür 10x so kompliziert ist

Geändert von blablab (28. Jan 2011 um 09:51 Uhr)
  Mit Zitat antworten Zitat
Antwort Antwort


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 12:25 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz