Jarak antipodal (atau pengambilan poligon atau diameter poligon) untuk poligon cekung

8

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

Contoh Jarak Antipodal Interior

Dalam contoh cembung, titik pertama tidak memiliki vektor antipodal, namun, titik kedua tidak.

Contoh Antipodal Cekung

EDIT Saya telah mendapatkan beberapa pencarian sukses menggunakan "poligon mengambil" atau "diameter poligon" di web, saya menduga bahwa inilah yang saya cari.

PolyGeo
sumber
1
Hai, Dan. Apa definisi "jarak antipodal" yang Anda gunakan? Satu kemungkinan akan menjadi titik terjauh yang diukur dengan melakukan perjalanan di sepanjang batas poligon, tetapi itu tampaknya tidak konsisten dengan deskripsi Anda. Definisi lain adalah titik terjauh di mana perjalanan dapat terjadi di mana saja di dalam atau di luar poligon. Namun yang ketiga adalah titik terjauh di mana perjalanan hanya diperbolehkan di dalam interior dan batas poligon.
Whuber
1
@whuber, saya sedang mencari solusi yang hanya bepergian dalam poligon tidak termasuk segmen garis yang membentuk batas poligon. Dalam contoh cembung yang saya berikan, perpindahan dari titik p0 ke p1, atau p0 ke p5 tidak akan diizinkan karena mereka adalah bagian dari ujung poligon, namun, p0 ke p2, p3, p4 adalah. Karena itu, kekhawatiran saya bahwa "antipodal" mungkin bukan istilah yang tepat. Catatan, saya hanya tertarik pada poligon cembung satu bagian tanpa lubang saat ini. Jika saya terjebak dengan segmen tepi dalam solusi, saya selalu dapat menghapusnya nanti.
1
Ada masalah rumit di sini, Dan: meskipun segmen seperti itu mungkin dikesampingkan, namun mereka memberi tahu Anda apa yang paling tidak masuk akal dari semua jarak yang mungkin terjadi (mereka hanya mencegah infimum itu dari benar-benar direalisasikan). Solusi praktis akan tetap berada di dalam segmen tersebut tetapi tetap sangat dekat dengan mereka. Jadi, untuk poligon cembung algoritmanya sederhana: cari titik paling jauh dari titik awal (bisa ada banyak dari mereka: bayangkan setengah lingkaran dan mulai di tengah lingkaran asli).
Whuber
1
Saya masih tidak mengerti definisi Anda, Dan, karena tidak ada "jalur terpanjang" di dalam poligon apa pun: Anda dapat memutar-mutar untuk membuat jalur panjang yang sewenang-wenang. Mungkin yang Anda maksudkan adalah sebagai berikut: tentukan jarak antara titik P dan Q dalam poligon (terhubung) menjadi infimum dari panjang semua jalur dari P ke Q yang terletak sepenuhnya di dalam poligon. Maka "antipode" yang masuk akal untuk poligon terkoneksi kompak P akan menjadi titik Q pada jarak maksimum dari P. (Ketika P adalah simpul dari poligon cembung, antipodenya sekali lagi adalah simpul pada jarak Euclidean maksimum dari P.)
whuber
2
Titik terjauh dicirikan dengan keras menggunakan definisi "masuk akal" dalam komentar saya sebelumnya. Perhatikan bahwa dalam menemukannya Anda diizinkan mengasumsikan bahwa Anda dapat melakukan perjalanan di sepanjang tepi. Dalam gambar kedua Anda, E antipodal ke A dan B; A bersifat antipodal terhadap C, D, dan E; dan D dan A keduanya antipodal ke F. Menggunakan analogi kano, di mana bagian dalam poligon adalah danau, titik P antipodal ke titik awal Anda Q ketika dalam perlombaan kano dari Q melawan lawan yang bertujuan mencapai P sebelum Anda mencapai titik P ', mereka tidak memiliki keuntungan atas Anda di mana pun P'.
whuber

Jawaban:

4

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:

  1. Identifikasi semua simpul, simpan dalam daftar
  2. Identifikasi semua tepi, simpan dalam daftar (sebagai pasangan simpul dari 1, mungkin)
  3. untuk setiap simpul, dapatkan jarak ke semua simpul lainnya, kecuali:
    1. mengecualikan simpul tetangga (mereka yang berbagi pasangan dengan simpul ini dalam 2, mungkin)
    2. kecualikan setiap baris yang memotong 2. baris apa pun dengan menggunakan sesuatu dari sini .
  4. menyimpan semua jarak valide dengan mengacu pada simpul dalam 1.

  5. 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:

E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy ) 
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )

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 masukkan deskripsi gambar di sini

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

