Kleinstmögliche "Bounding Box" für beliebige drehende Dreiecke

Question

folgendes: Ich möchte per Programmierung überprüfen, ob sich beliebige Dreiecke überschneiden (die sich auch drehen können). Da die Wurzel zu ziehen ziemlich rechenaufwändig ist, möchte ich eine Vorüberprüfung mit Vierecken machen. Wenn diese sich nicht schneiden, können sich die Dreiecke auch in keinem Fall schneiden.

In dieser Grafik habe ich um jedes Dreieck eine quadratische "Bounding Box" gelegt, wobei deren Seitenlänge gleich der längsten Seite der Dreiecke ist. Der Schwerpunkt liegt in der Mitte der längsten Seite der Dreiecke und der Mitte der Quadrate. Um diesen können sich die Dreiecke drehen.

Natürlich könnte man auch Rechtecke um die (gedrehten) Dreiecke legen, das wäre etwas präziser, allerdings würde man da nicht ohne Wurzeln auskommen, oder?

Die Frage ist, ob es mit diesen Anforderungen noch präziser geht, ohne mehr Rechenaufwand für den Computer?

 

Danke,

 

Thilo

Comments

Je nach Programmiersprache kann dir hier viel Arbeit abgenommen werden, insbesondere wenn es um Performance geht.

Actionscript 2 + 3 bieten eine entsprechende Methode hierzu: getBounds()

---

Die Frage ist auch, worum sich die Dreiecke drehen?

Um den Schwerpunkt?

Answer 1

Leider gibst du nicht vor, was du jeweils von den Dreiecken gegeben hast.

Ich habe früher mal in Pascal eine Grafikbibliothek geschrieben die Körper aus Dreiecken zeichnen konnte. Dabei musste ich auch überprüfen ob sich zwei Dreiecke überlappen. Ich habe für ein Dreieck jeweils die Eckpunkte in Bildschirmkoordinaten gehabt.

P1(x1|y1); P2(x2|y2); P3(x3|y3)

Wenn ich jetzt ein Rechteck drum herum lege gilt:

xmin = min(x1, x2, x3)
xmax = max(x1, x2, x3)

 

ymin = min(y1, y2, y3)
ymax = max(y1, y2, y3)

Das Rechteck also aus

A(xmin, ymin); B(xmax, ymin); C(xmax, ymax); D(xmin, ymax)

Zwei Rechtecke überlappen sich wenn sich die x und die y-Bereiche überlappen. Das ist alles recht einfach im Bereich der Integerarithmetik zu lösen.