Schnitt: Gerade/Rechteck

[Medium]

Aloah! Wieder mal eine Schnitt-Frage...

Ich hab eine beliebige Gerade (bzw. Strecke, ich kann beides liefern) und ein achsenparalleles Rechteck. Ich möchte nun wissen, ob meine Gerade/Strecke dieses Rechteck schneidet/passiert, ohne dafür aufwendige Operationen machen zu müssen. Trigonometrie und Steigungsbestimmung scheiden z.B. aus. Am Rande: Ich brauch den genauen Schnittpunkt nicht.

Ich hab irgendwo mal aufgeschnappt, dass das nur über Vergleich von min/max Koordinaten geht (ein paar Differenzbildungen wären sicher kein Beinbruch falls nötig), aber ich komme einfach nicht dahinter.
Was ich bereits erkannt habe ist, dass eine Gerade die nicht schneidet, erst die minX und maxX (bzw. minY und maxY) Koordinate des Rechteckes passiert, und danach erst die anderen beiden. Eine Gerade die schneidet, passiert erst eine X, dann eine Y, dann die andere X dann die andere Y Koordinate - also abwechselnd.
Im Falle einer Strecke (die ja Anfang und Ende hat) können Schnitte fehlen, so dass sie z.B. nur die min/max X oder Y durchstößt, und sonst nichts.

Ob das überhaupt eine brauchbare Erkenntnis ist weiss ich leider nicht . Überlappung von 2 Rechtecken wäre einfach, da wüsste ich wie - aber bei der Geraden brauch ich mal nen Anstupser.

Danke schon Mal vorab, und nettes WE!

[Reinhard Kern]

Zitat von Medium:

...Ich hab eine beliebige Gerade (bzw. Strecke, ich kann beides liefern) und ein achsenparalleles Rechteck. Ich möchte nun wissen, ob meine Gerade/Strecke dieses Rechteck schneidet/passiert, ohne dafür aufwendige Operationen machen zu müssen. ...

Was immer du für aufwendig hältst (ich wills garnicht wissen), ich würde es so angehen: für Xmin und Xmax des Rechtecks die Y-Koordinate der Geraden berechnen (Geradengleichung) und mit Ymin und Ymax des Rechtecks vergleichen (= 4 x SUB). Die Gerade schneidet das Rechteck dann nicht, wenn die Y-Werte des Rechtecks alle (echt) kleiner sind als der Y-Wert der Geraden an diesem X-Wert. dann läuft die Gerade oben vorbei. Oder sie sind alle grösser, dann läuft die Gerade unter dem Rechteck vorbei.

Ist alles aus dem Kopf und ohne Zeichnung, wenn ich mich vertan habe bitte Korrektur. Wenn nicht dürfte es nicht einfacher gehen.

Gruss Reinhard

[Medium]

Aufwendig ist alles was CPU-Zeit kostet. Ich muss das ein paar 100.000 Mal mit so 100 Rechtecken durchexerzieren, und will dafür nicht mehr als ein paar Sekunden, gerne weniger brauchen. Addieren, Subtrahieren und Vergleichen ist okay, Multiplizieren wohl auch, ab Dividieren werd ich schon hellhörig

Nach deinem Beitrag etwas Gesuche bin ich nun auf folgende Methode gestoßen:
Ausgangslage ist ein Strahl, gegeben durch A+t*B (A und B = 2D-Vektoren) und ein beliebiges achsenparalleles Rechteck. Jetzt berechne ich den Schnitt des Strahls mit den 4 "Strahlen" die die Rechteck-Kanten beschreiben, aber nur so weit bis ich die 4 t's hab, welche mir quasi sagen bei welcher Entfernung mein 1. Strahl diese Achsenparallelen schneidet. 2 davon für die X-Schnitte, 2 für die Y-Schnitte. Wenn jetzt einer oder beide von einem Paar zwischen den Werten des anderen Paares liegen, müsste ich schneiden.

Jetzt muss ich nur noch testen ob das performancemäßig meinen Anforderungen standhalten kann - und ob's überhaupt wirklich so geht

Danke dir schon mal! Und falls da noch möglicherweise schnellere Einfälle in manchen Köpfen schwirren: Ich bin da sehr offen für

[Nikolas]

