Иногда нужно упростить список координат, например вывод kml(kmz) на маленьких уровнях увеличения - большая точность отображения не нужна, зато скорость очень важна.
Наиболее популярным вариантом в этом случае является Douglas-Peucker Algorithm дающим хорошую для человека результирующую траекторию. Но он является достаточно алгоритмически сложным, так как для удаления лишних точек удаляя определяя точки с минимальным векторный расстоянием между точками.
Более простым вариантом является замена всех точек на точку в середине между двумя соседними - в результате получается на 1 точку меньше. Эту операцию поврторяем пока количество точек не станет удолетворять максимально допустимому для отображения. Недостатки - не учитыват важность точек(смена направления), срезаются углы и выравнивается границы.
Более хорошая версия - проход по точкам и высчитывается минимальное растояние между точками, если оно слишком мало, то увеличиваем его до минимально допустимого.
Затем запускается цикл по точкам и добавляются только те точки, которые располагаются на расстоянии от последней добавленной точки больше, чем минимально допустимое полученное на предыдущим шаге. Эту операцию повторяют пока количество точек не станет меньше максимально допустимого (вычисляется в общем-то на глаз, до тех пор пока время пересчета допустимо по времени ожидания и дефекты в контурах карт еще мало заметны). Также итерации могут продолжаться пока в контуре более 3 точек и площадь полигона больше допустимого для отображения, меньше можно просто отбрасывать(можно считать, что площадь линейно зависима от произведения минимального расстояния на количество точек, что, конечно, геометрически не всегда верно). Для упрощения математической сложности модно считать что расстояние равно не квадрату различий между точками((x1-x2)^2 + (y1-y2)^2 ), а сумме расстояний по координатам по модулю(|(x1-x2)| + |(y1-y2)|), что опять таки не всегда верно, но зато быстро.
No comments:
Post a Comment