Comment les programmeurs graphiques gèrent-ils le rendu des sommets qui ne modifient pas l'image?

Donc, le titre est un peu gênant. Je vais donner quelques informations, puis poser ma question.

Contexte : Je travaille en tant que développeur d'applications Web SIG , mais pendant mon temps libre, j'ai joué avec le rendu de cartes et l'amélioration des formats d'échange de données. Je travaille uniquement dans l'espace 2D.

Un problème intéressant que j'ai rencontré est que lorsque vous effectuez le rendu d'un polygone à petite échelle (zoom arrière), de nombreux sommets sont redondants. Un cas extrême serait que vous ayez un polygone avec 500 000 sommets qui ne prend qu'un seul pixel. Si vous envoyez ces données au navigateur, il serait logique d'omettre ~ 499 999 de ces sommets. Une façon d'y parvenir est de rendre une image sur un serveur et de l'envoyer au format PNG: le tour est joué. Parfois, cependant, nous voulons que les données soient envoyées au navigateur où elles peuvent être rendues avec SVG (ou canvas, ou webgl) afin qu'elles puissent être interactives.

Le problème : il s'avère qu'en utilisant des ensembles de données géographiques modernes, il est très facile de surcharger les capacités de rendu de SVG. Afin de faire face à ces limitations, j'essaie de comprendre comment réduire visuellement sans perte un ensemble de données pour une échelle et une étendue de carte données (et, si nécessaire, pour une largeur et une hauteur de pixel de carte connues).

J'ai obtenu une grande réduction de la taille des données en utilisant simplement l' algorithme Douglas-Peucker , et je crois que j'ai pu l'obtenir pour garder les polygones fidèles à un pixel près. Malheureusement, Douglas-Peucker ne conserve pas la topologie, il a donc changé la façon dont les frontières entre les polygones ont été rendues. Je ne pouvais pas facilement trouver d'autres algorithmes pour essayer et m'adapter à l'objectif, mais je n'ai pas beaucoup de connaissances CS / algorithme et je ne les reconnaîtrais pas si je les voyais.

Ce que vous cherchez, c'est 2d level of detail algorithms.

Il y a beaucoup de documentation à ce sujet sur Google si vous recherchez ces termes en surbrillance.

Cette question sur stackoverflow contient les informations que vous recherchez sur le rendu de niveau de détail 2D.