又是地图，用射线法（点在多边形内部）计算地图点阵，当边界点多起来的时候，计算就很难了。
高德地图给出的基础中国经纬度边界有8万多个点，运行起来基本瘫痪。所以希望能够在尽量保持形状的基础上减少点的个数。下面是最常用的 道格拉斯-普克算法

道格拉斯-普克(Douglas-Peuker)算法

Douglas-Peuker算法(DP算法)过程如下:
1、连接曲线首尾两点A、B；
2、依次计算曲线上所有点到A、B两点所在曲线的距离；
3、计算最大距离D，如果D小于阈值threshold,则去掉曲线上出A、B外的所有点；如果D大于阈值threshold,则把曲线以最大距离分割成两段；
4、对所有曲线分段重复1-3步骤，知道所有D均小于阈值。即完成抽稀。

这种算法的抽稀精度与阈值有很大关系，阈值越大，简化程度越大，点减少的越多；反之简化程度越低，点保留的越多，形状也越趋于原曲线。下面Python代码是抄来的：

  1. # -*- coding: utf-8 -*-
  2. """
  3. -------------------------------------------------
  4.  File Name DouglasPeuker
  5.  Description : -
  6.  Author : J_hao
  7.  date 2017/8/16
  8. -------------------------------------------------
  9.  Change Activity:
  10.  2017/8/16: -
  11. -------------------------------------------------
  12. """
  13. from __future__ import division
  14. from math import sqrt, pow
  15. __author__ = 'J_hao'
  16. THRESHOLD = 0.0001 #
  18. def point2LineDistance(point_a, point_b, point_c):
  19.      """
  20.      ab c
  21.      :param point_a:
  22.      :param point_b:
  23.      :param point_c:
  24.      :return:
  25.      """
  26.       # b c
  27.       if point_b[0] == point_c[0]:
  28.       return 9999999
  29.       slope = (point_b[1] - point_c[1]) / (point_b[0] - point_c[0])
  30.       intercept = point_b[1] - slope * point_b[0]
  32.      # ab c
  33.      distance = abs(slope * point_a[0] - point_a[1] + intercept) / sqrt(1 + pow(slope, 2))
  34.      return distance
  35.   class DouglasPeuker(object):
  36.      def __init__(self):
  37.          self.threshold = THRESHOLD
  38.          self.qualify_list = list()
  39.          self.disqualify_list = list()
  40.      def diluting(self, point_list):
  41.          """
  43.          :param point_list:
  44.          :return:
  45.          """
  46.           if len(point_list) < 3:
  47.              self.qualify_list.extend(point_list[::-1])
  48.          else:
  49.              #
  50.              max_distance_index, max_distance = 0, 0
  51.              for index, point in enumerate(point_list):
  52.                  if index in [0, len(point_list) - 1]:
  53.                      continue
  54.              distance = point2LineDistance(point, point_list[0], point_list[-1])
  55.              if distance > max_distance:
  56.                  max_distance_index = index
  57.                  max_distance = distance
  58.              #
  59.              if max_distance < self.threshold:
  60.                  self.qualify_list.append(point_list[-1])
  61.                  self.qualify_list.append(point_list[0])
  62.              else:
  63.              #
  64.                  sequence_a = point_list[:max_distance_index]
  65.                  sequence_b = point_list[max_distance_index:]
  66.                   for sequence in [sequence_a, sequence_b]:
  67.                      if len(sequence) < 3 and sequence == sequence_b:
  68.                          self.qualify_list.extend(sequence[::-1])
  69.                      else:
  70.                          self.disqualify_list.append(sequence)
  71.      def main(self, point_list):
  72.          self.diluting(point_list)
  73.          while len(self.disqualify_list) > 0:
  74.              self.diluting(self.disqualify_list.pop())
  75.          print self.qualify_list
  76.          print len(self.qualify_list)
  77. if __name__ == '__main__':
  78.      d = DouglasPeuker()
  79.      d.main([[104.066228, 30.644527], [104.066279, 30.643528]])

垂距限值法

垂距限值法其实和DP算法原理一样，但是垂距限值不是从整体角度考虑，而是依次扫描每一个点，检查是否符合要求。算法过程如下:
1、以第二个点开始，计算第二个点到前一个点和后一个点所在直线的距离d；
2、如果d大于阈值，则保留第二个点，计算第三个点到第二个点和第四个点所在直线的距离d;若d小于阈值则舍弃第二个点，计算第三个点到第一个点和第四个点所在直线的距离d;
3、依次类推，直线曲线上倒数第二个点。

  1. # -*- coding: utf-8 -*-
  2. """
  3. -------------------------------------------------
  4.  File Name LimitVerticalDistance
  5.  Description :
  6.  Author : J_hao
  7.  date 2017/8/17
  8. -------------------------------------------------
  9.  Change Activity:
  10.  2017/8/17:
  11. -------------------------------------------------
  12. """
  13. from __future__ import division
  14. from math import sqrt, pow
  15. __author__ = 'J_hao'
  16. THRESHOLD = 0.0001 #
  18. def point2LineDistance(point_a, point_b, point_c):
  19.      """
  20.      ab c
  21.      :param point_a:
  22.      :param point_b:
  23.      :param point_c:
  24.      :return:
  25.      """
  26.      # b c
  27.      if point_b[0] == point_c[0]:
  28.          return 9999999
  29.      slope = (point_b[1] - point_c[1]) / (point_b[0] - point_c[0])
  30.      intercept = point_b[1] - slope * point_b[0]
  31.      # ab c
  32.      distance = abs(slope * point_a[0] - point_a[1] + intercept) / sqrt(1 + pow(slope, 2))
  33.          return distance
  34. class LimitVerticalDistance(object):
  35.      def __init__(self):
  36.      self.threshold = THRESHOLD
  37.      self.qualify_list = list()
  38.       def diluting(self, point_list):
  39.          """
  41.          :param point_list:
  42.          :return:
  43.          """
  44.           self.qualify_list.append(point_list[0])
  45.          check_index = 1
  46.          while check_index < len(point_list) - 1:
  47.              distance = point2LineDistance(point_list[check_index], self.qualify_list[-1], point_list[check_index + 1])
  48.              if distance < self.threshold:
  49.                  check_index += 1
  50.              else:
  51.                  self.qualify_list.append(point_list[check_index])
  52.                  check_index += 1
  53.              return self.qualify_list
  54. if __name__ == '__main__':
  55.      l = LimitVerticalDistance()
  56.      diluting = l.diluting([[104.066228, 30.644527], [104.066279,
  57. 30.643528]])

其实DP算法和垂距限值法原理一样，DP算法是从整体上考虑一条完整的曲线，实现时较垂距限值法复杂，但垂距限值法可能会在某些情况下导致局部最优。另外在实际使用中发现采用点到另外两点所在直线距离的方法来判断偏离，在曲线弧度比较大的情况下比较准确。如果在曲线弧度比较小，弯曲程度不明显时，这种方法抽稀效果不是很理想，建议使用三点所围成的三角形面积作为判断标准。