2015-01-01 24 views
6

Yolun basitleştirilmesi ve 2B yörüngelerin düzeltilmesi için bir algoritma araştırıyorum. Bu yüzden 2B noktaların sıralı bir listesini aldım. Bu noktalar basitleştirilmelidir, ör. Ramer-Douglas – Peucker algoritması ile. Ancak çıktı düzgün olmalı, sonuç olarak yolun Bezier eğrilerinden veya splinelardan yapılmalıdır. Bunun üstesinden gelebilecek Ramer – Douglas – Peucker algoritmasının herhangi bir modifikasyonu var mı?Yolun basitleştirilmesi ve 2 boyutlu yörüngelerin düzeltilmesi için algoritma

Tam olarak aradığım şeyi yapan paper.js kitaplığında bir yol sadeleştirme algoritması buldum: http://paperjs.org/examples/path-simplification/ Ama belgesiz javascript kaynak kodundan algoritmayı anlayamadım. Bir eğri uydurma algoritması bezier uyacak - büyük olasılıkla sonra Curve Fitting.

Ramer-Douglas-Peucker algoritması esasen gereksiz noktaları kaldırarak çoklu çizgi dışına 'gürültü' düzgünleştirir iken denir Ne

cevap

10

eser size kullanıldı yaklaşık neyi (görünüşte Ramer-Douglas-Peucker kullanıldı ama daha sonra kaldırılmış) neyi posta listesinde çok kısa tartışma yapmak istediğiniz "eğri uydurma" kategorisine girer. Eğri uydurma için tonlarca farklı algoritma vardır, ancak hemen hemen tüm eğri uydurma algoritmaları iki farklı kategoriye ayrılabilir: interpolasyon ve yaklaşım. İnterpolasyon algoritmaları, tüm veri noktalarından tam olarak geçen bir eğri oluşturur, yaklaşma algoritmaları ise veri noktalarına yakın bir eğri oluşturur. Elbette hibrit algoritmalar da var.

Veri noktalarının düzeltilmesini istediğinizde, yaklaşım algoritmalarını aramalısınız. Bahsettiğiniz iki algoritma için: RDP algoritması ve Schneider algoritması (Paper.js'deki), her ikisi de yaklaşım algoritmalarıdır. Yani, temel olarak bunlardan birini kullanabilirsiniz. RDP için, basitleştirilmiş yol elde edildikten sonra, yumuşak bir eğri elde etmek için basitleştirilmiş yolun köşelerinden bir Catmull Rom spline veya Overhauser spline'ı kullanabilirsiniz. Bununla birlikte, ortaya çıkan spline ve orijinal yoldaki köşe noktaları arasındaki sapma için doğrudan kontrolünüz yoktur.

Schneider algoritması için, veri noktalarının uç tanjant kısıtlamaları olan kübik bir Bezier eğrisi ile uydurulmasıyla başlayacaktır. Elde edilen eğrinin sapması çok büyükse, veri noktalarını iki "bölgeye" böler ve her bir veri bölgesini uç tanjant kısıtlamaları olan kübik Bezier eğrileriyle birleştirir. Bu işlem tüm kübik Bezier eğrilerine olan sapma yeterince küçük olana kadar tekrarlanacaktır.Sonuç olarak, C1 sürekliliği ile en iyi şekilde bağlanmış bir dizi kübik Bezier eğrisi üretir (büyük ihtimalle sadece G1'dir). Ayrıca, bu algoritma son veri noktalarını orijinal veri noktalarından değerlendirdiğinden, veri noktasındaki gürültü, uç tanjant değerlendirmesini ve bu nedenle kübik Bezier bağlantı parçasını etkileyecektir.

Eğri uydurma konusuna zaman harcadıysanız, B-spline eğrileriyle en az kare bağlantıya dikkat etmelisiniz. Bu, yüksek sürekliliğe sahip bir çıkış eğrisi (örneğin kübik B-spline eğrileri için C2) üretecektir. Eğer harcayacak fazla zamanınız yoksa, Schneider'in algoritması, uygulama maliyeti (eğer belirli bir dilde yeniden uygulamak zorunda kalırsanız) ve ortaya çıkan eğrinin kalitesi arasında bir denge yaratan iyi bir seçenektir.

4

Bu noktalardan eğriler.

Here, Youtube'da güzel bir örnektir ve here, algoritmanın kendisini tanımlayan orijinal belgedir. Paper.js Örneğin gelince


:

  • This Bahsettiğiniz o belirli işlevler için Github link ve bu oldukça iyi açıklanmıştır. 'un kullanıldığı araştırma makalesi this'dur.

  • Ayrıca here

İlgili konular