Algorithme de détection de collision de segment de ligne de cercle?

196

J'ai une ligne de A à B et un cercle positionné en C avec le rayon R.

Image

Quel est un bon algorithme à utiliser pour vérifier si la ligne coupe le cercle? Et à quelle coordonnée le long du bord des cercles cela s'est produit?

Mizipzor
la source
4
Hmm. Une question: parlez-vous de la ligne infinie passant par A et B, ou du segment de ligne finie de A à B?
Jason S
2
Dans ce cas, c'est le segment de ligne finie. La "ligne" est-elle appelée quelque chose d'autre selon qu'elle est finie ou infinie?
Mizipzor le
1
Y a-t-il une exigence de performance? Cela devrait-il être une méthode rapide?
chmike
À ce stade, non, tous les algorithmes que j'ai essayés ici ne ralentissent pas sensiblement l'application.
Mizipzor
13
@Mizipzor oui, ils s'appellent autre chose: des segments de ligne . Si vous dites simplement "ligne", cela implique un infini.
MestreLion

Réponses:

200

Prise

  1. E est le point de départ du rayon,
  2. L est le point final du rayon,
  3. C est le centre de la sphère contre laquelle vous testez
  4. r est le rayon de cette sphère

Calcul:
d = L - E (vecteur de direction du rayon, du début à la fin)
f = E - C (vecteur de la sphère centrale au début du rayon)

Ensuite, l'intersection est trouvée par ..
Obturation:
P = E + t * d
Ceci est une équation paramétrique:
P x = E x + td x
P y = E y + td y
dans
(x - h) 2 + (y - k) 2 = r 2
(h, k) = centre du cercle.

Remarque: Nous avons simplifié le problème en 2D ici, la solution que nous obtenons s'applique également en 3D

obtenir:

  1. Développez
    x 2 - 2xh + h 2 + y 2 - 2yk + k 2 - r 2 = 0
  2. Prise
    x = e x + td x
    y = e y + td y
    (e x + td x ) 2 - 2 (e x + td x ) h + h 2 + (e y + td y ) 2 - 2 (e y + td y ) k + k 2 - r 2 = 0
  3. Exploser
    e x 2 + 2e x td x + t 2 d x 2 - 2e x h - 2td x h + h 2 + e y 2 + 2e y td y + t 2 d y 2 - 2e y k - 2td y k + k 2 - r 2 = 0
  4. Groupe
    t 2 (d x 2 + d y 2 ) + 2t (e x d x + e y d y - d x h - d y k) + e x 2 + e y 2 - 2e x h - 2e y k + h 2 + k 2 - r 2 = 0
  5. Enfin,
    t 2 (_d * _d) + 2t (_e * _d - _d * _c) + _e * _e - 2 (_e * _c) + _c * _c - r 2 = 0
    * Où _d est le vecteur d et * est le produit scalaire. *
  6. Et puis,
    t 2 (_d * _d) + 2t (_d * (_e - _c)) + (_e - _c) * (_e - _c) - r 2 = 0
  7. Laisser _f = _e - _c
    t 2 (_d * _d) + 2t (_d * _f) + _f * _f - r 2 = 0

On obtient donc:
t 2 * (d DOT d) + 2t * (f DOT d) + (f DOT f - r 2 ) = 0
Donc, résoudre l'équation quadratique:

float a = d.Dot( d ) ;
float b = 2*f.Dot( d ) ;
float c = f.Dot( f ) - r*r ;

float discriminant = b*b-4*a*c;
if( discriminant < 0 )
{
  // no intersection
}
else
{
  // ray didn't totally miss sphere,
  // so there is a solution to
  // the equation.

  discriminant = sqrt( discriminant );

  // either solution may be on or off the ray so need to test both
  // t1 is always the smaller value, because BOTH discriminant and
  // a are nonnegative.
  float t1 = (-b - discriminant)/(2*a);
  float t2 = (-b + discriminant)/(2*a);

  // 3x HIT cases:
  //          -o->             --|-->  |            |  --|->
  // Impale(t1 hit,t2 hit), Poke(t1 hit,t2>1), ExitWound(t1<0, t2 hit), 

  // 3x MISS cases:
  //       ->  o                     o ->              | -> |
  // FallShort (t1>1,t2>1), Past (t1<0,t2<0), CompletelyInside(t1<0, t2>1)

  if( t1 >= 0 && t1 <= 1 )
  {
    // t1 is the intersection, and it's closer than t2
    // (since t1 uses -b - discriminant)
    // Impale, Poke
    return true ;
  }

  // here t1 didn't intersect so we are either started
  // inside the sphere or completely past it
  if( t2 >= 0 && t2 <= 1 )
  {
    // ExitWound
    return true ;
  }

  // no intn: FallShort, Past, CompletelyInside
  return false ;
}
bobobobo
la source
1
Semble fonctionner si je fais du copier-coller, mais je cherche à le comprendre. En (xh) ^ 2 + (yk) ^ 2 = r ^ 2 qu'est-ce que h et k? Est-ce que k est constant par lequel la ligne / le rayon augmente sur y sur x? Et qu'est-ce que t? En regardant le code, il semble que vous ayez supposé son 1 (donc c'est juste "supprimé"). Ces formules ont-elles un nom ou quelque chose? Je peux peut-être les rechercher en détail sur Wolfram.
Mizipzor
3
h et k sont le centre du cercle contre lequel vous vous croisez. t est le paramètre de l'équation linéaire. Dans le code, t1 et t2 sont les solutions. t1 et t2 vous indiquent "jusqu'où le long du rayon" l'intersection s'est produite.
bobobobo
1
Ok, j'ai compris. Le produit scalaire est simplement calculé sur les trois éléments (x, y, z) vecteurs. Je vais basculer mon code vers cet algorithme.
chmike
21
P = E + t * dQu'est-ce que c'est t?
Derek 朕 會 功夫
3
Je ne sais pas pourquoi, mais le code ne semble pas fonctionner pour le cas Impale. C'est le cas lorsque j'ajoute si t1 <= 0 && t1> = -1 && t2 <= 0 && t2> = -1 comme condition vraie, mais cela donne également un faux positif d'un côté de la ligne finie, lorsque le cercle est sur la partie "infinie". Je ne comprends pas encore les maths, mais copier / coller, méfiez-vous.
Nicolas Mommaerts
142

Personne ne semble envisager la projection, suis-je complètement hors de propos ici?

Projetez le vecteur ACsur AB. Le vecteur projeté,, ADdonne le nouveau point D.
Si la distance entre Det Cest inférieure à (ou égale à)R nous avons une intersection.

Comme ça:
Image de SchoolBoy

Mizipzor
la source
9
Il y a beaucoup de détails à prendre en considération: D se situe-t-il entre AB? La distance perpendiculaire C à la ligne est-elle supérieure au rayon? Tous ces éléments impliquent l'amplitude du vecteur, c'est-à-dire la racine carrée.
ADB
15
Bonne idée, mais comment calculer ensuite les deux points d'intersection?
Ben
4
@Spider, cela n'a pas d'importance. En général, puisqu'il s'agit d'une variante du problème d'intersection sphère-ligne, la stratégie de Mizipzor est parfaitement valide. CDest une projection, elle est perpendiculaire par définition.
2
C'est une vieille question, mais il y a une bonne ressource à ce sujet et sur les algorithmes associés sur ce site: paulbourke.net/geometry/pointlineplane
Andrew
1
Une grande explication de cette réponse: scratchapixel.com/lessons/3d-basic-rendering/…
ShawnFeatherly
50

J'utiliserais l'algorithme pour calculer la distance entre un point (centre du cercle) et une ligne (ligne AB). Cela peut ensuite être utilisé pour déterminer les points d'intersection de la ligne avec le cercle.

Disons que nous avons les points A, B, C. Ax et Ay sont les composantes x et y des points A. Idem pour B et C. Le scalaire R est le rayon du cercle.

Cet algorithme nécessite que A, B et C soient des points distincts et que R ne soit pas 0.

Voici l'algorithme

// compute the euclidean distance between A and B
LAB = sqrt( (Bx-Ax)²+(By-Ay)² )

// compute the direction vector D from A to B
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB

// the equation of the line AB is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= LAB.

// compute the distance between the points A and E, where
// E is the point of AB closest the circle center (Cx, Cy)
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)    

// compute the coordinates of the point E
Ex = t*Dx+Ax
Ey = t*Dy+Ay

// compute the euclidean distance between E and C
LEC = sqrt((Ex-Cx)²+(Ey-Cy)²)

// test if the line intersects the circle
if( LEC < R )
{
    // compute distance from t to circle intersection point
    dt = sqrt( R² - LEC²)

    // compute first intersection point
    Fx = (t-dt)*Dx + Ax
    Fy = (t-dt)*Dy + Ay

    // compute second intersection point
    Gx = (t+dt)*Dx + Ax
    Gy = (t+dt)*Dy + Ay
}

