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

j'ai une ligne de A à B et un cercle positionné à 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 il s'est produit?

173
demandé sur smci 2009-07-02 13:15:10

23 réponses

Prendre

  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, vous êtes des tests contre les
  4. r est le rayon de cette sphère

calculer:

d = l-E ( vecteur de direction du rayon, du début à la fin )

f = E-C (vecteur de la sphère centrale au départ du rayon )

puis l'intersection est trouvée par..

Branchement:

P = E + t * D

Il s'agit d'une équation paramétrique:

P x = E x + td x

P y = E y + td y

en

(x - h) 2 + (y-k) 2 = r 2

(h,k) = centre du cercle.

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

pour obtenir:

  1. Développer

    x 2 - 2XH + h 2 + y 2 - 2yk + k 2 - r 2 = 0
  2. Plug

    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. Letting _f = _e - _c

    t 2 (_d * _d ) + 2t (_d * _f ) + _f * _f-r 2 = 0

nous obtenons:

t 2 * (d POINT d) + 2t* (f point d) + (f point F - r 2 ) = 0

Ainsi la résolution de 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 ;
}
178
répondu bobobobo 2013-11-07 22:10:05

personne ne semble considérer la projection, suis-je complètement hors de propos ici?

projeter le vecteur AC sur AB . Le vecteur projeté, AD , donne le nouveau point D .

Si la distance entre D et C est plus petite que (ou égale à) R nous avons une intersection.

comme ceci:

Image by SchoolBoy

115
répondu Mizipzor 2013-02-27 10:18:49

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 droite 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 R scalaire est le rayon du cercle.

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

// 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)
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
Ex = t*Dx+Ax
Ey = t*Dy+Ay

// compute the euclidean distance from E to 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
40
répondu chmike 2012-11-30 22:23:31

une autre méthode utilise la formule du triangle 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 demande plus de travail. Au moins, il sera retardé au point où il est nécessaire.

la formule pour calculer la surface du triangle est : area = BH / 2

où b est la longueur de base et h la hauteur. Nous avons choisi le segment AB pour être la base afin qu'il soit distance la plus courte entre C, le centre du cercle, et la ligne.

étant donné que la surface du triangle peut aussi être calculée par un produit de points vectoriels, 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 de racine carrée inverse rapide décrit ici pour obtenir une bonne approximation de 1/LAB.

calcul de l'intersection point n'est pas que difficile.

// 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 des points 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.

9
répondu chmike 2012-06-22 16:18:18

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 pour les 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 /

6
répondu ercang 2015-08-19 11:33:55

Cette solution que j'ai trouvée a semblé un peu plus facile à suivre que certains des autres.

:

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ésoudrai pour l'équation de la ligne sous forme d'intersection de pente. Cependant, je ne voulais pas avoir à faire face à des équations difficiles avec c comme point, donc j'ai juste déplacé le système de coordonnées de sorte que le cercle est à 0,0

p3 = p1 - c
p4 = p2 - c

d'ailleurs, chaque fois que je soustrayez des points les uns des autres je soustrais le x 's et puis soustrayant le y 's, et les mettre dans un nouveau point, juste au cas où quelqu'un ne savait pas.

de toute façon, je résous maintenant pour l'équation de la ligne avec p3 et 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)

Ok. Maintenant, je dois mettre ces équations à égalité. D'abord, je dois résoudre l'équation du cercle pour x

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

Puis je les mets égaux:

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

et résoudre pour 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 mes a , b , et c .

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

donc j'ai mis ceci dans la formule quadratique:

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

et remplacer par des valeurs, puis simplifier 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 qu'il va simplifier. Enfin, séparer les é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 

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

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 cela aidera!

P.S. si quelqu'un trouve des erreurs ou a des suggestions, veuillez les commenter. Je suis très nouveau et bienvenue à tous de l'aide/suggestions.

5
répondu multitaskPro 2014-03-01 05:14:25

vous pouvez trouver un point sur une ligne infinie qui est la 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 plus grand que 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 de le cercle de centre. Cette distance peut facilement être calculée en utilisant le théorème de Pythagore. Voici l'algorithme en pseudo-code:

