Suite

Quel algorithme me permet de calculer l'ensemble de tous les points à l'intérieur d'un polygone ?

Quel algorithme me permet de calculer l'ensemble de tous les points à l'intérieur d'un polygone ?


Imaginez que j'ai un polygone qui représente les contours d'un bâtiment sur une carte 3D entière (tout est un bloc de 1 mètre sur 1 mètre sur cette carte). Dans l'image ci-dessous, vous voyez plusieurs bâtiments sans toit.

Pour dessiner les toits, j'ai besoin de savoir quels sont les points à l'intérieur du polygone.

Quel algorithme puis-je utiliser pour cela ?

Les gens ont mentionné l'enveloppe convexe, mais cela me donne le polygone, que j'ai déjà.

Mise à jour 1 (01.10.2015 13:34 MSK): J'ai trouvé les noms potentiels suivants :

  1. Jointure spatiale (suggérée par Joseph)
  2. Algorithme de ligne de balayage (une autre explication)
  3. Z-buffering

Mise à jour 2 (01.10.2015 14:22 MSK): Imaginez que j'ai un rectangle défini par la ligne noire dans l'image ci-dessous, dessiné sur une grille.

J'ai besoin d'un algorithme pour trouver les coordonnées de tous les points à l'intérieur du polygone, i. e. tous les points verts.

Mise à jour 3 (01.10.2015 15:09 MSK): Notez qu'il s'agit d'une carte Minecraft, que vous pouvez imaginer comme un raster en 3 dimensions, chaque "pixel" étant un bloc de 1 mètre de longueur, de largeur et de hauteur.

La seule commande que mon moteur de rendu accepte est celle-ci :

world.setBlock(x, y, z, tapez),

  • x,y,zsont des coordonnées et
  • taperest le matériau du bloc (par exemple pavés, herbe ou briques).

Cette commande place un bloc exactement à ces coordonnées. L'espace qui l'entoure reste libre. Quand je veux tracer des lignes, je dois faire plusieurs appels comme ça. Quand je veux remplir une zone (par exemple un toit plat), je dois faire ces appels pour tous des points internes du polygone. Mon moteur de rendu n'a pas de fonctionnalité "remplir le polygone", je dois l'implémenter moi-même.


Dans vos commentaires, vous avez déclaré que vous aviez les points et les lignes de vos polygones. Je ne sais pas pourquoi vous auriez besoin de tous les points verts à l'intérieur de votre polygone pour créer votre toit. Je suggérerais de construire l'axe médian (squelette) de votre polygone et d'utiliser ses points pour construire vos toits (Images). C'est l'algorithme utilisé par de nombreux logiciels en 3D pour construire des bâtiments en 3D.

Mettre à jour

Pour avoir un toit plat, vous n'avez pas besoin de points internes de polygone pour créer un toit plat. Connectez simplement les points (par exemple, les sommets des polygones) comme le sol du bâtiment. La procédure simple consisterait à extraire les sommets des polygones, puis à les extruder pour construire les bâtiments 3D.


Les algorithmes pour cela sont appelés remplissage d'inondation. Il est intéressant que nous l'utilisions tous les jours, mais que nous ne le connaissions pas par son nom.


Voir la vidéo: Algorithmes - partie 6: polynômes, complexité dun algorithme