Bagaimana cara menghitung jarak antara titik dan persegi panjang selaras sumbu?

29

Saya memiliki persegi panjang 2D dengan posisi x, y, tinggi dan lebar, dan titik yang diposisikan secara acak di dekatnya.

Apakah ada cara untuk memeriksa apakah titik ini mungkin bertabrakan dengan persegi panjang jika lebih dekat dari jarak tertentu? Bayangkan sebuah radius yang tidak terlihat di luar titik yang bertabrakan dengan kata persegi panjang. Saya punya masalah dengan ini hanya karena itu bukan persegi!

John Smith
sumber

Jawaban:

26

Jika (x,y)merupakan pusat persegi panjang, jarak kuadrat dari titik (px,py)ke batas persegi panjang dapat dihitung dengan cara ini:

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

Jika jarak kuadrat itu nol, itu berarti titik tersebut menyentuh atau berada di dalam persegi panjang.

sam hocevar
sumber
6
Bagi siapa pun yang bertanya-tanya, (x, y) adalah pusat dari persegi panjang, bukan sudut
Greg Rozmarynowycz
2
Maaf untuk komentar lama, tetapi apakah persamaan ini mengasumsikan bahwa persegi panjang disejajarkan dengan sumbu?
BitNinja
1
@ BitNinja ya, itu pertanyaannya. Jika tidak sejajar sumbu, algoritma tercepat / paling sederhana akan tergantung pada bagaimana informasi persegi panjang disimpan.
sam hocevar
katakanlah, titik adalah (4: 4), persegi panjang berada di (5: 5) dengan lebar / tinggi (5: 5). Kode Anda akan mengklaim bahwa titik tersebut menyentuh atau berada di dalam persegi panjang, tetapi jelas di luar
LRN
@ LRN persegi panjang berpusat di (5: 5) dengan lebar / tinggi (5: 5) membentang dari (2.5: 2.5) hingga (7.5: 7.5). Intinya (4: 4) ada di dalam persegi panjang itu.
sam hocevar
11

Saya menganggap persegi panjang Anda adalah Axis-Aligned.

Anda hanya perlu "menjepit" titik ke dalam persegi panjang dan kemudian menghitung jarak dari titik dijepit.

Point = (px, py), Rectangle = (rx, ry, rwidth, rheight) // (sudut kiri atas, dimensi)

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

Anda harus menggunakan tabrakan lingkaran-persegi panjang untuk ini. Ada pertanyaan serupa tentang Stack Overflow.

Pusat lingkaran Anda akan menjadi titik yang dimaksud, dan jari-jari akan menjadi jarak yang ingin Anda periksa.

Eric B
sumber
3

Jika Anda mencoba mencari tahu jarak dari titik ke tepi persegi panjang, bekerja dengan masing-masing dari sembilan daerah yang dibuat oleh persegi panjang mungkin cara tercepat:

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

[Jawaban yang dimodifikasi berdasarkan komentar]

Jika Anda ingin melihat apakah titik tersebut dalam katakanlah 10 unit jika persegi panjang abu-abu pada gambar di bawah ini, Anda memeriksa apakah titik tersebut di salah satu dari

  1. persegi panjang merah
  2. Kotak biru
  3. salah satu dari lingkaran hijau (radius 10)

masukkan deskripsi gambar di sini

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

Pendekatan ini sedikit tidak berlaku. Metode serupa yang menghindari harus menguji semua 4 sudut dengan menggunakan simetri persegi panjang didokumentasikan di sini di stackoverflow

Ken
sumber
Dalam arah diagonal ini akan memberikan false positive ke titik-titik yang mis. 11 unit jauhnya.
Eric B
Gambar yang diperbarui benar-benar salah, bahkan sebenarnya menggambarkan kasus kesalahan dan membuatnya tampak benar. Titik hijau itu bisa dengan mudah lebih dari 10 unit jauhnya dan berada di dalam persegi panjang luar itu.
Eric B
Hai @ EricB, saya telah memperbaiki kesalahan yang Anda tunjukkan, bagaimana dengan membatalkan downvote Anda?
Ken
Jawaban Anda tidak akan lagi memberikan hasil yang benar-benar salah, jadi saya menghapus downvote, tetapi itu juga bukan cara terbaik sama sekali. Mengapa tidak hanya menguji untuk melihat apakah pusat berada di dalam persegi panjang, dan jika empat segmen garis memotong lingkaran? Konstruksi persegi panjang dan lingkaran baru ini tidak diperlukan. Jawaban Anda juga tidak memberikan jarak aktual dari titik ke persegi panjang.
Eric B
Jawaban ini benar-benar buruk. 12 tambahan, 4 konstruksi objek, 12 tes, 4 akar kuadrat untuk tugas yang sebenarnya membutuhkan 3 baris kode?
sam hocevar
-2

Anda dapat menggunakan sesuatu seperti ini: masukkan deskripsi gambar di sini

AlexanderBrevig
sumber
Metode ini tampaknya tidak perlu rumit. Menemukan x1 dan y1 tidak diperlukan untuk menyelesaikan masalah ini.
Eric B
Bahkan, ini bahkan tidak memenuhi persyaratan menemukan tabrakan dalam jarak tertentu. Itu hanya cara yang buruk untuk mendeteksi jika titik berada dalam persegi panjang.
Eric B
Ukuran jarak sudah secara implisit ada. if (d2 <10 * 10) {/ * dalam 10 unit ukuran * /}
AlexanderBrevig