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

Question

İ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?

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!

Answer 1

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