Bagaimana untuk mengetahui sama ada titik berada di dalam poligon menggunakan JavaScript

Dalam pembangunan bahagian hadapan, kita sering menghadapi situasi di mana kita perlu menentukan sama ada titik berada dalam poligon. Sebagai contoh, apabila kami menambah acara klik pada peta, kami perlu menentukan sama ada titik yang diklik oleh pengguna berada dalam kawasan tertentu untuk menentukan operasi yang sepadan. Artikel ini akan memperkenalkan cara menggunakan JavaScript untuk menentukan sama ada titik berada dalam poligon.

1. Algoritma Poligon

Terdapat banyak algoritma untuk menentukan sama ada sesuatu titik berada dalam poligon, antaranya kaedah sinar dan kaedah hasil titik lebih biasa digunakan. Artikel ini akan memperkenalkan kaedah produk titik sebagai contoh.

Idea teras kaedah hasil titik ialah menggunakan sifat vektor untuk menganggap titik P pada setiap bucu poligon sebagai vektor, dan kemudian mengira sama ada titik P berada di dalam poligon melalui hasil darab titik antara vektor. Secara khusus, sama ada titik P berada di dalam poligon bergantung pada tanda hasil tambah titik P dan vektor sisi poligon.

2. Formula pengiraan produk dot

Formula pengiraan produk titik adalah seperti berikut:

a · b = ax bx + ay oleh

Di mana a(x, y) dan b(x, y) ialah dua vektor, a · b mewakili hasil darab titiknya. Hasil darab titik ialah skalar yang mewakili kosinus sudut antara dua vektor.

Perlu diperhatikan bahawa jika hasil darab titik lebih besar daripada 0, ia bermakna sudut vektor kurang daripada 90 darjah; jika hasil darab titik kurang daripada 0, ia bermakna sudut vektor adalah lebih besar daripada 90 darjah; jika hasil produk titik adalah sama dengan 0, Ini bermakna vektor adalah menegak, iaitu, 90 darjah.

3 Tentukan sama ada titik berada dalam poligon

Seterusnya, kami akan memperkenalkan cara menggunakan kaedah hasil titik untuk menentukan sama ada titik P berada dalam poligon.

1. Membina vektor

Pertimbangkan titik P pada setiap bucu poligon sebagai vektor Anda boleh membina vektor dengan mengira beza koordinat vektor. Secara khusus, jika koordinat titik P ialah (xp, yp) dan koordinat bucu ke-i poligon ialah (xi, yi), maka koordinat vektor P->i ialah (vx, vy), dan formula pengiraannya ialah:

vx = xi - xp;
vy = yi - yp; dan kita juga boleh mendapatkan titik P Vektor kepada bucu poligon.

Kira hasil darab titik

2. Seterusnya, kita perlu mengira hasil tambah titik titik P dan vektor sisi poligon. Jika hasil tambah titik adalah positif, maka titik P berada di luar poligon; jika hasil tambah titik adalah negatif, maka titik P berada di dalam poligon.

Perlu diambil perhatian bahawa vektor dalam formula produk titik perlu dinormalisasi terlebih dahulu, iaitu panjang vektor berskala kepada 1. Ini memastikan hasil darab titik hanya berkaitan dengan sudut antara vektor dan tidak dipengaruhi oleh panjang vektor.

Kod untuk mengira hasil titik adalah seperti berikut:

fungsi ialahPointInsidePolygon(titik, poligon) {

sudut var = 0,

var n = polygon.length ;

i,
vertex1,
vertex2;

untuk (i = 0; i < n; i++) {

}

vertex1 = polygon[i];
vertex2 = polygon[(i + 1) % n];

angle += polarAngle(
  point[0],
  point[1],
  vertex1[0],
  vertex1[1],
  vertex2[0],
  vertex2[1]
);

kembali Math.abs(sudut) >= Math.PI ;

}

fungsi polarAngle(x, y, x1, y1, x2, y2) {

var angle1 = Math.atan2(y - y1, x - x1);

var angle2 = Math.atan2(y - y2, x - x2);

var diff = angle2 - angle1;

manakala (diff > Math.PI) {

}

diff -= 2 * Math.PI;

manakala (beza < -Math.PI) {

}

diff += 2 * Math.PI;

return diff;

}

Antaranya, fungsi isPointInsidePolygon digunakan Untuk menentukan sama ada titik berada di dalam poligon, fungsi polarAngle digunakan untuk mengira hasil darab titik.

4. Ringkasan

Artikel ini memperkenalkan cara menggunakan Javascript untuk menentukan sama ada titik berada di dalam poligon. Perlu diingat bahawa kaedah produk titik hanya boleh digunakan untuk poligon cembung Untuk poligon cekung, algoritma lain perlu digunakan untuk pertimbangan. Dalam aplikasi praktikal, beberapa situasi khas perlu dipertimbangkan, seperti poligon dengan tepi bertindih atau bucu, bucu pada tepi poligon, dsb., yang memerlukan pertimbangan dan pemprosesan tambahan.

Atas ialah kandungan terperinci Bagaimana untuk mengetahui sama ada titik berada di dalam poligon menggunakan JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!