Theorie hinter Shape intersects Test..?

[sirbender]

Hi,

ich kann einen Shape auf Intersection mit einem Rechteck pruefen.

Der Shape ist ein GeneralPath dessen intersects methode aufgerufen wird (in Path2D). Diese wiederum rectCrossings(...) in Path2D.Float aufruft.

Mich intressiert die Theorie die hinter dem Intersectionstest dahintersteckt.

Koennte man den Test beschleunigen

1. durch einen anderen Test?
2. indem man den Shape in ein Polygon wandelt?
3. indem man die Methoden umschreibt sodass int anstatt double benutzt wird?

Ich will diese Intersection extrem oft nutzen und bei einem sehr lang laufenden Programm macht jede Einsparung was aus wenn die Intersection 90% der Zeit in Anspruch nimmt.

 

[FArt]

... wenn die Intersection 90% der Zeit in Anspruch nimmt.

Zwischenfrage, keine Antwort: ist das so? Und wenn ja, was spricht der Profiler, wo bei der Berechnung die meiste Zeit verbraten wird? Und worauf basiert die Idee doubles durch ints zu ersetzten? Ist das ein Versuch ins Blaue, weil die Verarbeitung von doubles ja per se langsam ist?

Mein Tipp: Problem analysieren, und zwar wenn es auftritt. Und dann genau der Problematik angemessen entgegenwirken.
Diese Optimierungsdiskussionen "soll ich einfach mal schnell was komplizierter machen, was eigentlich geht aber vielleicht unheimlich viel Performance kostet" hatten wir schon oft...

[EDIT]
Schau mal in den Sourcecode, ob du der Theorie dahinter näher kommen könntest. Ansonsten bietet Google eine Menge Ideen zu dem Thema an...

 

[slawaweis]

Mich intressiert die Theorie die hinter dem Intersectionstest dahintersteckt.

die meisten geometrischen Operationen werden in Java nativ ausgeführt, wegen der Performance.

1. durch einen anderen Test?

man könnte zuerst den Bounds des Shapes nehmen und damit testen, ob sich 2 Rechtecke überschneiden und/oder ob eines in dem anderen liegt. Wenn sich die beiden Rechtecke nicht überschneiden, kann man sich auch den Shape-Test sparen.

2. indem man den Shape in ein Polygon wandelt?
3. indem man die Methoden umschreibt sodass int anstatt double benutzt wird?

das wäre alles zu ungenau.

Ich will diese Intersection extrem oft nutzen und bei einem sehr lang laufenden Programm macht jede Einsparung was aus wenn die Intersection 90% der Zeit in Anspruch nimmt.

ich habe schon oft mit Intersections in Java gearbeitet und die waren nie das Problem. Kannst Du vielleicht dein Problem/Aufgabe konkreter beschreiben?

Slawa

 

[SlaterB]

ja, wenn dann eher im allgemeinen Programm auf höherer Ebene optimieren,
z.B. zum genannen Rechteck noch den Mittelpunkt/ Ausbreitung speichern (Kreis statt Rechteck)
oder den Datenraum in ein Gitter aufteilen und Shapes nur in den zugehörigen Teilen speichern,

dann kann recht schnell ein Vergleich abgebrochen werden ohne intersect überhaupt zu bemühen,
oder besser wird vorher überhaupt die Anzahl benötigter Vergleiche stark vermindert

 

[Marco13]

ja, wenn dann eher im allgemeinen Programm auf höherer Ebene optimieren,
z.B. zum genannen Rechteck noch den Mittelpunkt/ Ausbreitung speichern (Kreis statt Rechteck)
oder den Datenraum in ein Gitter aufteilen und Shapes nur in den zugehörigen Teilen speichern,

dann kann recht schnell ein Vergleich abgebrochen werden ohne intersect überhaupt zu bemühen,
oder besser wird vorher überhaupt die Anzahl benötigter Vergleiche stark vermindert

Ich könnte mir vorstellen (müßte man nachsehen) dass derartige Optimierungen (im Sinne von Bounding-Box-Tests) schon intern gemacht werden. Wenn nicht, könnten sie sich aber ggf. wirklich lohnen.

 

[SlaterB]

zumindest

List<Shapes>l  = 1000 Elemente
for (Shape s1 : l) {
  for (Shape s2 : l) {
        s1 intersect s2
  }
}

könnte man von 1 Mio. auf weniger Vergleiche runterbrechen, wenn nur pro Region verglichen wird,
da hilft das beste intersect nichts




und falls bei Shapes nicht das Rectangle/ Mittelpunkt gecacht wird, könnte man auch in dem Punkt durch zusätzlichen Speicher Rechenzeit bei jedem neuen Vergleich sparen,
aber stimmt schon, dieser Punkt geht langsam wirklich in Richtung des betonten 'Java intersect machen lassen'