{
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
  }
}

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

4
répondu Juozas Kontvainis 2010-09-02 10:41:40

bizarrement, je peux répondre mais pas commenter... J'ai aimé L'approche de Multitaskpro de 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. Donc pas:

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 déplacer la solution arrière. Donc pas:

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

mais:

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

toute 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];
    }
}
4
répondu Duq 2015-08-13 23:42:21

vous aurez besoin de quelques mathématiques ici:

supposons A = (Xa, Ya), B = (Xb, Yb) et C = (Xc, Yc). N'importe quel 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 une distance R à C, il doit être sur le cercle. Ce que vous voulez est de résoudre

distance(P, C) = R

c'est-à-dire

(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 à ce équation pour le résoudre pour alpha, et calculer les coordonnées de P en utilisant la(Les) solution (s) pour alpha, vous obtenez les points d'intersection, s'il en existe.

3
répondu Martijn 2009-07-02 09:29:10

si vous trouvez la distance entre le centre de la sphère (puisque C'est 3D je suppose que vous voulez dire la sphère et pas le cercle) et la ligne, puis vérifier 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 calculerez la distance entre la sphère et la ligne)

Distance entre un point et une ligne:

http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

3
répondu Martin 2009-07-02 21:17:14

Voici une implémentation en Javascript. Mon approche est d'abord convertir le segment de ligne dans une ligne infinie puis de trouver le point d'intersection(s). De là je vérifie si le(s) point (S) trouvé (s) sont sur le segment de ligne. Le code est bien documenté, vous devriez pouvoir le suivre.

vous pouvez essayer le code ici sur ce live demo . Le code a été pris de mon algorithmes repo .

enter image description here

// 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 [];

}
3
répondu will.fiset 2017-07-07 17:56:02

dans cette collision de ligne après 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 N normal (Image 2) du centre du cercle au segment de ligne.

( /images/content/1073336/5f410535db0e50e7dc24d2d21a79495d.png ) Image 1. Finding vectors E and D

sur l'image 1 un cercle et une ligne sont affichés, vecteur Un point de départ de la ligne, vecteur B point à la fin de la ligne, vecteur C point au centre du cercle. Nous devons maintenant 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 de fin de la ligne).

( /images/contenu/1073336/70584d0b3a289a422465d399422c2b61.png ) Image 2. Finding vector X

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

maintenant, nous avons besoin de trouver vecteur Z (vecteur à Ipoint), son facile son simple ajout vecteur de vecteur a (point de départ sur la ligne) et vecteur X. Ensuite, nous devons traiter les cas spéciaux, nous devons vérifier est Ipoint sur segment de ligne, si son pas, nous devons savoir est-il à gauche ou à droite, nous utiliserons le vecteur le plus proche pour déterminer quel point est le plus proche du cercle.

( /images/content/1073336/bc18f335672c3a8c8283b6673d71ce.png ) Image 3. Finding closest point

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 plus grande que l'amplitude du vecteur d, alors Ipoint est à droite du segment de ligne, puis le plus proche le vecteur est égal au vecteur du point final de la ligne dans tous les autres cas le vecteur le plus proche est égal au vecteur Z.

maintenant quand nous avons le vecteur le plus proche , nous avons besoin de trouver le vecteur du centre du cercle à L'Ipoint (vecteur dist), son simple nous avons juste besoin de soustraire le vecteur le plus proche du vecteur du centre. Ensuite, il suffit de vérifier si la magnitude du vecteur dist est inférieure au rayon de cercle si elle est alors ils entrent en collision, si elle n'est pas il n'y a pas de collision.

( /images/contenu/1073336/5bf8feb6bf27ae00ebdc3dd66009dc91.png ) Image 4. Checking for collision

pour fin, nous pouvons retourner certaines valeurs pour résoudre la collision , la manière la plus simple est de retourner le chevauchement de la collision (soustraire le rayon de la magnitude vectorielle) et l'axe de retour de la collision, son vecteur D. le point d'intersection est aussi le vecteur Z si nécessaire.

3
répondu FunDeveloper89 2018-03-18 22:19:47

si les coordonnées de la ligne sont A. x, A. y et B. x, B. y et le centre des cercles est C. x, C. y alors les formules des lignes sont:

x = A. x * t + B. x * (1-t)

y = A. Y * t + B. y * (1-t)

où 0< = t<=1

et le cercle est

(C. x - x)^2 + (C. y - y)^2 = R^2

si vous substituez des formules x et y de la ligne dans la formule des cercles vous obtenez un équation de deuxième ordre de t et ses solutions sont les points d'intersection (s'il y en a). Si vous obtenez un t qui est plus petit que 0 ou plus grand que 1 alors ce n'est pas une solution mais il montre que la ligne "pointe" vers la direction du cercle.

