Wie berechne ich den Abstand zwischen einem Punkt und einem achsenausgerichteten Rechteck?

29

Ich habe ein 2D-Rechteck mit x-, y-Position, Höhe und Breite und einem zufällig positionierten Punkt in der Nähe.

Gibt es eine Möglichkeit zu prüfen, ob dieser Punkt möglicherweise mit dem Rechteck kollidiert, wenn er näher als eine bestimmte Entfernung ist? Stellen Sie sich einen unsichtbaren Radius außerhalb dieses Punktes vor, der mit dem Rechteck kollidiert. Ich habe Probleme damit, einfach weil es kein Quadrat ist!

John Smith
quelle

Antworten:

26

Wenn (x,y)es sich um die Mitte des Rechtecks ​​handelt, kann der quadratische Abstand von einem Punkt (px,py)zum Rand des Rechtecks ​​folgendermaßen berechnet werden:

dx = max(abs(px - x) - width / 2, 0);
dy = max(abs(py - y) - height / 2, 0);
return dx * dx + dy * dy;

Wenn dieser quadratische Abstand Null ist, bedeutet dies, dass der Punkt das Rechteck berührt oder sich innerhalb des Rechtecks ​​befindet.

sam hocevar
quelle
6
Für alle anderen, die sich fragen, ist (x, y) die Mitte des Rechtecks, nicht die Ecke
Greg Rozmarynowycz
2
Entschuldigen Sie den alten Kommentar, aber geht diese Gleichung davon aus, dass das Rechteck auf die Achse ausgerichtet ist?
BitNinja
1
@BitNinja ja, davon geht die Frage aus. Wenn die Achse nicht ausgerichtet ist, hängt der schnellste / einfachste Algorithmus davon ab, wie die Rechteckinformationen gespeichert werden.
Sam Hocevar
Sprich Punkt ist (4: 4), Rechteck ist bei (5: 5) mit Breite / Höhe (5: 5). Ihr Code würde behaupten, dass der Punkt das Rechteck berührt oder sich innerhalb des Rechtecks ​​befindet, aber offensichtlich außerhalb
LRN
@LRN Ein bei (5: 5) zentriertes Rechteck mit Breite / Höhe (5: 5) erstreckt sich von (2,5: 2,5) bis (7,5: 7,5). Der Punkt (4: 4) befindet sich innerhalb dieses Rechtecks.
Sam Hocevar
11

Ich gehe davon aus, dass Ihr Rechteck achsenausgerichtet ist.

Sie müssen nur den Punkt in das Rechteck "klemmen" und dann den Abstand vom geklemmten Punkt berechnen.

Punkt = (px, py), Rechteck = (rx, ry, rwidth, rheight) // (obere linke Ecke, Maße)

function pointRectDist (px, py, rx, ry, rwidth, rheight)
{
    var cx = Math.max(Math.min(px, rx+rwidth ), rx);
    var cy = Math.max(Math.min(py, ry+rheight), ry);
    return Math.sqrt( (px-cx)*(px-cx) + (py-cy)*(py-cy) );
}
Ivan Kuckir
quelle
3

Dazu müssen Sie Kreis-Rechteck-Kollisionen verwenden. Es gibt eine ähnliche Frage zum Stapelüberlauf.

Der Mittelpunkt Ihres Kreises ist der fragliche Punkt, und der Radius ist der Abstand, den Sie überprüfen möchten.

Eric B
quelle
3

Wenn Sie versuchen, den Abstand zwischen einem Punkt und der Kante eines Rechtecks ​​zu ermitteln, ist es möglicherweise am schnellsten, mit den neun vom Rechteck erstellten Bereichen zu arbeiten:

function pointRectangleDistance(x, y, x1, y1, x2, y2) {
    var dx, dy;
    if (x < x1) {
        dx = x1 - x;
        if (y < y1) {
            dy = y1 - y;
            return Math.sqrt(dx * dx + dy * dy);
        }
        else if (y > y2) {
            dy = y - y2;
            return Math.sqrt(dx * dx + dy * dy);
        }
        else {
            return dx;
        }
    }
    else if (x > x2) {
        dx = x - x2;
        if (y < y1) {
            dy = y1 - y;
            return Math.sqrt(dx * dx + dy * dy);
        }
        else if (y > y2) {
            dy = y - y2;
            return Math.sqrt(dx * dx + dy * dy);
        }
        else {
            return dx;
        }
    }
    else {
        if (y < y1) {
            return y1 - y;
        }
        else if (y > y2) {
            return y - y2;
        }
        else {
            return 0.0; // inside the rectangle or on the edge
        }
    }
}
Heliodor
quelle
2

