Hmm. Uma pergunta: você está falando da linha infinita através de A e B ou do segmento de linha finita de A a B?
Jason S
2
Nesse caso, é o segmento de linha finita. A "linha" é chamada de outra coisa, dependendo de ser finita ou infinita?
Mizipzor 03/07/2009
1
Existe um requisito de desempenho? Deve ser um método rápido?
chmike
Neste ponto, não, todos os algoritmos aqui que eu tentei não diminuem visivelmente o aplicativo.
Mizipzor 07/07/2009
13
@Mizipzor sim, eles são chamados de outra coisa: segmentos de linha . Se você diz apenas "linha", é implícita uma infinita.
MestreLion 6/08/14
Respostas:
200
Levando
E é o ponto de partida do raio,
L é o ponto final do raio,
C é o centro da esfera contra a qual você está testando
r é o raio dessa esfera
Cálculo: d = L - E (vetor de direção do raio, do início ao fim) f = E - C (vetor da esfera central ao início do raio)
Então a interseção é encontrada por ..
Plugging: P = E + t * d
Esta é uma equação paramétrica:
P x = E x + td x
P y = E y + td y
em (x - h) 2 + (y - k) 2 = r 2
(h, k) = centro do círculo.
Nota: simplificamos o problema para 2D aqui, a solução que obtemos se aplica também em 3D
para obter:
Expandir
x 2 - 2xh + h 2 + y 2 - 2yk + k 2 - r 2 = 0
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
Explode
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
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
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. *
E então,
t 2 (_d * _d) + 2t (_d * (_e - _c)) + (_e - _c) * (_e - _c) - r 2 = 0
Portanto, obtemos: t 2 * (d DOT d) + 2t * (f DOT d) + (f DOT f - r 2 ) = 0
Portanto, 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:
// -> 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 ;
}
Parece funcionar se eu copiar e colar diretamente, mas estou procurando entender. Em (xh) ^ 2 + (yk) ^ 2 = r ^ 2, o que são hek? É k a constante pela qual a linha / raio aumenta em y sobre x? E o que é t? Olhando para o código, parece que você assumiu o seu 1 (então é apenas "removido"). Essas fórmulas têm um nome ou algo assim? Talvez eu possa procurá-los em detalhes no Wolfram.
Mizipzor 06/07/2009
3
hek são o centro do círculo em que você está cruzando. t é o parâmetro da equação da linha. No código, t1 e t2 são as soluções. t1 e t2 dizem "a que distância do raio" ocorreu a interseção.
22909 bobobobo
1
OK, entendi. O produto escalar é simplesmente calculado sobre os três elementos (x, y, z) vetores. Vou mudar meu código para esse algoritmo.
chmike
21
P = E + t * dO que é t?
Derek朕會功夫
3
Não sei por que, mas o código não parece funcionar no caso Impale. Isso acontece quando adiciono se t1 <= 0 && t1> = -1 && t2 <= 0 && t2> = -1 como condição verdadeira, mas também fornece um falso positivo em um lado da linha finita, quando o círculo está na parte "infinita". Ainda não entendo a matemática, mas copie / troque, cuidado.
Nicolas Mommaerts
142
Ninguém parece considerar a projeção, estou completamente fora dos trilhos aqui?
Projete o vetor ACem AB. O vetor projetado,, ADdá o novo ponto D.
Se a distância entre De Cé menor que (ou igual a) R, temos uma interseção.
Há muitos detalhes a serem levados em consideração: D fica entre AB? A distância perpendicular à linha C é maior que o raio? Tudo isso envolve magnitude do vetor, ou seja, raiz quadrada.
BAD
15
Boa ideia, mas como você calcula os dois pontos de interseção?
21412 Ben
4
@ Spider, não importa. Em geral, como essa é uma variante do problema de interseção esfera-linha, a estratégia de Mizipzor é perfeitamente válida. CDé uma projeção, é perpendicular por definição.
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.
Digamos 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.
Este algoritmo requer que A, B e C sejam pontos distintos e que R não seja 0.
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
// the equation of the line AB is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= LAB.
// compute the distance between the points A and E, where
// E is the point of AB closest the circle center (Cx, Cy)
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)
// compute the coordinates of the point E
Ex = t*Dx+Ax
Ey = t*Dy+Ay
// compute the euclidean distance between E and C
LEC = sqrt((Ex-Cx)²+(Ey-Cy)²)
// test if the line intersects the circle
if( LEC < R )
{
// compute distance from t to circle intersection point
dt = sqrt( R² - LEC²)
// compute first intersection point
Fx = (t-dt)*Dx + Ax
Fy = (t-dt)*Dy + Ay
// compute second intersection point
Gx = (t+dt)*Dx + Ax
Gy = (t+dt)*Dy + Ay
}
// else test if the line is tangent to circle
else if( LEC == R )
// tangent point to circle is E
else
// line doesn't touch circle
se qualquer linha que não esteja cruzando o círculo e seus pontos p1 e p2 estiverem dentro do círculo. neste caso, como o seu algoritmo funciona?
Prashant
1
Você tem que testar t-dt et + dt. Se t-dt <0, então p1 está dentro do círculo. Se t + dt> 1, então p2 está dentro do círculo. Isso é verdade se LEC <R, é claro.
21814 chmike #
Obrigado. Gostei dos comentários deste pgm como explicação, porque não havia uso das palavras "produto pontilhado", pois minha matemática está enferrujada. No entanto, t e dt não estão entre 0..1 e, ao mudar isso para python, mudei t para ser dividido pelo LAB ** 2. Meu entendimento é que a primeira divisão do LAB é projetar o centro do círculo na linha AB, e a segunda divisão do LAB é normalizá-lo no intervalo 0..1. Além disso, o dt precisa ser dividido pelo LAB, para que também seja normalizado. Assim, "se (t-dt> = 0,0)" existe a primeira interseção "se (t + dt <= 1,0)" existe a segunda interseção. Isso funcionou com testes.
Punchcard
2
Porque o ponto de interseção com o círculo está na "distância" t+dte t-dtna linha. té o ponto na linha mais próxima do centro do círculo. Os pontos de interseção com o círculo estão a uma distância simétrica de t. Os pontos de interseção estão em "distâncias" t-dte t+dt. Eu citei distância porque não é a distância euclidiana. Para obter a distância euclidiana de Aonde t=0, você deve multiplicar o valor por LAB.
Chmike 27/05
1
@ Matt W Você quer dizer "Como determinar se a interseção ocorre fora dos pontos finais da seção de linha AB"? Pense em t como uma medida da distância ao longo da linha. O ponto A está em t=0. Ponto B em t=LAB. Quando os dois pontos de interseção ( t1=t-tde t2=t+td) têm valores negativos, as interseções ficam fora da seção (atrás do ponto A, olhando pelo lado da seção). Quando t1 e t2 são maiores que LAB, eles também estão fora (desta vez atrás do ponto B). A interseção t1 (ou t2) ocorre entre A e B somente quando t1 (ou t2) está entre 0 e LAB.
Marconius
20
Ok, não vou dar o código, mas desde que você marcou isso algoritmo, Não acho que isso importe para você. Primeiro, você deve 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 passar pelo centro do círculo.
Ou seja,
conecte o local do centro do círculo à equação da linha e resolva c.
Em seguida, calcule o ponto de interseção da linha original e seu normal.
Isso lhe dará o ponto mais próximo da linha ao 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, temos uma interseção!
Na verdade, era isso que eu queria. Eu quero a teoria, uma pesquisa no google do algoritmo de colisão de círculo de linha gera apenas código, tanto quanto eu posso ver.
Mizipzor 02/07/2009
Ok, c é desconhecido na sua equação, mas o que é "a"? As outras respostas parecem se referir a essa variável como "alfa" e "t". Embora essa seja apenas uma função linear (y = kx + m), matemática bastante básica, de repente me sinto um pouco enferrujada. K não é também desconhecido? Ou você quer dizer que podemos assumir m = 0 e resolver k? Então m (isto é, c) não seria sempre zero para o nosso k resolvido?
Mizipzor 03/07/2009
1
Ah, desculpe, estou usando a equação simples de uma linha com um gradiente e um deslocamento (a equação cartesiana). Eu assumi que você estava armazenando a linha como uma equação - nesse caso, você usa o negativo do gradiente para k. Se você não tem a linha armazenada como este, você poderia calcular k como (y2-y1) / (x2-x1)
a_m0d
1
Não assumimos que m seja zero; calculamos primeiro o gradiente (para que a equação da linha pareça y = 2x + m como exemplo) e, depois que tivermos o gradiente, podemos resolver m inserindo no centro do círculo y e x .
a_m0d
1
+1 Explicação impressionante! Mas acho que isso assume uma linha, não um segmento de linha. Portanto, se o ponto mais próximo dessa linha ao centro do círculo não estivesse entre os pontos A e B, ele ainda seria contado.
Hassan
12
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 exige mais trabalho. Pelo menos, será atrasado até o ponto 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 menor distância entre C, o centro do círculo e a linha.
Como a área do triângulo também pode ser calculada por um produto 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.
Computar o 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, a linha AB é tangente ao círculo e o valor dt = 0 e E = F. As coordenadas do ponto são as de E e F.
Você deve verificar se A é diferente de B e o comprimento do segmento não é nulo, se isso acontecer no seu aplicativo.
Eu gosto da simplicidade neste método. Talvez eu possa adaptar parte do código ao redor para não precisar do ponto de colisão real. Vou ver o que acontece se eu usar A ou B em vez do ponto calculado no meio.
Mizipzor 07/07/2009
1
t = Dx * (Cx-Ax) + Dy * (Cy-Ax) deve ler t = Dx * (Cx-Ax) + Dy * (Cy-Ay)
Stonetip
Isto está certo. Obrigado por apontar. Eu o corrigi no post.
chmike
acabou de editar - a primeira linha calcula a área do triângulo usando um produto cruzado , não um produto escalar. verificado com o código aqui: stackoverflow.com/questions/2533011/…
ericsoco
4
observe também que a primeira metade desta resposta testa a interseção com uma linha, não um segmento de linha (conforme solicitado na pergunta).
Ericsoco 21/06
8
Escrevi um pequeno script para testar a interseção projetando o ponto central do círculo na linha.
Esta solução que encontrei parecia 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 reta na forma de interceptação de inclinação. No entanto, eu não queria ter que lidar com equações difíceis ccomo um ponto, então apenas mudei o sistema de coordenadas para que o círculo estivesse em0,0
p3 = p1 - c
p4 = p2 - c
A propósito, sempre que subtraio pontos um do outro, subtraio os xe depois subtraí os y, colocando-os em um novo ponto, caso alguém não saiba.
Enfim, agora resolvo a equação da linha com p3e 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 eu preciso definir essas equações iguais. Primeiro, preciso resolver a equação do círculo parax
Em seguida, basta conectar o resultado dessas duas equações ao xin mx + b. Para maior clareza, escrevi algum 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 - 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];
}
}
Eu espero que isso ajude!
PS Se alguém encontrar algum erro ou tiver alguma sugestão, por favor, comente. Sou muito novo e bem-vindo a toda ajuda / sugestões.
Se possível, publique também alguns valores de amostra para que possamos entender rapidamente o fluxo.
Prabindh
Com underRadicalextra ')'
byJeevan
4
Você pode encontrar um ponto em uma linha infinita 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 for 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 for menor que R, existem 2 pontos de interseção. Eles ficam à 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.
Você perdeu um caso, pois estamos falando de um segmento de linha: quando o segmento termina no círculo.
BAD
@ADB, na verdade, meu algoritmo funciona apenas para linhas infinitas, não para segmentos de linha. Há muitos casos que ele não lida com segmentos de linha.
Juozas Kontvainis
A pergunta original era sobre segmentos de linha, e não interseção de círculo, que é um problema muito mais fácil.
msumme
4
Estranhamente, posso responder, mas não comentar ... Gostei da abordagem da Multitaskpro de mudar tudo para fazer o centro do círculo cair sobre a origem. Infelizmente, existem dois problemas em seu código. Primeiro na parte da raiz quadrada, você precisa remover a dupla potência. 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 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+c.x, y:m*t1+b+c.y};
Toda a funçã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 - 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];
}
}
sugestões: Primeiro, lide com o caso em que o segmento de linha é vertical (ou seja, tem inclinação infinita). Em segundo lugar, retorne apenas os pontos que realmente caem dentro do intervalo do segmento de linha original - acredito que ele retorne felizmente todos os pontos que caem na linha infinita, mesmo que esses pontos fiquem fora do segmento de linha.
Gino
Nota: Isso funciona bem para linhas, mas não para segmentos de linha.
22419 Mike
3
Você precisará de matemática aqui:
Suponha que 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 tem distância R a C, ele deve estar no círculo. O que você quer é resolver
se você aplicar a fórmula ABC a esta equação para resolvê-la para alfa e calcular as coordenadas de P usando as soluções para alfa, obterá os pontos de interseção, se houver algum.
Se você encontrar a distância entre o centro da esfera (já que é 3D, presumo que você queira dizer esfera e não círculo) e a linha, 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)
Está em 2D, não em 3D; como você diz, isso realmente não importa #
287
Eu não sou matemático, então eu pensei que eu estaria esboçando melhor uma abordagem geral e deixando para os outros a descobrir a matemática específicos (embora eu não olhar bastante trivial)
Martin
2
+1 com um voto positivo forte. (embora eu tivesse vinculado a outro site, o site pbourke parece confuso) Todas as outras respostas até agora são complicadas demais. Embora o seu comentário "Esse ponto também seja o ponto de interseção na linha" esteja incorreto, não há nenhum ponto que tenha sido construído no processo de computação.
Expliquei um pouco melhor sobre o ponto mais próximo, e ligado a Mathworld vez de pbourke :)
Martin
3
Aqui está uma implementação em Javascript. Minha abordagem é primeiro converter o segmento de linha em uma linha infinita e depois encontrar o (s) ponto (s) de interseção. A partir daí, verifico se os pontos encontrados estão no segmento de linha. O código está bem documentado, você deve acompanhar.
// Small epsilon valuevar EPS =0.0000001;// point (x, y)functionPoint(x, y){this.x = x;this.y = y;}// Circle with center at (x,y) and radius rfunctionCircle(x, y, r){this.x = x;this.y = y;this.r = r;}// A line segment (x1, y1), (x2, y2)functionLineSegment(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 = cfunctionLine(a, b, c){this.a = a;this.b = b;this.c = c;// Normalize line for good measureif(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) = 0var 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 = 0if(Math.abs(b)< EPS){// Line equation is ax + by = c, but b = 0, so x = c/a
x1 = c/a;// No intersectionif(Math.abs(x-x1)> r)return[];// Vertical line is tangent to circleif(Math.abs((x1-r)-x)< EPS ||Math.abs((x1+r)-x)< EPS)return[newPoint(x1, y)];var dx =Math.abs(x1 - x);var dy =Math.sqrt(r*r-dx*dx);// Vertical line cuts through circlereturn[newPoint(x1,y+dy),newPoint(x1,y-dy)];// Line is tangent to circle}elseif(Math.abs(D)< EPS){
x1 =-B/(2*A);
y1 =(c - a*x1)/b;return[newPoint(x1,y1)];// No intersection}elseif(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[newPoint(x1, y1),newPoint(x2, y2)];}}// Converts a line segment to a line in general formfunction segmentToGeneralForm(x1,y1,x2,y2){var a = y1 - y2;var b = x2 - x1;var c = x2*y1 - x1*y2;returnnewLine(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 circlefunction 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 intersectionif(pts.length ===0)return[];var pt1 = pts[0];var includePt1 = pointInRectangle(pt1,x1,y1,x2,y2);// Check for unique intersectionif(pts.length ===1){if(includePt1)return[pt1];return[];}var pt2 = pts[1];var includePt2 = pointInRectangle(pt2,x1,y1,x2,y2);// Check for remaining intersectionsif(includePt1 && includePt2)return[pt1, pt2];if(includePt1)return[pt1];if(includePt2)return[pt2];return[];}
Neste post, a colisão da linha do círculo será verificada verificando a distância entre o centro do círculo e o ponto no segmento de linha (Ipoint), que representam o ponto de interseção entre N normal (Imagem 2) do centro do círculo ao segmento de linha.
Na imagem 1, um círculo e uma linha são mostrados, vetor A ponto a ponto ponto inicial, vetor B ponto a ponto final da linha, vetor C ponto ao centro do círculo. Agora devemos 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.
Na imagem 2, podemos ver que o vetor E é projetado no vetor D pelo "produto pontual" do vetor E e pelo vetor unitário D, o resultado do produto pontual é o Xp escalar que representa a distância entre o ponto inicial da linha e o ponto de interseção (Ipoint) de o vetor N e o 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 Ipoint), é fácil a adição simples de vetor do vetor A (ponto inicial na linha) e do vetor X. Em seguida, precisamos lidar com casos especiais que devemos verificar se é Ipoint no segmento de linha, se não é preciso descobrir se é esquerda ou direita, usaremos o vetor mais próximo para determinar qual ponto é o mais próximo do círculo.
Quando a projeção Xp é negativa, o ponto é deixado no segmento de 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, em seguida, Ipoint está à direita do segmento de linha, o vetor mais próximo é igual ao vetor do final da linha. em qualquer outro caso, o vetor mais próximo é igual ao vetor Z.
Agora, quando temos o vetor mais próximo, precisamos encontrar o vetor do centro do círculo até o ponto (vetor dist), é simples subtrair o vetor mais próximo do vetor central. Em seguida, basta verificar se a magnitude do vetor dist é menor que o raio do círculo, se for, então eles colidem, se não houver colisão.
Para finalizar, podemos retornar alguns valores para resolver a colisão, a maneira mais fácil é retornar a sobreposição de colisão (subtrair o raio da magnitude do vetor dist) e retornar o eixo de colisão, seu vetor D. Também o ponto de interseção é o vetor Z, se necessário.
Se as coordenadas da linha são Ax, Ay e Bx, By e o centro dos círculos é Cx, Cy, as fórmulas das linhas sã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ê substituir as fórmulas xey da linha na fórmula dos círculos, obtém uma equação de segunda ordem de te suas soluções são os pontos de interseção (se houver). Se você chegar a um valor menor que 0 ou maior que 1, não será uma solução, mas isso mostra que a linha está 'apontando' para a direção do círculo.
Apenas uma adição a este segmento ... Abaixo está uma versão do código postado por pahlevan, mas para C # / XNA e arrumado um pouco:
/// <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));
}
' 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 função 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;
}
Outro em c # (classe Circle parcial). Testado e funciona como um encanto.
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);
}
Requeridos:
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;
}
// ******************************************************************
}
}
O círculo é realmente um cara mau :) Então, uma boa maneira é evitar o círculo verdadeiro, se você puder. Se você estiver fazendo uma verificação de colisão para jogos, poderá fazer algumas simplificações e ter apenas três produtos de ponto e algumas comparações.
Eu chamo isso de "ponto gordo" ou "círculo fino". seu tipo de elipse com raio zero em uma direção paralela a um segmento. mas raio completo em uma direção perpendicular a um segmento
Primeiro, eu consideraria renomear e alternar o sistema de coordenadas para evitar dados excessivos:
s0s1 = B-A;
s0qp = C-A;
rSqr = r*r;
Segundo, o índice h em hvec2f significa que o vetor deve favorecer operações horizontais, como dot () / det (). O que significa que seus componentes devem ser colocados em um registro xmm separado, para evitar embaralhar / arrumar / arrumar. E aqui vamos nós, com a versão com melhor desempenho da detecção de colisão mais simples para jogos 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;
}
Duvido que você possa otimizá-lo ainda mais. Estou usando-o para a detecção de colisão de corrida de carro com rede neural, para processar milhões de milhões de etapas de iteração.
Se o segmento de linha cruzar o círculo, mas apenas um pouco para que não ultrapasse o ponto central, essa função não retornará false quando deve retornar true? O valor t pode estar fora do intervalo 0..1.
Chris
1
Esta função Java retorna um objeto DVec2. É necessário um DVec2 para o centro do círculo, o raio do círculo e uma linha.
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;
}
Aqui está minha solução no TypeScript, seguindo a ideia que @Mizipzor sugeriu (usando projeção):
/**
* Determines whether a line segment defined by a start and end point intersects with a sphere defined by a center point and a radius
* @param a the start point of the line segment
* @param b the end point of the line segment
* @param c the center point of the sphere
* @param r the radius of the sphere
*/exportfunction lineSphereIntersects(
a:IPoint,
b:IPoint,
c:IPoint,
r: number
): boolean {// find the three sides of the triangle formed by the three pointsconst ab: number = distance(a, b);const ac: number = distance(a, c);const bc: number = distance(b, c);// check to see if either ends of the line segment are inside of the sphereif(ac < r || bc < r){returntrue;}// find the angle between the line segment and the center of the sphereconst numerator: number =Math.pow(ac,2)+Math.pow(ab,2)-Math.pow(bc,2);const denominator: number =2* ac * ab;const cab: number =Math.acos(numerator / denominator);// find the distance from the center of the sphere and the line segmentconst cd: number =Math.sin(cab)* ac;// if the radius is at least as long as the distance between the center and the lineif(r >= cd){// find the distance between the line start and the point on the line closest to// the center of the sphereconst ad: number =Math.cos(cab)* ac;// intersection occurs when the point on the line closest to the sphere center is// no further away than the end of the linereturn ad <= ab;}returnfalse;}exportfunction distance(a:IPoint, b:IPoint): number {returnMath.sqrt(Math.pow(b.z - a.z,2)+Math.pow(b.y - a.y,2)+Math.pow(b.x - a.x,2));}exportinterfaceIPoint{
x: number;
y: number;
z: number;}
Eu sei que já faz um tempo desde que este tópico foi aberto. Da resposta dada por chmike e aprimorada por Aqib Mumtaz. Eles dão uma boa resposta, mas só funcionam para uma linha infinita, como disse Aqib. Então, adiciono algumas comparações para saber se o segmento de linha toca o círculo, eu o escrevo em Python.
def LineIntersectCircle(c, r, p1, p2):
#p1 is the first line point
#p2 is the second line point
#c is the circle's center
#r is the circle's radius
p3 = [p1[0]-c[0], p1[1]-c[1]]
p4 = [p2[0]-c[0], p2[1]-c[1]]
m = (p4[1] - p3[1]) / (p4[0] - p3[0])
b = p3[1] - m * p3[0]
underRadical = math.pow(r,2)*math.pow(m,2) + math.pow(r,2) - math.pow(b,2)
if (underRadical < 0):
print("NOT")
else:
t1 = (-2*m*b+2*math.sqrt(underRadical)) / (2 * math.pow(m,2) + 2)
t2 = (-2*m*b-2*math.sqrt(underRadical)) / (2 * math.pow(m,2) + 2)
i1 = [t1+c[0], m * t1 + b + c[1]]
i2 = [t2+c[0], m * t2 + b + c[1]]
if p1[0] > p2[0]: #Si el punto 1 es mayor al 2 en X
if (i1[0] < p1[0]) and (i1[0] > p2[0]): #Si el punto iX esta entre 2 y 1 en X
if p1[1] > p2[1]: #Si el punto 1 es mayor al 2 en Y
if (i1[1] < p1[1]) and (i1[1] > p2[1]): #Si el punto iy esta entre 2 y 1
print("Intersection")
if p1[1] < p2[1]: #Si el punto 2 es mayo al 2 en Y
if (i1[1] > p1[1]) and (i1[1] < p2[1]): #Si el punto iy esta entre 1 y 2
print("Intersection")
if p1[0] < p2[0]: #Si el punto 2 es mayor al 1 en X
if (i1[0] > p1[0]) and (i1[0] < p2[0]): #Si el punto iX esta entre 1 y 2 en X
if p1[1] > p2[1]: #Si el punto 1 es mayor al 2 en Y
if (i1[1] < p1[1]) and (i1[1] > p2[1]): #Si el punto iy esta entre 2 y 1
print("Intersection")
if p1[1] < p2[1]: #Si el punto 2 es mayo al 2 en Y
if (i1[1] > p1[1]) and (i1[1] < p2[1]): #Si el punto iy esta entre 1 y 2
print("Intersection")
if p1[0] > p2[0]: #Si el punto 1 es mayor al 2 en X
if (i2[0] < p1[0]) and (i2[0] > p2[0]): #Si el punto iX esta entre 2 y 1 en X
if p1[1] > p2[1]: #Si el punto 1 es mayor al 2 en Y
if (i2[1] < p1[1]) and (i2[1] > p2[1]): #Si el punto iy esta entre 2 y 1
print("Intersection")
if p1[1] < p2[1]: #Si el punto 2 es mayo al 2 en Y
if (i2[1] > p1[1]) and (i2[1] < p2[1]): #Si el punto iy esta entre 1 y 2
print("Intersection")
if p1[0] < p2[0]: #Si el punto 2 es mayor al 1 en X
if (i2[0] > p1[0]) and (i2[0] < p2[0]): #Si el punto iX esta entre 1 y 2 en X
if p1[1] > p2[1]: #Si el punto 1 es mayor al 2 en Y
if (i2[1] < p1[1]) and (i2[1] > p2[1]): #Si el punto iy esta entre 2 y 1
print("Intersection")
if p1[1] < p2[1]: #Si el punto 2 es mayo al 2 en Y
if (i2[1] > p1[1]) and (i2[1] < p2[1]): #Si el punto iy esta entre 1 y 2
print("Intersection")
Aqui está uma solução escrita em golang. O método é semelhante a algumas outras respostas postadas aqui, mas não é o mesmo. É fácil de implementar e foi testado. Aqui estão os passos:
Traduzir coordenadas para que o círculo esteja na origem.
Expresse o segmento de linha como funções parametrizadas de t para as coordenadas x e y. Se t for 0, os valores da função serão um ponto final do segmento e se t for 1, os valores da função serão o outro ponto final.
Resolva, se possível, a equação quadrática resultante dos valores de restrição de t que produzem x, y coordena com distâncias da origem iguais ao raio do círculo.
Jogue fora soluções onde t é <0 ou> 1 (<= 0 ou> = 1 para um segmento aberto). Esses pontos não estão contidos no segmento.
Traduzir de volta para as coordenadas originais.
Os valores para A, B e C para o quadrático são derivados aqui, onde (n-et) e (m-dt) são as equações para as coordenadas x e y da linha, respectivamente. r é o raio do círculo.
(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
Portanto A = ee + dd, B = - 2 (en + dm) e C = nn + mm - rr.
Aqui está o código golang para a função:
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
}
Eu testei com esta função, que confirma que os pontos de solução estão dentro do segmento de linha e no círculo. Ele cria um segmento de teste e o varre em torno do círculo especificado:
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.")
}
Aqui está a saída do teste:
=== RUN TestSegmentCircleIntersection
--- PASS: TestSegmentCircleIntersection (0.00s)
geom_test.go:105: Tested 40000 examples and found 7343 solutions.
Finalmente, o método é facilmente extensível ao caso de um raio começando em um ponto, passando pelo outro e estendendo-se até o infinito, testando apenas se t> 0 ou t <1, mas não ambos.
Eu só precisava disso, então criei esta solução. O idioma é maxscript, mas deve ser facilmente traduzido para qualquer outro idioma. sideA, sideB e CircleRadius são escalares, o restante das variáveis são pontos como [x, y, z]. Estou assumindo que z = 0 para resolver no plano 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)
)
def check_line_segment_circle_intersection(line, point, radious):
""" Checks whether a point intersects with a line defined by two points.
A `point` is list with two values: [2, 3]
A `line` is list with two points: [point1, point2]
"""
line_distance = distance(line[0], line[1])
distance_start_to_point = distance(line[0], point)
distance_end_to_point = distance(line[1], point)
if (distance_start_to_point <= radious or distance_end_to_point <= radious):
return True
# angle between line and point with law of cosines
numerator = (math.pow(distance_start_to_point, 2)
+ math.pow(line_distance, 2)
- math.pow(distance_end_to_point, 2))
denominator = 2 * distance_start_to_point * line_distance
ratio = numerator / denominator
ratio = ratio if ratio <= 1 else 1 # To account for float errors
ratio = ratio if ratio >= -1 else -1 # To account for float errors
angle = math.acos(ratio)
# distance from the point to the line with sin projection
distance_line_to_point = math.sin(angle) * distance_start_to_point
if distance_line_to_point <= radious:
point_projection_in_line = math.cos(angle) * distance_start_to_point
# Intersection occurs whent the point projection in the line is less
# than the line distance and positive
return point_projection_in_line <= line_distance and point_projection_in_line >= 0
return False
def distance(point1, point2):
return math.sqrt(
math.pow(point1[1] - point2[1], 2) +
math.pow(point1[0] - point2[0], 2)
)
Function lineCircleCollision(p1,p2,c,r,precision){
Let dx = (p2.x-p1.x)/precision
Let dy = (p2.y-p1.y)/precision
Let collision=false
For(let i = 0;i<precision:i++){
If(Math.sqrt((p1.x+dx*i-c.x)**2+(p1.y+dy*i-c.y)**2).<r {
Collision=true
}
}
Você pode pegar X pontos espaçados uniformemente da linha e, se houver algum dentro do círculo, há uma colisão
Respostas:
Levando
Cálculo:
d = L - E (vetor de direção do raio, do início ao fim)
f = E - C (vetor da esfera central ao início do raio)
Então a interseção é encontrada por ..
Plugging:
P = E + t * d
Esta é uma equação paramétrica:
P x = E x + td x
P y = E y + td y
em
(x - h) 2 + (y - k) 2 = r 2
(h, k) = centro do círculo.
para obter:
x 2 - 2xh + h 2 + y 2 - 2yk + k 2 - r 2 = 0
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
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
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
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. *
t 2 (_d * _d) + 2t (_d * (_e - _c)) + (_e - _c) * (_e - _c) - r 2 = 0
t 2 (_d * _d) + 2t (_d * _f) + _f * _f - r 2 = 0
Portanto, obtemos:
t 2 * (d DOT d) + 2t * (f DOT d) + (f DOT f - r 2 ) = 0
Portanto, resolvendo a equação quadrática:
fonte
P = E + t * d
O que ét
?Ninguém parece considerar a projeção, estou completamente fora dos trilhos aqui?
Projete o vetor
AC
emAB
. O vetor projetado,,AD
dá o novo pontoD
.Se a distância entre
D
eC
é menor que (ou igual a)R
, temos uma interseção.Como isso:
fonte
CD
é uma projeção, é perpendicular por definição.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.
Digamos 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.
Este algoritmo requer que A, B e C sejam pontos distintos e que R não seja 0.
Aqui está o algoritmo
fonte
t+dt
et-dt
na linha.t
é o ponto na linha mais próxima do centro do círculo. Os pontos de interseção com o círculo estão a uma distância simétrica det
. Os pontos de interseção estão em "distâncias"t-dt
et+dt
. Eu citei distância porque não é a distância euclidiana. Para obter a distância euclidiana deA
ondet=0
, você deve multiplicar o valor porLAB
.t=0
. Ponto B emt=LAB
. Quando os dois pontos de interseção (t1=t-td
et2=t+td
) têm valores negativos, as interseções ficam fora da seção (atrás do ponto A, olhando pelo lado da seção). Quando t1 e t2 são maiores que LAB, eles também estão fora (desta vez atrás do ponto B). A interseção t1 (ou t2) ocorre entre A e B somente quando t1 (ou t2) está entre 0 e LAB.Ok, não vou dar o código, mas desde que você marcou isso algoritmo, Não acho que isso importe para você. Primeiro, você deve 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 passar pelo centro do círculo.
Ou seja,
conecte o local do centro do círculo à equação da linha e resolva
c
.Em seguida, calcule o ponto de interseção da linha original e seu normal.
Isso lhe dará o ponto mais próximo da linha ao 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, temos uma interseção!
fonte
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 exige mais trabalho. Pelo menos, será atrasado até o ponto 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 menor distância entre C, o centro do círculo e a linha.
Como a área do triângulo também pode ser calculada por um produto vetorial, podemos determinar h.
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.
Computar o ponto de interseção não é tão difícil. Aqui vai
Se h = R, a linha AB é tangente ao círculo e o valor dt = 0 e E = F. As coordenadas do ponto são as de E e F.
Você deve verificar se A é diferente de B e o comprimento do segmento não é nulo, se isso acontecer no seu aplicativo.
fonte
Escrevi um pequeno script para testar a interseção projetando o ponto central do círculo na linha.
http://jsfiddle.net/ercang/ornh3594/1/
Se você precisar verificar a colisão com o segmento, considere também a distância do centro do círculo aos pontos inicial e final.
https://jsfiddle.net/ercang/menp0991/
fonte
Esta solução que encontrei parecia um pouco mais fácil de seguir do que algumas outras.
Levando:
Eu resolveria a equação da reta na forma de interceptação de inclinação. No entanto, eu não queria ter que lidar com equações difíceis
c
como um ponto, então apenas mudei o sistema de coordenadas para que o círculo estivesse em0,0
A propósito, sempre que subtraio pontos um do outro, subtraio os
x
e depois subtraí osy
, colocando-os em um novo ponto, caso alguém não saiba.Enfim, agora resolvo a equação da linha com
p3
ep4
:Está bem. Agora eu preciso definir essas equações iguais. Primeiro, preciso resolver a equação do círculo para
x
Então eu os coloco iguais:
E resolva a equação quadrática (
0 = ax^2 + bx + c
):Agora eu tenho o meu
a
,b
ec
.Então, eu coloquei isso na fórmula quadrática:
E substitua por valores e simplifique o máximo possível:
Isso é quase o máximo possível. Por fim, separe as equações com ±:
Em seguida, basta conectar o resultado dessas duas equações ao
x
inmx + b
. Para maior clareza, escrevi algum código JavaScript para mostrar como usar isso:Eu espero que isso ajude!
PS Se alguém encontrar algum erro ou tiver alguma sugestão, por favor, comente. Sou muito novo e bem-vindo a toda ajuda / sugestões.
fonte
underRadical
extra ')'Você pode encontrar um ponto em uma linha infinita 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 for 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 for menor que R, existem 2 pontos de interseção. Eles ficam à 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:
EDIT: código adicionado para verificar se os pontos de interseção encontrados realmente estão dentro do segmento de linha.
fonte
Estranhamente, posso responder, mas não comentar ... Gostei da abordagem da Multitaskpro de mudar tudo para fazer o centro do círculo cair sobre a origem. Infelizmente, existem dois problemas em seu código. Primeiro na parte da raiz quadrada, você precisa remover a dupla potência. 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 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+c.x, y:m*t1+b+c.y};
Toda a função se torna:
fonte
Você precisará de matemática aqui:
Suponha que 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 tem distância R a C, ele deve estar no círculo. O que você quer é resolver
isso é
se você aplicar a fórmula ABC a esta equação para resolvê-la para alfa e calcular as coordenadas de P usando as soluções para alfa, obterá os pontos de interseção, se houver algum.
fonte
Se você encontrar a distância entre o centro da esfera (já que é 3D, presumo que você queira dizer esfera e não círculo) e a linha, 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
fonte
Aqui está uma implementação em Javascript. Minha abordagem é primeiro converter o segmento de linha em uma linha infinita e depois encontrar o (s) ponto (s) de interseção. A partir daí, verifico se os pontos encontrados estão no segmento de linha. O código está bem documentado, você deve acompanhar.
Você pode experimentar o código aqui nesta demonstração ao vivo . O código foi retirado do repositório de algoritmos .
fonte
Neste post, a colisão da linha do círculo será verificada verificando a distância entre o centro do círculo e o ponto no segmento de linha (Ipoint), que representam o ponto de interseção entre N normal (Imagem 2) do centro do círculo ao segmento de linha.
( https://i.stack.imgur.com/3o6do.png )
Na imagem 1, um círculo e uma linha são mostrados, vetor A ponto a ponto ponto inicial, vetor B ponto a ponto final da linha, vetor C ponto ao centro do círculo. Agora devemos 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 )
Na imagem 2, podemos ver que o vetor E é projetado no vetor D pelo "produto pontual" do vetor E e pelo vetor unitário D, o resultado do produto pontual é o Xp escalar que representa a distância entre o ponto inicial da linha e o ponto de interseção (Ipoint) de o vetor N e o 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 Ipoint), é fácil a adição simples de vetor do vetor A (ponto inicial na linha) e do vetor X. Em seguida, precisamos lidar com casos especiais que devemos verificar se é Ipoint no segmento de linha, se não é preciso descobrir se é esquerda ou direita, usaremos o vetor mais próximo para determinar qual ponto é o mais próximo do círculo.
( https://i.stack.imgur.com/p9WIr.png )
Quando a projeção Xp é negativa, o ponto é deixado no segmento de 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, em seguida, Ipoint está à direita do segmento de linha, o vetor mais próximo é igual ao vetor do final da linha. em qualquer outro caso, o vetor mais próximo é igual ao vetor Z.
Agora, quando temos o vetor mais próximo, precisamos encontrar o vetor do centro do círculo até o ponto (vetor dist), é simples subtrair o vetor mais próximo do vetor central. Em seguida, basta verificar se a magnitude do vetor dist é menor que o raio do círculo, se for, então eles colidem, se não houver colisão.
( https://i.stack.imgur.com/QJ63q.png )
Para finalizar, podemos retornar alguns valores para resolver a colisão, a maneira mais fácil é retornar a sobreposição de colisão (subtrair o raio da magnitude do vetor dist) e retornar o eixo de colisão, seu vetor D. Também o ponto de interseção é o vetor Z, se necessário.
fonte
Se as coordenadas da linha são Ax, Ay e Bx, By e o centro dos círculos é Cx, Cy, as fórmulas das linhas sã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ê substituir as fórmulas xey da linha na fórmula dos círculos, obtém uma equação de segunda ordem de te suas soluções são os pontos de interseção (se houver). Se você chegar a um valor menor que 0 ou maior que 1, não será uma solução, mas isso mostra que a linha está 'apontando' para a direção do círculo.
fonte
Apenas uma adição a este segmento ... Abaixo está uma versão do código postado por pahlevan, mas para C # / XNA e arrumado um pouco:
fonte
Ray.Intersects(BoundingSphere)
fonte
Eu criei esta função para iOS seguindo a resposta dada por
chmike
fonte
Outro em c # (classe Circle parcial). Testado e funciona como um encanto.
Requeridos:
fonte
Aqui está uma boa solução em JavaScript (com toda a matemática necessária e ilustração ao vivo) https://bl.ocks.org/milkbread/11000965
Embora a
is_on
função nessa solução precise de modificações:fonte
O círculo é realmente um cara mau :) Então, uma boa maneira é evitar o círculo verdadeiro, se você puder. Se você estiver fazendo uma verificação de colisão para jogos, poderá fazer algumas simplificações e ter apenas três produtos de ponto e algumas comparações.
Eu chamo isso de "ponto gordo" ou "círculo fino". seu tipo de elipse com raio zero em uma direção paralela a um segmento. mas raio completo em uma direção perpendicular a um segmento
Primeiro, eu consideraria renomear e alternar o sistema de coordenadas para evitar dados excessivos:
Segundo, o índice h em hvec2f significa que o vetor deve favorecer operações horizontais, como dot () / det (). O que significa que seus componentes devem ser colocados em um registro xmm separado, para evitar embaralhar / arrumar / arrumar. E aqui vamos nós, com a versão com melhor desempenho da detecção de colisão mais simples para jogos 2D:
Duvido que você possa otimizá-lo ainda mais. Estou usando-o para a detecção de colisão de corrida de carro com rede neural, para processar milhões de milhões de etapas de iteração.
fonte
Esta função Java retorna um objeto DVec2. É necessário um DVec2 para o centro do círculo, o raio do círculo e uma linha.
fonte
Aqui está minha solução no TypeScript, seguindo a ideia que @Mizipzor sugeriu (usando projeção):
fonte
Eu sei que já faz um tempo desde que este tópico foi aberto. Da resposta dada por chmike e aprimorada por Aqib Mumtaz. Eles dão uma boa resposta, mas só funcionam para uma linha infinita, como disse Aqib. Então, adiciono algumas comparações para saber se o segmento de linha toca o círculo, eu o escrevo em Python.
fonte
Aqui está uma solução escrita em golang. O método é semelhante a algumas outras respostas postadas aqui, mas não é o mesmo. É fácil de implementar e foi testado. Aqui estão os passos:
Os valores para A, B e C para o quadrático são derivados aqui, onde (n-et) e (m-dt) são as equações para as coordenadas x e y da linha, respectivamente. r é o raio do círculo.
Portanto A = ee + dd, B = - 2 (en + dm) e C = nn + mm - rr.
Aqui está o código golang para a função:
Eu testei com esta função, que confirma que os pontos de solução estão dentro do segmento de linha e no círculo. Ele cria um segmento de teste e o varre em torno do círculo especificado:
Aqui está a saída do teste:
Finalmente, o método é facilmente extensível ao caso de um raio começando em um ponto, passando pelo outro e estendendo-se até o infinito, testando apenas se t> 0 ou t <1, mas não ambos.
fonte
Eu só precisava disso, então criei esta solução. O idioma é maxscript, mas deve ser facilmente traduzido para qualquer outro idioma. sideA, sideB e CircleRadius são escalares, o restante das variáveis são pontos como [x, y, z]. Estou assumindo que z = 0 para resolver no plano XY
fonte
Solução em python, baseada em @Joe Skeen
fonte
Você pode pegar X pontos espaçados uniformemente da linha e, se houver algum dentro do círculo, há uma colisão
fonte