Suite

Comment augmenter les performances de la requête du voisin le plus proche à l'aide d'un multipoint ? (Améliorer la géométrie)


La fonction suivante obtient le point le plus proche dans un rtree à une géométrie multipoint. J'aimerais que les performances de la fonction soient meilleures. Y a-t-il un moyen de le rendre plus rapide?

TimingLink* JourneyPattern::getClosestFromTimingLink(multipoint g,int maxFromSequence) { std::vector result_n; linkFromTree.query(bgi::nearest(g, 1) && bgi::satisfies([maxFromSequence](LinkPair const& v) { return ((v.second)->fromSequence < maxFromSequence); }), std::back_inserter( résultat_n)); if (!result_n.empty()) renvoie result_n[0].second; sinon renvoie NULL ; }

Le but de la fonction est de trouver un point dans le rtree linkFromTree qui est le plus proche du multipoint g et dont fromSequence est inférieur à maxFromSequence. linkFromTree est un rtree créé à l'aide de l'algorithme d'emballage et il contient généralement environ 100 points. Le g multipoint contiendra également environ 100 points.

La partie lente semble utiliser un multipoint (g) pour effectuer la requête du voisin le plus proche, car j'ai une fonction similaire qui utilise un point à la place et elle est beaucoup plus rapide (en moyenne 20 fois plus rapide).


La solution consistait à utiliser un kdtree au lieu de rtree. J'ai utilisé du nanoflann. Il fonctionne environ 20 fois plus vite.