[Geänderte Antwort basierend auf Kommentaren]

Wenn Sie sehen möchten, ob der Punkt innerhalb von beispielsweise 10 Einheiten liegt, wenn sich das graue Rechteck im Bild unten befindet, überprüfen Sie, ob sich der Punkt in einem von befindet

  1. rotes Rechteck
  2. Blaues Rechteck
  3. irgendeiner der grünen Kreise (Radius 10)

Bildbeschreibung hier eingeben

inside=false;

bluerect.x=oldrect.x-10;
bluerect.y=oldrect.y;
bluerect.width=oldrect.width;
bluerect.height=oldrect.height+20;

if(  point.x >=bluerect && point.x <=redrect.x+bluerect.width &&
     point.y >=bluerect && point.y <=redrect.y+bluerect.height){
         //now point is side the blue rectangle
         inside=true;
}

redrect.x=oldrect.x;
redrect.y=oldrect.y-10;
redrect.width=oldrect.width+20;
redrect.height=oldrect.height;

if(  point.x >=redrect&& point.x <=redrect.x+redrect.width &&
     point.y >=redrect&& point.y <=redrect.y+redrect.height){
         //now point is side the redrectangle
         inside=true;
}


d1= distance(point, new point(oldrect.x, oldrect.y)) //calculate distance between point and (oldrect.x, oldrect.y)
d2= distance(point, new point(oldrect.x+10, oldrect.y))
d3= distance(point, new point(oldrect.x, oldrect.y+10))
d4= distance(point, new point(oldrect.x+10, oldrect.y+10))
if (d1 < 10 || d2 <10 || d3 < 10 || d4 <10){
    inside=true;
}

//inside is now true if the point is within 10 units of rectangle

Dieser Ansatz ist ein wenig unelegant. Eine ähnliche Methode, bei der nicht alle 4 Ecken mit Hilfe der Rechtecksymmetrie getestet werden müssen, ist hier beim Stackoverflow dokumentiert

Ken
quelle
In diagonaler Richtung ergibt dies ein falsches Positiv für Punkte, die z. 11 Einheiten entfernt.
Eric B
Das aktualisierte Bild ist offensichtlich falsch, es zeigt tatsächlich den Fehlerfall und lässt es richtig erscheinen. Dieser grüne Punkt könnte leicht mehr als 10 Einheiten entfernt sein und sich innerhalb des äußeren Rechtecks ​​befinden.
Eric B
Hey @EricB, ich habe den Fehler behoben, auf den Sie hingewiesen haben. Wie wäre es, wenn Sie Ihre Ablehnung rückgängig machen?
Ken
Ihre Antwort wird nicht länger zu absolut falschen Ergebnissen führen, daher habe ich die Ablehnung entfernt, aber es ist auch nicht der beste Weg. Warum nicht einfach testen, ob der Mittelpunkt innerhalb des Rechtecks ​​liegt und ob die vier Liniensegmente den Kreis schneiden? Die Konstruktion dieser neuen Rechtecke und Kreise ist einfach nicht notwendig. Ihre Antwort gibt auch nicht die tatsächliche Entfernung vom Punkt zum Rechteck an.
Eric B
Diese Antwort ist ehrlich gesagt schrecklich. 12 Ergänzungen, 4 Objektkonstruktionen, 12 Tests, 4 Quadratwurzeln für eine Aufgabe, die tatsächlich 3 Codezeilen benötigt?
Sam Hocevar
-2

Sie könnten so etwas verwenden: Bildbeschreibung hier eingeben

AlexanderBrevig
quelle
Diese Methode erscheint unnötig kompliziert. Es ist nicht erforderlich, x1 und y1 zu finden, um dieses Problem zu lösen.
Eric B
Tatsächlich erfüllt dies nicht einmal die Anforderung, eine Kollision innerhalb einer gegebenen Entfernung zu finden. Es ist nur eine schlechte Methode, um festzustellen, ob sich der Punkt innerhalb des Rechtecks ​​befindet.
Eric B
Ein Abstandsmaß ist implizit schon da. if (d2 <10 * 10) {/ * innerhalb von 10 Maßeinheiten * /}
AlexanderBrevig