// else test if the line is tangent to circle
else if( LEC == R )
    // tangent point to circle is E

else
    // line doesn't touch circle
chmike
la source
si une ligne qui ne coupe pas le cercle et ses deux points p1 et p2 sont à l'intérieur du cercle. dans ce cas, comment fonctionne votre algorithme ??
Prashant
1
Vous devez tester t-dt et t + dt. Si t-dt <0, alors p1 est à l'intérieur du cercle. Si t + dt> 1, alors p2 est à l'intérieur du cercle. C'est vrai si LEC <R bien sûr.
chmike
Merci. J'ai aimé ces commentaires pgm comme explication car il n'y avait pas d'utilisation des mots "produit scalaire" car mes calculs sont rouillés. Cependant, t et dt ne sont pas compris entre 0..1, donc en changeant cela en python, j'ai changé t pour être divisé par LAB ** 2. Ma compréhension est que la première division par LAB est de projeter le centre du cercle sur la ligne AB, et la deuxième division par LAB est de le normaliser dans la plage 0..1. Le dt doit également être divisé par LAB, il est donc également normalisé. Ainsi, "si (t-dt> = 0,0)" la première intersection existe "si (t + dt <= 1,0)" la deuxième intersection existe. Cela a fonctionné avec les tests.
punchcard
2
Parce que le point d'intersection avec le cercle est à "distance" t+dtet t-dtsur la ligne. test le point sur la ligne la plus proche du centre du cercle. Les points d'intersection avec le cercle sont à une distance symétrique de t. Les points d'intersection sont à "distances" t-dtet t+dt. J'ai cité la distance car ce n'est pas la distance euclidienne. Pour obtenir la distance euclidienne d' At=0, vous devez multiplier la valeur par LAB.
chmike
1
@Matt W Vous voulez dire "Comment déterminer si l'intersection se produit en dehors des points d'extrémité de la section de ligne AB"? Pensez simplement à t comme une mesure de la distance le long de la ligne. Le point A est à t=0. Point B à t=LAB. Lorsque les deux points d'intersection ( t1=t-tdet t2=t+td) ont des valeurs négatives, les intersections se trouvent à l'extérieur de la section (derrière le point A en regardant du côté de la section du point). Lorsque t1 et t2 sont plus grands que LAB, ils sont également à l'extérieur (cette fois derrière le point B). L'intersection t1 (ou t2) se produit entre A et B uniquement lorsque t1 (ou t2) est comprise entre 0 et LAB.
mars 2015
20

D'accord, je ne vous donnerai pas de code, mais puisque vous avez marqué cela , Je ne pense pas que cela vous importera. Tout d'abord, vous devez obtenir un vecteur perpendiculaire à la ligne.

Vous aurez une variable inconnue dans y = ax + c ( c sera inconnue )
Pour résoudre ce problème, calculez sa valeur lorsque la ligne passe par le centre du cercle.

Autrement dit,
branchez l'emplacement du centre du cercle sur l'équation de la ligne et résolvez c.
Calculez ensuite le point d'intersection de la ligne d'origine et sa normale.

Cela vous donnera le point le plus proche sur la ligne du cercle.
Calculez la distance entre ce point et le centre du cercle (en utilisant la magnitude du vecteur).
Si c'est moins que le rayon du cercle - le tour est joué, nous avons une intersection!

a_m0d
la source
2
C'était en fait ce que je voulais. Je veux la théorie, une recherche google d'algorithme de collision ligne-cercle ne révèle que du code pour autant que je puisse voir.
Mizipzor
Ok, c est inconnu dans votre équation, mais qu'est-ce que "a"? Les autres réponses semblent se référer à cette variable comme "alpha" et "t". Bien que ce soit juste une fonction linéaire (y = kx + m), des mathématiques assez basiques, je me sens soudain un peu rouillé. N'est-ce pas aussi inconnu? Ou voulez-vous dire que nous pouvons supposer m = 0 et résoudre k? Est-ce que m (c'est-à-dire c) ne serait pas toujours nul pour notre k résolu?
Mizipzor le
1
Oh, désolé - j'utilise l'équation simple d'une ligne avec un gradient et un décalage (l'équation cartésienne). J'ai supposé que vous stockiez la ligne comme une telle équation - auquel cas vous utilisez le négatif du gradient pour k. Si vous n'avez pas la ligne stockée comme ceci, vous pouvez calculer k comme (y2-y1) / (x2-x1)
a_m0d
1
Nous ne supposons pas que m est zéro; nous calculons d'abord le gradient (de sorte que l'équation de la ligne ressemble alors à y = 2x + m à titre d'exemple), puis une fois que nous avons le gradient, nous pouvons résoudre pour m en branchant au centre du cercle pour y et x .
a_m0d
1
+1 Explication impressionnante! Mais je pense que cela suppose une ligne, pas un segment de ligne. Donc, si le point le plus proche sur cette ligne du centre du cercle n'était pas entre les points A et B, il serait quand même compté.
Hassan
12

Une autre méthode utilise la formule de la zone triangulaire ABC. Le test d'intersection est plus simple et plus efficace que la méthode de projection, mais trouver les coordonnées du point d'intersection nécessite plus de travail. Au moins, il sera retardé au point où il est nécessaire.

La formule pour calculer l'aire du triangle est: aire = bh / 2

où b est la longueur de base et h est la hauteur. Nous avons choisi le segment AB comme base afin que h soit la distance la plus courte entre C, le centre du cercle, et la ligne.

Puisque la zone du triangle peut également être calculée par un produit vectoriel vectoriel, nous pouvons déterminer h.

// compute the triangle area times 2 (area = area2/2)
area2 = abs( (Bx-Ax)*(Cy-Ay) - (Cx-Ax)(By-Ay) )

// compute the AB segment length
LAB = sqrt( (Bx-Ax)² + (By-Ay)² )

// compute the triangle height
h = area2/LAB

// if the line intersects the circle
if( h < R )
{
    ...
}        

MISE À JOUR 1:

Vous pouvez optimiser le code en utilisant le calcul rapide de la racine carrée inverse décrit ici pour obtenir une bonne approximation de 1 / LAB.

Le calcul du point d'intersection n'est pas si difficile. Ça y est

// compute the line AB direction vector components
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB

// compute the distance from A toward B of closest point to C
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)

// t should be equal to sqrt( (Cx-Ax)² + (Cy-Ay)² - h² )

// compute the intersection point distance from t
dt = sqrt( R² - h² )

// compute first intersection point coordinate
Ex = Ax + (t-dt)*Dx
Ey = Ay + (t-dt)*Dy

// compute second intersection point coordinate
Fx = Ax + (t+dt)*Dx
Fy = Ay + (t+dt)*Dy

Si h = R alors la ligne AB est tangente au cercle et la valeur dt = 0 et E = F. Les coordonnées du point sont celles de E et F.

Vous devez vérifier que A est différent de B et que la longueur du segment n'est pas nulle si cela peut se produire dans votre application.

chmike
la source
2
J'aime la simplicité de cette méthode. Peut-être que je pourrais adapter une partie du code environnant pour ne pas avoir besoin du point de collision lui-même, je verrai ce qui se passe si j'utilise A ou B plutôt que le point calculé entre les deux.
Mizipzor, le
1
t = Dx * (Cx-Ax) + Dy * (Cy-Ax) devrait lire t = Dx * (Cx-Ax) + Dy * (Cy-Ay)
Stonetip
C'est juste. Je vous remercie de le faire remarquer. Je l'ai corrigé dans le post.
chmike
vient d'être édité - la première ligne calcule la zone du triangle en utilisant un produit croisé , pas un produit scalaire. vérifié avec le code ici: stackoverflow.com/questions/2533011/…
ericsoco
4
notez également que la première moitié de cette réponse teste l'intersection avec une ligne, pas un segment de ligne (comme demandé dans la question).
ericsoco
8

J'ai écrit un petit script pour tester l'intersection en projetant le point central du cercle sur la ligne.

vector distVector = centerPoint - projectedPoint;
if(distVector.length() < circle.radius)
{
    double distance = circle.radius - distVector.length();
    vector moveVector = distVector.normalize() * distance;
    circle.move(moveVector);
}

http://jsfiddle.net/ercang/ornh3594/1/

Si vous devez vérifier la collision avec le segment, vous devez également tenir compte de la distance du centre du cercle aux points de début et de fin.

vector distVector = centerPoint - startPoint;
if(distVector.length() < circle.radius)
{
    double distance = circle.radius - distVector.length();
    vector moveVector = distVector.normalize() * distance;
    circle.move(moveVector);
}

https://jsfiddle.net/ercang/menp0991/

ercang
la source
5

