Saya sedang mengerjakan beberapa contoh kelas dengan Python diimplementasikan dalam ArcMap untuk menghitung jarak antipodal dalam poligon. Ini cukup rutin untuk poligon cembung, namun untuk poligon cekung, saya ingin mengecualikan solusi (dibentuk oleh sinar yang menghubungkan titik batas), yang tidak sepenuhnya berada dalam poligon dan tidak pada batas poligon atau memotongnya. Apakah saya telah menafsirkan definisi yang salah atau apakah binatang ini pergi dengan nama lain.
Pertimbangkan dua poligon ini
pnts = [[0,0], [0,1], [1,4], [3,5], [5,4], [4,1], [0,0]] # loop tertutup cembung
pnts = [[0,0], [2,1], [1,4], [3,5], [5,4], [4,1], [0,0]] # loop tertutup poligon cekung
Dalam interpretasi saya, titik 0,0 seharusnya tidak memiliki jarak antipodal yang terkait dengannya karena vektor yang menghubungkannya dengan titik-titik lain adalah baik berpotongan poligon atau berada pada batas poligon.
Jika ada yang punya klarifikasi tentang definisi atau solusi potensial, saya akan sangat menghargainya.
Visual dari poligon cembung dan garis yang diinginkan (ditunjukkan dengan warna merah) tertutup (contoh vektor dari titik 0 hanya ditampilkan).
Dalam contoh cembung, titik pertama tidak memiliki vektor antipodal, namun, titik kedua tidak.
EDIT Saya telah mendapatkan beberapa pencarian sukses menggunakan "poligon mengambil" atau "diameter poligon" di web, saya menduga bahwa inilah yang saya cari.
sumber
Jawaban:
Jika saya menulis sebuah algoritma saya hanya akan memeriksa apakah garis antara dua simpul pada poligon memotong garis yang membentuk salah satu ujungnya. Ini kode semu saya:
menyimpan semua jarak valide dengan mengacu pada simpul dalam 1.
lakukan apa yang Anda inginkan dengan hasilnya, tulis baris baru, simpan yang terpanjang untuk setiap poligon ...
Sekarang, saya tidak yakin apakah ini yang Anda cari, tetapi Anda tentu bisa melakukan hal di atas di ArcPy.
EDIT: Kode untuk langkah 2.2:
Jika h adalah antara 0 dan 1, garis-garis berpotongan, jika tidak maka h. Jika F * P adalah nol, tentu saja Anda tidak dapat membuat perhitungan, tetapi dalam kasus ini garisnya paralel dan oleh karena itu hanya berpotongan dalam kasus yang jelas. Jika h adalah 1, maka garis berakhir pada titik yang sama. Tangani ini sesuka Anda! (Saya akan mengatakan mereka berpotongan, itu membuat saya lebih mudah.)
Contoh lain untuk langkah 2.2 dari sini: http://en.wikipedia.org/wiki/Line-line_intersection
Pertama periksa penyebut tidak sama dengan 0, yang berarti bahwa garis-garisnya paralel.
Kemudian periksa bahwa koordinat yang ditemukan di atas tidak di luar kotak pembatas dari kedua baris.
Lebih banyak bacaan: http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf
sumber
Saya akan tergoda untuk melakukan ini menggunakan malaikat, hampir seperti saling berhadapan. Jika saat iterasi simpul dalam bentuk sudut antara titik asal dan titik tujuan terus dalam arah yang konsisten, semua poin adalah kandidat untuk antipodal. Jika suatu sudut berganti arah, maka titik itu disembunyikan oleh atau menyembunyikan titik sebelumnya. Jika disembunyikan oleh titik sebelumnya, titik harus dilewati. Jika menyembunyikan poin sebelumnya, poin sebelumnya harus dihapus dari daftar kandidat.
Saya tidak yakin apa yang harus dilakukan dengan kasus-kasus di mana asalnya, dan dua simpul lainnya semuanya berada di garis yang sama. Dalam hal ini, sudutnya akan sama. Jika Anda memiliki poligon berlubang, Anda bisa menemukan sudut min / maks dari setiap lubang, dan menghilangkan titik kandidat yang ada di dalam rentang itu.
Keuntungan utama dari pendekatan ini adalah Anda tidak perlu menguji untuk perpotongan garis antara segmen garis saat ini dan semua tepi poligon.
Ini berfungsi ... saya pikir. Saya telah memperbarui kode semu di atas dan python untuk membuatnya lebih mudah dibaca.
Ini harus menjadi suntingan terakhir. Contoh di bawah ini harus menemukan anitpole terbesar untuk geometri yang diberikan. Saya mengubah skrip sehingga menggunakan Poin dan Vektor, untuk mencoba dan membuatnya lebih mudah dibaca.
sumber
Mungkin mempertimbangkan triangulasi dataset. Garis mana yang umum untuk tepi poligon akan mudah dibuat dan yang tersisa dapat dibandingkan untuk menemukan yang terpanjang? Pertanyaannya kemudian adalah algoritma triangulasi apa yang Anda butuhkan.
Ini hanya dugaan tetapi saya menduga (ironisnya) triangulasi "kualitas terendah" yang dapat dibuat harus berisi garis yang Anda cari misalnya Gambar 1 di https://www.google.co.id/url?sa=t&rct= j & q = & esrc = s & sumber = web & cd = 6 & ved = 0CEoQFjAF & url = http% 3A% 2F% 2Fhrcak.srce.hr% 2Ffile% 2F69457 & ei = alIcUsb6HsLnswbfnYHoDwGjHjHjHjHm
sumber