Jak obliczyć odległość między punktem a prostokątem wyrównanym do osi?

29

Mam prostokąt 2D z pozycją x, y, wysokością i szerokością oraz w pobliżu losowo ustawionego punktu.

Czy istnieje sposób, aby sprawdzić, czy ten punkt może kolidować z prostokątem, jeśli znajduje się bliżej niż pewna odległość? Wyobraź sobie, że niewidoczny promień poza tym punktem koliduje ze wspomnianym prostokątem. Mam z tym problemy po prostu dlatego, że to nie jest kwadrat!

John Smith
źródło

Odpowiedzi:

26

Jeśli (x,y)jest środkiem prostokąta, kwadratową odległość od punktu (px,py)do granicy prostokąta można obliczyć w następujący sposób:

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

Jeśli ta kwadratowa odległość wynosi zero, oznacza to, że punkt dotyka lub znajduje się w prostokącie.

sam hocevar
źródło
6
Dla każdego, kto się zastanawia, (x, y) jest środkiem prostokąta, a nie narożnikiem
Greg Rozmarynowycz
2
Przepraszamy za stary komentarz, ale czy to równanie zakłada, że ​​prostokąt jest wyrównany względem osi?
BitNinja,
1
@ BitNinja tak, tak zakłada pytanie. Jeśli nie jest wyrównany względem osi, najszybszy / najprostszy algorytm będzie zależał od sposobu przechowywania informacji o prostokącie.
sam hocevar
powiedzmy, punkt to (4: 4), prostokąt to (5: 5) o szerokości / wysokości (5: 5). Twój kod twierdzi, że punkt dotyka lub znajduje się w prostokącie, ale oczywiście jest na zewnątrz
LRN
@LRN prostokąt wyśrodkowany na (5: 5) o szerokości / wysokości (5: 5) rozciąga się od (2,5: 2,5) do (7,5: 7,5). Punkt (4: 4) znajduje się wewnątrz tego prostokąta.
sam hocevar
11

Zakładam, że twój prostokąt jest wyrównany względem osi.

Musisz tylko „zaciśnąć” punkt w prostokącie, a następnie obliczyć odległość od zaciśniętego punktu.

Punkt = (px, py), Prostokąt = (rx, ry, szerokość, wysokość) // (lewy górny róg, wymiary)

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
źródło
3

W tym celu należy użyć kolizji koło-prostokąt. Jest podobny pytanie na przepełnienie stosu.

Środek twojego okręgu byłby pytaniem, a promień byłby odległością, którą chcesz sprawdzić.

Eric B.
źródło
3

Jeśli próbujesz obliczyć odległość od punktu do krawędzi prostokąta, praca z każdym z dziewięciu regionów utworzonych przez prostokąt może być najszybszym sposobem:

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
źródło
2

[Zmodyfikowana odpowiedź na podstawie komentarzy]

Jeśli chcesz sprawdzić, czy punkt znajduje się w granicach powiedzmy 10 jednostek, jeśli szary prostokąt na obrazku poniżej, sprawdzisz, czy punkt znajduje się w jednym z

  1. czerwony prostokąt
  2. Niebieski prostokąt
  3. dowolny z zielonych kół (promień 10)

wprowadź opis zdjęcia tutaj

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

To podejście jest trochę nieeleganckie. Podobna metoda, która pozwala uniknąć konieczności testowania wszystkich 4 rogów za pomocą symetrii prostokąta, jest tutaj udokumentowana podczas przepływu stosu

Rozpoznać
źródło
W kierunku ukośnym da to fałszywie dodatni punkty, które są np. 11 jednostek dalej.
Eric B
Zaktualizowany obraz jest rażąco niepoprawny, w rzeczywistości ilustruje przypadek błędu i sprawia, że ​​wydaje się poprawny. Ten zielony punkt może z łatwością znajdować się w odległości większej niż 10 jednostek i znajdować się w tym zewnętrznym prostokącie.
Eric B
Hej @ EricB, naprawiłem wskazany przez ciebie błąd, a może cofniesz głosowanie?
Ken
Twoja odpowiedź nie przyniesie już całkowicie niepoprawnych wyników, więc usunąłem głos negatywny, ale nie jest to wcale najlepszy sposób. Dlaczego nie po prostu sprawdzić, czy środek znajduje się w prostokącie i czy cztery segmenty linii przecinają okrąg? Konstrukcja tych nowych prostokątów i okręgów po prostu nie jest konieczna. Twoja odpowiedź nie podaje również rzeczywistej odległości od punktu do prostokąta.
Eric B,
Ta odpowiedź jest naprawdę okropna. 12 dodatków, 4 konstrukcje obiektowe, 12 testów, 4 pierwiastki kwadratowe dla zadania, które w rzeczywistości wymaga 3 linii kodu?
sam hocevar
-2

Możesz użyć czegoś takiego: wprowadź opis zdjęcia tutaj

AlexanderBrevig
źródło
Ta metoda wydaje się niepotrzebnie skomplikowana. Znalezienie x1 i y1 nie jest konieczne do rozwiązania tego problemu.
Eric B
W rzeczywistości nie spełnia to nawet wymogu znalezienia kolizji w określonej odległości. To po prostu zły sposób na wykrycie, czy punkt znajduje się w prostokącie.
Eric B
Miara odległości jest już domyślnie dostępna. if (d2 <10 * 10) {/ * w obrębie 10 jednostek miary * /}
AlexanderBrevig