Cette solution que j'ai trouvée semblait un peu plus facile à suivre que certaines des autres.

Prise:

p1 and p2 as the points for the line, and
c as the center point for the circle and r for the radius

Je résoudrais l'équation de la droite sous forme d'interception de pente. Cependant, je ne voulais pas avoir à traiter des équations difficiles avec ccomme point, alors j'ai juste déplacé le système de coordonnées pour que le cercle soit à0,0

p3 = p1 - c
p4 = p2 - c

Soit dit en passant, chaque fois que je soustrais des points les uns des autres , je suis soustrayant le x« s, puis en soustrayant les y» s, et les mettre en un nouveau point, juste au cas où quelqu'un ne savait pas.

Quoi qu'il en soit, je résous maintenant l'équation de la droite avec p3et p4:

m = (p4_y - p3_y) / (p4_x - p3) (the underscore is an attempt at subscript)
y = mx + b
y - mx = b (just put in a point for x and y, and insert the m we found)

D'accord. Maintenant, je dois définir ces équations égales. Je dois d'abord résoudre l'équation du cercle pourx

x^2 + y^2 = r^2
y^2 = r^2 - x^2
y = sqrt(r^2 - x^2)

Ensuite, je les mets égaux:

mx + b = sqrt(r^2 - x^2)

Et résolvez l'équation quadratique ( 0 = ax^2 + bx + c):

(mx + b)^2 = r^2 - x^2
(mx)^2 + 2mbx + b^2 = r^2 - x^2
0 = m^2 * x^2 + x^2 + 2mbx + b^2 - r^2
0 = (m^2 + 1) * x^2 + 2mbx + b^2 - r^2

Maintenant , j'ai mon a, bet c.

a = m^2 + 1
b = 2mb
c = b^2 - r^2

J'ai donc mis cela dans la formule quadratique:

(-b ± sqrt(b^2 - 4ac)) / 2a

Et substituez les valeurs par par puis simplifiez autant que possible:

(-2mb ± sqrt(b^2 - 4ac)) / 2a
(-2mb ± sqrt((-2mb)^2 - 4(m^2 + 1)(b^2 - r^2))) / 2(m^2 + 1)
(-2mb ± sqrt(4m^2 * b^2 - 4(m^2 * b^2 - m^2 * r^2 + b^2 - r^2))) / 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * b^2 - (m^2 * b^2 - m^2 * r^2 + b^2 - r^2))))/ 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * b^2 - m^2 * b^2 + m^2 * r^2 - b^2 + r^2)))/ 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * r^2 - b^2 + r^2)))/ 2m^2 + 2
(-2mb ± sqrt(4) * sqrt(m^2 * r^2 - b^2 + r^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(m^2 * r^2 - b^2 + r^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(m^2 * r^2 + r^2 - b^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2

C'est presque aussi loin que cela simplifie. Enfin, séparez-vous des équations avec le ±:

(-2mb + 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2 or     
(-2mb - 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2 

Ensuite , branchez simplement le résultat de ces deux équations dans l' xen mx + b. Pour plus de clarté, j'ai écrit du code JavaScript pour montrer comment l'utiliser:

function interceptOnCircle(p1,p2,c,r){
    //p1 is the first line point
    //p2 is the second line point
    //c is the circle's center
    //r is the circle's radius

    var p3 = {x:p1.x - c.x, y:p1.y - c.y} //shifted line points
    var p4 = {x:p2.x - c.x, y:p2.y - c.y}

    var m = (p4.y - p3.y) / (p4.x - p3.x); //slope of the line
    var b = p3.y - m * p3.x; //y-intercept of line

    var underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2)); //the value under the square root sign 

    if (underRadical < 0){
    //line completely missed
        return false;
    } else {
        var t1 = (-2*m*b+2*Math.sqrt(underRadical))/(2 * Math.pow(m,2) + 2); //one of the intercept x's
        var t2 = (-2*m*b-2*Math.sqrt(underRadical))/(2 * Math.pow(m,2) + 2); //other intercept's x
        var i1 = {x:t1,y:m*t1+b} //intercept point 1
        var i2 = {x:t2,y:m*t2+b} //intercept point 2
        return [i1,i2];
    }
}

J'espère que ça aide!

PS Si quelqu'un trouve des erreurs ou a des suggestions, veuillez commenter. Je suis très nouveau et j'accueille toute aide / suggestion.

multitaskPro
la source
Si possible, publiez également avec quelques exemples de valeurs afin que nous puissions saisir rapidement le flux.
Prabindh
Avec underRadicalextra ')'
byJeevan
4

Vous pouvez trouver un point sur une ligne infinie le plus proche du centre du cercle en projetant le vecteur AC sur le vecteur AB. Calculez la distance entre ce point et le centre du cercle. S'il est supérieur à R, il n'y a pas d'intersection. Si la distance est égale à R, la ligne est une tangente du cercle et le point le plus proche du centre du cercle est en fait le point d'intersection. Si la distance est inférieure à R, alors il y a 2 points d'intersection. Ils se trouvent à la même distance du point le plus proche du centre du cercle. Cette distance peut facilement être calculée en utilisant le théorème de Pythagore. Voici l'algorithme en pseudocode:

{
dX = bX - aX;
dY = bY - aY;
if ((dX == 0) && (dY == 0))
  {
  // A and B are the same points, no way to calculate intersection
  return;
  }

dl = (dX * dX + dY * dY);
t = ((cX - aX) * dX + (cY - aY) * dY) / dl;

// point on a line nearest to circle center
nearestX = aX + t * dX;
nearestY = aY + t * dY;

dist = point_dist(nearestX, nearestY, cX, cY);

if (dist == R)
  {
  // line segment touches circle; one intersection point
  iX = nearestX;
  iY = nearestY;

  if (t < 0 || t > 1)
    {
    // intersection point is not actually within line segment
    }
  }
else if (dist < R)
  {
  // two possible intersection points

  dt = sqrt(R * R - dist * dist) / sqrt(dl);

  // intersection point nearest to A
  t1 = t - dt;
  i1X = aX + t1 * dX;
  i1Y = aY + t1 * dY;
  if (t1 < 0 || t1 > 1)
    {
    // intersection point is not actually within line segment
    }

  // intersection point farthest from A
  t2 = t + dt;
  i2X = aX + t2 * dX;
  i2Y = aY + t2 * dY;
  if (t2 < 0 || t2 > 1)
    {
    // intersection point is not actually within line segment
    }
  }
else
  {
  // no intersection
  }
}

EDIT: code ajouté pour vérifier si les points d'intersection trouvés se trouvent réellement dans le segment de ligne.

Juozas Kontvainis
la source
Vous avez manqué un cas puisque nous parlons d'un segment de ligne: lorsque le segment se termine dans le cercle.
ADB
@ADB en fait mon algorithme ne fonctionne que pour les lignes infinies, pas pour les segments de ligne. Il existe de nombreux cas qu'il ne gère pas avec des segments de ligne.
Juozas Kontvainis
La question initiale portait sur les segments de ligne, et non sur l'intersection de lignes de cercle, ce qui est un problème beaucoup plus facile.
msumme
4

Bizarrement, je peux répondre mais pas commenter ... J'ai aimé l'approche de Multitaskpro consistant à tout déplacer pour faire tomber le centre du cercle sur l'origine. Malheureusement, il y a deux problèmes dans son code. Tout d'abord dans la partie sous la racine carrée, vous devez supprimer la double puissance. Alors non:

var underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2));

mais:

var underRadical = Math.pow(r,2)*(Math.pow(m,2)+1)) - Math.pow(b,2);

Dans les coordonnées finales, il oublie de reculer la solution. Alors non:

var i1 = {x:t1,y:m*t1+b}

mais:

var i1 = {x:t1+c.x, y:m*t1+b+c.y};

L'ensemble de la fonction devient alors:

function interceptOnCircle(p1, p2, c, r) {
    //p1 is the first line point
    //p2 is the second line point
    //c is the circle's center
    //r is the circle's radius

    var p3 = {x:p1.x - c.x, y:p1.y - c.y}; //shifted line points
    var p4 = {x:p2.x - c.x, y:p2.y - c.y};

    var m = (p4.y - p3.y) / (p4.x - p3.x); //slope of the line
    var b = p3.y - m * p3.x; //y-intercept of line

    var underRadical = Math.pow(r,2)*Math.pow(m,2) + Math.pow(r,2) - Math.pow(b,2); //the value under the square root sign 

    if (underRadical < 0) {
        //line completely missed
        return false;
    } else {
        var t1 = (-m*b + Math.sqrt(underRadical))/(Math.pow(m,2) + 1); //one of the intercept x's
        var t2 = (-m*b - Math.sqrt(underRadical))/(Math.pow(m,2) + 1); //other intercept's x
        var i1 = {x:t1+c.x, y:m*t1+b+c.y}; //intercept point 1
        var i2 = {x:t2+c.x, y:m*t2+b+c.y}; //intercept point 2
        return [i1, i2];
    }
}
Duq
la source
1
suggestions: Tout d'abord, demandez-lui de gérer le cas où le segment de ligne est vertical (c'est-à-dire à pente infinie). Deuxièmement, il ne doit renvoyer que les points qui se situent réellement dans la plage du segment de ligne d'origine - je pense qu'il retourne avec plaisir tous les points qui tombent sur la ligne infinie, même si ces points se trouvent en dehors du segment de ligne.
Gino
Remarque: cela fonctionne bien pour les lignes, mais pas pour les segments de ligne.
Mike
3

