Saya mencoba membuat titik 2D cepat di dalam algoritma poligon, untuk digunakan dalam pengujian-hit (misalnya Polygon.contains(p:Point)
). Saran untuk teknik yang efektif akan dihargai.
performance
graphics
collision-detection
polygon
point-in-polygon
Scott Evernden
sumber
sumber
Jawaban:
Untuk grafis, saya lebih suka tidak memilih bilangan bulat. Banyak sistem menggunakan bilangan bulat untuk lukisan UI (piksel ints setelah semua), tetapi macOS misalnya menggunakan float untuk semuanya. macOS hanya tahu titik dan satu titik dapat menerjemahkan ke satu piksel, tetapi tergantung pada resolusi monitor, itu mungkin diterjemahkan ke sesuatu yang lain. Pada layar retina setengah titik (0,5 / 0,5) adalah piksel. Namun, saya tidak pernah memperhatikan bahwa macOS UI secara signifikan lebih lambat daripada UI lainnya. Lagipula API 3D (OpenGL atau Direct3D) juga berfungsi dengan float dan perpustakaan grafik modern yang sangat sering memanfaatkan akselerasi GPU.
Sekarang Anda mengatakan kecepatan adalah perhatian utama Anda, oke, mari kita pergi untuk kecepatan. Sebelum Anda menjalankan algoritma canggih apa pun, pertama-tama lakukan tes sederhana. Buat kotak bounded aligned axis sekitar poligon Anda. Ini sangat mudah, cepat dan sudah bisa menyelamatkan Anda dari banyak perhitungan. Bagaimana cara kerjanya? Iterasi semua titik poligon dan temukan nilai min / maks X dan Y.
Misalnya Anda punya poin
(9/1), (4/3), (2/7), (8/2), (3/6)
. Ini berarti Xmin adalah 2, Xmax adalah 9, Ymin adalah 1 dan Ymax adalah 7. Suatu titik di luar persegi panjang dengan dua sisi (2/1) dan (9/7) tidak dapat berada dalam poligon.Ini adalah tes pertama yang dijalankan untuk setiap titik. Seperti yang Anda lihat, tes ini sangat cepat tetapi juga sangat kasar. Untuk menangani titik-titik yang berada dalam persegi panjang pembatas, kita membutuhkan algoritma yang lebih canggih. Ada beberapa cara bagaimana ini dapat dihitung. Metode mana yang bekerja juga tergantung pada kenyataan apakah poligon dapat memiliki lubang atau akan selalu padat. Berikut adalah contoh yang solid (satu cembung, satu cekung):
Dan ini satu lubang:
Yang hijau memiliki lubang di tengah!
Algoritma termudah, yang dapat menangani ketiga kasus di atas dan masih cukup cepat bernama ray casting . Gagasan algoritmanya sangat sederhana: Gambarlah sinar virtual dari mana saja di luar poligon ke titik Anda dan hitung seberapa sering ia menyentuh sisi poligon. Jika jumlah hitnya genap, itu di luar poligon, jika aneh, itu di dalam.
The algoritma nomor berliku akan menjadi alternatif, itu lebih akurat untuk titik-titik yang sangat dekat dengan garis poligon tetapi juga jauh lebih lambat. Ray casting mungkin gagal untuk titik yang terlalu dekat dengan sisi poligon karena ketelitian titik mengambang dan masalah pembulatan terbatas, tetapi pada kenyataannya itu hampir tidak menjadi masalah, seolah-olah suatu titik terletak dekat dengan sisi, seringkali secara visual bahkan tidak mungkin untuk suatu penampil untuk mengenali apakah sudah di dalam atau masih di luar.
Anda masih memiliki kotak pembatas di atas, ingat? Cukup pilih satu titik di luar kotak pembatas dan gunakan itu sebagai titik awal untuk ray Anda. Misalnya intinya di
(Xmin - e/p.y)
luar poligon pasti.Tapi apa itu
e
? Nah,e
(sebenarnya epsilon) memberikan kotak berlari beberapa padding . Seperti yang saya katakan, ray tracing gagal jika kita mulai terlalu dekat dengan garis poligon. Karena kotak pembatas mungkin sama dengan poligon (jika poligon adalah persegi panjang yang disejajarkan dengan sumbu, kotak pembatas sama dengan poligon itu sendiri!), Kita perlu beberapa pelapis untuk membuat ini aman, itu saja. Seberapa besar yang harus Anda pilihe
? Tidak terlalu besar. Itu tergantung pada skala sistem koordinat yang Anda gunakan untuk menggambar. Jika lebar langkah piksel Anda adalah 1.0, maka pilih saja 1.0 (belum 0.1 juga akan berfungsi)Sekarang kita memiliki sinar dengan koordinat awal dan akhir, masalahnya bergeser dari " adalah titik dalam poligon " ke " seberapa sering sinar memotong sisi poligon ". Karena itu kita tidak bisa hanya bekerja dengan titik poligon seperti sebelumnya, sekarang kita membutuhkan sisi sebenarnya. Sisi selalu ditentukan oleh dua poin.
Anda perlu menguji sinar terhadap semua sisi. Anggaplah sinar itu sebagai vektor dan setiap sisi adalah vektor. Sinar harus mengenai setiap sisi tepat sekali atau tidak sama sekali. Itu tidak bisa mengenai sisi yang sama dua kali. Dua garis dalam ruang 2D akan selalu berpotongan tepat sekali, kecuali jika paralel, dalam hal ini mereka tidak pernah berpotongan. Namun karena vektor memiliki panjang yang terbatas, dua vektor mungkin tidak sejajar dan masih tidak pernah berpotongan karena mereka terlalu pendek untuk saling bertemu.
Sejauh ini sangat baik, tetapi bagaimana Anda menguji jika dua vektor berpotongan? Berikut adalah beberapa kode C (tidak diuji), yang seharusnya bisa melakukan trik:
Nilai input adalah dua titik akhir dari vektor 1 (
v1x1/v1y1
danv1x2/v1y2
) dan vektor 2 (v2x1/v2y1
danv2x2/v2y2
). Jadi, Anda memiliki 2 vektor, 4 poin, 8 koordinat.YES
danNO
jelas.YES
meningkatkan persimpangan,NO
tidak melakukan apa pun.Bagaimana dengan COLLINEAR? Ini berarti kedua vektor terletak pada garis tak terbatas yang sama, tergantung pada posisi dan panjangnya, mereka tidak berpotongan sama sekali atau berpotongan dalam jumlah titik yang tak berujung. Saya tidak benar-benar yakin bagaimana menangani kasus ini, saya tidak akan menganggapnya sebagai persimpangan. Nah, kasus ini agak jarang dalam praktek karena kesalahan pembulatan titik mengambang; kode yang lebih baik mungkin tidak akan diuji
== 0.0f
tetapi untuk sesuatu seperti< epsilon
, di mana epsilon adalah angka yang agak kecil.Jika Anda perlu menguji jumlah poin yang lebih besar, Anda tentu bisa mempercepat semuanya dengan mempertahankan bentuk standar persamaan linear sisi poligon dalam memori, sehingga Anda tidak perlu menghitung ulang ini setiap waktu. Ini akan menghemat dua perkalian floating point dan tiga pengurangan floating point pada setiap tes dengan imbalan menyimpan tiga nilai floating point per sisi poligon dalam memori. Ini adalah memori yang khas vs waktu penghitungan tradeoff
Last but not least: Jika Anda dapat menggunakan perangkat keras 3D untuk memecahkan masalah, ada alternatif yang menarik. Biarkan GPU melakukan semua pekerjaan untuk Anda. Buat permukaan lukisan yang off screen. Isi sepenuhnya dengan warna hitam. Sekarang biarkan OpenGL atau Direct3D mengecat poligon Anda (atau bahkan semua poligon Anda jika Anda hanya ingin menguji apakah intinya ada di dalamnya, tetapi Anda tidak peduli yang mana) dan isi poligon dengan yang berbeda warna, misalnya putih. Untuk memeriksa apakah suatu titik berada dalam poligon, dapatkan warna titik ini dari permukaan gambar. Ini hanya pengambilan memori O (1).
Tentu saja metode ini hanya dapat digunakan jika permukaan gambar Anda tidak harus besar. Jika tidak dapat masuk ke memori GPU, metode ini lebih lambat daripada melakukannya di CPU. Jika harus besar dan GPU Anda mendukung shader modern, Anda masih dapat menggunakan GPU dengan menerapkan ray casting yang ditunjukkan di atas sebagai shader GPU, yang tentu saja dimungkinkan. Untuk sejumlah besar poligon atau sejumlah besar poin yang akan diuji, ini akan terbayar, pertimbangkan beberapa GPU akan dapat menguji 64 hingga 256 poin secara paralel. Namun perlu dicatat bahwa mentransfer data dari CPU ke GPU dan kembali selalu mahal, jadi untuk hanya menguji beberapa poin terhadap beberapa poligon sederhana, di mana poin atau poligon itu dinamis dan akan sering berubah, pendekatan GPU jarang membayar mati.
sumber
Saya pikir potongan kode berikut adalah solusi terbaik (diambil dari sini ):
Argumen
Keduanya pendek dan efisien dan berfungsi baik untuk poligon cembung dan cekung. Seperti yang disarankan sebelumnya, Anda harus memeriksa persegi panjang pembatas terlebih dahulu dan memperlakukan lubang poligon secara terpisah.
Gagasan di balik ini cukup sederhana. Penulis menggambarkannya sebagai berikut:
Variabel c beralih dari 0 ke 1 dan 1 ke 0 setiap kali sinar horizontal melewati setiap tepi. Jadi pada dasarnya itu melacak apakah jumlah tepi yang dilintasi genap atau ganjil. 0 berarti genap dan 1 berarti ganjil.
sumber
verty[i]
danverty[j]
kedua sisitesty
, sehingga mereka tidak pernah sama.Ini adalah versi C # dari jawaban yang diberikan oleh nirg , yang berasal dari profesor RPI ini . Perhatikan bahwa penggunaan kode dari sumber RPI tersebut membutuhkan atribusi.
Kotak kotak pembatas telah ditambahkan di bagian atas. Namun, seperti yang ditunjukkan oleh James Brown, kode utama hampir secepat kotak pembatas memeriksa sendiri, sehingga kotak pembatas memeriksa sebenarnya dapat memperlambat keseluruhan operasi, dalam kasus bahwa sebagian besar poin yang Anda periksa ada di dalam kotak pembatas . Jadi Anda bisa membiarkan kotak pembatas memeriksa, atau alternatifnya adalah dengan mengkompilasi kotak pembatas poligon Anda jika kotak itu tidak terlalu sering berubah bentuk.
sumber
Berikut adalah varian JavaScript dari jawaban oleh M. Katz berdasarkan pendekatan Nirg:
sumber
Hitung jumlah sudut yang berorientasi antara titik p dan masing-masing apeks poligon. Jika sudut total berorientasi 360 derajat, titik di dalam. Jika totalnya 0, intinya di luar.
Saya suka metode ini lebih baik karena lebih kuat dan kurang tergantung pada ketepatan numerik.
Metode yang menghitung pemerataan jumlah persimpangan terbatas karena Anda dapat 'menekan' puncak selama perhitungan jumlah persimpangan.
EDIT: By The Way, metode ini bekerja dengan poligon cekung dan cembung.
EDIT: Baru-baru ini saya menemukan seluruh artikel Wikipedia tentang topik itu.
sumber
Pertanyaan ini sangat menarik. Saya punya ide lain yang bisa diterapkan berbeda dari jawaban lain untuk posting ini. Idenya adalah menggunakan jumlah sudut untuk memutuskan apakah target di dalam atau di luar. Lebih dikenal dengan nomor berliku .
Biarkan x menjadi titik target. Biarkan array [0, 1, .... n] menjadi semua titik area. Hubungkan titik target dengan setiap titik perbatasan dengan garis. Jika titik target ada di dalam area ini. Jumlah semua sudut akan 360 derajat. Jika tidak, sudutnya akan kurang dari 360.
Lihat gambar ini untuk mendapatkan pemahaman dasar tentang ide:
Algoritme saya menganggap searah jarum jam adalah arah positif. Berikut adalah input potensial:
Berikut ini adalah kode python yang mengimplementasikan ide:
sumber
Artikel Eric Haines dikutip oleh bobobobo sangat bagus. Yang sangat menarik adalah tabel yang membandingkan kinerja algoritma; metode penjumlahan sudut benar-benar buruk dibandingkan dengan yang lain. Yang juga menarik adalah optimisasi seperti menggunakan kotak pencarian untuk membagi poligon menjadi beberapa sektor "dalam" dan "keluar" dapat membuat pengujian sangat cepat bahkan pada poligon dengan sisi> 1000.
Ngomong-ngomong, ini masih hari-hari awal tapi pilihanku pergi ke metode "penyeberangan", yang menurut saya cukup banyak menggambarkan Mecki. Namun saya menemukan itu dijelaskan dan dikodifikasikan oleh David Bourke dengan sangat mudah . Saya suka bahwa tidak ada trigonometri nyata yang diperlukan, dan itu berfungsi untuk cembung dan cekung, dan berkinerja cukup baik karena jumlah sisi meningkat.
Ngomong-ngomong, inilah salah satu tabel kinerja dari artikel Eric Haines untuk minat, pengujian pada poligon acak.
sumber
Versi cepat jawaban oleh nirg :
sumber
Sangat suka solusi yang diposting oleh Nirg dan diedit oleh bobobobo. Saya baru saja membuatnya ramah javascript dan sedikit lebih mudah dibaca untuk saya gunakan:
sumber
Saya melakukan beberapa pekerjaan di belakang ini ketika saya adalah seorang peneliti di bawah Michael Stonebraker - Anda tahu, profesor yang datang dengan Ingres , PostgreSQL , dll.
Kami menyadari bahwa cara tercepat adalah pertama-tama melakukan kotak berlari karena itu SUPER cepat. Jika di luar kotak pembatas, itu di luar. Jika tidak, Anda melakukan pekerjaan yang lebih sulit ...
Jika Anda menginginkan algoritma yang hebat, lihat proyek open source kode sumber PostgreSQL untuk pekerjaan geo ...
Saya ingin menunjukkan, kami tidak pernah mendapatkan wawasan tentang kidal vs kanan (juga dapat diungkapkan sebagai masalah "dalam" vs "di luar" ...
MEMPERBARUI
Tautan BKB menyediakan sejumlah algoritma yang masuk akal. Saya sedang mengerjakan masalah-masalah Ilmu Bumi dan karena itu membutuhkan solusi yang bekerja di lintang / bujur, dan memiliki masalah khusus tentang kidal - apakah area di dalam area yang lebih kecil atau area yang lebih besar? Jawabannya adalah bahwa "arah" dari hal-hal vertikal penting - itu kidal atau tangan kanan dan dengan cara ini Anda dapat menunjukkan salah satu area sebagai "di dalam" setiap poligon yang diberikan. Karena itu, pekerjaan saya menggunakan solusi tiga yang disebutkan pada halaman itu.
Selain itu, pekerjaan saya menggunakan fungsi terpisah untuk pengujian "on the line".
... Karena seseorang bertanya: kami menemukan bahwa tes kotak pembatas adalah yang terbaik ketika jumlah vertikal melampaui beberapa angka - lakukan tes yang sangat cepat sebelum melakukan tes yang lebih lama jika perlu ... Kotak pembatas dibuat dengan hanya mengambil x terbesar, x terkecil, y terbesar dan y terkecil dan menyatukannya untuk membuat empat poin dari sebuah kotak ...
Kiat lain untuk mereka yang mengikuti: kami melakukan semua komputasi yang lebih canggih dan "meredupkan cahaya" dalam ruang grid semuanya dalam titik-titik positif pada pesawat dan kemudian memproyeksikan kembali ke garis bujur / lintang "nyata", sehingga menghindari kemungkinan kesalahan membungkus ketika satu garis silang 180 garis bujur dan ketika menangani wilayah kutub. Bekerja dengan baik!
sumber
Jawaban David Segond adalah cukup banyak jawaban umum standar, dan Richard T adalah optimasi yang paling umum, meskipun ada beberapa yang lain. Optimalisasi kuat lainnya didasarkan pada solusi yang kurang umum. Sebagai contoh jika Anda akan memeriksa poligon yang sama dengan banyak poin, triangulasi poligon dapat mempercepat semuanya karena ada sejumlah algoritma pencarian TIN yang sangat cepat. Lain adalah jika poligon dan titik berada pada bidang terbatas pada resolusi rendah, katakanlah tampilan layar, Anda dapat melukis poligon ke buffer layar dipetakan memori dalam warna yang diberikan, dan memeriksa warna piksel yang diberikan untuk melihat apakah itu terletak dalam poligon.
Seperti banyak optimasi, ini didasarkan pada kasus-kasus spesifik dan bukan umum, dan menghasilkan keuntungan berdasarkan waktu diamortisasi daripada penggunaan tunggal.
Bekerja di bidang ini, saya menemukan Geometri Komputasi Joeseph O'Rourkes dalam C 'ISBN 0-521-44034-3 sangat membantu.
sumber
Solusi sepele adalah dengan membagi poligon menjadi segitiga dan tekan uji segitiga seperti dijelaskan di sini
Jika poligon Anda adalah CONVEX mungkin ada pendekatan yang lebih baik. Lihatlah poligon sebagai kumpulan garis yang tak terbatas. Setiap garis membagi ruang menjadi dua. untuk setiap titik mudah untuk mengatakan apakah itu di satu sisi atau sisi lain dari garis. Jika suatu titik berada di sisi yang sama dari semua garis maka itu berada di dalam poligon.
sumber
Saya menyadari ini sudah tua, tetapi di sini adalah algoritma pengecoran sinar diimplementasikan dalam Kakao, kalau-kalau ada yang tertarik. Tidak yakin itu adalah cara paling efisien untuk melakukan sesuatu, tetapi mungkin membantu seseorang.
sumber
Versi Obj-C dari jawaban nirg dengan metode sampel untuk poin pengujian. Jawaban Nirg bekerja dengan baik untuk saya.
sumber
CGPathContainsPoint()
adalah teman Anda.CGPathContainsPoint()
Tidak ada yang lebih baik daripada definisi induktif dari suatu masalah. Demi kelengkapan di sini Anda memiliki versi dalam prolog yang mungkin juga menjelaskan pemikiran di balik pengecoran sinar :
Berdasarkan simulasi algoritma kesederhanaan di http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
Beberapa predikat pembantu:
Persamaan garis yang diberikan 2 poin A dan B (Garis (A, B)) adalah:
Adalah penting bahwa arah rotasi untuk garis diatur ke clock-wise untuk batas dan anti-clock-wise untuk lubang. Kita akan memeriksa apakah titik (X, Y), yaitu titik yang diuji adalah di setengah bidang kiri dari garis kita (itu adalah masalah selera, itu juga bisa menjadi sisi kanan, tetapi juga arah batas) garis harus diubah dalam hal ini), ini adalah untuk memproyeksikan sinar dari titik ke kanan (atau ke kiri) dan mengakui persimpangan dengan garis. Kami telah memilih untuk memproyeksikan sinar ke arah horizontal (sekali lagi ini masalah selera, bisa juga dilakukan secara vertikal dengan pembatasan serupa), jadi kami memiliki:
Sekarang kita perlu tahu apakah titik di sisi kiri (atau kanan) dari segmen garis saja, bukan seluruh bidang, jadi kita perlu membatasi pencarian hanya untuk segmen ini, tetapi ini mudah karena berada di dalam segmen hanya satu titik dalam garis yang bisa lebih tinggi dari Y pada sumbu vertikal. Karena ini adalah batasan yang lebih kuat, ini perlu menjadi yang pertama untuk memeriksa, jadi kami mengambil hanya garis-garis pertama yang memenuhi persyaratan ini dan kemudian memeriksa kepemilikannya. Dengan teorema Jordan Curve, setiap sinar yang diproyeksikan ke poligon harus berpotongan pada sejumlah garis. Jadi kita sudah selesai, kita akan melempar sinar ke kanan dan kemudian setiap kali memotong garis, beralih ke keadaan. Namun dalam implementasi kami, kami akan memeriksa panjang paket solusi yang memenuhi batasan yang diberikan dan memutuskan hubungan keanggotaan di dalamnya. untuk setiap baris dalam poligon ini harus dilakukan.
sumber
Versi C # jawaban nirg ada di sini: Saya hanya akan membagikan kodenya. Mungkin menghemat waktu seseorang.
sumber
Versi Java:
sumber
.Net port:
sumber
VBA VERSION:
Catatan: Ingat bahwa jika poligon Anda adalah area dalam peta yang Latitude / Longitude adalah nilai Y / X yang bertentangan dengan X / Y (Latitude = Y, Longitude = X) karena dari apa yang saya pahami adalah implikasi historis dari jalan kembali ketika Bujur bukan ukuran.
MODUL KELAS: CPoint
MODUL:
sumber
Aku sudah membuat implementasi Python dari nirg ini c ++ kode :
Input
bounding_box_positions: kandidat poin untuk disaring. (Dalam implementasi saya dibuat dari kotak pembatas.
(Input adalah daftar tupel dalam format:
[(xcord, ycord), ...]
)Kembali
Sekali lagi, ide diambil dari sini
sumber
Tidak ada yang terkejut yang mengemukakan ini sebelumnya, tetapi bagi para pragmatis yang membutuhkan database: MongoDB memiliki dukungan yang sangat baik untuk pertanyaan Geo termasuk yang ini.
Apa yang Anda cari adalah:
Neighborhoods
adalah koleksi yang menyimpan satu atau lebih poligon dalam format GeoJson standar. Jika kueri mengembalikan nol, itu tidak berpotongan sebaliknya.Didokumentasikan dengan sangat baik di sini: https://docs.mongodb.com/manual/tutorial/geospatial-tutorial/
Kinerja lebih dari 6.000 poin yang diklasifikasikan dalam 330 grid poligon beraturan kurang dari satu menit tanpa optimasi sama sekali dan termasuk waktu untuk memperbarui dokumen dengan poligon masing-masing.
sumber
Inilah poin dalam tes poligon dalam C yang tidak menggunakan ray-casting. Dan itu dapat bekerja untuk area yang tumpang tindih (persimpangan diri), lihat
use_holes
argumennya.Catatan: ini adalah salah satu metode yang kurang optimal karena mencakup banyak panggilan
atan2f
, tetapi mungkin menarik bagi pengembang yang membaca utas ini (dalam pengujian saya ~ 23x lebih lambat daripada menggunakan metode persimpangan garis).sumber
Untuk mendeteksi hit pada Polygon kita perlu menguji dua hal:
sumber
Untuk menangani kasus khusus berikut dalam algoritma pengecoran Ray :
Periksa Menentukan Apakah Suatu Titik Di Dalam Poligon Yang Kompleks . Artikel ini menyediakan cara mudah untuk menyelesaikannya sehingga tidak ada perawatan khusus yang diperlukan untuk kasus-kasus di atas.
sumber
Anda dapat melakukan ini dengan memeriksa apakah area yang terbentuk dengan menghubungkan titik yang diinginkan ke simpul poligon Anda cocok dengan area poligon itu sendiri.
Atau Anda dapat memeriksa apakah jumlah sudut dalam dari titik Anda ke setiap pasangan dari dua simpul poligon berurutan ke titik pemeriksaan Anda berjumlah 360, tetapi saya merasa bahwa opsi pertama lebih cepat karena tidak melibatkan pembagian atau perhitungan kebalikan dari fungsi trigonometri.
Saya tidak tahu apa yang terjadi jika poligon Anda memiliki lubang di dalamnya, tetapi menurut saya ide utama dapat disesuaikan dengan situasi ini.
Anda juga dapat memposting pertanyaan di komunitas matematika. Saya yakin mereka memiliki satu juta cara untuk melakukan itu
sumber
Jika Anda mencari perpustakaan java-script ada ekstensi google maps javascript google v3 untuk kelas Polygon untuk mendeteksi apakah suatu titik berada di dalamnya.
Google Extention Github
sumber
Ketika menggunakan qt(Qt 4.3+), salah satu dapat menggunakan QPolygon ini fungsi containsPoint
sumber
Jawabannya tergantung pada apakah Anda memiliki poligon yang sederhana atau kompleks. Poligon sederhana tidak boleh memiliki persimpangan segmen garis. Jadi mereka bisa memiliki lubang tetapi garis tidak bisa saling silang. Daerah kompleks dapat memiliki persimpangan garis - sehingga mereka dapat memiliki daerah yang tumpang tindih, atau daerah yang saling bersinggungan hanya dengan satu titik.
Untuk poligon sederhana, algoritma terbaik adalah algoritma Ray casting (Crossing number). Untuk poligon yang rumit, algoritma ini tidak mendeteksi titik yang ada di dalam wilayah yang tumpang tindih. Jadi untuk poligon kompleks Anda harus menggunakan algoritma bilangan Winding.
Berikut ini adalah artikel yang sangat baik dengan implementasi C dari kedua algoritma. Saya mencobanya dan mereka bekerja dengan baik.
http://geomalgorithms.com/a03-_inclusion.html
sumber
Versi scala solusi oleh nirg (mengasumsikan pre-check rectangle rectangle dilakukan secara terpisah):
sumber
Ini adalah versi golang dari jawaban @nirg (terinspirasi oleh kode C # oleh @@ m-katz)
sumber