2
répondu Gábor Hargitai 2009-07-02 09:30:00

juste un ajout à ce fil... Ci - dessous est une version du code posté par pahlevan, mais pour C# / XNA et rangé 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));
    }
2
répondu Rob 2012-05-01 02:30:42

enter image description here

' 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
2
répondu A.J.Bauer 2014-02-27 10:43:02

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;
}
2
répondu Aqib Mumtaz 2014-11-24 13:30:23

cette fonction Java renvoie un objet DVec2. Il prend 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;
}
1
répondu pahlevan 2009-07-19 11:12:57

un autre en c# (Classe de cercle partiel). 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);
    }

Requis:

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;
        }

        // ******************************************************************
    }
}
1
répondu Eric Ouellet 2016-05-13 16:57:29

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

Si is_on fonction dans cette solution a besoin de modifications:

function is_on(a, b, c) {
    return Math.abs(distance(a,c) + distance(c,b) - distance(a,b))<0.000001;
}
1
répondu nazar kuliyev 2017-06-08 11:19:32

Cercle est vraiment un mauvais gars :) Donc un bon moyen est d'éviter de vrai cercle, si vous le pouvez. Si vous faites le contrôle de collision pour les jeux, vous pouvez aller avec quelques simplifications et ont juste 3 produits de point, et quelques comparaisons.

j'appelle cela" le point de graisse "ou"le cercle mince". c'est une sorte d'ellipse à rayon zéro dans une direction parallèle à un segment. mais rayon plein dans une direction perpendiculaire à un segment

D'abord, j'envisagerais de renommer et commutation du système de coordonnées pour éviter les données excessives:

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

Deuxièmement, l'indice h dans hvec2f signifie que le vecteur doit favoriser les opérations horisontales, comme dot()/det(). Ce qui signifie que ses composants doivent être placés dans un registre xmm séparé, pour éviter le mélange/hadd'ing/hsub'ing. Et nous y voilà, avec la version la plus performante de la détection de collision la plus simple pour le jeu 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 pouvez l'optimiser. Je l'utilise pour l' détection de collision de course de voiture par réseau neuronal, pour traiter des millions d'étapes d'itération.

1
répondu xakepp35 2018-02-25 17:13:07

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

  1. Traduire des coordonnées de sorte que le cercle est à l'origine.
  2. exprimer le segment de ligne en 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 de contrainte de t qui produisent des coordonnées x, y avec des distances de l'origine égale au rayon du cercle.
  4. jeter les solutions où t est < 0 ou > 1 (<=0 ou >= 1 pour un segment ouvert). Ces points ne figurent pas dans le segment.
  5. renvoie aux coordonnées originales.

les valeurs de 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

donc a = ee+dd, B = - 2(en + dm), et C = nn + mm - rr.

voici le code de golang pour 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, qui confirme que les points de solution sont dans le segment de ligne et sur le cercle. Il fait un segment d'essai 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 le résultat 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 ne testant que si t > 0 ou t < 1 mais pas les deux.

0
répondu Steller 2018-03-21 05:47:11

j'en avais juste besoin, alors j'ai trouvé cette solution. Le langage est en maxscript, mais il doit être facilement traduit dans n'importe quelle autre langue. sideA, sideB et CircleRadius sont des scalaires, le reste des 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)
)
0
répondu user18965 2018-07-24 19:53:33