Vous aurez besoin de quelques calculs ici:

Supposons que A = (Xa, Ya), B = (Xb, Yb) et C = (Xc, Yc). Tout point sur la ligne de A à B a des coordonnées (alpha * Xa + (1-alpha) Xb, alpha Ya + (1-alpha) * Yb) = P

Si le point P a la distance R à C, il doit être sur le cercle. Ce que tu veux c'est résoudre

distance(P, C) = R

C'est

(alpha*Xa + (1-alpha)*Xb)^2 + (alpha*Ya + (1-alpha)*Yb)^2 = R^2
alpha^2*Xa^2 + alpha^2*Xb^2 - 2*alpha*Xb^2 + Xb^2 + alpha^2*Ya^2 + alpha^2*Yb^2 - 2*alpha*Yb^2 + Yb^2=R^2
(Xa^2 + Xb^2 + Ya^2 + Yb^2)*alpha^2 - 2*(Xb^2 + Yb^2)*alpha + (Xb^2 + Yb^2 - R^2) = 0

si vous appliquez la formule ABC à cette équation pour la résoudre en alpha et calculez les coordonnées de P en utilisant la ou les solutions pour alpha, vous obtenez les points d'intersection, s'il en existe.

Martijn
la source
3

Si vous trouvez la distance entre le centre de la sphère (puisque c'est 3D, je suppose que vous voulez dire sphère et non cercle) et la ligne, vérifiez si cette distance est inférieure au rayon qui fera l'affaire.

Le point de collision est évidemment le point le plus proche entre la ligne et la sphère (qui sera calculé lorsque vous calculez la distance entre la sphère et la ligne)

Distance entre un point et une ligne:
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

Martin
la source
1
C'est en 2D, pas en 3D; comme vous le dites, cela n'a pas vraiment d'importance
Martijn
Je ne suis pas un mathématicien, j'ai donc pensé que je ferais mieux de décrire une approche générale et de laisser le soin aux autres de trouver des mathématiques spécifiques (même si j'ai l'air plutôt trivial)
Martin
2
+1 avec une forte augmentation. (bien que j'aurais lié à un autre site, le site pbourke semble déroutant) Toutes les autres réponses jusqu'à présent sont trop compliquées. Bien que votre commentaire "Ce point est également le point d'intersection sur la ligne" soit incorrect, aucun point n'a été construit dans le processus de calcul.
Jason S
J'ai expliqué un peu mieux le point le plus proche, et lié à mathworld au lieu de pbourke :)
Martin
3

Voici une implémentation en Javascript. Mon approche consiste à convertir d'abord le segment de ligne en une ligne infinie, puis à trouver le ou les points d'intersection. De là, je vérifie si les points trouvés se trouvent sur le segment de ligne. Le code est bien documenté, vous devriez pouvoir suivre.

Vous pouvez essayer le code ici sur cette démo en direct . Le code a été tiré de mon dépôt d'algorithmes .

entrez la description de l'image ici

// Small epsilon value
var EPS = 0.0000001;

// point (x, y)
function Point(x, y) {
  this.x = x;
  this.y = y;
}

// Circle with center at (x,y) and radius r
function Circle(x, y, r) {
  this.x = x;
  this.y = y;
  this.r = r;
}

// A line segment (x1, y1), (x2, y2)
function LineSegment(x1, y1, x2, y2) {
  var d = Math.sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
  if (d < EPS) throw 'A point is not a line segment';
  this.x1 = x1; this.y1 = y1;
  this.x2 = x2; this.y2 = y2;
}

// An infinite line defined as: ax + by = c
function Line(a, b, c) {
  this.a = a; this.b = b; this.c = c;
  // Normalize line for good measure
  if (Math.abs(b) < EPS) {
    c /= a; a = 1; b = 0;
  } else { 
    a = (Math.abs(a) < EPS) ? 0 : a / b;
    c /= b; b = 1; 
  }
}

// Given a line in standard form: ax + by = c and a circle with 
// a center at (x,y) with radius r this method finds the intersection
// of the line and the circle (if any). 
function circleLineIntersection(circle, line) {

  var a = line.a, b = line.b, c = line.c;
  var x = circle.x, y = circle.y, r = circle.r;

  // Solve for the variable x with the formulas: ax + by = c (equation of line)
  // and (x-X)^2 + (y-Y)^2 = r^2 (equation of circle where X,Y are known) and expand to obtain quadratic:
  // (a^2 + b^2)x^2 + (2abY - 2ac + - 2b^2X)x + (b^2X^2 + b^2Y^2 - 2bcY + c^2 - b^2r^2) = 0
  // Then use quadratic formula X = (-b +- sqrt(a^2 - 4ac))/2a to find the 
  // roots of the equation (if they exist) and this will tell us the intersection points

  // In general a quadratic is written as: Ax^2 + Bx + C = 0
  // (a^2 + b^2)x^2 + (2abY - 2ac + - 2b^2X)x + (b^2X^2 + b^2Y^2 - 2bcY + c^2 - b^2r^2) = 0
  var A = a*a + b*b;
  var B = 2*a*b*y - 2*a*c - 2*b*b*x;
  var C = b*b*x*x + b*b*y*y - 2*b*c*y + c*c - b*b*r*r;

  // Use quadratic formula x = (-b +- sqrt(a^2 - 4ac))/2a to find the 
  // roots of the equation (if they exist).

  var D = B*B - 4*A*C;
  var x1,y1,x2,y2;

  // Handle vertical line case with b = 0
  if (Math.abs(b) < EPS) {

    // Line equation is ax + by = c, but b = 0, so x = c/a
    x1 = c/a;

    // No intersection
    if (Math.abs(x-x1) > r) return [];

    // Vertical line is tangent to circle
    if (Math.abs((x1-r)-x) < EPS || Math.abs((x1+r)-x) < EPS)
      return [new Point(x1, y)];

    var dx = Math.abs(x1 - x);
    var dy = Math.sqrt(r*r-dx*dx);

    // Vertical line cuts through circle
    return [
      new Point(x1,y+dy),
      new Point(x1,y-dy)
    ];

  // Line is tangent to circle
  } else if (Math.abs(D) < EPS) {

    x1 = -B/(2*A);
    y1 = (c - a*x1)/b;

    return [new Point(x1,y1)];

  // No intersection
  } else if (D < 0) {

    return [];

  } else {

    D = Math.sqrt(D);

    x1 = (-B+D)/(2*A);
    y1 = (c - a*x1)/b;

    x2 = (-B-D)/(2*A);
    y2 = (c - a*x2)/b;

    return [
      new Point(x1, y1),
      new Point(x2, y2)
    ];

  }

}

// Converts a line segment to a line in general form
function segmentToGeneralForm(x1,y1,x2,y2) {
  var a = y1 - y2;
  var b = x2 - x1;
  var c = x2*y1 - x1*y2;
  return new Line(a,b,c);
}

// Checks if a point 'pt' is inside the rect defined by (x1,y1), (x2,y2)
function pointInRectangle(pt,x1,y1,x2,y2) {
  var x = Math.min(x1,x2), X = Math.max(x1,x2);
  var y = Math.min(y1,y2), Y = Math.max(y1,y2);
  return x - EPS <= pt.x && pt.x <= X + EPS &&
         y - EPS <= pt.y && pt.y <= Y + EPS;
}

// Finds the intersection(s) of a line segment and a circle
function lineSegmentCircleIntersection(segment, circle) {

  var x1 = segment.x1, y1 = segment.y1, x2 = segment.x2, y2 = segment.y2;
  var line = segmentToGeneralForm(x1,y1,x2,y2);
  var pts = circleLineIntersection(circle, line);

  // No intersection
  if (pts.length === 0) return [];

  var pt1 = pts[0];
  var includePt1 = pointInRectangle(pt1,x1,y1,x2,y2);

  // Check for unique intersection
  if (pts.length === 1) {
    if (includePt1) return [pt1];
    return [];
  }

  var pt2 = pts[1];
  var includePt2 = pointInRectangle(pt2,x1,y1,x2,y2);

  // Check for remaining intersections
  if (includePt1 && includePt2) return [pt1, pt2];
  if (includePt1) return [pt1];
  if (includePt2) return [pt2];
  return [];

}
will.fiset
la source
3

Dans ce cas, la collision de lignes post-cercle sera vérifiée en vérifiant la distance entre le centre du cercle et le point sur le segment de ligne (Ipoint) qui représente le point d'intersection entre la normale N (image 2) du centre du cercle au segment de ligne.

( https://i.stack.imgur.com/3o6do.png )Image 1. Recherche des vecteurs E et D

Sur l'image 1, un cercle et une ligne sont représentés, vecteur A point à point de départ, vecteur B point à point de fin de ligne, vecteur C point à centre de cercle. Maintenant, nous devons trouver le vecteur E (du point de départ de la ligne au centre du cercle) et le vecteur D (du point de départ de la ligne au point d'arrivée de la ligne) ce calcul est montré sur l'image 1.

( https://i.stack.imgur.com/7098a.png )Image 2. Recherche du vecteur X

Sur l'image 2, nous pouvons voir que le vecteur E est projeté sur le vecteur D par le "produit scalaire" du vecteur E et le vecteur unitaire D, le résultat du produit scalaire est scalaire Xp qui représente la distance entre le point de départ de la ligne et le point d'intersection (Ipoint) de le vecteur N et le vecteur D. Le vecteur X suivant est trouvé en multipliant le vecteur unitaire D et le scalaire Xp.

Maintenant, nous devons trouver le vecteur Z (vecteur vers Ipoint), sa simple addition vectorielle simple du vecteur A (point de départ en ligne) et du vecteur X. Ensuite, nous devons traiter des cas spéciaux, nous devons vérifier si Ipoint sur le segment de ligne, si ce n'est pas que nous devons savoir s'il est à gauche ou à droite de celui-ci, nous utiliserons le vecteur le plus proche pour déterminer quel point est le plus proche du cercle.

( https://i.stack.imgur.com/p9WIr.png )Image 3. Trouver le point le plus proche

Lorsque la projection Xp est négative, Ipoint est à gauche du segment de ligne, le vecteur le plus proche est égal au vecteur du point de départ de la ligne, lorsque la projection Xp est supérieure à la magnitude du vecteur D, puis Ipoint est à droite du segment de ligne, puis le vecteur le plus proche est égal au vecteur de fin de ligne dans tout autre cas, le vecteur le plus proche est égal au vecteur Z.

Maintenant, lorsque nous avons le vecteur le plus proche, nous devons trouver le vecteur du centre du cercle au point I (vecteur dist), il suffit de soustraire le vecteur le plus proche du vecteur central. Ensuite, vérifiez simplement si la magnitude du vecteur dist est inférieure au rayon du cercle si c'est le cas, ils entrent en collision, sinon, il n'y a pas de collision.

( https://i.stack.imgur.com/QJ63q.png )Image 4. Vérification de la collision

Pour finir, nous pouvons renvoyer quelques valeurs pour résoudre la collision, le moyen le plus simple est de retourner le chevauchement de la collision (soustraire le rayon de la magnitude du vecteur dist) et de renvoyer l'axe de collision, son vecteur D.Le point d'intersection est également le vecteur Z si nécessaire.

FunDeveloper89
la source
2

Si les coordonnées de la ligne sont Ax, Ay et Bx, By et que le centre des cercles est Cx, Cy alors les formules des lignes sont:

x = Axe * t + Bx * (1 - t)

y = Ay * t + By * (1 - t)

où 0 <= t <= 1

et le cercle est

(Cx - x) ^ 2 + (Cy - y) ^ 2 = R ^ 2

si vous substituez les formules x et y de la ligne dans la formule des cercles, vous obtenez une équation de second ordre de t et ses solutions sont les points d'intersection (s'il y en a). Si vous obtenez une valeur inférieure à 0 ou supérieure à 1, ce n'est pas une solution, mais cela montre que la ligne "pointe" vers la direction du cercle.

Gábor Hargitai
la source
2

Juste un ajout à ce fil ... Voici une version du code posté par pahlevan, mais pour C # / XNA et remanié un peu:

    /// <summary>
    /// Intersects a line and a circle.
    /// </summary>
    /// <param name="location">the location of the circle</param>
    /// <param name="radius">the radius of the circle</param>
    /// <param name="lineFrom">the starting point of the line</param>
    /// <param name="lineTo">the ending point of the line</param>
    /// <returns>true if the line and circle intersect each other</returns>
    public static bool IntersectLineCircle(Vector2 location, float radius, Vector2 lineFrom, Vector2 lineTo)
    {
        float ab2, acab, h2;
        Vector2 ac = location - lineFrom;
        Vector2 ab = lineTo - lineFrom;
        Vector2.Dot(ref ab, ref ab, out ab2);
        Vector2.Dot(ref ac, ref ab, out acab);
        float t = acab / ab2;

        if (t < 0)
            t = 0;
        else if (t > 1)
            t = 1;

        Vector2 h = ((ab * t) + lineFrom) - location;
        Vector2.Dot(ref h, ref h, out h2);

        return (h2 <= (radius * radius));
    }
Rob
la source
En C # / XNA, vous pouvez utiliserRay.Intersects(BoundingSphere)
bobobobo
2

entrez la description de l'image ici

' VB.NET - Code

Function CheckLineSegmentCircleIntersection(x1 As Double, y1 As Double, x2 As Double, y2 As Double, xc As Double, yc As Double, r As Double) As Boolean
    Static xd As Double = 0.0F
    Static yd As Double = 0.0F
    Static t As Double = 0.0F
    Static d As Double = 0.0F
    Static dx_2_1 As Double = 0.0F
    Static dy_2_1 As Double = 0.0F

    dx_2_1 = x2 - x1
    dy_2_1 = y2 - y1

    t = ((yc - y1) * dy_2_1 + (xc - x1) * dx_2_1) / (dy_2_1 * dy_2_1 + dx_2_1 * dx_2_1)

    If 0 <= t And t <= 1 Then
        xd = x1 + t * dx_2_1
        yd = y1 + t * dy_2_1

        d = Math.Sqrt((xd - xc) * (xd - xc) + (yd - yc) * (yd - yc))
        Return d <= r
    Else
        d = Math.Sqrt((xc - x1) * (xc - x1) + (yc - y1) * (yc - y1))
        If d <= r Then
            Return True
        Else
            d = Math.Sqrt((xc - x2) * (xc - x2) + (yc - y2) * (yc - y2))
            If d <= r Then
                Return True
            Else
                Return False
            End If
        End If
    End If
End Function
AJBauer
la source
2

J'ai créé cette fonction pour iOS suite à la réponse donnée par chmike

+ (NSArray *)intersectionPointsOfCircleWithCenter:(CGPoint)center withRadius:(float)radius toLinePoint1:(CGPoint)p1 andLinePoint2:(CGPoint)p2
{
    NSMutableArray *intersectionPoints = [NSMutableArray array];

    float Ax = p1.x;
    float Ay = p1.y;
    float Bx = p2.x;
    float By = p2.y;
    float Cx = center.x;
    float Cy = center.y;
    float R = radius;


    // compute the euclidean distance between A and B
    float LAB = sqrt( pow(Bx-Ax, 2)+pow(By-Ay, 2) );

    // compute the direction vector D from A to B
    float Dx = (Bx-Ax)/LAB;
    float Dy = (By-Ay)/LAB;

    // Now the line equation is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= 1.

    // compute the value t of the closest point to the circle center (Cx, Cy)
    float t = Dx*(Cx-Ax) + Dy*(Cy-Ay);

    // This is the projection of C on the line from A to B.

    // compute the coordinates of the point E on line and closest to C
    float Ex = t*Dx+Ax;
    float Ey = t*Dy+Ay;

    // compute the euclidean distance from E to C
    float LEC = sqrt( pow(Ex-Cx, 2)+ pow(Ey-Cy, 2) );

    // test if the line intersects the circle
    if( LEC < R )
    {
        // compute distance from t to circle intersection point
        float dt = sqrt( pow(R, 2) - pow(LEC,2) );

        // compute first intersection point
        float Fx = (t-dt)*Dx + Ax;
        float Fy = (t-dt)*Dy + Ay;

        // compute second intersection point
        float Gx = (t+dt)*Dx + Ax;
        float Gy = (t+dt)*Dy + Ay;

        [intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Fx, Fy)]];
        [intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Gx, Gy)]];
    }

    // else test if the line is tangent to circle
    else if( LEC == R ) {
        // tangent point to circle is E
        [intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Ex, Ey)]];
    }
    else {
        // line doesn't touch circle
    }

    return intersectionPoints;
}
Aqib Mumtaz
la source
2

