Vous recherchez un algorithme efficace trouver rapidement la ligne la plus proche (définie par la distance perpendiculaire) à un point arbitraire

Question

J'ai un grand jeu de lignes en 2D avec un point de départ connu et un point d'extrémité, et je voudrais trouver la distance la plus proche (définie par la distance perpendiculaire) de ces bords (ou l'extension de ces bords dépassant leurs points de départ et de fin) à un point arbitraire.

Le meilleur que j'ai fait jusqu'à présent est de générer un ensemble de points d'échantillonnage sur chaque ligne et d'utiliser un arbre KD pour résoudre le problème de voisin le plus proche pour les points - c'est-à-dire trouver le point d'échantillon de ligne le plus proche sur le point de requête.Mais cela est inexact et nécessite un grand nombre d'échantillons pour de longues lignes.

J'ai vu ceci: algorithme pour le bord le plus procheDétection par rapport à un point (dans toutes les directions)

mais il reposait sur une méthode de balayage et un petit nombre de lignes de longueur finie.

Answer 1

Toutes vos lignes définissent un Subdivision planaire , où chaque région polygonale est délimitée par un nombre fini de segments de ligne ou de rayons. Donc, au début, vous devez trouver une région (probablement infinie), contenant un point de requête, puis vous pourrez sélectionner sa ligne de frontière avec une distance minimale à partir de ce point.

Il existe de nombreuses façons de pré-traiter une subdivision planaire afin de résoudre le Problème de localisation du point avec complexité de temps logarithmique. Une certaine structure de données hiérarchique est typiquement conçue, qui peut être traversée pour tout point de requête, et il est prouvé que la longueur du chemin Traverse est limitée par $ O (journal (n)) $ , où $ n $ est le nombre de régions. Comme @PSeudonyonym mentionné dans les commentaires, vous pouvez également utiliser Partitionnement de l'espace binaire (BSP) pour construire un BSP Tree - C'est également une structure de données hiérarchique (arbre binaire), qui vous permettra de trouver efficacement une région, contenant un point de requête. Il semble que votre problème convient bien à cette approche BSP.

Désolé de dire, vous pouvez obtenir des régions avec $ o (n) $ segments de limite / rayons, où $ N. $ est le nombre de lignes. Pour surmonter cette difficulté, vous pouvez davantage subdiviser chaque région dans Voronoi Diagram , généralisé pour ses segments de limites et des rayons. Il est facile de voir que le nombre total de ces régions raffinées sera limitée par $ O (n ^ 2) $ , qui vous donne toujours une complexité de temps logarithmique pour la ligne la plus proche rechercher. Toutefois, dans des cas moyens, ces régions avec de nombreux segments / rayons frontières constitueront une petite fraction de toutes les régions - vous pourrez donc toujours sélectionner rapidement le segment de limite / rayon le plus proche en boucle sur la limite de la région.

---

Si vous voulez en savoir plus sur les propriétés générales de la structure géométrique, vous travaillez avec - il est logique de lire Cette page wiki.

Answer 2

J'ai peut-être mal compris votre objectif - supposez-vous que les bords continuent dans les deux directions, même s'ils sont définis par 2 points spécifiques qui leur sont-ils?Je suppose donc parce que vous dites que la distance est définie par une distance perpendiculaire.Dans quel cas comment de cette -

1. Pour chaque segment de ligne, calculez l'angle.
2. Dessinez une ligne imaginaire qui passe par votre point arbitraire à un angle perpendiculaire au segment de ligne.
3. Trouvez le point d'intersection entre le segment de ligne et la nouvelle ligne imaginaire, trouvez la distance entre ce point et votre point arbitraire.Gardez la distance la plus basse.
Si les lignes ne sont pas infiniment longs, alors lorsque vous vérifiez la distance, vérifiez Min (distance au point de départ, distance jusqu'au point de fin).