Anderer Algorithmus für Bounding Box

[krgewb]

Ich möchte ein Programm schreiben, das mir sagt, ob der Mauszeiger über ein Rechteck gehovert wird. Mit einer AABB (axis-aligned bounding box) ist das ganz einfach. Ich möchte das aber mit einem Rechteck machen, das gedreht ist. Bisher erstelle ich eine Bounding-Box um dieses Rechteck herum. Der resultierende Hoverbereich ist dann aber relativ groß.

 

[kneitzel]

Also ich habe mich damit noch nicht im Detail beschäftigt, aber eine Idee, die mir durch den Kopf geht:
Ein gedrehtes Rechteck könnte man doch unterteilen in ein Rechteck, welches nicht gedreht ist mit jeweils einem rechtwinkligen Dreieck an jeder Seite dran.

Somit kann man prüfen, ob der Mauszeiger in dem inneren Rechteck ist. Ist dies nicht der Fall, prüft man, in welchem Dreieck er evtl. sein könnte um dann da zu prüfen, ob der Mauszeiger in dem Dreieck ist.

Bezüglich Performance kann man sich überlegen, ob man zuerst das äußere Rechteck prüft um schnell zu einem negativen Ergebnis zu kommen. Aber das kann man ja etwas austesten. (Hängt halt davon ab, was öfters vorkommt. Wenn ich z.B. ganz viele Schaltflächen zu prüfen habe, dann wird von n Schaltflächen bei n-1 Schaltflächen dieser Test direkt negativ ausfallen...
Aber das nur als Gedanke, der eine tiefere Betrachtung benötigt.

Prüfung: Punkt in Dreieck - diverse Möglichkeiten:
https://python-programmieren.com/punkt-im-dreieck/
(Vom python im Link erst mal nicht verwirren lassen 🙂 )

 

[krgewb]

Meinst du so? Ich habe nämlich das Gefühl, dass du es nicht so meinst.

 

[kneitzel]

Das Bild zeigt ja, was Du derzeit machst mit innerem Rechteck das Du testen willst und Großer Binding Box außen rum.

Jetzt dreh dieses Bild so, dass das innere Rechteck aufrecht steht. Dann hast Du außen das gedrehte Rechteck und dann hast Du innen zum einen das innere Rechteck sowie die 4 Dreiecke, die ggf. zu prüfen sind.

Wobei ich mich gerade damit beschäftige und es geht deutlich einfacher:
- gegeben ist ein gedrehtes Rechteck.
- Wir haben einen Algorithmus, um Dreiecke abzuprüfen
==> Wir erzeugen uns einfach zwei Dreiecke, die wir prüfen können.



-> Schwarzes Rechteck (Oder auch gerne ein Viereck - es müssen nicht zwangsläufig 90° Winkel sein!) ist das gedrehte Rechteck.
-> Rote Linie zeigt, wie wir es zu zwei Dreiecken machen, damit wir einen Algorithmus eben aus meinem Link verwenden können.
-> Die blauen Linien brauchen wir erst einmal nicht. Das ist die Idee, es evtl. zu optimieren. Dann wäre es die OuterBox, die zuerst geprüft wird um zu sehen, ob wir die Dreiecke prüfen müssen oder nicht.

 

[mihe7]

Somit kann man prüfen, ob der Mauszeiger in dem inneren Rechteck ist. Ist dies nicht der Fall, prüft man, in welchem Dreieck er evtl. sein könnte um dann da zu prüfen, ob der Mauszeiger in dem Dreieck ist.

Man könnte auch einfach aus dem Rechteck zwei Dreiecke machen (Diagonale).

EDIT: Jetzt war der @kneitzel wieder schneller.

 

[kneitzel]

Man könnte auch einfach aus dem Rechteck zwei Dreiecke machen (Diagonale).

EDIT: Jetzt war der @kneitzel wieder schneller.

Ja, wenn man das so aufgezeichnet bekommt, dann wird es einfacher. Und vor allem: Ich bin auf ein xy Problem gelaufen:
X: ist ja klar - die Anforderung vom TE
Y: Rechteck mit maximaler Größe Berechnen, dessen Ecke auf den Linien des gegebenen Rechtecks sind und dessen Seiten waagerecht und Senkrecht sind (Also zurück gedreht). Und da merkt man dann ja schnell: Das braucht man nicht wirklich 🙂

 

[httpdigest]

Mit ein bisschen linearer Algebra ist das alles ganz einfach: Definiere eine orthogonale Basistransformation, die das Einheitsrechteck (-1, -1)...(+1, +1) auf dein möglicherweise gestrecktes, rotatiertes/orientiertes Rechteck mapped. Dann invertiere diese 3x2 Matrix und multipliziere das Resultat mit dem Spaltenvektor deines zu testenden Punktes (x, y, 1). Wenn die x und y Koordinate des Ergebnisses innerhalb von (-1, -1)..(+1, +1) ist, liegt der Punkt innerhalb des rotierten Rechtecks:

public static boolean pointInOrientedRectangle(
        float halfX, float halfY, // <- halbe Seitenlängen des Rechtecks
        float centerX, float centerY, // <- Zentrum des Rechtecks
        float angle, // <- Rotationswinkel (im mathematischen Sinne: positive Werte rotieren gegen den Uhrzeigersinn)
        // Rotation erfolgt um das Zentrum des Rechtecks
        float px, float py) { // <- zu testender Punkt
  // Translation und Rotation als 3x2 matrix
  float cos = (float) Math.cos(angle), sin = (float) Math.sin(angle);
  float m10 = -sin * halfY, m11 = cos * halfY;
  float m00 = cos * halfX, m01 = sin * halfX;
  float m20 = centerX, m21 = centerY;
  // 3x2 matrix invertieren
  float s = 1.0f / (m00 * m11 - m01 * m10);
  float n00 = m11 * s, n01 = -m01 * s;
  float n10 = -m10 * s, n11 = m00 * s;
  float n20 = (m10 * m21 - m20 * m11) * s, n21 = (m20 * m01 - m00 * m21) * s;
  // M * (px, py, 1)
  float dpx = n00 * px + n10 * py + n20;
  float dpy = n01 * px + n11 * py + n21;
  return dpx >= -1.0f && dpy >= -1.0f && dpx <= 1.0f && dpy <= 1.0f;
}

EDIT: Das oben ist eine naive Implementierung nach dem benannten Prinzip.
Jetzt kann man natürlich ausnutzen, dass die angewandten affinen Transformationen (Translation, Rotation und Skalierung) einfach sind und auch gut in ihrer invertierten Form selbst angegeben werden können: Translation^-1 ist einfach Translation in die andere Richtung, Rotation^-1 ist Rotation in die andere Richtung und Skalierung^-1 ist einfach Skalierung mit Faktor: 1.0/s.
Wenn man jetzt noch zu Hilfe nimmt, dass (T * R * S)^-1 = S^-1 * R^-1 * T^-1, dann vereinfacht sich die ganze Sache zu:

public static boolean pointInOrientedRectangle(
        float halfX, float halfY,
        float centerX, float centerY,
        float angle,
        float px, float py) {
    float cos = (float) Math.cos(-angle), sin = (float) Math.sin(-angle);
    float n00 =  cos / halfX, n01 = sin / halfY;
    float n10 = -sin / halfX, n11 = cos / halfY;
    float dpx = n00 * px + n10 * py + n00 * -centerX + n10 * -centerY;
    float dpy = n01 * px + n11 * py + n01 * -centerX + n11 * -centerY;
    return dpx >= -1.0f && dpy >= -1.0f && dpx <= 1.0f && dpy <= 1.0f;
}

 

[JCODA]

Eine weitere Möglichkeit könnte folgende sein:
Man testet für jede Seite des Rechtecks, ob man "links" oder "rechts" davon liegt, nachdem man den Ecken eine Reihenfolge und damit den Kanten eine Richtung gegeben hat. Wenn man zum Beispiel die Ecken im Uhrzeigersinn numeriert und entsprechend die Richtung wählt, bedeutet "innerhalb" genau, dass der Punkt "rechts" von allen Kanten liegt.

Die Unterscheidung zwischen Links und Rechts kann man einfach durch ein Skalarprodukt mit "der" Normale einer Seite gewählt werden. Hierbei ist es natürlich wichtig, die Normale konsistent zu wählen, sodass alle nach "außen" oder "innen" zeigen.

Anbei ein kleines Python-Script, auch wenn etwas kryptisch und unleserlich, wenn man mit numpy nicht vertraut ist:

Spoiler: Click4Python

import sys

import numpy as np
from PyQt5.QtGui import QPainter, QColor
from PyQt5.QtWidgets import QWidget, QApplication

points = [np.array((400, 400)), np.array((100, 450)), np.array((100, 600)), np.array((400, 550))]
sides = [points[(i + 1) % 4] - points[i] for i in range(4)]
normals = [np.array([p[1], -p[0]]) for p in sides]

tested = []


def test(p, v, t):
    return (t - p).dot(v) > 0


class Example(QWidget):

    def __init__(self):
        super().__init__()
        self.setGeometry(300, 300, 800, 800)
        self.setWindowTitle('RectangleTest')
        self.show()


    def paintEvent(self, event):
        qp = QPainter()
        qp.begin(self)
        for i in range(4):
            qp.drawLine(*points[i - 1], *points[i])
        for p, c in tested:
            qp.setBrush(QColor(*c))
            s = np.array([10, 10])
            qp.drawEllipse(*(p - s / 2), *s)
        qp.setBrush(QColor(0, 0, 0))
        qp.end()

    def mousePressEvent(self, event):
        pos = np.array([event.pos().x(), event.pos().y()])
        res = [test(p, n, pos) for p, n in zip(points, normals)]
        print(res, all(res))
        tested.append((pos, (0, 255, 0) if all(res) else (255, 0, 0)))
        self.repaint()


if __name__ == '__main__':
    app = QApplication([])
    ex = Example()
    sys.exit(app.exec_())

Achja diese Variante lässt sich trivialerweise auf alle konvexen Polygone verallgemeinern. Natürlich würde man für obiges Problem die Lösung von @httpdigest bevorzugen.
Noch eine zusätzliche Bemerkung: Das ist im Prinzip die Idee einer SupportVektorMaschine.

 

[mihe7]

Viel zu kompliziert. Man kann einfach die Dreiecksfläche (bzw. hier das Doppelte) verwenden.

| px  py 1 |
| qx  qy 1 | = (rx - px)(ry + py) + (qx - rx)(ry + ry) + (px - qx)(py + qy) =: f(p,q,r) = A
| rx  ry 1 |

A < 0 (A > 0), falls r rechts (links) der Geraden liegt, die durch p und q verläuft.

EDIT: überschnitten mit @JCODA

 

[httpdigest]

Jepp. Die optimale Lösung hängt sehr davon ab, in welcher Form man das Rechteck eigentlich definiert hat und wie umständlich die Umrechnung von der gegebenen Form in die für den gewählten Algorithmus nötige Form ist. Hat man die Eckpunkte? Hat man die Kanten/Liniensegmente? Hat man einen Eckpunkt und die Kantenvektoren? Hat man einen Eckpunkt oder das Zentrum, die Kantenlängen und den Rotationswinkel? ...
@mihe7 kannst du das auch in Code formulieren? Was ist px, py, qx, qy, rx, ry und A und f?

EDIT: Für die Form: Eckpunkt/Zentrum + Kantenlängen + Winkel oder auch Eckpunkt/Zentrum + Kantenvektoren ist die Lösung mit der Basistransformation garantiert die kürzeste. Plus: Wenn du Eckpunkt/Zentrum + Kantenvektoren hast, fällt sogar die Sinus/Kosinus-Berechnung weg.