algorithme pour diviser récursive un polygone en quarts de cercle in / out: quel est-il appelé et où est le code?

Question

J'ai beaucoup de points (centaines de milliers) et je veux vérifier ceux qui sont à l'intérieur d'un polygone. Pour un polygone relativement faible (par exemple, susceptibles de ne contenir que des dizaines ou des centaines de points) je peux utiliser la zone de délimitation du polygone comme une vérification initiale, puis faire un point de vérification en poly régulière pour les points à l'intérieur de la boîte . Mais imaginez un grand (par exemple, susceptible de contenir des milliers de mes points), polygone de forme irrégulière. De nombreux points seront soumis à la vérification de la boîte englobante, et en outre le point de vérification en poly sera plus cher parce que le polygone plus grand est composé de beaucoup plus de points. Donc, je voudrais être en mesure de filtrer la plupart des points ou sans avoir à faire le plein contrôle de point en poly.

Alors, j'ai un plan, et surtout je veux savoir si ce que je décris est un algorithme bien connu, et si oui ce qu'il appelle et où je pourrais trouver le code existant pour elle. Je ne crois pas ce que je décris est soit un quad-arbre ou un r-arbre, et je ne sais pas comment chercher. J'appelle un « arbre rect » ci-dessous.

L'idée est, pour gérer ces grands polygones:

Effectuer un pré-processus « d'arbre rect », où la profondeur de l'arbre de rect varie selon la taille du polygone (à savoir, permettre à plus de profondeur pour un polygone plus grand). L'arbre de rect diviserait le cadre de contour du polygone en quatre quartiers. Il vérifier si chaque trimestre rect est entièrement à l'intérieur du polygone, complètement en dehors du polygone, ou aucun des deux. Dans le cas de non plus il diviserait récursive les subrects, continuant ainsi jusqu'à ce que tous rects étaient soit complètement à l'intérieur ou à l'extérieur, ou la profondeur maximale avait été atteinte. L'idée est que (a) le temps de pré-traitement pour faire cet arbre, même si elle se fera plusieurs vérifications point dans le polygone, est bien la peine parce que le temps est éclipsée par le nombre de points à vérifier, et (b) la grande majorité des points peuvent être traités en utilisant les contrôles du cadre de sélection simple (généralement quelques vérifications que vous descendez l'arbre), puis un nombre relativement restreint devrait faire le plein de point en polygone contrôle ( lorsque vous atteignez un nœud feuille qui est encore « ni »).

Qu'est-ce que l'algorithme appelé? Et où est le code? Il ne constitue pas en fait semble si difficile à écrire, mais je me suis dit que je demande avant de sauter dans le codage.

Answer 1

En fait, je fini par utiliser une approche différente mais connexe. Je compris que l'essentiel de cette structure d'arbre que je construis n'était plus que le polygone dessiné à une basse résolution. Par exemple, si mon arbre est descendu à une profondeur de 8, vraiment qui était comme mon dessin polygone sur un bitmap avec une résolution 256x256 et ensuite faire des tests de succès de pixels contre ce polygone. Donc, j'ai étendu cette idée et a utilisé une bibliothèque graphique rapide (la bibliothèque CImg). Je dessine le polygone sur un bitmap en noir et blanc de taille 4000x4000. Ensuite, je vérifie juste les points que pixels contre cette bitmap. La magie est que le dessin bitmap est énorme que très rapide par rapport au temps qu'il me prenait pour construire l'arbre. Donc, je reçois une résolution beaucoup plus que je ne pourrais jamais avoir avec mon arbre.

Une question est d'être capable de détecter les points près du bord du polygone, qui peut être inclus ou exclus de manière incorrecte en raison de problèmes d'arrondi / résolution, même à la taille 4000x4000. Si vous avez besoin de savoir précisément si ces points sont ou, vous pouvez dessiner une course autour du polygone dans une autre couleur, et si votre test de pixel frappé cette couleur, vous feriez le point complet en échec poly. Pour mes fins la résolution 4000x4000 était assez bon (je ne pouvais tolérer l'inclusion / exclusion incorrecte pour certains de mes points de bord).

Donc, l'astuce fondamentale de cette solution est l'idée que les algorithmes de dessin de polygone sont juste super rapide par rapport à d'autres façons que vous pourriez « digitalisation » polygone.