User Tools

Site Tools

blog:2024-12-05-003



2024-12-05 Share: Douglas Peucker演算法的C#實現

  • 一、演算法原理
    • Douglas-Peucker演算法
    • 在數位化過程中,需要對曲線進行取樣簡化,即在曲線上取有限個點,將其變為折線,並且能夠在一定程度上保持原有的形狀。
    • 經典的Douglas-Peucker演算法描述如下:
      • (1)在曲線首尾兩點A,B之間連接一條直線AB,該直線為曲線的弦;
      • (2)得到曲線上離該直線段距離最大的點C,計算其與AB的距離D;
      • (3)比較該距離與預先給定的閾值threshold的大小,如果小於threshold,則該直線段作為曲線的近似,該段曲線處理完畢。
      • (4)如果距離大於閾值,則用C將曲線分為兩段AC和BC,並分別對兩段取信進行1~3的處理。
      • (5)當所有曲線都處理完畢時,依序連接各個分割點所形成的折線,即可以作為曲線的近似。

Local Backup

  • 二、演算法C#實現
    • using System;
      using System.Collections.Generic;
      using System.Linq;
      using System.Text;
      
      namespace ConsoleApplication2
      {
          public struct cvPoint
          {
              public int X;
              public int Y;
              public cvPoint(int x, int y)
              {
                  X = x;
                  Y = y;
              }
          }
          class Program
          {
              static void Main(string[] args)
              {
                  var points = new List<cvPoint>();
                  points.Add(new cvPoint(1, 1));
                  points.Add(new cvPoint(2, 2));
                  points.Add(new cvPoint(3, 3));
                  points.Add(new cvPoint(4, 3));
                  points.Add(new cvPoint(5, 3));
                  points.Add(new cvPoint(6, 3));
                  points.Add(new cvPoint(5, 3));
                  points.Add(new cvPoint(6, 3));
                  points.Add(new cvPoint(7, 3));
                  points.Add(new cvPoint(8, 3));
                  var epsilon = 0.8d;
                  var filteredPoints = new List<cvPoint>();
                  DouglasPeucker(points, epsilon, ref filteredPoints);
                  Console.WriteLine("Filtered points:");
                  foreach (var f in filteredPoints)
                  {
                      Console.WriteLine(string.Format("{0},{1}", f.X, f.Y));
                  }
                  Console.ReadKey();
              }
              private static double distanceToSegment(cvPoint p, cvPoint start, cvPoint end)
              {
                  var m1 = ((double)(end.Y - start.Y)) / ((double)(end.X - start.X));
                  var c1 = start.Y - m1 * start.X;
                  var interPointX = 0d;
                  var interPointY = 0d;
                  if (m1 == 0)
                  {
                      interPointX = p.X;
                      interPointY = c1;
      
                  }
                  else
                  {
                      var m2 = -1 / m1;
                      var c2 = p.Y - m2 * p.X;
                      interPointX = (c1 - c2) / (m2 - m1);
                      interPointY = m2 * interPointX + c2;
                  }
                  return Math.Sqrt(Math.Pow(p.X - interPointX, 2) + Math.Pow(p.Y - interPointY, 2));
              }
      
              private static void DouglasPeucker(IList<cvPoint> PointList, double epsilon, ref List<cvPoint> filteredPoints)
              {
                  var dmax = 0d;
                  int index = 0;
                  int length = PointList.Count;
                  for (int i = 1; i < length - 1; i++)
                  {
                      var d = distanceToSegment(PointList[i], PointList[0], PointList[length - 1]);
                      Console.WriteLine(string.Format("{0}.distence:{1}", i, d));
                      if (d > dmax)
                      {
                          index = i;
                          dmax = d;
                      }
                  }
                  Console.WriteLine(string.Format("dMax:{0}", dmax));
                  // If max distance is greater than epsilon, recursively simplify
                  if (dmax > epsilon)
                  {
                      filteredPoints.Add(PointList[0]);
                      filteredPoints.Add(PointList[index]);
                      filteredPoints.Add(PointList[length - 1]);
                      DouglasPeucker(PointList.Take(index + 1).ToList(), epsilon, ref filteredPoints);
                      DouglasPeucker(PointList.Skip(index + 1).Take(PointList.Count - index - 1).ToList(), epsilon, ref filteredPoints);
                  }
              }
          }
      }

TAGS

  • 6 person(s) visited this page until now.

Permalink blog/2024-12-05-003.txt · Last modified: 2024/12/05 11:20 by jethro

oeffentlich