it-swarm-tr.com

2B içbükey gövdesi oluşturmak için etkili bir algoritma var mı?

Bir CBS dosyasından (bir şehir haritası) bir dizi (2B) noktaya sahipken, o harita için 'sınırını tanımlayan çokgen oluşturmam gerekiyor (bunun sınırı). Giriş parametreleri, ayarlanan noktalar ve bir "maksimum Kenar uzunluğu" olacaktır. Daha sonra karşılık gelen (muhtemelen dışbükey olmayan) poligon çıktı.

Şimdiye kadar bulduğum en iyi çözüm, Delaunay üçgenlerini oluşturmak ve sonra da maksimum Kenar uzunluğundan daha uzun olan dış kenarları çıkarmaktı. Tüm dış kenarlar bundan daha kısa olduktan sonra, sadece iç kenarları söküp istediğim çokgeni alıyorum. Sorun şu ki, bu çok zaman alıyor ve daha iyi bir yol olup olmadığını merak ediyorum.

59
Fabio Ceconello

Bu makale tartışıyor Düzlemdeki bir nokta kümesinin şeklini karakterize etmek için verimli basit poligon üretimi ve algoritmayı sağlar. Aynı algoritmayı kullanan bir Java uygulaması da var here .

2
Amirali

Laboratuvarımızdaki eski öğrencilerden biri doktora tezi için bazı uygulanabilir teknikler kullandı. Bunlardan birinin "alfa şekilleri" olarak adlandırıldığına ve aşağıdaki makalede referans verildiğine inanıyorum:

http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf

Bu makale takip edebileceğiniz bazı referanslar veriyor.

10
nsanders

Cevap başkaları için hala ilginç olabilir: Biri içbükey gövde içinde bir yürüyen kare algoritmasının çeşitliliği, uygulanmış (1) ve (2) sonra (örneğin 3) farklı ) olabilir. ölçekler bu benim noktaların ortalama yoğunluğuna bağlıdır. Ölçeklerin birbirlerinin katı olması gerekir, öyle ki verimli örnekleme için kullanabileceğiniz bir ızgara inşa edersiniz. Bu, boş örnekleri hızlı bir şekilde bulmanızı sağlar = kareler, tamamen noktaların bir "küme/bulut" unda bulunan örnekler ve bunların arasında olanlar. İkinci kategori daha sonra içbükey kabuğunun bir parçasını temsil eden çoklu çizgiyi kolayca belirlemek için kullanılabilir.

Bu yaklaşımda her şey doğrusaldır, üçgenlemeye gerek yoktur, alfa şekilleri kullanmaz ve burada açıklandığı gibi ticari/patentli tekliflerden farklıdır ( http://www.concavehull.com/ )

2
monnoo

Çocuklar burada “en az nokta sayısı üzerinde doğrusal olarak hareket eden” bir takım noktaların içbükey kabuğunu belirlemeye en yakın komşular yaklaşımı geliştirdiklerini iddia ediyor. Ne yazık ki makaleleri çok iyi korunuyor gibi görünüyor ve bunun için onlara sormanız gerekecek.

İşte a iyi bir referanslar dizisi yukarıdakileri içeren ve daha iyi bir yaklaşım bulmanıza yol açabilecek.

2
Vinko Vrsalovic

Bing Maps V8 interaktif SDK'nın gelişmiş şekil işlemleri içinde içbükey bir gövde seçeneği vardır.

https://www.bing.com/mapspreview/sdkrelease/mapcontrol/isdk/advancedshapeoperations?toWww=1&redig=D53FACBB1A00423195C53D841EA0D14E#JS

ArcGIS 10.5.1 içinde, 3D Analyst uzantısı, içbükey gövdesi, küre, zarf veya dışbükey kabuğunun geometrisi ile birlikte Minimum Sınırlama Hacmi aracına sahiptir. Herhangi bir lisans düzeyinde kullanılabilir.

Burada içbükey bir gövde algoritması var: https://github.com/mapbox/concaveman

1
Jaybird64

Çokgen Kenarından yürümek basit bir çözümdür. Geçerli bir Kenar verilmişse, sınır bağlantı noktaları P0 ve P1, P2 sınırındaki bir sonraki nokta, mümkün olan en küçük A işaretine sahip olacaktır

H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength

Sonra sen ayarladın

P0 <- P1
P1 <- P2

ve başladığınız yere geri dönene kadar tekrarlayın.

Bu hala O (N ^ 2) yani nokta listenizi biraz sıralamak isteyeceksiniz. Şehrin merkezinden aldıkları puanları sıralarsanız, her yinelemede dikkate almanız gereken puan kümesini sınırlayabilirsiniz.

1
Mike F

QGIS içinde bu fişle; https://github.com/detlevn/QGIS-ConcaveHull-Plugin

Verilerinizle etkileşimde bulunmak için nasıl ihtiyacınız olduğuna bağlı olarak, muhtemelen burada nasıl yapıldığını kontrol etmeye değer.

1
Cameron

İyi soru! Bunu hiç denemedim, ancak ilk şansım bu yinelemeli yöntem olacaktır:

  1. Bir küme N ("dahil değil") oluşturun ve kümenizdeki tüm noktaları N olarak ekleyin.
  2. İlk çokgen P'yi oluşturmak için rastgele N'den 3 puan toplayın.
  3. Çokgenli bazı nokta algoritmalarını kullanın ve N'deki noktalara bakın. N'deki her nokta için, eğer P içeriyorsa, N'den çıkarın. P'de yer almıyorsa, 4. adıma geçin. N boşalırsa bitirdiniz.
  4. A bulduğunuz noktayı çağırın. A'ya en yakın P çizgisini bulun ve ortasına A ekleyin.
  5. 3. adıma geri dönün

Yeterince iyi performans gösterdiği sürece işe yarayacağını düşünüyorum - ilk 3 puanınız için iyi bir sezgisel yardımcı olabilir.

İyi şanslar!

1
Rob Dickerson

Çılgınca benimsenmiş bir referans olarak, PostGIS bir dışbükey ile başlar ve sonra onu oyur, burada görebilirsiniz.

https://github.com/postgis/postgis/blob/380583da73227ca1a52da0e0b3413b92ae69af9d/postgis/postgis.sql.in#L5819

0
Evan Carroll

Hızlı bir yaklaşık çözüm (dışbükey gövdeler için de yararlıdır) doğu-batıdaki her küçük eleman için kuzey ve güney sınırlarını bulmaktır.

İstediğiniz ne kadar ayrıntıya bağlı olarak, sabit boyutlu bir üst/alt sınır dizisi oluşturun. • Her nokta için hangi E-W sütununda olduğunu hesaplayın ve sonra bu sütun için üst/alt sınırları güncelleyin. Tüm noktaları işledikten sonra, kaçırılan sütunların üst/alt noktalarını enterpolasyon yapabilirsiniz.

Önceden çok uzun ince şekiller için hızlı bir kontrol yapılması ve çöp kutusuna NS veya Ew olup olmadığına karar vermekte fayda var.

0
Martin Beckett