Alex Leith
sumber
Kode di blog saya melakukan semuanya kecuali 3.2 dan merujuk hasilnya kembali ke program panggilan untuk perhitungan lebih lanjut yang bekerja dengan baik untuk poligon cembung. Saya ingin beberapa referensi jika mungkin dan apakah nomor belitan akan efisien untuk menentukan persimpangan jalur atau saya harus pergi ke beberapa rute lain.
2
Saya menambahkan contoh perhitungan persimpangan dari artikel yang saya tautkan. Saya pikir saya tidak akan khawatir tentang efisiensi sampai masalah! Dapatkan sesuatu yang berfungsi, kemudian perbaiki jika itu tidak cukup baik!
Alex Leith
Terima kasih Alex, saya akan memeriksanya ... efisiensi bukan masalah karena ini hanya contoh untuk tidak dijalankan pada ribuan poligon
Meskipun sulit untuk mengatakan apa yang dijelaskan oleh jawaban ini, sepertinya ini adalah pemeriksaan apakah poligon itu cembung. Sangat membingungkan karena tampaknya menggunakan "baris" sebagai pengganti "segmen baris." Kode yang diberikan tampaknya bukan pemeriksaan yang valid untuk persimpangan segmen
whuber
Halo, ini memeriksa segmen garis. Contoh kedua yang saya tambahkan mungkin membuatnya lebih jelas, karena matematika menghitung titik intersectino untuk garis tak terbatas dan Anda kemudian perlu memeriksa apakah titik persimpangan itu berada di dalam kotak pembatas salah satu garis. Seperti semua matematika vektor, pasti ada perpustakaan yang melakukan ini, tetapi tidak begitu rumit, dan saya pikir perlu untuk apa yang ingin dilakukan OP.
Alex Leith
3

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.

  1. Buat daftar PolygonCandidates
  2. Untuk setiap titik (titik k)
    1. Buat daftar baru untuk kandidat (Point, Angle)
    2. Tambahkan simpul saat ini ke daftar kandidat (titik k)
    3. Iterasi searah jarum jam di sekitar poligon, untuk setiap simpul yang tersisa (titik i)
      1. Jika sudut ke titik saat ini (dari titik k ke titik i) berlanjut searah jarum jam 1. tambahkan titik
      2. Jika sudut ke titik saat ini berlanjut dalam arah berlawanan arah jarum jam
      3. Jika dua kandidat poin sebelumnya, ditambah poin saat ini membentuk giliran kanan.
      4. Hapus titik terakhir dalam daftar sampai sudut saat ini dan sudut daftar kandidat terakhir dalam arah berlawanan arah.
      5. Tambahkan titik saat ini ke daftar kandidat
    4. Tambahkan semua kecuali dua yang pertama, dan kandidat poin terakhir ke daftar PolygonCandidates
  3. Temukan titik terjauh dalam daftar PolygonCandidates.

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.

import math
from collections import namedtuple


Point = namedtuple("Point", "position x y")
Vector = namedtuple("Vector", "source dest angle")

def isClockwise(angle1, angle2):
    diff = angle2 - angle1
    #print("         angle1:%s angle2:%s diff: %s" % (angle1, angle2, diff))
    if(diff > math.pi/2):
        diff = diff - math.pi/2
    elif (diff < -math.pi/2):
        diff = diff + math.pi/2
    #print("         diff:%s" % (diff)) 
    if(diff > 0):
        return False
    return True

def getAngle(origin, point):
    return math.atan2(point.y - origin.y, point.x-origin.x)

#returns a list of candidate vertcies.  This will include the first, second, and second to last points 
#the first and last points in the polygon must be the same
#k is the starting position, only vertices after this position will be evaluated
def getCandidates (k, polygon):

    origin = polygon[k]
    candidates = [Vector(k,k,0)]
    prevAngle = 0;
    currentAngle = 0;
    for i in range(k + 1, len(polygon) - 1):

        current = polygon[i]
        #print("vertex i:%s x:%s y:%s  " % (i, current.x, current.y))

        if(i == k+1):
            prevAngle = getAngle(origin, current)
            candidates.append(Vector(k,i,prevAngle))
        else:   
            currentAngle = getAngle(origin, current)
            #print("     prevAngle:%s currentAngle:%s  " % (prevAngle, currentAngle))
            if isClockwise(prevAngle, currentAngle):
                #print("     append")
                candidates.append(Vector(k,i,currentAngle))
                prevAngle = currentAngle
            else:
                #look at the angle between current, candidate-1 and candidate-2
                if(i >= 2):
                    lastCandinate = polygon[candidates[len(candidates) - 1].dest]
                    secondLastCandidate = polygon[candidates[len(candidates) - 2].dest]
                    isleft = ((lastCandinate.x - secondLastCandidate.x)*(current.y - secondLastCandidate.y) - (lastCandinate.y - secondLastCandidate.y)*(current.x - secondLastCandidate.x)) > 0
                    #print("     test for what side of polygon %s" % (isleft))
                    if(i-k >= 2 and not isleft):
                        while isClockwise(currentAngle, candidates[len(candidates) - 1].angle):
                            #print("     remove %s" % (len(candidates) - 1))
                            candidates.pop()
                        #print("     append (after remove)")
                        candidates.append(Vector(k,i,currentAngle))
                        prevAngle = currentAngle

        #for i in range(len(candidates)):
        #   print("candidate i:%s x:%s y:%s a:%s " % (candidates[i][0], candidates[i][1], candidates[i][2], candidates[i][3]))

    return candidates

