インクリメンタルラインの簡素化

Question

通常のラインの簡素化に関するインターネット上の情報の多くは、あります

https://www.jasondavies.com/simplify/

https://bost.ocks.org/mike/simplify/

http://geomalgorithms.com/a16-_decimate-1.html

http://mourner.github.io/simplify-js/

前払い。 Visvalingamのアルゴリズム、Douglas-Peucker Algorithmですが、公差パラメータが固定されており、ポイントが前もって分かっていない場合はどうなりますか？私は多くのポイントがあり、N * Log（N）アルゴリズムを何千回も実行したくないのですが、代わりに私のセットを徐々に処理したいと思います。交差点は問題ではありません。視覚的影響を最小限に抑えたデータセットのサイズは、この問題に対処するためのスマートな方法ですか？

Answer 1

交差点が問題ではなく、視覚的な類似性が必要な場合（おそらくラスタライズ後、ピクセルサイズに近いε）、チェーンを縮小するのに十分近い点を破棄するだけで作業が可能です。擬似コードで

：

Let C be the original chain 
Let R be the reduced chain (initially empty) 

Add the first point of C to R 
For every subsequent point p of C: 
    If distance(p, the last point of R) >= ε: 
     Add p to R 

何このアプローチ保証：

• 低減チェーン内のすべてのセグメントの長さになり、少なくともε
• であろう鎖間のハウスドルフ距離ほとんどε

は保証していないもの：自己交差の

• 不在は
• 最適の任意の種類

（点数の両方のハウスドルフ距離に近づくと小さくなる異なる鎖があってもよいです）