Algoritma, birçok bölüm arasında bir noktaya en yakın kesimi bulmak için (Ters Coğrafi Kodlama)

İki nokta tarafından tanımlanan bir dizi segmentim var. Bir nokta göz önüne alındığında, bu noktaya en yakın segmenti nasıl keşfedebilirim?Algoritma, birçok bölüm arasında bir noktaya en yakın kesimi bulmak için (Ters Coğrafi Kodlama)

Bir nokta ile segment arasındaki mesafeyi hesaplayan bir algoritma yazmıştım. Her segment için böyle bir mesafe hesaplamak ve sonra en düşük mesafeye sahip segmenti seçmek gerçekten verimli değil :(

Segmentler sokakları temsil ettiğinden, bu aslında bir Ters GeoCoding problemi olduğundan, bunun iyi bilinen çözümleri olduğunu umuyorum sorun ...

Çok teşekkür ederim!

kaynak

2010-08-06 Giorgio

Parça kümesi herhangi bir şekilde sıralanmış mı? –

Segmentler çakışıyor mu? Bir satırdaki segmentleri mi yoksa ör. spherig segmentleri? İkincisi, iki noktanız segmenti nasıl tanımlar? (Farklı tanımlar mümkündür) ---- Neyse, segmentleri bazı kriterlere göre sıralamak genellikle yardımcı olur. – peterchen

@Giorgio: Algoritmayı buldunuz mu? Bu algoritma ile bağlantı kurabilir veya bağlantı kurabilir misiniz? Şimdiden teşekkür ederim! –

bir ızgara, kd-ağaç, dörtlü ağaç veya benzeri ikili uzay bölümleme yöntemi kullanın. Ardından, nokta yatıyor ağaç hücreden başlayarak kadar segmentleri keşfetmeye başlamak Parçayı içeren noktadan noktaya kadar olan mesafe, şimdiye kadar bulunan en küçük mesafeden daha büyüktür

http://en.wikipedia.org/wiki/Binary_space_partitioning

(Bu segmentleri/sokaklar çok nadiren sadece değiştirmek varsayarak, tabii ki, ama puan çok bulmak gerekir).

kaynak

2010-08-06 12:57:03

Verilen herhangi bir bölümün herhangi bir bölümle (en az) eşit derecede pahalı (nokta segmenti mesafesine kıyasla) hesaplama yapmadan kesişip bölmediğini bilmenin bir yolu yoktur, bu nedenle herhangi bir bölümleme yaklaşımı yalnızca segment segmenti için daha hızlı olabilir belirli koşulları karşılar (maksimum bölüm uzunluğu << bölüm boyutları gibi). – MusiGenesis

@MusiGenesis: Anahtar, ağaç oluşturulduğunda kesiştiği tüm yaprakların her parçasını oluşturmaktır. Bu şekilde, yapraklardan biri noktalara yeterince yakınsa, segment test edilecek ve eğer yapraklardan hiçbiri yeterince yakın değilse, segment hiçbir zaman test edilmeyecektir. Ağaç sadece bir kez inşa edildiği için, bunu yapmanın maliyeti daha sonra gerçekleşen tüm isteklere bölünür. –

kabul etti. Her seferinde farklı bir bölüm kümesi olduğunu varsayıyordum. – MusiGenesis

Algoritma, birçok bölüm arasında bir noktaya en yakın kesimi bulmak için (Ters Coğrafi Kodlama)

cevap

İlgili konular