Un autre en c # (classe Circle partielle). Testé et fonctionne comme un charme.

public class Circle : IEquatable<Circle>
{
    // ******************************************************************
    // The center of a circle
    private Point _center;
    // The radius of a circle
    private double _radius;

   // ******************************************************************
    /// <summary>
    /// Find all intersections (0, 1, 2) of the circle with a line defined by its 2 points.
    /// Using: http://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle
    /// Note: p is the Center.X and q is Center.Y
    /// </summary>
    /// <param name="linePoint1"></param>
    /// <param name="linePoint2"></param>
    /// <returns></returns>
    public List<Point> GetIntersections(Point linePoint1, Point linePoint2)
    {
        List<Point> intersections = new List<Point>();

        double dx = linePoint2.X - linePoint1.X;

        if (dx.AboutEquals(0)) // Straight vertical line
        {
            if (linePoint1.X.AboutEquals(Center.X - Radius) || linePoint1.X.AboutEquals(Center.X + Radius))
            {
                Point pt = new Point(linePoint1.X, Center.Y);
                intersections.Add(pt);
            }
            else if (linePoint1.X > Center.X - Radius && linePoint1.X < Center.X + Radius)
            {
                double x = linePoint1.X - Center.X;

                Point pt = new Point(linePoint1.X, Center.Y + Math.Sqrt(Radius * Radius - (x * x)));
                intersections.Add(pt);

                pt = new Point(linePoint1.X, Center.Y - Math.Sqrt(Radius * Radius - (x * x)));
                intersections.Add(pt);
            }

            return intersections;
        }

        // Line function (y = mx + b)
        double dy = linePoint2.Y - linePoint1.Y;
        double m = dy / dx;
        double b = linePoint1.Y - m * linePoint1.X;

        double A = m * m + 1;
        double B = 2 * (m * b - m * _center.Y - Center.X);
        double C = Center.X * Center.X + Center.Y * Center.Y - Radius * Radius - 2 * b * Center.Y + b * b;

        double discriminant = B * B - 4 * A * C;

        if (discriminant < 0)
        {
            return intersections; // there is no intersections
        }

        if (discriminant.AboutEquals(0)) // Tangeante (touch on 1 point only)
        {
            double x = -B / (2 * A);
            double y = m * x + b;

            intersections.Add(new Point(x, y));
        }
        else // Secant (touch on 2 points)
        {
            double x = (-B + Math.Sqrt(discriminant)) / (2 * A);
            double y = m * x + b;
            intersections.Add(new Point(x, y));

            x = (-B - Math.Sqrt(discriminant)) / (2 * A);
            y = m * x + b;
            intersections.Add(new Point(x, y));
        }

        return intersections;
    }

