Топойсон: упрощение квантования VS

Ответ 1

Общий размер вашей геометрии зависит от двух факторов: количество точек и количество цифр (точность) каждой координаты.

Скажем, у вас большая геометрия с 1 000 000 точек, где каждая двумерная точка представлена ​​как долгота в ± 180 ° и широта в ± 90 °:

[-90.07231180399987,29.501753271000098],[-90.06635619599979,29.499494248000133],…

Реальные числа могут иметь произвольную точность (в JSON, в JavaScript они ограничены точностью IEEE 754) и, следовательно, бесконечное количество цифр. Но на практике вышеприведенное довольно типично, поэтому скажем, что каждая координата имеет 18 цифр. Включая дополнительные символы ([, ] и ,), каждая точка занимает не более 1 + 18 + 1 + 18 + 1 = 39 байтов для кодирования в JSON, а вся геометрия составляет около 39 * 1 000 000 ≈ 39 МБ.

Теперь скажем, что мы преобразуем эти действительные числа в целые числа: как долгота, так и широта сводятся к целым числам x и y, где 0 ≤ x ≤ 99 и 0 ≤ y ≤ 99. Простой сопоставление между точками реального числа ⟨λ, φ⟩ и целочисленные координаты ⟨x, y⟩:

x = floor((λ + 180) / 360 * 100);
y = floor((φ + 90) / 180 * 100);

Поскольку для каждой координаты требуется не более двух цифр для кодирования, каждая точка занимает не более 1 + 2 + 1 + 2 + 1 = 7 байтов для кодирования в JSON, а вся геометрия составляет около 7 МБ; мы уменьшили общий размер на 82%.

Конечно, ничего не приходит бесплатно: если вы удалите слишком много информации, вы больше не сможете точно отображать геометрию. Эмпирическое правило состоит в том, что размер вашей сетки должен быть как минимум в два раза больше, чем наибольший ожидаемый размер отображения для всей карты. Например, если вы показываете карту мира в пространстве размером 960 × 500 пикселей, то по умолчанию 10 000 × 10000 (-q 1e4) является разумным выбором.

Таким образом, квантование удаляет информацию, уменьшая точность каждой координаты, эффективно привязывая каждую точку к регулярной сетке. Это уменьшает размер сгенерированного файла TopoJSON, поскольку каждая координата представляется как целое число (например, между 0 и 9999) с меньшим количеством цифр.

Напротив, упрощение удаляет информацию, удаляя точки, применяя эвристику, которая пытается измерить визуальную значимость каждой точки и удалить наименее заметные точки. Существует множество различных методов упрощения, но метод Visvalingam, используемый ссылочной реализацией TopoJSON, описан в моей статье Упрощение линии, поэтому я не буду повторять здесь.

В то время как квантование и упрощение адресуют эти два разных типа информации в основном независимо друг от друга, это дополнительное усложнение: квантование применяется до построения , тогда как упрощение обязательно применяется после сохранить топологию. Поскольку квантование часто вводит совпадающие точки ([24,62],[24,62],[24,62]…), а совпадающие точки удаляются, квантование также может удалять точки.

Причина, по которой квантование применяется до построения топологии, состоит в том, что геометрические входы часто не являются топологически действительными. Например, если вы берете шейп файл графств Невады и объединяете его с шейп файлом государственной границы штата Невада, координаты в одном файле формы могут не точно соответствовать координатам в другом шейп файле. Путем квантования координат перед построением топологии вы привязываете координаты к обычной сетке и можете получить более чистую топологию с меньшим количеством дуг, надеясь правильно идентифицировать все общие дуги. (Конечно, если вы переквалифицируете, вы можете вызвать слишком много совпадающих точек и получить самопересекающиеся дуги, что вызывает другие проблемы.)

В будущем выпуске, возможно, 1.5.0, TopoJSON позволит вам управлять квантованием до того, как топология будет построена независимо от квантования выходного файла TopoJSON. Таким образом, вы можете использовать более тонкую сетку (или вообще нет сетки!), Чтобы вычислить топологию, а затем упростить, а затем использовать более грубую сетку, подходящую для экрана с низким разрешением. На данный момент они связаны друг с другом, поэтому я рекомендую использовать более тонкую сетку (например, -q 1e6), которая создает чистую топологию за счет чуть большего файла. Поскольку TopoJSON также использует дельта-кодированные координаты, вы в любом случае платите полную цену за все цифры!

Ответ 2

Эти два связаны друг с другом, но имеют разные цели и результаты.

Я считаю, что квантование сворачивает соседние точки на основе параметра (который вы настраиваете на ожидаемое разрешение представления) - не имеет смысла иметь разрешение выше пикселей, которые будут рисовать карту. Но это не мешает анализировать путь для определения оптимального количества точек, необходимых для представления формы.

Упрощение - это алгоритм, который будет анализировать полигон и оптимально уменьшать количество точек таким образом, чтобы общая деформация многоугольника была минимизирована. В принципе, его можно использовать для драматического уменьшения количества точек (и, следовательно, размера файла) без заметного влияния на качество пути.

Как параллельное исследование, рассмотрим прямую линию, состоящую из 10 пунктов. Квантование уменьшит количество точек (сворачивание близлежащих или совпадающих точек) на основе используемого вами значения. Упрощение будет анализировать линию и понять, что 8 из десяти точек можно удалить без существенного изменения общей формы многоугольника и уменьшить линию до двух точек (поскольку нет деформации пути путем удаления точек на линии).

См. также:

• Ссылка Topojson: https://github.com/mbostock/topojson/wiki/Command-Line-Reference
• M. Bostock Simplification article: http://bost.ocks.org/mike/simplify/

Оба должны использоваться в комбинации: quitation, чтобы уменьшить карту до сетки нужного размера, упрощение для оптимизации путей.