Ein sehr schneller Einfall: http://www.cgal.org/
Das ist eine freie Computer-Geometrie-Bibliothek, die unter anderem so etwas sehr gut abdeckt. Es werden ziemlich viele Beispiele mitgeliefert, also sollte es recht gut machbar sein.

CGAL::do_intersect (iso_rect!)

[Medium]

Eine externe Lib kommt leider überhaupt nicht in Frage

[alzaimar]

Wenn Du das umgebende (achsenparallele) Rechteck einer Stecke betrachtest, dann könnten Dir deine Erkenntnisse bezüglich der Erkennung der Überlappung von Rechtecken weiterhelfen. Eventuell gepaart mit einer Fallunterscheidung, denn das umschließende Rechteck (P1-P2-P3-P4) einer Geraden (P1-P3) überlappt ein anderes Rechteck am Punkt P2, aber damit schneidet die Gerade P1-P3 nicht notwendigerweise(!) das Rechteck. Hier müsstest Du also analytisch prüfen, sonst ist der Fall klar.

[Medium]

Genau den Ansatz hatte ich schon, allerdings ist das Verfahren viel zu grob. Es geht darum: Ich habe ein Bild in kleinere Bilder zerlegt. Dann nehm ich einen Punkt im Bild, und von diesem aus einen Vektor. Nun will ich eine Liste aller Rechtecke haben, die dieser daraus erzeugte Strah schneidet.
Ich kann nun aus dem Strahl durchaus eine Strecke machen in dem ich einfach den 2. Punkt so wähle dass er ausserhalb des Bildes liegt um den selben Effekt zu haben, jedoch führt das dazu, dass ich viel zu viele Rechtecke als Schnittkandidaten habe - im Worst-Case alle.

Das hier hängt mit meinem kürzlich hier erstellten Thema zusammen, wie man eine Gerade mit einer Fkt. 3. Grades schneidet, und das braucht eben so arg lange, dass ich diese Methode hier brauche um vorab sehr "billig" möglichst viel auszuschließen. Im Grunde macht man das bei fast allen 3D Anwendungen genau so, nur eben mit dem "View-Frustum" und einem Octree der Szene. Bei mir isses halt nur 2D, der Frustum ist eine Linie, und der Octree ist ein regelmäßiges Gitter von Rechtecken.

[Nikolas]

Warum willst du denn keine Bibliothek einsetzen? Räder neu zu erfinden ist nicht immer notwendig.

Kleiner Vorschlag:

Nimm deine Strecke als Geradengleichung und evaluiere sie an den waagrechten Kanten. Für Einheitskästchen also
y=mx+c ->
y = 1 => x=3.4, abgerundet bist du also im Kästchen (3,1)
y = 2 => x=4.9, -> (4,1)
y = 3 => x=6.4 -> (5,1),(6,1) <- kleiner Spezialfall für recht flache Geraden.

Damit solltest auf jeden Fall recht schnell sein, da du fuer jede Ebene nur eine Addition und ein Abrunden ausfuehren musst. (und dazu noch nie Abfrage bei sehr flachen geraden, wobei du schon durch m>0.5? entscheiden kannst, ob der Fall auftreten kann.

Alternativ koenntest du dir auch den Bresenham-Algorithmus anschauen, der wird eigentlich eingesetzt, um Geraden oder Kreise zu zeichnen und entscheidet, welche Pixel geschwärzt werden, was recht genau deine Frage beantworten koennte.

Du willst aber nicht die Gerade und eine Parabel über Pixelvergleiche schneiden, oder?

[Medium]

Zitat von Nikolas:

Warum willst du denn keine Bibliothek einsetzen? Räder neu zu erfinden ist nicht immer notwendig.

Das Einweben einer externen Lib wäre bei mir recht rechenintensiv, da diese Prüfungen sehr eng in einem Kontext passieren. Im schlimmsten Fall müsste ich etliche Zeilen bestehendes Programm auf die Lib anpassen. Zudem geht's um meine Bachelorarbeit, wo ich schon ganz gerne den Großteil selbst in der Hand haben mag

Zitat:

Kleiner Vorschlag:

Bresenham hatte ich auch schon als Alternative im Kopf, aber zunächst zugunsten anderer Ansätze hinten angestellt. Die Variante mit der Form y=mx+c hat leider zwei gravierende Nachteile: Ich müsste jeden Strahl erst von Vektorform in diese Form überführen, und der "Spezial"-Fall flacher Geraden käme recht oft vor.

Zitat:

Du willst aber nicht die Gerade und eine Parabel über Pixelvergleiche schneiden, oder?

Neee! Ich will Vektoren um Pixel drehen, und diese mit Catmull-Rom-Splines schneiden (wirklich)


Ich hab bei meiner Suche 2 Ansätze gefunden die ganz nett sind jetzt:

1) Schnitt des Vektors mit den 4 Kanten des Rechtecks (bzw. mit den 4 Geraden die längs durch diese Kanten verlaufen). Da von diesen immer eine Koordinate 0 ist, reduziert sich das auf 4 Mal einen Term der Form "(a1-a0) / b". Daraus bekomme ich letztlich 4 Skalare für den Richtungsvektor meines Strahls, welche gestaffelt die Reihenfolge ergeben in der der Strahl diese 4 Geraden schneidet. Je nach dem wie diese Reihenfolge aussieht, kann ich aussagen ob ein Schnitt passiert oder nicht.

