Algoritmo de detecção de colisão de segmento de linha de círculo?

Eu tenho uma linha de A a B e um círculo posicionado em C com o raio R.

Imagem

O que é um bom algoritmo para usar para verificar se a linha cruza o círculo? E em que coordenada ao longo da borda dos círculos ocorreu?

Levando

  1. E é o ponto de partida do raio
  2. L é o ponto final do raio
  3. C é o centro da esfera que você está testando
  4. r é o raio dessa esfera

Calcular:
d = L – E (vetor de direção do raio, do início ao fim)
f = E – C (vetor da esfera central para o início do raio)

Então a interseção é encontrada por ..
Conectando:
P = E + t * d
Esta é uma equação paramétrica:
P x = E x + td x
P y = E y + td y
para dentro
(x – h) 2 + (y – k) 2 = r 2
(h, k) = centro do círculo.

Nota: Nós simplificamos o problema para 2D aqui, a solução que obtemos se aplica também em 3D

para obter:

  1. Expandir
    x 2 – 2xh + h 2 + y 2 – 2yk + k 2 – r 2 = 0
  2. Plugue
    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. Explodir
    e x 2 + 2e x td x + t 2 d x 2 – 2e x h – 2td xh + h 2 + e y 2 + 2e y td y + t 2 d y 2 – 2e y k – 2td ek + k 2 – r 2 = 0
  4. Grupo
    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. Finalmente,
    t 2 (_d * _d) + 2t (_e * _d – _d * _c) + _e * _e – 2 (_e * _c) + _c * _c – r 2 = 0
    * Onde _d é o vetor d e * é o produto escalar. *
  6. E depois,
    t 2 (_d * _d) + 2t (_d * (_e – _c)) + (_e – _c) * (_e – _c) – r 2 = 0
  7. Deixando _f = _e – _c
    t 2 (_d * _d) + 2t (_d * _f) + _f * _f – r 2 = 0

Então nós temos:
t 2 * (d DOT d) + 2t * (f DOT d) + (f DOT f – r 2 ) = 0
Então resolvendo a equação quadrática:

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: // -> oo -> | -> | // 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 ; } 

Ninguém parece considerar projeção, estou completamente fora de pista aqui?

Projete o vetor AC em AB . O vetor projetado, AD , fornece o novo ponto D
Se a distância entre D e C for menor que (ou igual a) R , temos uma interseção.

Como isso:
Imagem por SchoolBoy

Eu usaria o algoritmo para calcular a distância entre um ponto (centro do círculo) e uma linha (linha AB). Isso pode ser usado para determinar os pontos de interseção da linha com o círculo.

Vamos dizer que temos os pontos A, B, C. Ax e Ay são os componentes xey dos pontos A. O mesmo para B e C. O escalar R é o raio do círculo.

Aqui está o algoritmo

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

Ok, eu não vou te dar código, mas desde que você tenha marcado este algoritmo , eu não acho que isso seja importante para você. Primeiro, você precisa obter um vetor perpendicular à linha.

Você terá uma variável desconhecida em y = ax + c ( c será desconhecido )
Para resolver isso, calcule seu valor quando a linha passa pelo centro do círculo.

Isso é,
Conecte a localização do centro do círculo à equação da linha e resolva para c .
Em seguida, calcule o ponto de intersecção da linha original e sua normal.

Isso lhe dará o ponto mais próximo da linha para o círculo.
Calcule a distância entre este ponto e o centro do círculo (usando a magnitude do vetor).
Se isso é menor que o raio do círculo – voila, nós temos uma interseção!

Outro método usa a fórmula da área ABC do triângulo. O teste de interseção é mais simples e mais eficiente que o método de projeção, mas encontrar as coordenadas do ponto de interseção requer mais trabalho. Pelo menos, será adiada até o ponto em que é necessário.

A fórmula para calcular a área do triângulo é: area = bh / 2

onde b é o comprimento da base e h é a altura. Escolhemos o segmento AB como base para que h seja a distância mais curta entre C, o centro do círculo e a linha.

Como a área do triângulo também pode ser calculada por um produto de ponto vetorial, podemos determinar 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 ) { ... } 

ATUALIZAÇÃO 1:

Você pode otimizar o código usando a computação de raiz quadrada inversa rápida descrita aqui para obter uma boa aproximação de 1 / LAB.

A computação do ponto de interseção não é tão difícil. Aqui vai

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

Se h = R, então a linha AB é tangente ao círculo e o valor dt = 0 e E = F. As coordenadas dos pontos são aquelas de E e F.

Você deve verificar que A é diferente de B e o comprimento do segmento não é nulo se isso puder acontecer em sua aplicação.

Eu escrevi um pequeno script para testar a interseção projetando o ponto central do círculo na linha.

 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/

Se você precisar verificar a colisão com o segmento, você também precisa considerar a distância do centro do círculo para os pontos inicial e final.

 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/

Essa solução que encontrei pareceu um pouco mais fácil de seguir do que algumas outras.

Levando:

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

Eu resolveria a equação da linha em forma de interseção de declive. No entanto, eu não queria ter que lidar com equações difíceis com c como um ponto, então eu apenas mudei o sistema de coordenadas para que o círculo 0,0 a 0,0

 p3 = p1 - c p4 = p2 - c 

A propósito, sempre que subtrair pontos uns dos outros, estou subtraindo os x e subtraindo os y , e colocando-os em um novo ponto, para o caso de alguém não saber.

De qualquer forma, resolvo agora a equação da linha com p3 e 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) 

Está bem. Agora preciso definir essas equações como iguais. Primeiro eu preciso resolver a equação do círculo para x

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

Então eu os coloquei iguais:

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

