Déterminer si un point est dans un grand nombre de polygones

Question

Je suis conscient d'une méthodologie de lancer de rayon, cependant, cela ne fonctionne pas pour les points situés le long des sommets et il teste uniquement l'inclusion d'un point à l'intérieur d'un polygone .

Existe-t-il une meilleure façon de faire autre que d'itérer la méthodologie de lancer de rayon le long de chaque polygone?

Les pensées et les suggestions sont les bienvenues.

Answer 1

Si le prétraitement du jeu de polygones n'est pas autorisé, vous ne pouvez pas faire beaucoup mieux qu'un test exhaustif.

Sinon, vous pouvez utiliser une structure de données d'emplacement de point pour accélérer les requêtes.

https://en.wikipedia.org/wiki/Point_location