2) Der ist schon was heftiger, und basiert auf dem Separating-Axis-Theorem. Dafür werden Strahl und Rechteck auf die Senkrechte zum Strahl projeziert, und wenn diese sich nicht überlappen habe ich auch keinen Schnitt. Das klingt im Anstaz sehr aufwendig, ist in Code gegossen (dank Achsenparallelität der Rechtecke) lediglich das hier:

Code:

private static bool RayIntersectsRect(float posX, float posY, float dirX, float dirY, Rect rect)
{
   float rayProj = (posX*dirY - posY*dirX);
   float radProj = Math.Abs(dirY*rect.extX) + Math.Abs(dirX*rect.extY);
   float centProj = rect.centerX*dirY - rect.centerY*dirX;
   
   float min = centProj-radProj;
   float max = centProj+radProj;
   
   return !((rayProj < min) || (rayProj > max));
}

Wobei posX/posY der Ursprung des Strahls ist, dirX/dirY die normalisierte Richtung (ich hab sie von vorn herein eh schon normalisiert vorliegen), Rect.centerX/Y ist die Mitte eines Rechtecks, und Rect.extX/Y ist die halbe Kantenlänge in X bzw. Y.


Allein schon die Tatsache dass bei (2) keine Divisionen vorkommen macht es merkbar schneller als (1), was ich vom "Klang" her erstmal für schneller gehalten hätte. Das scheint wohl auch Stand der Theorie in 3D zu sein, weswegen ich erstmal nicht davon ausgehe dass das noch flotter gehen wird. Man darf nur nicht erwähnen, dass ich für diese 6 Zeilen jetzt 2 Tage getüftelt und nen Forum befragt hab .

Heissen Dank an euch, denn auch wenn die letztliche Lösung nicht mehr SO viel mit den Vorschlägen zu tun hat, bin ich so doch erst in die richtige Such-Richtung geraten!

[Nikolas]

Die Darstellung der Geraden ist beliebig austauschbar

Ich geh mal davon aus, dass dein Strahl im Kästchen mit Index (linke untere Ecke) s=(x,y) beginnt und Richtung d=(u,v) läuft, wobei d normalisiert ist. Deine Kästchen haben Länge (W,H). Mit L = H/v hast du den Vector d'=L*d, der von der der linken unteren ecke von (x,y) zu waagrechten mit y=x+W läuft.
Jetzt hast du die x-Werte x_i=x+i*u' (x*i*L*u) und kannst schauen, in welchem Kästchen das liegt.

Damit kommst du pro Ebene mit einer Addition (x_(i+1)=u'+x_i), einem Abrunden (und vielleicht noch der Abfrage wegen uebersprungener Kästchen hin.

Deine Ansätze nutzen überhaupt nicht aus, das die Rechtecke sehr nett angeordnet sind und du somit z.B. weisst, dass wenn deine Strecke durch (x,y) und (x+3,y) geht, wohl auch (x+1,y) geschnitten werden muss.


// Könntest du vielleicht dein Problem noch ein Mal erklären? Ich habe das Gefühl, dass es da vielleicht auch einen komplett anderen Ansatz für die Berechnung gibt, der noch mal schneller sein könnte.