def calcDistance(point1, point2):
    return math.sqrt(math.pow(point2.x - point1.x, 2) + math.pow(point2.y - point1.y, 2))

def findMaxDistance(polygon, candidates):
    #ignore the first 2 and last result
    maxDistance = 0
    maxVector = Vector(0,0,0);
    for i in range(len(candidates)):
        currentDistance = calcDistance(polygon[candidates[i].source], polygon[candidates[i].dest])
        if(currentDistance > maxDistance):
            maxDistance = currentDistance
            maxVector = candidates[i];
    if(maxDistance > 0):
        print ("The Antipodal distance is %s from %s to %s" % (maxDistance, polygon[candidates[i].source], polygon[candidates[i].dest]))
    else:
        print ("There is no Antipodal distance")

def getAntipodalDist(polygon):
    polygonCandidates = []
    for j in range(0, len(polygon) - 1):
        candidates = getCandidates(j, polygon)
        for i in range(2, len(candidates) - 1):
            #print("candidate i:%s->%s x:%s y:%s  " % (candidates[i].source, candidates[i].dest, candidates[i].x, candidates[i].y))
            polygonCandidates.append(candidates[i])

    for i in range(len(polygonCandidates)):
        print("candidate i:%s->%s" % (polygonCandidates[i].source, polygonCandidates[i].dest))
    findMaxDistance(polygon, polygonCandidates)


getAntipodalDist([Point(0,0,0),Point(1,-2,0),Point(2,-2,3),Point(3,2,2),Point(4,-1,1),Point(5,4,0),Point(6,0,0)])
getAntipodalDist([Point(0,0,0),Point(1,2,1),Point(2,1,4),Point(3,3,5),Point(4,5,4),Point(5,4,1),Point(6,0,0)])
getAntipodalDist([Point(0,0,0),Point(1,1,1),Point(2,2,1),Point(3,1,4),Point(4,3,5),Point(5,5,4),Point(6,4,1),Point(7,0,0)])
getAntipodalDist([Point(0,0,0),Point(1,-1,3),Point(2,1,4),Point(3,3,3),Point(4,2,0),Point(5,-2,-1),Point(6,0,0)])
travis
sumber
Apakah algoritma ini benar-benar berfungsi? Bisakah Anda menggambarkannya dengan contoh sederhana, seperti segi enam ((0,0), (- 2,0), (- 2,3), (2,2), (- 1,1), (4 , 0), (0,0))? Apa yang terjadi ketika Anda memulai pada (0,0)? Dan apa yang dimaksudkan oleh algoritma ini? Misalnya, ia tidak menemukan segmen garis terpanjang dalam poligon (dengan panjang 1,2 * sqrt (26)).
whuber
Terima kasih atas komentarnya, Travis, ini tidak akan berfungsi dalam semua kasus (lihat contoh cekung lambung), dari isRightTurn (A, B, C) akan salah, dan AC tidak akan menjadi segmen kandidat. Jika B lebih jauh ke utara, bisa dibayangkan semua untuk segmen AE, jadi saya tidak ingin mengesampingkan poin A sepenuhnya sampai semua poin lainnya diperiksa.
@whuber, mengingat geometri itu, saya tidak melihat bagaimana segmen garis terpanjang adalah 1,2 * sqrt (26). Kecuali saya benar-benar merindukan pertanyaan ini. Bukankah itu sqrt (2), dari (0,0) -> (- 1,1) atau (-2,0) -> (- 1,1).
Travis
1
@ DanPatterson, saya mungkin telah melewatkan apa yang Anda minta. Pemahaman saya adalah: apa jarak terbesar antara titik tertentu dan titik lainnya, yang tidak memotong batas poligon. Saya memperbarui skrip saya untuk menemukan jarak maksimum poligon.
Travis
Poligon cembung tampaknya tidak menjadi masalah mengingat contoh sederhana yang dapat ditemukan di web dan dalam teks. Diameter poligon untuk lambung cekung tampaknya memiliki beberapa interpretasi dan pengambilan poligon, sekarang saya mulai menyadari ketel ikan lain. Dalam hal apa pun, tanpa memotong apa pun, adalah apa yang saya cari. Kekhawatiran saya adalah kurangnya definisi dan contoh yang jelas dengan contoh dunia nyata. Saya dapat membahas yang cembung, tetapi yang cekung terbukti bermasalah dan melampaui keahlian matematika / komputasi saya karena didukung / disorot oleh beberapa saran Bill.
1

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

AnserGIS
sumber
Kode saya di blog saya lebih efektif daripada, itu terminologi yang saya perlu klarifikasi serta apa yang harus dilakukan dalam kasus lambung cekung.
Triangulasi secara inheren akan menangani lambung cekung (sebanyak itu tidak akan membuat tepi segitiga yang melewati batas poligon)
AnserGIS