J'ai deux cercles 2D dans un espace 3D (défini par un centre, normal et rayon) et j'essaie de proposer une paire de points qui est l'un des ensembles de paires de points les plus proches. Je sais qu'il y a lieu de 1 à un nombre infini de paires de points, j'ai juste besoin d'une seule paire correspondante.
Y a-t-il un moyen simple de faire ça? La précision n'est pas essentielle. Le rayon des deux cercles est la même valeur non nulle.
Si l'arrière-plan est utile, mon algorithme global prend une courbe de Nurbs dans l'espace et extrudes un polygone 2D le long de la courbe, ce qui donne un cylindre déformé. Je viens d'échantillonner plusieurs points le long de la courbe. La normale de chaque cercle est la tangente de courbe Nurbs, et j'essaie de comprendre comment aligner les échantillons adjacents, donc je n'ai pas de torsion étrange. Il semble que les points les plus proches des échantillons adjacents soient alignés.
Merci pour toutes les réponses ici .. Cette partie du projet a un peu retardé, c'est pourquoi je n'ai pas encore testé toutes les réponses. Je serai sûr de jeter des images ici et de marquer une réponse lorsque je vais travailler à nouveau.
7 Réponses :
n'est-ce pas simplement une question de construction de la ligne entre les deux centres des cercles / sphères et de trouver l'intersection de la ligne et des cercles? Les solutions les plus proches sont (sauf si le cercle intersect, la réponse dépend de la manière dont vous voulez interpréter ce cas).
Ils sont 2 cerclés sur différents plans 2D dans l'espace 3D, si je lisais la question correctement. S'ils étaient des sphères ou 2 cercles sur le même plan, votre réponse serait correcte.
Yikes, à moins que les cercles ne soient sur le même plan ou les mêmes avions parallèles, je pense que la seule façon de le faire est de trouver un minimum sur l'équation de la distance entre deux points du cercle.
http://www.physicsforums.com/showthread.php?t=123168
Ce lien montre comment obtenir l'équation de chaque cercle dans l'espace 3D, puis minimiser la formule de distance entre ces équations. Pas joli cependant, j'espère que quelqu'un va venir avec quelque chose de plus intelligent.
Pour ce que vous décrivez, il suffit de sélectionner un point sur le périmètre du premier cercle et de trouver le point sur le périmètre de chaque cercle le plus proche de celui sélectionné pour le cercle précédent; Cela contrariera complètement la polygonisation, sans torsion et devrait être beaucoup plus facile à résoudre que le cas général - trouve simplement le point sur le plan contenant le deuxième cercle le plus proche de celui sélectionné dans la première et intersectez la ligne traversant Ce point et le centre du deuxième cercle avec le périmètre du deuxième cercle.
Cependant, cela pourrait ne pas céder comme une polygone agréable pour le cylindre extrudé car il est possible de maintenir la zone de polygone que possible et de le faire nécessitera une torsion entre les cercles adjacents.
Ce que vous essayez vraiment de calculer est la paire de points qui minimisent la distance entre les points qui se trouvent sur 2 cercles différents en 3 dimensions. La méthode que vous devriez utiliser pour trouver la solution exacte (comme dans presque tous les problèmes d'optimisation) consiste à représenter la distance en fonction de tous les points possibles et de prendre son dérivé par rapport aux variables indépendantes et de définir les expressions résultantes à 0 . Depuis que vous avez 2 cercles, vous aurez 2 variables indépendantes (c'est-à-dire l'angle d'un point sur un cercle et un sur l'autre cercle). Une fois que vous avez résolu les équations de minimisation, vous auriez également trouvé les points sur les cercles qui satisferont votre contrainte. (Fondamentalement, vous trouverez les angles sur les cercles pour la paire de points que vous recherchez.)
J'ai trouvé un papier en ligne (à Ce site ) qui passe rigoureusement avec les calculs, mais le résultat final résoudra une équation polynomiale de 8ème ordre. Vous pouvez essayer de simplifier les équations et proposez une solution moins exacte qui répond à vos besoins.
Il y a aussi un papier qui prétend avoir un algorithme beaucoup plus rapide pour trouver la distance entre deux cercles en 3D; Cependant, je ne peux pas voir le contenu et, donc, ne peut donc pas dire si cela vous donne également la paire de points qui répondent à cette condition.
Mise à jour: Après avoir relu votre question, je vois que même si vous demandez un moyen de trouver la paire la plus proche des points sur deux cercles dans 3 dimensions, je pense que vous devriez payer Plus d'attention portée aux propriétés de la courbe Nurbs que vous essayez d'extruder le polygone 2D. Vous mentionnez que l'orientation du cercle à un point donné sur la courbe est spécifiée par le vecteur tangent à ce moment-là. Cependant, il y a plus de courbes 3D que le vecteur tangent; il y a le vecteur normal (ou Ma suspicion est que vous pouvez obtenir l'effet que vous désirez en rejoignant les points de cercles consécutifs qui se trouvent chacun le long du sens vectoriel normal de la courbe 3D sous-jacente. De cette façon, vous n'aurez tordant que lorsque la courbe est en train de tordre, c'est-à-dire lorsque le vecteur de torsion est non nul et que le vecteur normal change également. Dans d'autres circonstances, cela devrait satisfaire à votre besoin réel.
Vous n'avez probablement pas besoin de la surkilleuse de trouver des points les plus proches sur les cercles consécutifs.
Je n'ai pas regardé ça, mais ce site dit qu'il a une source C ++ pour l'algorithme du deuxième papier que vous avez mentionné: jgt.akpeters.com/papers/vranek02
Ma première tentative d'une solution utilisait des cadres Frenet, qui ont conduit à de mauvais résultats, je pense que lorsque la courbe a un point d'inflexion. Je vais essayer d'obtenir une capture d'écran ici sous peu.
Himm, je vois. Ce serait génial si vous pouvez poster la fonction de courbe, le point pour lequel vous obtenez un mauvais résultat et la capture d'écran correspondante. Je serais intéressé de voir ce qui se passe mal.
Donc, il s'avère que ce que je cherchais vraiment était la rotation minimisant les cadres. Ma mise en œuvre était pour cet outil: Tsplines.com/forum/viewtopic.php ? F = 16 & T = 31454 Merci pour votre aide .. :)
Je pense que avec les deux points les plus proches, vous pourriez toujours obtenir une torsion étrange ... Un exemple extrême: supposons que les deux cercles ont le r = 1. Si le centre du premier cercle est O, et qu'il est assis sur un plan XY, et le centre du second cercle est assis à x = 1, y = 0, z = 0,01, et il est légèrement incliné dans la direction de culture de x, le plus proche Les points sur les deux cercles feront sûrement la "bande bizarre" que vous essayez d'éviter. Étant donné que les points les plus proches ne vous feraient pas la touche étrange dans le cas où le deuxième cercle est à x = 0, y = 0, z = 0,01 et est également incliné, puis à un moment donné, les déclarations "alignées sur deux points les plus proches sur deux cercles" et "pas de torsion étrange vue" ne correspond plus à l'autre.
En supposant que cela puisse arriver dans la contrainte de Nurbs, voici une autre idée. Au début, prenez les trois points de la courbe Nurbs - deux qui appartiennent aux centres de vos cercles et que le troisième est précisément entre entre elles. Tracez un avion entre les trois. Cet avion traversera les deux cercles à 4 points. Deux de ces points seront sur le même "côté" de la ligne qui relie les centres des cercles - ce sont vos points d'alignement.
Pour les prochains points d'alignement, vous prenez le point d'alignement du "cercle précédent" et dessinez l'avion entre le centre du "cercle précédent", ce point d'alignement et le centre du "nouveau cercle". De cela, vous obtenez le "prochain point d'alignement" basé sur l'intersection avec l'autre cercle.
prochaine étape - "Circle précédent" = "nouveau cercle" et le "nouveau cercle" - votre suivant selon la courbe Nurbs.
Si les rayons des centres des cercles aux points d'alignement sélectionnés, vous vous connaissez que la photo sera un peu laide - c'est le scénario où l'algorithme «point le plus proche» vous obtiendriez toujours la torsion étrange.
Je pense que les coordonnées du point sur le cercle qui est intersection avec l'avion qui se passe via son centre devrait être facile à calculer (il s'agit d'un point sur la ligne faite par intersection des deux plans, l'un des cercle et la cible plan; à la distance r du centre).
Je n'ai pas la preuve rigoureuse pour affirmer ou nier complètement ce qui précède - mais j'espère que cela aide du tout, et je pense que cela devrait être suffisamment rapide pour vérifier, par rapport au calcul des points de placard sur les deux cercles ... (S'il y a des défauts dans ma logique, les corrections dans les commentaires sont les bienvenues).
Bon point, je vais devoir vérifier mes hypothèses. Je pense que pour la tuyauterie d'une courbe, il doit y avoir une sorte de contrainte entre le rayon minimum de courbure et du rayon du tuyau. J'essaie toujours de visualiser ce qui se passe avec l'exemple que vous avez posté, mais cela semble apparenté. La torsion que je crains de tordre la tangente ..
Oui, je pense que cette contrainte pourrait être vérifiée en appliquant l'étape similaire à celle du premier, sur une pièce suffisamment petite de la courbe - alors si les rayons des cercles se croisent (lorsqu'ils sont dessinés sur le plan reliant les trois points suivants sur la courbe ), alors les cercles sont trop gros pour cette courbure.
Étendez les cercles aux planes (à l'aide des points centraux et des normales). Si les avions sont parallèles, tous les points feront le faire. Si les plans ne sont pas parallèles, ils se croisent dans une ligne. Construisez l'avion à travers les deux centres des cercles perpendiculaires à la ligne. Les deux cercles intersectent ce nouvel avion en quatre points. Ces quatre points sont les deux points les plus proches et les deux points les plus éloignés sur les cercles.
"Si les avions sont parallèles, tous les points feront le faire." Est-ce vrai? Ne devriez-vous pas prendre dans ce cas un avion à travers les deux centres perpendiculaires aux avions des cercles?
-1 Désolé, cette réponse est complètement fausse. Si les plans sont parallèles, deux points ne seront pas ; Pour voir cela, considérez simplement le cas où les cercles sont dans le même avion . L'autre partie est également fausse. Imaginez couper une sphère avec deux avions (aucun d'entre eux qui traverse le centre de la sphère). Cela découpe deux cercles à la surface de la sphère. Faites-le de manière à ce que les cercles se croisent réellement (c'est-à-dire que la ligne d'intersection entre les plans traverse la sphère). La distance entre les cercles est nulle, mais cette réponse dit qu'il est strictement positif.
Il peut exister même un plan perpendiculaire à la ligne d'intersection et traverse les deux centres des cercles.
thread ici , mentionné dans une autre réponse donne la formule de paramétrage pour un cercle 3D: p = r cos (t) u + r sin (t) nxu + c, où u est un vecteur d'unité du centre du cercle à n'importe quel point de la circonférence; R est le rayon; n est un vecteur d'unité perpendiculaire à l'avion et c est le centre du cercle, T passe de 0 à 2pi, et par NXU, je veux dire "N Croix U". Paramétrage un cercle de cette façon, et une autre de manière similaire avec un paramètre différent, disons s. Ensuite, chaque point PT sur le premier cercle aura des coordonnées dans la variable T, et chaque point PS sur le second cercle aura des coordonnées dans la variable s.
Écrivez la fonction de distance D (S, T) entre PS et PT de la manière habituelle (ou mieux, le carré de la distance euclidienne afin de ne pas avoir à gaver avec la racine carrée lorsque vous prenez des dérivés). Le graphique de cette fonction D de deux variables est une surface sur une surface de 2pi par 2pi carré dans l'avion S, T, et son minimum est ce que vous avez après. Vous pouvez le déterminer avec les méthodes de calcul standard, par ex. Comme expliqué ici .
3D cercles? : O Vous ne voulez pas dire des sphères?
@Meeh: Vous n'avez pas besoin d'une normale pour les sphères.
Vous avez raison. J'ai besoin de faire des brosser sur mes mathématiques :)
ERREUR: Trop de dimensions !! MDR ;-)
Y a-t-il des progrès supplémentaires à ce sujet? Je suis vraiment curieux de voir le résultat de certains de vos tests.