    // ******************************************************************
    // Get the center
    [XmlElement("Center")]
    public Point Center
    {
        get { return _center; }
        set
        {
            _center = value;
        }
    }

    // ******************************************************************
    // Get the radius
    [XmlElement]
    public double Radius
    {
        get { return _radius; }
        set { _radius = value; }
    }

    //// ******************************************************************
    //[XmlArrayItemAttribute("DoublePoint")]
    //public List<Point> Coordinates
    //{
    //    get { return _coordinates; }
    //}

    // ******************************************************************
    // Construct a circle without any specification
    public Circle()
    {
        _center.X = 0;
        _center.Y = 0;
        _radius = 0;
    }

    // ******************************************************************
    // Construct a circle without any specification
    public Circle(double radius)
    {
        _center.X = 0;
        _center.Y = 0;
        _radius = radius;
    }

    // ******************************************************************
    // Construct a circle with the specified circle
    public Circle(Circle circle)
    {
        _center = circle._center;
        _radius = circle._radius;
    }

    // ******************************************************************
    // Construct a circle with the specified center and radius
    public Circle(Point center, double radius)
    {
        _center = center;
        _radius = radius;
    }

    // ******************************************************************
    // Construct a circle based on one point
    public Circle(Point center)
    {
        _center = center;
        _radius = 0;
    }

    // ******************************************************************
    // Construct a circle based on two points
    public Circle(Point p1, Point p2)
    {
        Circle2Points(p1, p2);
    }

Obligatoire:

using System;

namespace Mathematic
{
    public static class DoubleExtension
    {
        // ******************************************************************
        // Base on Hans Passant Answer on:
        // http://stackoverflow.com/questions/2411392/double-epsilon-for-equality-greater-than-less-than-less-than-or-equal-to-gre

        /// <summary>
        /// Compare two double taking in account the double precision potential error.
        /// Take care: truncation errors accumulate on calculation. More you do, more you should increase the epsilon.
        public static bool AboutEquals(this double value1, double value2)
        {
            if (double.IsPositiveInfinity(value1))
                return double.IsPositiveInfinity(value2);

            if (double.IsNegativeInfinity(value1))
                return double.IsNegativeInfinity(value2);

            if (double.IsNaN(value1))
                return double.IsNaN(value2);

            double epsilon = Math.Max(Math.Abs(value1), Math.Abs(value2)) * 1E-15;
            return Math.Abs(value1 - value2) <= epsilon;
        }

        // ******************************************************************
        // Base on Hans Passant Answer on:
        // http://stackoverflow.com/questions/2411392/double-epsilon-for-equality-greater-than-less-than-less-than-or-equal-to-gre

        /// <summary>
        /// Compare two double taking in account the double precision potential error.
        /// Take care: truncation errors accumulate on calculation. More you do, more you should increase the epsilon.
        /// You get really better performance when you can determine the contextual epsilon first.
        /// </summary>
        /// <param name="value1"></param>
        /// <param name="value2"></param>
        /// <param name="precalculatedContextualEpsilon"></param>
        /// <returns></returns>
        public static bool AboutEquals(this double value1, double value2, double precalculatedContextualEpsilon)
        {
            if (double.IsPositiveInfinity(value1))
                return double.IsPositiveInfinity(value2);

            if (double.IsNegativeInfinity(value1))
                return double.IsNegativeInfinity(value2);

            if (double.IsNaN(value1))
                return double.IsNaN(value2);

            return Math.Abs(value1 - value2) <= precalculatedContextualEpsilon;
        }

        // ******************************************************************
        public static double GetContextualEpsilon(this double biggestPossibleContextualValue)
        {
            return biggestPossibleContextualValue * 1E-15;
        }

        // ******************************************************************
        /// <summary>
        /// Mathlab equivalent
        /// </summary>
        /// <param name="dividend"></param>
        /// <param name="divisor"></param>
        /// <returns></returns>
        public static double Mod(this double dividend, double divisor)
        {
            return dividend - System.Math.Floor(dividend / divisor) * divisor;
        }

