Recherche de superficies de polygones pondérés superposés

Question

J'ai un certain nombre de polygones sous la forme d'une liste de coordonnées. Chacun de ces polygones représente une zone sur une carte globale et chacun a un poids.

J'ai besoin de trouver la zone sur la carte où ce poids est le plus élevé. Cela signifie que lorsque les polygones se chevauchent, le poids sera la somme des deux polygones pour la zone d'intersection. Je voudrais rendre le calcul aussi efficace que possible. Toute aide serait grandement appréciée.

Answer 1

L'approche la plus simple de ce problème serait de regrouper les polygones par les voisins les plus proches. Cette étape est facultative et n'est utilisée que pour rendre la recherche de polygones croisés plus efficace. Au lieu de cela, le regroupement peut également être omis, ce qui nécessiterait une recherche exhaustive des polygones qui se croisent.

Dans l'étape suivante, vous pouvez remplacer deux polygones coupant A et B par trois polygones comme suit: un polygone qui se compose de la zone de A sans l'intersection de la zone avec le poids de A, un polygone équivalent pour B, et un troisième polygone qui couvre la zone d'intersection de A et B avec les poids ajoutés de A et B comme poids. Remplacez A et B par les trois polygones générés et mettez à jour le cluster. Répétez cette étape jusqu'à ce que vous ne trouviez plus aucun rectangle d'intersection et que vous avez terminé.