Ligne conteneur de segment pour rapide intersection Ray? (2D)

Question

J'ai un rayon, je dois trouver le segment de ligne le plus proche qu'il frappe. Je pense qu'il est possible de le faire en O (log n) si je trier les segments de première, mais je ne me souviens pas comment les trier ... Je pense une sorte d'arbre serait le mieux, mais comment puis-je trier les deux par point de départ et de fin? Je voudrais également des insertions rapides dans cette structure de données si possible.

Il y a beaucoup de code pour un rayon vs un segment de ligne, mais je besoin de quelque chose pour un rayon vs beaucoup de segments de ligne ... Je ne sais pas quels termes à Google pour.

Un lien vers un article approprié est bon, le code C ++ est encore mieux. Merci! :)

PS: Les segments de ligne sont en fait les bords d'un polygone non auto-intersection, classés dans l'ordre CCW ... mais je pense qu'il peut y avoir un avantage à les trier de façon différente

Ceci est tout 2D.

---

À la réflexion, je ne suis pas tout à fait sûr que ce est possible. Une sorte de répartition spatiale peut aider, mais sinon, je ne peux pas penser à une façon de trier les lignes afin qu'ils puissent être comparés à un rayon arbitraire.

Answer 1

On peut prendre un cadre de contour du polygone (min-max coordonnées x, y) et construire une grille à l'intérieur de la boîte. Ensuite, pour chaque cellule, rappelez-vous toutes les lignes qui traversent la cellule.

Trouver un intesection comme ceci:

• Découvrez quelle cellule le rayon frappe d'abord (O (1))
• Grille traversal algorithme pour « dessiner » un rayon à travers la grille . Lorsque vous cliquez sur la cellule non vide, vérifiez toutes ses lignes, vérifiez si l'intersection est à l'intérieur de la cellule et choisir la plus proche intersection. Si toutes les intersections sont en dehors de la cellule, continue (ce qui est O (longueur du réseau)).

Vous pouvez également faire de la hiérarchie du réseau (c.-à- quadtree - a. arbre que vous demandiez), et marcher en utilisant le même algorithme. Cela se fait en raytracing en 3D et la complexité est en O (sqrt ( N)).

---

Ou, utilisez l'approche que je l'ai fait dans mon raytracer:

• quadtree contenant les lignes (bâtiment quadtree est desribed dans le article) - vous divisez noeuds (= zones) si elles contiennent trop d'objets en 4 sous-nœuds (sous-zones)

• Collectez tous les nœuds feuilles de la quadtree qui sont touchés par le rayon:

  Calculer intersection rectangle ray (pas dur) pour la racine. Si la racine est frappé par le rayon, procéder à ses enfants récursive.

La chose cool à ce sujet est que lorsqu'un nœud de l'arbre est pas coup, vous avez le traitement sautée sous-arbre entier (potentiellement une grande zone rectangulaire).

En fin de compte, cela équivaut à traverser la grille - vous collectez les plus petites cellules sur le chemin du rayon, puis de tester tous les objets en eux pour intersection. Il vous suffit de tester tous et choisir la plus proche intersection (vous explorer toutes les lignes sur le chemin du rayon).

Ceci est O (sqrt (N)).

Dans la grille traversal, lorsque vous trouvez une intersection, vous pouvez arrêter la recherche. Pour y parvenir avec quadtree traversal, vous devez seach les enfants dans l'ordre - soit 4 trier les intersections rect par la distance ou habilement traverser la grille 4 cellules (un nous sommes de retour à traversal)

.

Ceci est juste une approche différente, relativement difficile à mettre en œuvre même, je pense, et fonctionne bien (je l'ai testé sur des données réelles - O (sqrt (N))). Encore une fois, vous pourriez bénéficier seulement de cette approche si vous avez au moins deux ou trois lignes, lorsque le polygone a 10 arêtes l'avantage par rapport à l'essai juste tous serait peu que je pense.

Answer 2

Vous cherchez scanline / Tableau de bord actifs méthodes basées? Vous pouvez jeter un oeil à l'entrée Wikipedia pour Scanline Rendu ou recherche répertoire des Gems graphiques pour les algorithmes (la plupart du temps C, mais un peu de code C ++ ainsi) .

Answer 3

Gardez à l'esprit que le tri est une opération O (n log n) au mieux. Vous pouvez être mieux juste de vérifier chacun individuellement.

Answer 4

Comment êtes-vous certain que vous allez frapper l'un d'eux? Si elles sont des lignes, il est peu probable.

Si c'est vraiment un polygone (c.-à-plan) que vous essayez de tester, la façon habituelle de faire ce genre de chose est intersecte avec le plan d'abord, puis tester ce point (les coordonnées 2d) pour l'intérieur / extérieur polygone.

Peut-être que j'ai mal compris ce que vous faites réellement.

Dans les intersections générales avec des figures complexes accélération se fait avec le partitionnement spatial (et des techniques comme boîte à lettres, si vos tests sont chers).

[Mise à jour: J'ai mal lu l'intention originale] Vous pouvez toujours utiliser (2d) partitionnement spatial, mais les frais généraux peut-être pas la peine. test individuel ne coûtent pas cher, si vos polys ne sont pas compliquées, il pourrait être moins cher de simplement les marcher. Difficile à dire de la description.

Answer 5

Demandez des précisions, est-ce correct?

• Vous avez un ensemble dynamique de segments de ligne L .
• Requête: donné tout point (x, y) et tout direction du rayon de ce point, vous voulez déterminer la ligne la plus proche dans L (le cas échéant)?

Ainsi, le point (x, y) est pas fixé? (Il pourrait être un point quelconque, et toute direction?)