        // ******************************************************************
    }
}
Eric Ouellet
la source
2

Voici une bonne solution en JavaScript (avec toutes les mathématiques requises et l'illustration en direct) https://bl.ocks.org/milkbread/11000965

Bien que la is_onfonction dans cette solution nécessite des modifications:

function is_on(a, b, c) {
    return Math.abs(distance(a,c) + distance(c,b) - distance(a,b))<0.000001;
}

nazar kuliyev
la source
2

Le cercle est vraiment un méchant :) Donc, un bon moyen est d'éviter le vrai cercle, si vous le pouvez. Si vous effectuez un contrôle de collision pour les jeux, vous pouvez opter pour quelques simplifications et n'avoir que 3 produits scalaires et quelques comparaisons.

J'appelle cela "point gras" ou "cercle mince". son genre d'ellipse de rayon nul dans une direction parallèle à un segment. mais plein rayon dans une direction perpendiculaire à un segment

Tout d'abord, j'envisagerais de renommer et de changer de système de coordonnées pour éviter des données excessives:

s0s1 = B-A;
s0qp = C-A;
rSqr = r*r;

Deuxièmement, l'index h dans hvec2f signifie que le vecteur doit favoriser les opérations horizontales, comme dot () / det (). Ce qui signifie que ses composants doivent être placés dans des registres xmm séparés, pour éviter de mélanger / hadd'ing / hsub'ing. Et c'est parti, avec la version la plus performante de la détection de collision la plus simple pour les jeux 2D:

bool fat_point_collides_segment(const hvec2f& s0qp, const hvec2f& s0s1, const float& rSqr) {
    auto a = dot(s0s1, s0s1);
    //if( a != 0 ) // if you haven't zero-length segments omit this, as it would save you 1 _mm_comineq_ss() instruction and 1 memory fetch
    {
        auto b = dot(s0s1, s0qp);
        auto t = b / a; // length of projection of s0qp onto s0s1
        //std::cout << "t = " << t << "\n";
        if ((t >= 0) && (t <= 1)) // 
        {
            auto c = dot(s0qp, s0qp);
            auto r2 = c - a * t * t;
            return (r2 <= rSqr); // true if collides
        }
    }   
    return false;
}

Je doute que vous puissiez l'optimiser davantage. Je l'utilise pour la détection de collisions de course automobile pilotée par un réseau de neurones, pour traiter des millions de millions d'étapes d'itération.

xakepp35
la source
Si le segment de ligne intersecte le cercle mais seulement légèrement pour qu'il ne dépasse pas son point central, cette fonction ne retournera-t-elle pas faux alors qu'elle devrait retourner vrai? La valeur t peut être en dehors de la plage 0..1.
Chris
1

Cette fonction Java renvoie un objet DVec2. Il faut un DVec2 pour le centre du cercle, le rayon du cercle et une ligne.

public static DVec2 CircLine(DVec2 C, double r, Line line)
{
    DVec2 A = line.p1;
    DVec2 B = line.p2;
    DVec2 P;
    DVec2 AC = new DVec2( C );
    AC.sub(A);
    DVec2 AB = new DVec2( B );
    AB.sub(A);
    double ab2 = AB.dot(AB);
    double acab = AC.dot(AB);
    double t = acab / ab2;

    if (t < 0.0) 
        t = 0.0;
    else if (t > 1.0) 
        t = 1.0;

    //P = A + t * AB;
    P = new DVec2( AB );
    P.mul( t );
    P.add( A );

    DVec2 H = new DVec2( P );
    H.sub( C );
    double h2 = H.dot(H);
    double r2 = r * r;

    if(h2 > r2) 
        return null;
    else
        return P;
}
pahlevan
la source
1

Voici ma solution en TypeScript, suivant l'idée suggérée par @Mizipzor (en utilisant la projection):

/**
 * Determines whether a line segment defined by a start and end point intersects with a sphere defined by a center point and a radius
 * @param a the start point of the line segment
 * @param b the end point of the line segment
 * @param c the center point of the sphere
 * @param r the radius of the sphere
 */
export function lineSphereIntersects(
  a: IPoint,
  b: IPoint,
  c: IPoint,
  r: number
): boolean {
  // find the three sides of the triangle formed by the three points
  const ab: number = distance(a, b);
  const ac: number = distance(a, c);
  const bc: number = distance(b, c);

  // check to see if either ends of the line segment are inside of the sphere
  if (ac < r || bc < r) {
    return true;
  }

  // find the angle between the line segment and the center of the sphere
  const numerator: number = Math.pow(ac, 2) + Math.pow(ab, 2) - Math.pow(bc, 2);
  const denominator: number = 2 * ac * ab;
  const cab: number = Math.acos(numerator / denominator);

  // find the distance from the center of the sphere and the line segment
  const cd: number = Math.sin(cab) * ac;

  // if the radius is at least as long as the distance between the center and the line
  if (r >= cd) {
    // find the distance between the line start and the point on the line closest to
    // the center of the sphere
    const ad: number = Math.cos(cab) * ac;
    // intersection occurs when the point on the line closest to the sphere center is
    // no further away than the end of the line
    return ad <= ab;
  }
  return false;
}

export function distance(a: IPoint, b: IPoint): number {
  return Math.sqrt(
    Math.pow(b.z - a.z, 2) + Math.pow(b.y - a.y, 2) + Math.pow(b.x - a.x, 2)
  );
}

export interface IPoint {
  x: number;
  y: number;
  z: number;
}
Joe Skeen
la source
1

Je sais que cela fait un moment que ce fil n'a pas été ouvert. D'après la réponse donnée par chmike et améliorée par Aqib Mumtaz. Ils donnent une bonne réponse mais ne fonctionnent que pour une ligne infinie comme l'a dit Aqib. J'ajoute donc quelques comparaisons pour savoir si le segment de ligne touche le cercle, je l'écris en Python.

def LineIntersectCircle(c, r, p1, p2):
    #p1 is the first line point
    #p2 is the second line point
    #c is the circle's center
    #r is the circle's radius

    p3 = [p1[0]-c[0], p1[1]-c[1]]
    p4 = [p2[0]-c[0], p2[1]-c[1]]

    m = (p4[1] - p3[1]) / (p4[0] - p3[0])
    b = p3[1] - m * p3[0]

    underRadical = math.pow(r,2)*math.pow(m,2) + math.pow(r,2) - math.pow(b,2)

    if (underRadical < 0):
        print("NOT")
    else:
        t1 = (-2*m*b+2*math.sqrt(underRadical)) / (2 * math.pow(m,2) + 2)
        t2 = (-2*m*b-2*math.sqrt(underRadical)) / (2 * math.pow(m,2) + 2)
        i1 = [t1+c[0], m * t1 + b + c[1]]
        i2 = [t2+c[0], m * t2 + b + c[1]]

        if p1[0] > p2[0]:                                           #Si el punto 1 es mayor al 2 en X
            if (i1[0] < p1[0]) and (i1[0] > p2[0]):                 #Si el punto iX esta entre 2 y 1 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i1[1] < p1[1]) and (i1[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i1[1] > p1[1]) and (i1[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")

        if p1[0] < p2[0]:                                           #Si el punto 2 es mayor al 1 en X
            if (i1[0] > p1[0]) and (i1[0] < p2[0]):                 #Si el punto iX esta entre 1 y 2 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i1[1] < p1[1]) and (i1[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i1[1] > p1[1]) and (i1[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")

        if p1[0] > p2[0]:                                           #Si el punto 1 es mayor al 2 en X
            if (i2[0] < p1[0]) and (i2[0] > p2[0]):                 #Si el punto iX esta entre 2 y 1 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i2[1] < p1[1]) and (i2[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i2[1] > p1[1]) and (i2[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")

        if p1[0] < p2[0]:                                           #Si el punto 2 es mayor al 1 en X
            if (i2[0] > p1[0]) and (i2[0] < p2[0]):                 #Si el punto iX esta entre 1 y 2 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i2[1] < p1[1]) and (i2[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i2[1] > p1[1]) and (i2[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")
Jorge Eduardo G
la source
0

Voici une solution écrite en golang. La méthode est similaire à certaines autres réponses publiées ici, mais pas tout à fait la même. Il est facile à mettre en œuvre et a été testé. Voici les étapes:

