Anderer Algorithmus für Bounding Box

krgewb

krgewb

Top Contributor
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ß.
 
K

kneitzel

Gast
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

krgewb

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

Anhänge

  • Unbenannt.png
    Unbenannt.png
    8 KB · Aufrufe: 4
K

kneitzel

Gast
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.

12185


-> 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

mihe7

Top Contributor
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.
 
K

kneitzel

Gast
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 :)
 
H

httpdigest

Top Contributor
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:
Java:
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:
Java:
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;
}
 
Zuletzt bearbeitet:
JCODA

JCODA

Top Contributor
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:
Python:
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

mihe7

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

Code:
| 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
 
H

httpdigest

Top Contributor
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.
 
Zuletzt bearbeitet:
Ähnliche Java Themen
  Titel Forum Antworten Datum
T MouseMotionListener aus anderer Klasse verwenden. Spiele- und Multimedia-Programmierung 1
H Zugreifen/Benutzen anderer Variable aus anderer Klasse Spiele- und Multimedia-Programmierung 1
V BufferedImage[] aus anderer Classe auslesen Spiele- und Multimedia-Programmierung 2
T Overlay in anderer OpenGL Anwendung Spiele- und Multimedia-Programmierung 4
F Algorithmus für bessere Kollisionsabfragen Spiele- und Multimedia-Programmierung 10
Z Minimax-Algorithmus für TicTacToe Spiele- und Multimedia-Programmierung 5
Z Such-Algorithmus Spiele- und Multimedia-Programmierung 2
E A-Stern Algorithmus Problem und Implementierung einer Map Spiele- und Multimedia-Programmierung 6
E Pathfinding Algorithmus Spiele- und Multimedia-Programmierung 2
B minimax Algorithmus Spiele- und Multimedia-Programmierung 5
S Problem mit 4 gewinnt(MinMax Algorithmus) Spiele- und Multimedia-Programmierung 2
S A*-Algorithmus Spiele- und Multimedia-Programmierung 12
S A* Algorithmus Spiele- und Multimedia-Programmierung 14
S Algorithmus zur Ressourcesuche für die KI Spiele- und Multimedia-Programmierung 5
C Algorithmus um Flächen zu erkennen Spiele- und Multimedia-Programmierung 6
L Fehlersuche beim Weichzeichner-Algorithmus Spiele- und Multimedia-Programmierung 9
A Negamax-Algorithmus Spiele- und Multimedia-Programmierung 7
B Umsetzung des Minimax-Algorithmus Spiele- und Multimedia-Programmierung 2
B Deepmind Poker Bot für PokerStars konfigurieren? Spiele- und Multimedia-Programmierung 2
G Minecraft PlayerBot (Listener Thread für jeden Spieler?) Spiele- und Multimedia-Programmierung 3
K Wie bekomme ich eine Transition für alle Objekte zum stoppen? Spiele- und Multimedia-Programmierung 1
E Organisation für Game Spiele- und Multimedia-Programmierung 1
Excess Ballerfisch für Android Spiele- und Multimedia-Programmierung 3
coolian ich brauche irgendeine gui lib für lwjgl2 Spiele- und Multimedia-Programmierung 51
M MP3 Dateien für Metadaten abgleichen Spiele- und Multimedia-Programmierung 0
Freshy Bot für Discord Spiele- und Multimedia-Programmierung 61
R Ideen für die Backend-Entwicklung eines Games gesucht Spiele- und Multimedia-Programmierung 8
trustlesseyes Mikrophon-/Audiosteuerung für einen Character Spiele- und Multimedia-Programmierung 1
P Tennis- Spielstand- Zähler für Schule programmieren Spiele- und Multimedia-Programmierung 6
M Logik für ein Quiz Spiele- und Multimedia-Programmierung 7
P Hilfe für Seminar Arbeit Spiele- und Multimedia-Programmierung 9
M Metadaten für Multimedia Daten ermitteln Spiele- und Multimedia-Programmierung 4
G Übungsprogramm für Matheaufgaben Spiele- und Multimedia-Programmierung 1
S Bilder Für Schachfiguren Spiele- und Multimedia-Programmierung 14
Timo_neu_in_java Suche etwas einfaches für Anfänger Spiele- und Multimedia-Programmierung 6
S GUI erstellen für Text Adventure Spiele- und Multimedia-Programmierung 4
S Eigene Klasse vec_t - 3 oder 4 Einheiten für x, y, z und w Spiele- und Multimedia-Programmierung 11
R Vererbbarer GameLoop für Engine Spiele- und Multimedia-Programmierung 14
J Vektor für Gravitation erzeugen Spiele- und Multimedia-Programmierung 34
I Minecraft: Craftingrecipe für Braustand ändern Spiele- und Multimedia-Programmierung 9
H KI für Spiele Spiele- und Multimedia-Programmierung 1
S Pssende Datenstruktur für ein Netz Spiele- und Multimedia-Programmierung 5
S MouseEvents für Sprites Spiele- und Multimedia-Programmierung 3
I Spectator Modus für Spiel ähnlich zu Terraria Spiele- und Multimedia-Programmierung 8
K Bestes Bildformat für Spielegrafiken und deren Einbindung in Java Spiele- und Multimedia-Programmierung 2
J mehrere Listener für einen Button / Label Spiele- und Multimedia-Programmierung 1
C Port umleiten: lesen und schreiben für MCServer-Client über Skype Spiele- und Multimedia-Programmierung 0
J Musik Bibliothek für GUI Spiele- und Multimedia-Programmierung 7
B Hauptmenü für Spiel Spiele- und Multimedia-Programmierung 1
R Ratschlag für 2D-3D Engine für die Spieleentwicklung gesucht Spiele- und Multimedia-Programmierung 4
Androbin KI für Verfolgung im Raster Spiele- und Multimedia-Programmierung 2
A Bot für Browsergame Spiele- und Multimedia-Programmierung 2
H Tutorials für Fortgeschrittene 3D-Anwedungen Spiele- und Multimedia-Programmierung 2
lord239123 suche Graphiker für ein Pokemon-Spiel Spiele- und Multimedia-Programmierung 6
Furtano Vektoren für Bewegung für eine 2D-Simulation Spiele- und Multimedia-Programmierung 3
T Sinusgenerator für eine Hp Spiele- und Multimedia-Programmierung 8
J Menü für Snakespiel in einzelnem JFrame Spiele- und Multimedia-Programmierung 5
Guybrush Threepwood Ketzerische Frage: Opus-Codec für Java Spiele- und Multimedia-Programmierung 14
L Hilfe bei Klassendesign für Spiel Spiele- und Multimedia-Programmierung 2
N Animationen für ein 2D game Spiele- und Multimedia-Programmierung 6
S Aufbau für 2D Spiele Spiele- und Multimedia-Programmierung 7
L Client für ein Browsergame Spiele- und Multimedia-Programmierung 21
Devil0s Swing Elemente für Inventar? Spiele- und Multimedia-Programmierung 9
Kenan89 Ansatzfrage: Kartenspiel für 2 Spieler Online Spiele- und Multimedia-Programmierung 3
F Ideen für spiel Spiele- und Multimedia-Programmierung 4
P Spielfeld für RPG Spiele- und Multimedia-Programmierung 15
Hoppelmann Alphamap (Bild) für 3D-Terrain generieren Spiele- und Multimedia-Programmierung 2
M Farbwerte für Flächen aus einem Bild erkennen Spiele- und Multimedia-Programmierung 3
K Einfache Engine für einfaches 3D gesucht Spiele- und Multimedia-Programmierung 10
C KI für Skatspiel - Wie können die Computerspieler eigenständig handeln? Spiele- und Multimedia-Programmierung 10
S Aufbau von Klassen für Spiel Spiele- und Multimedia-Programmierung 13
Kenan89 Kleines Projekt für Java Spiele- und Multimedia-Programmierung 5
M Empfehlungen für ein 2D-Jump'n'run Spiele- und Multimedia-Programmierung 4
A Grundlagensuche für Spiel Spiele- und Multimedia-Programmierung 8
C Wo ist der MP3 Plugin für JMF? Spiele- und Multimedia-Programmierung 3
sla89 Design Pattern gesucht für Spielregeln Spiele- und Multimedia-Programmierung 2
M Java als Programmiersprache für kommerzielle Spieleentwicklung? Spiele- und Multimedia-Programmierung 3
K Game Engine für selbstprogrammiertes Spiel Spiele- und Multimedia-Programmierung 27
Y Warum Thread für Spieleprogrammierung? Spiele- und Multimedia-Programmierung 27
A Music für Android game Spiele- und Multimedia-Programmierung 3
Gossi Probleme beim Laden der Images aus dem "Tutorial für Java-Spiele" Spiele- und Multimedia-Programmierung 4
Luk10 Tipps für bessere Animationen / Grafik Engine Spiele- und Multimedia-Programmierung 2
T 2D Menü für 3D Spiel Spiele- und Multimedia-Programmierung 5
T Grundlagenwissen für den 3D Raum Spiele- und Multimedia-Programmierung 6
I getSubImage sorgt für starken Performanceeinbruch Spiele- und Multimedia-Programmierung 6
M technologie für video, webcam & co Spiele- und Multimedia-Programmierung 25
C Java für große Spiele geeignet ? Spiele- und Multimedia-Programmierung 101
D Libraryempfehlung für Effekte Spiele- und Multimedia-Programmierung 3
B Spiele programmieren für ein Fenster? Spiele- und Multimedia-Programmierung 14
D Tabelle für Spiel Spiele- und Multimedia-Programmierung 3
N Grundlagen für ein Jump&Run Spiele- und Multimedia-Programmierung 3
S Datenbank gesucht für Bilder(gif-dateien) Spiele- und Multimedia-Programmierung 5
J Suche 3D Programm für jMonkeyEngine Spiele- und Multimedia-Programmierung 5
W 3D-APIs für Java - Eine Übersicht Spiele- und Multimedia-Programmierung 8
D Problem beim Öffnen einer PHP für eine Highscore Spiele- und Multimedia-Programmierung 5
S Game Client für kleine Competition Spiele- und Multimedia-Programmierung 3
F Programm für Bildbearbeitung gesucht: Skalieren und Speichern Spiele- und Multimedia-Programmierung 6
K Lösungsansätze für ein Spiel Spiele- und Multimedia-Programmierung 2
Plastagen Frameworls für Animationen und co Spiele- und Multimedia-Programmierung 3
aze Wie Transform3D für PosPathInterpolator bestimmen Spiele- und Multimedia-Programmierung 8

Ähnliche Java Themen

Anzeige

Neue Themen


Oben