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!

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.


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) );
}

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


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

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


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


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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.