  1. Traduire les coordonnées de sorte que le cercle soit à l'origine.
  2. Exprimez le segment de ligne sous la forme de fonctions paramétrées de t pour les coordonnées x et y. Si t est 0, les valeurs de la fonction sont un point final du segment, et si t est 1, les valeurs de la fonction sont l'autre point final.
  3. Résoudre, si possible, l'équation quadratique résultant des valeurs contraignantes de t qui produisent des coordonnées x, y avec des distances de l'origine égales au rayon du cercle.
  4. Jetez les solutions où t est <0 ou> 1 (<= 0 ou> = 1 pour un segment ouvert). Ces points ne sont pas contenus dans le segment.
  5. Revenez aux coordonnées d'origine.

Les valeurs pour A, B et C pour le quadratique sont dérivées ici, où (n-et) et (m-dt) sont les équations pour les coordonnées x et y de la ligne, respectivement. r est le rayon du cercle.

(n-et)(n-et) + (m-dt)(m-dt) = rr
nn - 2etn + etet + mm - 2mdt + dtdt = rr
(ee+dd)tt - 2(en + dm)t + nn + mm - rr = 0

Par conséquent, A = ee + dd, B = - 2 (en + dm) et C = nn + mm - rr.

Voici le code golang de la fonction:

package geom

import (
    "math"
)

// SegmentCircleIntersection return points of intersection between a circle and
// a line segment. The Boolean intersects returns true if one or
// more solutions exist. If only one solution exists, 
// x1 == x2 and y1 == y2.
// s1x and s1y are coordinates for one end point of the segment, and
// s2x and s2y are coordinates for the other end of the segment.
// cx and cy are the coordinates of the center of the circle and
// r is the radius of the circle.
func SegmentCircleIntersection(s1x, s1y, s2x, s2y, cx, cy, r float64) (x1, y1, x2, y2 float64, intersects bool) {
    // (n-et) and (m-dt) are expressions for the x and y coordinates
    // of a parameterized line in coordinates whose origin is the
    // center of the circle.
    // When t = 0, (n-et) == s1x - cx and (m-dt) == s1y - cy
    // When t = 1, (n-et) == s2x - cx and (m-dt) == s2y - cy.
    n := s2x - cx
    m := s2y - cy

    e := s2x - s1x
    d := s2y - s1y

    // lineFunc checks if the  t parameter is in the segment and if so
    // calculates the line point in the unshifted coordinates (adds back
    // cx and cy.
    lineFunc := func(t float64) (x, y float64, inBounds bool) {
        inBounds = t >= 0 && t <= 1 // Check bounds on closed segment
        // To check bounds for an open segment use t > 0 && t < 1
        if inBounds { // Calc coords for point in segment
            x = n - e*t + cx
            y = m - d*t + cy
        }
        return
    }

    // Since we want the points on the line distance r from the origin,
    // (n-et)(n-et) + (m-dt)(m-dt) = rr.
    // Expanding and collecting terms yeilds the following quadratic equation:
    A, B, C := e*e+d*d, -2*(e*n+m*d), n*n+m*m-r*r

    D := B*B - 4*A*C // discriminant of quadratic
    if D < 0 {
        return // No solution
    }
    D = math.Sqrt(D)

    var p1In, p2In bool
    x1, y1, p1In = lineFunc((-B + D) / (2 * A)) // First root
    if D == 0.0 {
        intersects = p1In
        x2, y2 = x1, y1
        return // Only possible solution, quadratic has one root.
    }

    x2, y2, p2In = lineFunc((-B - D) / (2 * A)) // Second root

    intersects = p1In || p2In
    if p1In == false { // Only x2, y2 may be valid solutions
        x1, y1 = x2, y2
    } else if p2In == false { // Only x1, y1 are valid solutions
        x2, y2 = x1, y1
    }
    return
}

Je l'ai testé avec cette fonction, ce qui confirme que les points de solution sont dans le segment de ligne et sur le cercle. Il fait un segment de test et le balaie autour du cercle donné:

package geom_test

import (
    "testing"

    . "**put your package path here**"
)

func CheckEpsilon(t *testing.T, v, epsilon float64, message string) {
    if v > epsilon || v < -epsilon {
        t.Error(message, v, epsilon)
        t.FailNow()
    }
}

func TestSegmentCircleIntersection(t *testing.T) {
    epsilon := 1e-10      // Something smallish
    x1, y1 := 5.0, 2.0    // segment end point 1
    x2, y2 := 50.0, 30.0  // segment end point 2
    cx, cy := 100.0, 90.0 // center of circle
    r := 80.0

    segx, segy := x2-x1, y2-y1

    testCntr, solutionCntr := 0, 0

    for i := -100; i < 100; i++ {
        for j := -100; j < 100; j++ {
            testCntr++
            s1x, s2x := x1+float64(i), x2+float64(i)
            s1y, s2y := y1+float64(j), y2+float64(j)

            sc1x, sc1y := s1x-cx, s1y-cy
            seg1Inside := sc1x*sc1x+sc1y*sc1y < r*r
            sc2x, sc2y := s2x-cx, s2y-cy
            seg2Inside := sc2x*sc2x+sc2y*sc2y < r*r

            p1x, p1y, p2x, p2y, intersects := SegmentCircleIntersection(s1x, s1y, s2x, s2y, cx, cy, r)

            if intersects {
                solutionCntr++
                //Check if points are on circle
                c1x, c1y := p1x-cx, p1y-cy
                deltaLen1 := (c1x*c1x + c1y*c1y) - r*r
                CheckEpsilon(t, deltaLen1, epsilon, "p1 not on circle")

                c2x, c2y := p2x-cx, p2y-cy
                deltaLen2 := (c2x*c2x + c2y*c2y) - r*r
                CheckEpsilon(t, deltaLen2, epsilon, "p2 not on circle")

                // Check if points are on the line through the line segment
                // "cross product" of vector from a segment point to the point
                // and the vector for the segment should be near zero
                vp1x, vp1y := p1x-s1x, p1y-s1y
                crossProd1 := vp1x*segy - vp1y*segx
                CheckEpsilon(t, crossProd1, epsilon, "p1 not on line ")

                vp2x, vp2y := p2x-s1x, p2y-s1y
                crossProd2 := vp2x*segy - vp2y*segx
                CheckEpsilon(t, crossProd2, epsilon, "p2 not on line ")

                // Check if point is between points s1 and s2 on line
                // This means the sign of the dot prod of the segment vector
                // and point to segment end point vectors are opposite for
                // either end.
                wp1x, wp1y := p1x-s2x, p1y-s2y
                dp1v := vp1x*segx + vp1y*segy
                dp1w := wp1x*segx + wp1y*segy
                if (dp1v < 0 && dp1w < 0) || (dp1v > 0 && dp1w > 0) {
                    t.Error("point not contained in segment ", dp1v, dp1w)
                    t.FailNow()
                }

                wp2x, wp2y := p2x-s2x, p2y-s2y
                dp2v := vp2x*segx + vp2y*segy
                dp2w := wp2x*segx + wp2y*segy
                if (dp2v < 0 && dp2w < 0) || (dp2v > 0 && dp2w > 0) {
                    t.Error("point not contained in segment ", dp2v, dp2w)
                    t.FailNow()
                }

                if s1x == s2x && s2y == s1y { //Only one solution
                    // Test that one end of the segment is withing the radius of the circle
                    // and one is not
                    if seg1Inside && seg2Inside {
                        t.Error("Only one solution but both line segment ends inside")
                        t.FailNow()
                    }
                    if !seg1Inside && !seg2Inside {
                        t.Error("Only one solution but both line segment ends outside")
                        t.FailNow()
                    }

                }
            } else { // No intersection, check if both points outside or inside
                if (seg1Inside && !seg2Inside) || (!seg1Inside && seg2Inside) {
                    t.Error("No solution but only one point in radius of circle")
                    t.FailNow()
                }
            }
        }
    }
    t.Log("Tested ", testCntr, " examples and found ", solutionCntr, " solutions.")
}

Voici la sortie du test:

=== RUN   TestSegmentCircleIntersection
--- PASS: TestSegmentCircleIntersection (0.00s)
    geom_test.go:105: Tested  40000  examples and found  7343  solutions.

Enfin, la méthode est facilement extensible au cas d'un rayon commençant à un point, passant par l'autre et s'étendant à l'infini, en testant seulement si t> 0 ou t <1 mais pas les deux.

Steller
la source
0

J'avais juste besoin de ça, alors j'ai trouvé cette solution. La langue est maxscript, mais elle devrait être facilement traduite dans n'importe quelle autre langue. sideA, sideB et CircleRadius sont des scalaires, les autres variables sont des points comme [x, y, z]. Je suppose que z = 0 pour résoudre sur le plan XY

fn projectPoint p1 p2 p3 = --project  p1 perpendicular to the line p2-p3
(
    local v= normalize (p3-p2)
    local p= (p1-p2)
    p2+((dot v p)*v)
)
fn findIntersectionLineCircle CircleCenter CircleRadius LineP1 LineP2=
(
    pp=projectPoint CircleCenter LineP1 LineP2
    sideA=distance pp CircleCenter
    --use pythagoras to solve the third side
    sideB=sqrt(CircleRadius^2-sideA^2) -- this will return NaN if they don't intersect
    IntersectV=normalize (pp-CircleCenter)
    perpV=[IntersectV.y,-IntersectV.x,IntersectV.z]
    --project the point to both sides to find the solutions
    solution1=pp+(sideB*perpV)
    solution2=pp-(sideB*perpV)
    return #(solution1,solution2)
)
Martin
la source
0

Solution en python, basée sur @Joe Skeen

def check_line_segment_circle_intersection(line, point, radious):
    """ Checks whether a point intersects with a line defined by two points.

    A `point` is list with two values: [2, 3]

    A `line` is list with two points: [point1, point2]

    """
    line_distance = distance(line[0], line[1])
    distance_start_to_point = distance(line[0], point)
    distance_end_to_point = distance(line[1], point)

    if (distance_start_to_point <= radious or distance_end_to_point <= radious):
        return True

    # angle between line and point with law of cosines
    numerator = (math.pow(distance_start_to_point, 2)
                 + math.pow(line_distance, 2)
                 - math.pow(distance_end_to_point, 2))
    denominator = 2 * distance_start_to_point * line_distance
    ratio = numerator / denominator
    ratio = ratio if ratio <= 1 else 1  # To account for float errors
    ratio = ratio if ratio >= -1 else -1  # To account for float errors
    angle = math.acos(ratio)

    # distance from the point to the line with sin projection
    distance_line_to_point = math.sin(angle) * distance_start_to_point

    if distance_line_to_point <= radious:
        point_projection_in_line = math.cos(angle) * distance_start_to_point
        # Intersection occurs whent the point projection in the line is less
        # than the line distance and positive
        return point_projection_in_line <= line_distance and point_projection_in_line >= 0
    return False

def distance(point1, point2):
    return math.sqrt(
        math.pow(point1[1] - point2[1], 2) +
        math.pow(point1[0] - point2[0], 2)
    )
Ian Douglas
la source
0
Function lineCircleCollision(p1,p2,c,r,precision){
Let dx = (p2.x-p1.x)/precision
Let dy = (p2.y-p1.y)/precision
Let collision=false
For(let i = 0;i<precision:i++){
If(Math.sqrt((p1.x+dx*i-c.x)**2+(p1.y+dy*i-c.y)**2).<r {
Collision=true
}
}

Vous pouvez prendre X points régulièrement espacés de la ligne et s'il y en a à l'intérieur du cercle, il y a une collision

Matthew Perlman
la source