Überlappende Objekte suchen

[André]

Hallo zusammen,

ich habe zwei mathematische/programmiertechnische Probleme, bei denen ich Hilfe brauche.
Es geht um die Auswahl von Objekten (Strecken oder Rechtecken), die innerhalb eines bestimmten Bereichs (Rechteck) liegen.

Problem 1:
Gegeben ist ein Bereich B, der durch die Koordinaten BX1, BY1, BX2, BY2 definiert ist. Der Bereich ist immer rechteckig und waagerecht ausgerichtet.

Nun habe ich eine Strecke S, welche durch die Koordinaten SX1, SY1, SX2, SY2 definiert ist.

Was ich brauche ist eine Formel, die mir als Ergebnis zurückgibt, ob Strecke S durch den Bereich B läuft (teilweise oder komplett) oder nicht. Die Formel muss so einfach wie möglich sein, da sie in einem Scriptdurchlauf mehrere Tausend mal berechnet werden muss (für unterschiedliche Strecken).

Problem 2:
Gegeben ist wieder derselbe Bereich B.

Dazu habe ich einen zweiten Bereich C, der durch CX1, CY1, CX2, CY2 definiert ist. Wie B ist auch C immer rechteckig und waagerecht ausgerichtet.

Was ich brauche ist eine Formel, die mir als Ergebnis zurückgibt, ob B und C sich überschneiden (teilweise/ganz) oder nicht. Auch hier wieder möglichst einfach, da diese im WHERE-Bereich einer SQL-Abfrage stehen soll.

Danke für eure Hilfe.

Gruß, André

[Tom]

Hello,

da empfehle ich Dir die Vektorgeometrie
http://de.wikipedia.org/wiki/Vektor

Harzliche Grüße vom Berg
http://www.annerschbarrich.de

Tom

[André]

da empfehle ich Dir die Vektorgeometrie
http://de.wikipedia.org/wiki/Vektor

Hallo Tom,

Danke für den Hinweis. Allerdings hatte ich an etwas praxisorientiertes gedahct. Ich wollte nicht erst Mathematik studieren.

Die Problemstellung, überlappende Bereiche/Objekte zu finden ist ja sicher eine Sache, mit der sich schon einige Programmierer auseinandergesetzt haben.
Was ich suche, sind möglichst effiziente Formeln für den Einsatz in Scriptsprachen oder SQL-Abfragen.

Gruß, André

[Blaubart]

Hallo.

Danke für den Hinweis. Allerdings hatte ich an etwas praxisorientiertes gedahct. Ich wollte nicht erst Mathematik studieren.

Ein Mathestudium brauchst du für Vektorgeometrie zwar nicht, aber vielleicht findest du den Cohen-Sutherland-Algorithmus ja einfacher.

[Mia]

Hallo André,

Tom hat aber wirklich recht mit seinem Hinweis. Die Menge der
Punkte auf deiner Strecke erreichst du nämlich mit

(I) X = S1 + t * (S2-S1) und (0<=t<=1)

X, S1 und S2 sind Vektoren:
X=(x,y),  S1=(sx1, sy1), S2 = (sx2, sy2)

Wenn du dann noch die Bedingungen
(II)    x<= rechter Rand des Rechtecks
(III)   x>= linker Rand des Rechtecks
(IV)    y<= oberer Rand des Rechtecks
(V)     y>= unterer Rand des Rechtecks

berücksichtigst, müsstest du eigentlich feststellen können, ob es ein passendes t gibt.

Die Menge der Punkte in einem Rechteck erreichst du übrigens mit
X = C1 + r* (Länge unterer Rand) * (1,0) + t* (Länge rechter Rand) * (0,1)
und 0<=s,t<=1
Wieder sind X=(x,y), C1=(cx1, cy1) und (1,0) und (0,1) Vektoren.

Gruß Mia

[Danny]

Hi André,

mach' Dir doch eine Zeichnung mit Beispielen. Vielleicht stelle ich es mir zu einfach vor aber wenn es nur Rechtecke sind, müßten ein paar If-Abfragen ausreichen.

MfG

• Danny