Algoritmaları izleyen raster yolu

Question

Aşağıdaki görüntü gibi bir şeye benzeyen raster bir ızgara ızgaram var (beyaz yüksek değerler, siyah arka plan değeri sıfırdır). Ben hatlarının birinin ucundan başlayıp (mümkün olan en yüksek değer üzerinden gidiş, diğer uca iz yolu-aşağıdaki kodla çeşit yazmaya çalışıyorum

yani, daha beyaz olan çizgide daha iyi seçilmiş pikseller) ama yine de diğer tarafa geçiyor.

Bir süredir bununla uğraşıyorum ve çalışmayı denediğim her şeyi elde edemiyorum. Bu yüzden merak ettim, bu tür bir problem için geliştirilmiş olan genel bir algoritma var mı? Çok fazla arama yaptım, ancak çoğu yol algoritması, vektörler/ağlar üzerinde çalışmak için tasarlanmış gibi görünüyor, bunun gibi ızgaraları değil.

Herhangi bir fikrin var mı?

Answer 1

Genetik bir algoritmaya veya saçma bir şeye ihtiyacınız olduğunu sanmıyorum; iyi eski moda özyineleme ve dinamik programlama yeterli olmalıdır. İlk başta düşünürüm, hedefinizi ilk genişlikte bir arama yaparak gerçekleştirebilmeniz gerekir. Başlangıç ​​noktasından, tüm komşuları daha büyük puanlara sahip olacaksınız, daha sonra o hücreler sonsuza dek başlar - ve tüm hücreler sonsuza dek başlar ve kara hücrelerin maliyeti sonsuza dek olur, ve bunlar bunları kurtarabileceğiniz yollardır). Hedefinize ulaştığınızda, eğer ulaşılabilirse, yolu bulmak için geri dönebilmelisiniz. Bu açgözlü, ama yolların iyi gibi davrandığında, iyi olmalı.

Daha fazla gri ve kıvrımlı ve dönüşlü yollar için, raster görüntüsünü bir grafiğe dönüştürmek iyi bir fikir olabilir; kenar ağırlığı komşuların gri skala değerleridir (veya gri skala değerlerindeki fark, Bu verilerin gerçekte ne anlama geldiğine bağlı olarak). Yani, bu yoruma dayanarak en kısa yollar için herhangi bir algoritma kullanabilmeniz gerekir.

Answer 2

Muhtemelen en basit fikir, her bir pikselin bir düğüm olduğu ve düğümün maliyetinin piksel karanlık olduğu A* algorithm'u kullanmaktır.

Güncelleme: Çok güzel bir tutorial bulundu. Bunu yapmak için

Answer 3

Tek yönlü:

1. Filtre görüntü daha yakın siyah-beyaz tek piksellere almak için.
2. Beyaz piksellerden bir çizgi çizin. Bunu yapmak için beyaz bir pikselle başlayın. Bu pikselden bir beyaz piksele 2 (veya 3 veya daha fazla) uzaklıkta bir mesafe çizin, ancak bir önceki çizginin yanındaki pikselleri yok sayın. Her piksel kapanmadan (2 veya 3 piksel) bir satırdan devam etmeden devam edin. İyi çalışması için bazı küçük ayarlamalar yapmanız gerekecek.
3. Çizdiğiniz satırların uç noktalarını bağlayın. İki uç nokta (1 veya 2 piksel?) Yakınındaysa, bunları bağlayın. Çok sayıda kısa parçadan oluşan birkaç çizgi ile, muhtemelen bazı döngüler ve çatallarla bitmelidir.
4. Çizgilerdeki küçük halkalardan kurtulun ve çizgileri çatallardan ayırın, böylece çok sayıda kısa parçadan oluşan birkaç satırınız olur.
5. Noktaları azaltın. Her satır için, neredeyse düz olup olmadığını kontrol edin. Eğer öyleyse, tüm iç noktaları kaldırın. Değilse, minimum segment uzunluklarına inene kadar, çizginin iki yarısını yinelemeli olarak kontrol edin.
6. İsteğe bağlı olarak bir eğri eğrisini bu noktadaki çizgilerden geçirebilirsiniz.
7. Kar.

İyi çalışması için biraz ince ayar yapacaktır, ancak bunu bu şekilde yapmak mümkündür. Diğer bir değişken ise, 1 veya 2 veya 3 pikselden daha geniş olan ve daha sonra çift çizgileri birleştiren beyaz bölümleri çizmektir.

Answer 4

Eğer büyük ölçekte yapıyoruz veya araştırma için size http://en.wikipedia.org/wiki/Ant_colony_optimization katiyen çalışıyorum ama bunu para için yaptığını eğer sadece sel gibi bir şey bu vardır klasik maliyet mesafeli sorunudur http://en.wikipedia.org/wiki/Flood_fill