E resolva para a equação quadrática ( 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 

Agora eu tenho meus a , b e c .

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

Então eu coloquei isso na fórmula quadrática:

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

E substitua por valores e simplifique o máximo possível:

 (-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 

Isso é quase tão longe quanto irá simplificar. Por fim, separe as equações com o ±:

 (-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 

Então, simplesmente conecte o resultado de ambas as equações no x em mx + b . Para maior clareza, escrevi um código JavaScript para mostrar como usar isso:

 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 - cx, y:p1.y - cy} //shifted line points var p4 = {x:p2.x - cx, y:p2.y - cy} 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]; } } 

Eu espero que isso ajude!

PS Se alguém encontrar algum erro ou tiver alguma sugestão, por favor, comente. Eu sou muito novo e saúdo todas as ajudas / sugestões.

Você pode encontrar um ponto em uma linha infinita que esteja mais próxima do centro do círculo projetando o vetor AC no vetor AB. Calcule a distância entre esse ponto e o centro do círculo. Se é maior que R, não há interseção. Se a distância é igual a R, a linha é uma tangente do círculo e o ponto mais próximo ao centro do círculo é, na verdade, o ponto de interseção. Se a distância menor que R, então há dois pontos de interseção. Eles estão à mesma distância do ponto mais próximo ao centro do círculo. Essa distância pode ser facilmente calculada usando o teorema de Pitágoras. Aqui está o algoritmo no pseudocódigo:

 { 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: código adicionado para verificar se os pontos de interseção encontrados realmente estão dentro do segmento de linha.

Estranhamente eu posso responder, mas não comentar … Eu gostei da abordagem do Multitaskpro de mudar tudo para fazer o centro do círculo cair na origem. Infelizmente, existem dois problemas em seu código. Primeiro na parte inferior da raiz quadrada, você precisa remover o poder duplo. Então não:

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

mas:

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

Nas coordenadas finais ele se esquece de mudar a solução de volta. Então não:

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

mas:

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

A function inteira então se torna:

 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 - cx, y:p1.y - cy}; //shifted line points var p4 = {x:p2.x - cx, y:p2.y - cy}; 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+cx, y:m*t1+b+cy}; //intercept point 1 var i2 = {x:t2+cx, y:m*t2+b+cy}; //intercept point 2 return [i1, i2]; } } 

Você precisará de um pouco de matemática aqui:

Suponha A = (Xa, Ya), B = (Xb, Yb) e C = (Xc, Yc). Qualquer ponto na linha de A a B tem coordenadas (alfa * Xa + (1-alfa) Xb, alfa Ya + (1-alfa) * Yb) = P

Se o ponto P tiver a distância de R a C, deve estar no círculo. O que você quer é resolver

 distance(P, C) = R 

isso é

 (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 

se você aplicar a fórmula ABC a essa equação para resolvê-la para alfa e calcular as coordenadas de P usando a (s) solução (ões) para alfa, você obtém os pontos de interseção, se existir algum.

Se você encontrar a distância entre o centro da esfera (já que é 3D, eu suponho que você quer dizer esfera e não círculo) e a linha, então verifique se essa distância é menor que o raio que fará o truque.

O ponto de colisão é obviamente o ponto mais próximo entre a linha e a esfera (que será calculado quando você estiver calculando a distância entre a esfera e a linha)

Distância entre um ponto e uma linha:
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

Aqui está uma implementação em JavaScript. Minha abordagem é primeiro converter o segmento de linha em uma linha infinita, em seguida, encontrar o (s) ponto (s) de interseção. De lá, eu verifico se os pontos encontrados estão no segmento de linha. O código está bem documentado, você deve ser capaz de acompanhar.

Você pode experimentar o código aqui nesta demonstração ao vivo . O código foi retirado do meu repository de algoritmos .

insira a descrição da imagem aqui

 // 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 (xX)^2 + (yY)^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 = (-BD)/(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 []; } 

Nesta colisão de linha pós-círculo será verificada pela verificação da distância entre o centro do círculo e o ponto no segmento de linha (Ipoint) que representa o ponto de intersecção entre o N normal (Imagem 2) do centro do círculo ao segmento da linha.

( https://i.stack.imgur.com/3o6do.png ) Imagem 1. Encontrando vetores E e D

Na imagem 1, um círculo e uma linha são mostrados, vetor ponto a ponto ponto inicial, ponto B ponto final da linha, ponto C vetor ao centro do círculo. Agora temos que encontrar o vetor E (do ponto inicial da linha ao centro do círculo) e o vetor D (do ponto inicial da linha ao ponto final da linha) este cálculo é mostrado na imagem 1.

( https://i.stack.imgur.com/7098a.png ) Imagem 2. Encontrando o vetor X

Na imagem 2 podemos ver que o vetor E é projetado no vetor D por “produto de ponto” do vetor E e vetor unitário D, resultado do produto escalar é Xp escalar que representa a distância entre o ponto inicial da linha e o ponto de intersecção (ponto) vetor N e vetor D. O próximo vetor X é encontrado multiplicando o vetor unitário D e o escalar Xp.

Agora precisamos encontrar o vetor Z (vetor para ponto), é fácil a adição vetorial simples do vetor A (ponto inicial na linha) e vetor X. Em seguida, precisamos lidar com casos especiais que devemos verificar se é ponto no segmento de linha, se Não é preciso descobrir se é a esquerda ou direita dele, vamos usar vetor mais próximo para determinar qual ponto está mais próximo do círculo.

( https://i.stack.imgur.com/p9WIr.png ) Imagem 3. Encontrando o ponto mais próximo

Quando a projeção Xp é negativa Ipoint é o segmento da esquerda da linha, o vetor mais próximo é igual ao vetor do ponto inicial da linha, quando a projeção Xp é maior que a magnitude do vetor D então o ponto é o segmento da direita da linha ponto em qualquer outro caso, o vetor mais próximo é igual ao vetor Z.

Agora, quando temos o vetor mais próximo, precisamos encontrar um vetor do centro do círculo para o ponto (vetor dist), é simples, basta subtrair o vetor mais próximo do vetor central. Em seguida, basta verificar se a magnitude da distensão do vetor é menor que o raio do círculo se, então, eles colidirem, se não houver colisão.

( https://i.stack.imgur.com/QJ63q.png ) Imagem 4. Checando por colisão

Por fim, podemos retornar alguns valores para resolver a colisão, a maneira mais fácil é retornar a sobreposição de colisão (subtrair raio da magnitude da distensão vetorial) e retornar o eixo de colisão, seu vetor D. O ponto de interseção também é vetor Z, se necessário.

Se as coordenadas da linha forem Ax, Ay e Bx, By e o centro dos círculos for Cx, Cy, as fórmulas das linhas serão:

x = Ax * t + Bx * (1 – t)

y = Ay * t + Por * (1 – t)

onde 0 <= t <= 1

e o círculo é

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

Se você replace as fórmulas xey da linha na fórmula de círculos, você obtém uma equação de segunda ordem de te suas soluções são os pontos de interseção (se houver algum). Se você chegar a qual é menor que 0 ou maior que 1 então não é uma solução, mas mostra que a linha está ‘apontando’ para a direção do círculo.

Apenas uma adição a este tópico … Abaixo está uma versão do código postado por pahlevan, mas para C # / XNA e arrumou um pouco:

  ///  /// Intersects a line and a circle. ///  /// the location of the circle /// the radius of the circle /// the starting point of the line /// the ending point of the line /// true if the line and circle intersect each other 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)); } 

insira a descrição da imagem aqui

 ' 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 

Eu criei esta function para iOS seguindo a resposta dada por 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; } 

This Java Function returns a DVec2 Object. It takes a DVec2 for the center of the circle, the radius of the circle, and a Line.

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

Another one in c# (partial Circle class). Tested and works like a charm.

 public class Circle : IEquatable { // ****************************************************************** // The center of a circle private Point _center; // The radius of a circle private double _radius; // ****************************************************************** ///  /// 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 ///  ///  ///  ///  public List GetIntersections(Point linePoint1, Point linePoint2) { List intersections = new List(); 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 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); } 

Required:

 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 ///  /// 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 ///  /// 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. ///  ///  ///  ///  ///  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; } // ****************************************************************** ///  /// Mathlab equivalent ///  ///  ///  ///  public static double Mod(this double dividend, double divisor) { return dividend - System.Math.Floor(dividend / divisor) * divisor; } // ****************************************************************** } } 

Here is good solution in JavaScript (with all required mathematics and live illustration) https://bl.ocks.org/milkbread/11000965

Though is_on function in that solution needs modifications:

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

Circle is really a bad guy 🙂 So a good way is to avoid true circle, if you can. If you are doing collision check for games you can go with some simplifications and have just 3 dot products, and a few comparisons.

I call this “fat point” or “thin circle”. its kind of a ellipse with zero radius in a direction parallel to a segment. but full radius in a direction perpendicular to a segment

First, i would consider renaming and switching coordinate system to avoid excessive data:

 s0s1 = BA; s0qp = CA; rSqr = r*r; 

Second, index h in hvec2f means than vector must favor horisontal operations, like dot()/det(). Which means its components are to be placed in a separate xmm registers, to avoid shuffling/hadd’ing/hsub’ing. And here we go, with most performant version of simpliest collision detection for 2D game:

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

I doubt you can optimize it any further. I am using it for neural-network driven car racing collision detection, to process millions of millions iteration steps.

Here is a solution written in golang. The method is similar to some other answers posted here, but not quite the same. It is easy to implement, and has been tested. Aqui estão os passos:

  1. Translate coordinates so that the circle is at the origin.
  2. Express the line segment as parametrized functions of t for both the x and y coordinates. If t is 0, the function’s values are one end point of the segment, and if t is 1, the function’s values are the other end point.
  3. Solve, if possible, the quadratic equation resulting from constraining values of t that produce x, y coordinates with distances from the origin equal to the circle’s radius.
  4. Throw out solutions where t is < 0 or > 1 ( <= 0 or >= 1 for an open segment). Those points are not contained in the segment.
  5. Translate back to original coordinates.

The values for A, B, and C for the quadratic are derived here, where (n-et) and (m-dt) are the equations for the line’s x and y coordinates, respectively. r is the radius of the circle.

 (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 

Therefore A = ee+dd, B = – 2(en + dm), and C = nn + mm – rr.

Here is the golang code for the function:

 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*mr*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 } 

I tested it with this function, which confirms that solution points are within the line segment and on the circle. It makes a test segment and sweeps it around the given circle:

 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.") } 

Here is the output of the test:

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

Finally, the method is easily extendable to the case of a ray starting at one point, going through the other and extending to infinity, by only testing if t > 0 or t < 1 but not both.

I just needed that, so I came up with this solution. The language is maxscript, but it should be easily translated to any other language. sideA, sideB and CircleRadius are scalars, the rest of the variables are points as [x,y,z]. I’m assuming z=0 to solve on the plane 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 vp)*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) )