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

10

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.

canisrufus
la source
1
Google pour "Douglas-Peucker topologiquement cohérent" et vous trouverez des liens vers des résumés de certains articles. Malheureusement, vous devez payer pour les articles complets que j'ai vus.
Doc Brown
@DocBrown Merci! Questia semble même avoir un essai gratuit.
canisrufus

Réponses:

3

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.

Communauté
la source
+1 pour le vocabulaire très pertinent. Il semble que j'utilise en fait une approche de niveau de détail, mais j'ai besoin d'un algorithme de simplification des polygones qui convient à mes besoins. Trouvé une vue d'ensemble soignée pour les 3D. Je crois que j'ai en fait élaboré une stratégie de simplification appropriée, même si je n'ai pas eu le temps de la coder.
canisrufus