원 선분 충돌 감지 알고리즘?
https://stackoverflow.com/questions/1073336
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
A에서 B까지의 선이 있고 C에 반지름이 R인 원이 있습니다.
선이 원과 교차하는지 확인하는 데 사용할 수 있는 좋은 알고리즘은 무엇입니까?그리고 원 가장자리를 따라 어떤 좌표에서 발생했습니까?
해결책
취득
- 이자형 광선의 출발점입니다.
- 엘 광선의 종말점입니다.
- 씨 당신이 테스트하는 구체의 중심입니다
- 아르 자형 그 구체의 반경입니다
컴퓨팅 :
디 = l -e (광선의 방향 벡터, 처음부터 끝까지)
에프 = E -C (중앙 구에서 Ray Start까지 벡터)
그런 다음 교차로는 ..
플러그 :
p = e + t * d
이것은 파라 메트릭 방정식입니다.
피엑스 = e엑스 + TD엑스
피와이 = e와이 + TD와이
~ 안으로
(X -H)2 + (Y -K)2 = r2
(H, K) = 원의 중심.
참고 : 문제를 2D로 단순화했습니다. 여기서는 3D에도 적용됩니다.
얻기 위해 :
- 확장하다
엑스2 -2xh + h2 + y2 -2yk + k2 -R2 = 0 - 플러그
x = e엑스 + TD엑스
y = e와이 + TD와이
(e엑스 + TD엑스 )2 -2 (e엑스 + TD엑스 ) h + h2 + (e와이 + TD와이 )2 -2 (e와이 + TD와이 ) k + k2 -R2 = 0 - 터지다
이자형엑스2 + 2E엑스TD엑스 + t2디엑스2 -2E엑스H -2TD엑스H + h2 + e와이2 + 2E와이TD와이 + t2디와이2 -2E와이K -2TD와이K + K2 -R2 = 0 - 그룹
티2(d엑스2 + d와이2 ) + 2T (e엑스디엑스 + e와이디와이 -d엑스H -d와이k) + e엑스2 + e와이2 -2E엑스H -2E와이K + h2 + k2 -R2 = 0 - 드디어,
티2(_d * _d) + 2t (_e * _d -_d * _c) + _e * _e -2 (_e * _c) + _c * _c -r2 = 0
* 여기서 _d는 벡터 D이고 *는 도트 제품입니다. * - 그리고,
티2(_d * _d) + 2t (_d * (_e -_c)) + (_e -_c) * (_e -_c) -r2 = 0 - _f = _e -_c를 보자
티2(_d * _d) + 2t (_d * _f) + _f * _f -r2 = 0
그래서 우리는 얻는다 :
티2 * (D DOT D) + 2T* (F DOT D) + (F DOT F -R2 ) = 0
이차 방정식을 해결하기 :
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 ;
}
다른 팁
아무도 투영을 고려하지 않는 것 같습니다. 여기서 완전히 추적됩니까?
벡터를 투사하십시오 AC 에 AB. 투영 된 벡터, AD, 새로운 요점을 제공합니다 D.
사이의 거리 D 그리고 C (또는 동일)보다 작습니다. R 우리는 교차로가 있습니다.
이와 같이:
알고리즘을 사용하여 지점 (원 중심)과 라인 (라인 AB) 사이의 거리를 계산합니다. 그런 다음이를 사용하여 원과 라인의 교차점을 결정할 수 있습니다.
포인트 A, B, C. AX 및 Ay는 A 포인트의 X 및 Y 구성 요소라고 가정 해 봅시다. B와 C에 대해 동일합니다. 스칼라 R은 원 반경입니다.
이 알고리즘은 a, b 및 c가 뚜렷한 점이며 r은 0이 아니라고 요구합니다.
알고리즘은 다음과 같습니다
// 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
알겠습니다. 코드를 제공하지는 않겠습니다. 하지만 태그를 지정했으므로 연산, 내 생각엔 그건 당신에게 중요하지 않을 것 같아요.먼저, 선에 수직인 벡터를 얻어야 합니다.
알 수 없는 변수가 있습니다. y = ax + c ( c 알려지지 않을 것이다 )
이를 해결하려면 선이 원의 중심을 통과할 때의 값을 계산하세요.
그건,
원 중심의 위치를 선 방정식에 연결하고 다음을 해결합니다. c.
그런 다음 원래 선과 법선의 교차점을 계산합니다.
그러면 선에서 원에 가장 가까운 지점이 표시됩니다.
이 점과 원 중심 사이의 거리를 계산합니다(벡터의 크기를 사용하여).
이것이 원의 반경보다 작다면 짜잔, 교차점이 생겼습니다!
다른 방법은 삼각형 ABC 영역 공식을 사용합니다. 교차 테스트는 프로젝션 방법보다 간단하고 효율적이지만 교차점의 좌표를 찾으려면 더 많은 작업이 필요합니다. 적어도 필요한 시점까지 지연 될 것입니다.
삼각형 영역을 계산하는 공식은 다음과 같습니다. 면적 = BH/2
여기서 B는 기본 길이이고 H는 높이입니다. 우리는 세그먼트 AB를 기본으로 선택하여 h가 C, 원 중심에서 줄까지 가장 짧은 거리가되도록 선택했습니다.
삼각형 영역은 벡터 도트 생성물에 의해 계산 될 수 있으므로 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 )
{
...
}
UPDATE 1 :
설명 된 빠른 역 제곱근 계산을 사용하여 코드를 최적화 할 수 있습니다. 여기 1/실험실의 좋은 근사치를 얻으려면.
교차점을 계산하는 것은 그리 어렵지 않습니다. 여기 간다
// 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
h = r이면 선 AB는 원에 접하는 것이고 값 dt = 0 및 e = F입니다. 점 좌표는 e와 f의 것입니다.
A가 B와 다르고 응용 프로그램에서 발생할 수있는 경우 세그먼트 길이가 무효가 아닌지 확인해야합니다.
나는 서클의 중심 지점을 라인에 투사하여 교차로를 테스트하기 위해 작은 대본을 썼습니다.
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/
세그먼트와의 충돌을 확인 해야하는 경우 서클 센터의 거리를 고려하여 시작 및 엔드 포인트를 고려해야합니다.
vector distVector = centerPoint - startPoint;
if(distVector.length() < circle.radius)
{
double distance = circle.radius - distVector.length();
vector moveVector = distVector.normalize() * distance;
circle.move(moveVector);
}
내가 찾은이 솔루션은 다른 것 중 일부를 따르기가 조금 더 쉬워 보였습니다.
취득:
p1 and p2 as the points for the line, and
c as the center point for the circle and r for the radius
나는 경사 간격 형태의 선 방정식을 해결할 것입니다. 그러나 나는 어려운 방정식을 다루고 싶지 않았다. c 요점으로서, 나는 원이 0,0
p3 = p1 - c
p4 = p2 - c
그건 그렇고, 내가 서로에서 포인트를 빼면 나는 xS를 빼고 y누군가가 모르는 경우를 대비하여 새로운 지점에 넣습니다.
어쨌든, 나는 이제 라인의 방정식을 해결합니다. p3 그리고 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)
확인. 이제이 방정식을 동일하게 설정해야합니다. 먼저 원의 방정식을 해결해야합니다. x
x^2 + y^2 = r^2
y^2 = r^2 - x^2
y = sqrt(r^2 - x^2)
그런 다음 동일하게 설정했습니다.
mx + b = sqrt(r^2 - x^2)
2 차 방정식에 대한 해결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
이제 내가 있습니다 a, b, 그리고 c.
a = m^2 + 1
b = 2mb
c = b^2 - r^2
그래서 이것을 2 차 공식에 넣었습니다.
(-b ± sqrt(b^2 - 4ac)) / 2a
그리고 값으로 대체 한 다음 가능한 한 많이 단순화하십시오.
(-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
이것은 단순화 할 정도로 거의입니다. 마지막으로, ± :
(-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
그런 다음 두 방정식의 결과를 x 안에 mx + b. 명확성을 위해, 나는 이것을 사용하는 방법을 보여주기 위해 JavaScript 코드를 작성했습니다.
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];
}
}
이게 도움이 되길 바란다!
추신 : 누군가 오류를 찾거나 제안이 있으면 의견을 제시하십시오. 나는 매우 새롭고 모든 도움/제안을 환영합니다.
벡터 AC를 벡터 AB에 투사하여 Circle Center에 가장 가까운 무한 선에서 포인트를 찾을 수 있습니다. 해당 지점과 원 센터 사이의 거리를 계산하십시오. R보다 더 큰 경우 교차로가 없습니다. 거리가 r과 같으면 선은 원의 접선이고 원 중심에서 가장 가까운 지점은 실제로 교차점입니다. 거리가 r보다 작 으면 두 개의 교차점이 있습니다. 그들은 가장 가까운 지점에서 Circle Center까지 같은 거리에 있습니다. 이 거리는 피타고라스 정리를 사용하여 쉽게 계산할 수 있습니다. 유사 코드의 알고리즘은 다음과 같습니다.
{
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
}
}
편집 : 발견 된 교차점이 실제로 라인 세그먼트 내에 있는지 확인하기 위해 코드가 추가되었습니다.
이상하게도 대답 할 수는 있지만 댓글을 달 수는 없습니다 ... 나는 원의 중심이 원점에 떨어지도록 모든 것을 바꾸는 MultitaskPro의 접근을 좋아했습니다. 불행히도 그의 코드에는 두 가지 문제가 있습니다. 먼저 제곱 뿌리 아래 부품에서는 이중 전력을 제거해야합니다. 그래서 :
var underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2));
하지만:
var underRadical = Math.pow(r,2)*(Math.pow(m,2)+1)) - Math.pow(b,2);
최종 좌표에서 그는 솔루션을 다시 전환하는 것을 잊어 버립니다. 그래서 :
var i1 = {x:t1,y:m*t1+b}
하지만:
var i1 = {x:t1+c.x, y:m*t1+b+c.y};
그런 다음 전체 기능이 다음과 같습니다.
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];
}
}
여기에는 몇 가지 수학이 필요합니다.
a = (xa, ya), b = (xb, yb) 및 c = (xc, yc)라고 가정합니다. A에서 B 로의 라인의 모든 지점에는 좌표가 있습니다 (alpha*xa + (1-Alpha)XB, 알파Ya + (1- 알파)*yb) = p
지점 P의 거리 r에서 c에서 c가 있으면 원에 있어야합니다. 당신이 원하는 것은 해결하는 것입니다
distance(P, C) = R
그건
(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
ABC- 형식을이 방정식에 적용하여 알파 용으로 해결하고 알파 용 솔루션을 사용하여 P의 좌표를 계산하는 경우, 존재하는 경우 교차점을 얻습니다.
구의 중심 사이의 거리를 찾으면 (3D이기 때문에 원이 아닌 구체를 의미한다고 가정하고) 라인이 그 거리가 트릭을 수행 할 반경보다 적은지 확인하십시오.
충돌 지점은 분명히 선과 구 사이의 가장 가까운 지점입니다 (구와 선 사이의 거리를 계산할 때 계산됩니다).
점과 선 사이의 거리 :
http://mathworld.wolfram.com/point-linedistance3-dimensional.html
JavaScript의 구현은 다음과 같습니다. 내 접근 방식은 먼저 라인 세그먼트를 무한 선으로 변환 한 다음 교차점을 찾는 것입니다. 거기에서 나는 발견 된 포인트가 줄 세그먼트에 있는지 확인합니다. 코드는 잘 문서화되어 있으므로 따라갈 수 있어야합니다.
여기에서 코드를 시험해 볼 수 있습니다 라이브 데모. 코드는 내에서 가져 왔습니다 알고리즘 repo.
// Small epsilon value
var EPS = 0.0000001;
// point (x, y)
function Point(x, y) {
this.x = x;
this.y = y;
}
// Circle with center at (x,y) and radius r
function Circle(x, y, r) {
this.x = x;
this.y = y;
this.r = r;
}
// A line segment (x1, y1), (x2, y2)
function LineSegment(x1, y1, x2, y2) {
var d = Math.sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
if (d < EPS) throw 'A point is not a line segment';
this.x1 = x1; this.y1 = y1;
this.x2 = x2; this.y2 = y2;
}
// An infinite line defined as: ax + by = c
function Line(a, b, c) {
this.a = a; this.b = b; this.c = c;
// Normalize line for good measure
if (Math.abs(b) < EPS) {
c /= a; a = 1; b = 0;
} else {
a = (Math.abs(a) < EPS) ? 0 : a / b;
c /= b; b = 1;
}
}
// Given a line in standard form: ax + by = c and a circle with
// a center at (x,y) with radius r this method finds the intersection
// of the line and the circle (if any).
function circleLineIntersection(circle, line) {
var a = line.a, b = line.b, c = line.c;
var x = circle.x, y = circle.y, r = circle.r;
// Solve for the variable x with the formulas: ax + by = c (equation of line)
// and (x-X)^2 + (y-Y)^2 = r^2 (equation of circle where X,Y are known) and expand to obtain quadratic:
// (a^2 + b^2)x^2 + (2abY - 2ac + - 2b^2X)x + (b^2X^2 + b^2Y^2 - 2bcY + c^2 - b^2r^2) = 0
// Then use quadratic formula X = (-b +- sqrt(a^2 - 4ac))/2a to find the
// roots of the equation (if they exist) and this will tell us the intersection points
// In general a quadratic is written as: Ax^2 + Bx + C = 0
// (a^2 + b^2)x^2 + (2abY - 2ac + - 2b^2X)x + (b^2X^2 + b^2Y^2 - 2bcY + c^2 - b^2r^2) = 0
var A = a*a + b*b;
var B = 2*a*b*y - 2*a*c - 2*b*b*x;
var C = b*b*x*x + b*b*y*y - 2*b*c*y + c*c - b*b*r*r;
// Use quadratic formula x = (-b +- sqrt(a^2 - 4ac))/2a to find the
// roots of the equation (if they exist).
var D = B*B - 4*A*C;
var x1,y1,x2,y2;
// Handle vertical line case with b = 0
if (Math.abs(b) < EPS) {
// Line equation is ax + by = c, but b = 0, so x = c/a
x1 = c/a;
// No intersection
if (Math.abs(x-x1) > r) return [];
// Vertical line is tangent to circle
if (Math.abs((x1-r)-x) < EPS || Math.abs((x1+r)-x) < EPS)
return [new Point(x1, y)];
var dx = Math.abs(x1 - x);
var dy = Math.sqrt(r*r-dx*dx);
// Vertical line cuts through circle
return [
new Point(x1,y+dy),
new Point(x1,y-dy)
];
// Line is tangent to circle
} else if (Math.abs(D) < EPS) {
x1 = -B/(2*A);
y1 = (c - a*x1)/b;
return [new Point(x1,y1)];
// No intersection
} else if (D < 0) {
return [];
} else {
D = Math.sqrt(D);
x1 = (-B+D)/(2*A);
y1 = (c - a*x1)/b;
x2 = (-B-D)/(2*A);
y2 = (c - a*x2)/b;
return [
new Point(x1, y1),
new Point(x2, y2)
];
}
}
// Converts a line segment to a line in general form
function segmentToGeneralForm(x1,y1,x2,y2) {
var a = y1 - y2;
var b = x2 - x1;
var c = x2*y1 - x1*y2;
return new Line(a,b,c);
}
// Checks if a point 'pt' is inside the rect defined by (x1,y1), (x2,y2)
function pointInRectangle(pt,x1,y1,x2,y2) {
var x = Math.min(x1,x2), X = Math.max(x1,x2);
var y = Math.min(y1,y2), Y = Math.max(y1,y2);
return x - EPS <= pt.x && pt.x <= X + EPS &&
y - EPS <= pt.y && pt.y <= Y + EPS;
}
// Finds the intersection(s) of a line segment and a circle
function lineSegmentCircleIntersection(segment, circle) {
var x1 = segment.x1, y1 = segment.y1, x2 = segment.x2, y2 = segment.y2;
var line = segmentToGeneralForm(x1,y1,x2,y2);
var pts = circleLineIntersection(circle, line);
// No intersection
if (pts.length === 0) return [];
var pt1 = pts[0];
var includePt1 = pointInRectangle(pt1,x1,y1,x2,y2);
// Check for unique intersection
if (pts.length === 1) {
if (includePt1) return [pt1];
return [];
}
var pt2 = pts[1];
var includePt2 = pointInRectangle(pt2,x1,y1,x2,y2);
// Check for remaining intersections
if (includePt1 && includePt2) return [pt1, pt2];
if (includePt1) return [pt1];
if (includePt2) return [pt2];
return [];
}
이 Post Circle Line 충돌은 원 중심에서 라인 세그먼트에 이르기까지 정상 N (이미지 2) 사이의 교차점을 나타내는 원 중
(https://i.stack.imgur.com/3o6do.png)
이미지 1 하나의 원과 하나의 라인이 표시되고, 벡터 A는 선 시작점, 벡터 B 포인트에서 라인 엔드 포인트, 벡터 C는 원 중심에서 포인트입니다. 이제 벡터 E (라인 시작점에서 원 중심으로)와 벡터 D (라인 시작점에서 라인 엔드 포인트까지)를 찾아야합니다.이 계산은 이미지 1에 표시됩니다.
(https://i.stack.imgur.com/7098a.png)
이미지 2에서 벡터 E가 벡터 E와 단위 벡터 D의 "도트 곱"에 의해 벡터 D에 투사되는 것을 볼 수 있습니다. 도트 제품의 결과는 라인 시작점과 교차점 (iPoint) 사이의 거리를 나타내는 스칼라 XP입니다. 벡터 N 및 벡터 D. 다음 벡터 X는 단위 벡터 D 및 스칼라 XP를 곱하여 발견된다.
이제 우리는 벡터 z (벡터에서 iPoint)를 찾아야합니다. 벡터 A (출발점 온 라인) 및 벡터 X의 간단한 벡터 첨가는 쉽게 찾아야합니다. 다음은 특별 케이스를 처리해야합니다. 그것은 우리가 그것을 왼쪽이나 오른쪽으로 찾아야한다는 것을 알아야합니다. 우리는 벡터를 가장 가까운 벡터를 사용하여 어떤 지점이 원에 가장 가까운 지 결정합니다.
(https://i.stack.imgur.com/p9wir.png)
프로젝션 XP가 음의 iPoint가 라인 세그먼트가 남아있을 때, 가장 가까운 벡터는 선 시작점의 벡터와 동일합니다. 투영 XP가 벡터 D의 크기보다 더 큰 경우 iPoint가 라인 세그먼트의 오른쪽이면 가장 가까운 벡터는 선 끝의 벡터와 같습니다. 다른 경우 가장 가까운 벡터는 벡터 Z와 같습니다.
이제 가장 가까운 벡터가 있으면 서클 중심에서 iPoint (Dist Vector)까지 벡터를 찾아야합니다. 간단하게 중앙 벡터에서 가장 가까운 벡터를 빼야합니다. 다음으로 벡터 디스크 크기가 원이 늘어나지 않으면 충돌이 없으면 충돌이 발생하는 경우 반경 반경이 적습니다.
(https://i.stack.imgur.com/qj63q.png)
끝을 위해 충돌 해결을위한 일부 값을 반환 할 수 있습니다. 가장 쉬운 방법은 충돌의 중첩 (벡터 디스크 크기에서 반경을 빼기)과 충돌 축, 벡터 D도 필요한 경우 벡터 z입니다.
라인의 좌표가 AX, AY 및 BX, By 및 Circles Center는 CX, CY 인 경우 라인 공식은 다음과 같습니다.
x = ax * t + bx * (1 -t)
y = ay * t + by * (1 -t)
여기서 0 <= t <= 1
그리고 원은입니다
(cx -x)^2 + (cy -y)^2 = r^2
라인의 x와 y 공식을 원형 공식으로 대체하면 t의 2 차 방정식을 얻고 해당 솔루션은 교차점입니다 (있는 경우). 당신이 0보다 작거나 1보다 큰 것을 얻으면 솔루션은 아니지만 선이 원의 방향을 '포인트'하고 있음을 보여줍니다.
이 스레드에 추가 된 것만 ... 아래는 Pahlevan이 게시 한 코드의 버전이지만 C#/XNA 용은 다음과 같습니다.
/// <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
주어진 답변에 따라 iOS를 위해이 기능을 만들었습니다. 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;
}
이 Java 함수는 DVEC2 객체를 반환합니다. 필요합니다 DVEC2 원의 중심, 원의 반경 및 선.
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;
}
C#의 다른 하나 (부분 원 클래스). 테스트하고 매력처럼 작동합니다.
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);
}
필수의:
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;
}
// ******************************************************************
}
}
JavaScript의 좋은 솔루션은 다음과 같습니다 (모든 필수 수학 및 라이브 일러스트)https://bl.ocks.org/milkbread/11000965
그렇지만 is_on 해당 솔루션의 기능 수정이 필요합니다.
function is_on(a, b, c) {
return Math.abs(distance(a,c) + distance(c,b) - distance(a,b))<0.000001;
}원은 정말 나쁜 사람입니다 :) 그래서 좋은 방법은 가능한 경우 진정한 원을 피하는 것입니다. 게임에 대한 충돌 점검을하고 있다면 단순화를 통해 갈 수 있고 단 3 개의 도트 제품과 몇 가지 비교를 가질 수 있습니다.
나는 이것을 "지방 지점"또는 "얇은 원"이라고 부릅니다. 세그먼트와 평행 한 방향으로 반경이 0 인 일종의 타원. 그러나 세그먼트에 수직 인 방향의 전체 반경
먼저 과도한 데이터를 피하기 위해 변환 시스템을 바꾸고 스위칭하는 것을 고려할 것입니다.
s0s1 = B-A;
s0qp = C-A;
rSqr = r*r;
둘째, 벡터보다 HVEC2F 평균의 인덱스 H는 dot ()/det ()와 같은 수평 연산을 선호해야합니다. 이는 셔플 링/hadd'ing/hsub'ing을 피하기 위해 구성 요소가 별도의 XMM 레지스터에 배치되어야 함을 의미합니다. 그리고 여기서 우리는 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;
}
더 이상 최적화 할 수 있을지 의심 스럽다. 나는 신경망 구동 자동차 경주 충돌 감지에 그것을 사용하여 수백만 반복 단계를 처리하고 있습니다.
다음은 @mizipzor가 제안한 아이디어 (투영 사용) : 다음과 같습니다.
/**
* Determines whether a line segment defined by a start and end point intersects with a sphere defined by a center point and a radius
* @param a the start point of the line segment
* @param b the end point of the line segment
* @param c the center point of the sphere
* @param r the radius of the sphere
*/
export function lineSphereIntersects(
a: IPoint,
b: IPoint,
c: IPoint,
r: number
): boolean {
// find the three sides of the triangle formed by the three points
const ab: number = distance(a, b);
const ac: number = distance(a, c);
const bc: number = distance(b, c);
// check to see if either ends of the line segment are inside of the sphere
if (ac < r || bc < r) {
return true;
}
// find the angle between the line segment and the center of the sphere
const numerator: number = Math.pow(ac, 2) + Math.pow(ab, 2) - Math.pow(bc, 2);
const denominator: number = 2 * ac * ab;
const cab: number = Math.acos(numerator / denominator);
// find the distance from the center of the sphere and the line segment
const cd: number = Math.sin(cab) * ac;
// if the radius is at least as long as the distance between the center and the line
if (r >= cd) {
// find the distance between the line start and the point on the line closest to
// the center of the sphere
const ad: number = Math.cos(cab) * ac;
// intersection occurs when the point on the line closest to the sphere center is
// no further away than the end of the line
return ad <= ab;
}
return false;
}
export function distance(a: IPoint, b: IPoint): number {
return Math.sqrt(
Math.pow(b.z - a.z, 2) + Math.pow(b.y - a.y, 2) + Math.pow(b.x - a.x, 2)
);
}
export interface IPoint {
x: number;
y: number;
z: number;
}
다음은 Golang으로 작성된 솔루션입니다. 이 방법은 여기에 게시 된 다른 답변과 유사하지만 동일하지는 않습니다. 구현하기 쉽고 테스트되었습니다. 단계는 다음과 같습니다.
- 원이 원점에 있도록 좌표를 번역하십시오.
- x 및 y 좌표 모두에 대한 라인 세그먼트를 t의 매개 변수로 표현하십시오. t가 0이면 함수의 값은 세그먼트의 하나의 엔드 포인트이고 t가 1이면 함수의 값이 다른 엔드 포인트입니다.
- 가능하면 x를 생성하는 t의 제한 값으로 인한 2 차 방정식을 해결하고, y는 원의 반경과 동일한 원점에서 거리와 조정됩니다.
- T가 <0 또는> 1 인 솔루션을 버리십시오 (열린 세그먼트의 경우 <= 0 또는> = 1). 이러한 점은 세그먼트에 포함되어 있지 않습니다.
- 원본 좌표로 다시 번역하십시오.
2 차 A, B 및 C의 값은 여기서 파생되며, 여기서 (N-ET) 및 (M-DT)는 각각 라인의 X 및 Y 좌표에 대한 방정식입니다. R은 원의 반경입니다.
(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
따라서 a = ee + dd, b = -2 (en + dm) 및 c = nn + mm -rr입니다.
다음은 기능에 대한 Golang 코드입니다.
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
}
이 기능으로 테스트했는데 솔루션 포인트가 라인 세그먼트 내에 있고 원 안에 있음을 확인했습니다. 테스트 세그먼트를 만들고 주어진 원 주위를 청소합니다.
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.")
}
테스트 출력은 다음과 같습니다.
=== RUN TestSegmentCircleIntersection
--- PASS: TestSegmentCircleIntersection (0.00s)
geom_test.go:105: Tested 40000 examples and found 7343 solutions.
마지막으로,이 방법은 T> 0 또는 T <1 인 경우에만 테스트함으로써 한 지점에서 시작하여 다른 점을 통과하고 무한대로 확장하는 경우에 쉽게 확장 할 수 있습니다.
방금 필요했기 때문에이 솔루션을 생각해 냈습니다. 언어는 MaxScript이지만 다른 언어로 쉽게 번역해야합니다. Sidea, Sideb 및 Circleradius는 스칼라이며 나머지 변수는 [x, y, z]입니다. 평면 xy에서 z = 0이라고 가정합니다.
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)
)
제휴하지 않습니다 StackOverflow
