Как графические программисты имеют дело с вершинами рендеринга, которые не меняют изображение?

10

Итак, название немного неловко. Я дам немного предыстории, а затем задам свой вопрос.

Предыстория : я работаю разработчиком веб- приложений ГИС , но в свободное время я играю с рендерингом карт и улучшением форматов обмена данными. Я работаю только в 2D пространстве.

Одна интересная проблема, с которой я столкнулся, заключается в том, что при рендеринге многоугольника в небольшом масштабе (с уменьшенным масштабом) многие вершины являются избыточными. В крайнем случае, у вас есть многоугольник с 500 000 вершин, который занимает всего один пиксель. Если вы отправляете эти данные в браузер, имеет смысл пропустить ~ 499 999 из этих вершин. Один из способов достижения этого - рендеринг изображения на сервере и отправка его в формате PNG: вуаля, это точка. Иногда, однако, мы хотим, чтобы данные отправлялись в браузер, где они могут быть отображены с помощью SVG (или canvas, или webgl), чтобы они могли быть интерактивными.

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

Я получил значительное уменьшение размера данных, просто используя алгоритм Дугласа-Пейкера , и я считаю, что смог добиться того, чтобы многоугольники оставались верными с точностью до одного пикселя. К сожалению, Дуглас-Пейкер не сохраняет топологию, поэтому он изменил способ отображения границ между полигонами. Я не мог легко найти другие алгоритмы, чтобы попробовать и приспособиться к цели, но у меня нет большого опыта работы с CS / алгоритмом, и я мог бы не распознать их, если бы увидел их.

canisrufus
источник
1
Google для "Топологически согласованного Дугласа-Пекера", и вы найдете некоторые ссылки на рефераты некоторых статей. К сожалению, вы должны заплатить за полные статьи, которые я видел.
Док Браун
@DocBrown Спасибо! Квестия даже, кажется, имеет бесплатную пробную версию.
canisrufus

Ответы:

3

То, что вы ищете, это 2d level of detail algorithms.

Об этом много говорится в Google, если вы ищете эти выделенные термины.

Этот вопрос о stackoverflow содержит информацию, которую вы ищете для 2D уровня детализации рендеринга.

Сообщество
источник
+1 за очень уместную лексику. Похоже, что я на самом деле использую подход с уровнем детализации, но мне нужен алгоритм упрощения полигонов, который соответствует моим потребностям. Нашел аккуратный обзор для 3d. Я считаю, что я действительно разработал подходящую стратегию упрощения, хотя у меня не было времени ее кодировать.
canisrufus