Алгоритм обнаружения столкновений круг-линия-сегмент?
У меня есть линия от A до B и круг, расположенный в C с радиусом R.
Какой хороший алгоритм использовать, чтобы проверить, пересекает ли линия окружность? А по какой координате по краю окружности это произошло?
30 ответов
Принятие
- Е - отправная точка луча,
- L - конечная точка луча,
- С - центр сферы, с которой вы тестируете
- r - радиус этой сферы
Вычислите:
d = L - E (вектор направления луча от начала до конца)
f = E - C (Вектор от центральной сферы до начала луча)
Тогда перекресток найден..
Подключив:
P = E + T * D
Это параметрическое уравнение:
Px = Ex + tdx
Py = Ey + tdy
в
(x - h)2 + (y - k)2 = r2
(h, k) = центр круга.
Примечание. Мы упростили задачу до 2D, решение, которое мы получаем, применимо и к 3D
получить:
- расширять
x2 - 2xh + h2 + y2 - 2yk + k2 - r2 = 0 - штепсель
х = ех + тдх
у = эу + тду
(ex + tdx)2 - 2 (ex + tdx) h + h2 + (ey + tdy)2 - 2 (ey + tdy) k + k2 - r2 = 0 - взрываться
ex2 + 2ex tdx + t2 dx2 - 2ex h - 2tdx h + h2 + ey2 + 2ey tdy + t2 dy2 - 2ey k - 2tdy k + k2 - r2 = 0 - группа
t2(dx2 + dy2) + 2t (ex dx + ey dy - dx h - dy k) + ex2 + ey2 - 2ex h - 2ey k + h2 + k2 - r2 = 0 - В заключение,
t2(_d * _d) + 2t (_e * _d - _d * _c) + _e * _e - 2 (_e * _c) + _c * _c - r2 = 0
* Где _d - вектор d, а * - скалярное произведение. * - А потом,
t2(_d * _d) + 2t (_d * (_e - _c)) + (_e - _c) * (_e - _c) - r2 = 0 - Пусть _f = _e - _c
t2(_d * _d) + 2t (_d * _f) + _f * _f - r2 = 0
Итак, мы получаем:
t2 * (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 являются компонентами x и y точек A. То же самое для 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 треугольника. Проверка пересечения проще и эффективнее, чем проекционный метод, но поиск координат точки пересечения требует больше работы. По крайней мере, это будет отложено до того момента, когда это требуется.
Формула для вычисления площади треугольника: area = 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 )
{
...
}
ОБНОВЛЕНИЕ 1:
Вы можете оптимизировать код, используя быстрое вычисление обратного квадратного корня, описанное здесь, чтобы получить хорошее приближение 1/LAB.
Вычислить точку пересечения не так сложно. Вот оно идет
// 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
Кстати, всякий раз, когда я вычитал очки друг от друга, я вычитал xи затем вычитая 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)
И решить для квадратного уравнения (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
Итак, я поместил это в квадратную формулу:
(-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];
}
}
Надеюсь, это поможет!
PS Если кто-то найдет какие-либо ошибки или есть предложения, пожалуйста, прокомментируйте. Я очень новичок и приветствую любую помощь / предложения.
Вот реализация в Javascript. Мой подход заключается в том, чтобы сначала преобразовать отрезок в бесконечную линию, а затем найти точку (точки) пересечения. Оттуда я проверяю, находятся ли найденные точки на отрезке. Код хорошо документирован, вы должны быть в состоянии следовать.
Вы можете опробовать код здесь на этой демонстрации. Код был взят из моего алгоритма репо.
// 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 [];
}
Вы можете найти точку на бесконечной прямой, ближайшую к центру окружности, проецируя вектор AC на вектор AB. Рассчитайте расстояние между этой точкой и центром круга. Если оно больше, чем R, пересечения нет. Если расстояние равно R, прямая является касательной к окружности, а точка, ближайшая к центру окружности, фактически является точкой пересечения. Если расстояние меньше R, то есть 2 точки пересечения. Они лежат на одинаковом расстоянии от точки, ближайшей к центру круга. Это расстояние легко вычислить, используя теорему Пифагора. Вот алгоритм в псевдокоде:
{
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
}
}
РЕДАКТИРОВАТЬ: добавлен код, чтобы проверить, действительно ли найденные точки пересечения находятся в отрезке.
Просто дополнение к этой теме... Ниже приведена версия кода, размещенная 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));
}
Странно, но я могу отвечать, но не комментировать... Мне понравился подход 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];
}
}
В этом сообщении будет проверяться столкновение линии окружности путем проверки расстояния между центром окружности и точкой на отрезке линии (Ipoint), которая представляет точку пересечения между нормалью N (Изображение 2) от центра окружности к отрезку линии.
( )
На изображении 1 показаны одна окружность и одна линия, вектор A указывает на начальную точку линии, вектор B указывает на конечную точку линии, вектор C указывает на центр окружности. Теперь мы должны найти вектор E (от начальной точки линии до центра окружности) и вектор D (от начальной точки линии до конечной точки линии), этот расчет показан на рисунке 1.
( )
На изображении 2 мы можем видеть, что вектор E проецируется на вектор D посредством "точечного произведения" вектора E и единичного вектора D, результатом точечного произведения является скалярное Xp, которое представляет расстояние между начальной точкой линии и точкой пересечения (Ipoint) вектор N и вектор D. Следующий вектор X находится путем умножения единичного вектора D и скалярного Xp.
Теперь нам нужно найти вектор Z (вектор в точку Ipoint), его простое сложное векторное добавление вектора A (начальная точка на линии) и вектора X. Далее нам нужно разобраться с особыми случаями, которые мы должны проверить, это Ipoint на отрезке линии, если мы не должны выяснять, слева от него или справа от него, мы будем использовать ближайший вектор, чтобы определить, какая точка ближе всего к окружности.
( )
Когда проекция Xp отрицательна, Ipoint находится слева от сегмента линии, ближайший вектор равен вектору начальной точки линии, когда проекция Xp больше, чем величина вектора D, тогда Ipoint находится справа от сегмента линии, тогда как ближайший вектор равен вектору конца линии точка в любом другом случае ближайший вектор равен вектору Z.
Теперь, когда у нас есть ближайший вектор, нам нужно найти вектор от центра круга до точки (вектор dist), просто, нам нужно просто вычесть ближайший вектор из вектора центра. Затем просто проверьте, меньше ли вектор dist distitude, чем радиус окружности, если он есть, тогда они сталкиваются, если его нет, столкновения нет.
( )
В конце мы можем вернуть некоторые значения для разрешения коллизии, самый простой способ - вернуть перекрытие коллизии (вычесть радиус из вектора dist distitude) и вернуть ось коллизии, ее вектор D. Также точкой пересечения является вектор Z, если необходимо.
Я знаю, что эта тема давно не открывалась. Из ответа, данного chmike и улучшенного Акибом Мумтазом. Они дают хороший ответ, но работают только для бесконечной линии, как сказал Акиб. Поэтому я добавляю сравнения, чтобы узнать, касается ли сегмент линии круга, я пишу это на 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")
Вам понадобится немного математики здесь:
Предположим, что A = (Xa, Ya), B = (Xb, Yb) и C = (Xc, Yc). Любая точка на линии от A до B имеет координаты (альфа *Xa + (1-альфа)Xb, альфа Ya + (1-альфа)* Yb) = P
Если точка P имеет расстояние R до 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, используя решение (я) для альфы, вы получите точки пересечения, если таковые существуют.
Круг действительно плохой парень:) Так что хороший способ - избегать истинного круга, если можете. Если вы делаете проверку столкновений для игр, вы можете пойти с некоторыми упрощениями и получить всего лишь 3-х точечные продукты, а также несколько сравнений.
Я называю это "жирной точкой" или "тонким кругом". это своего рода эллипс с нулевым радиусом в направлении, параллельном отрезку. но полный радиус в направлении, перпендикулярном сегменту
Во-первых, я хотел бы рассмотреть переименование и переключение системы координат, чтобы избежать чрезмерных данных:
s0s1 = B-A;
s0qp = C-A;
rSqr = r*r;
Во-вторых, индекс h в hvec2f означает, что вектор должен благоприятствовать горизонтальным операциям, таким как dot()/det(). Это означает, что его компоненты должны быть помещены в отдельные xmm регистры, чтобы избежать случайного перемешивания /hasd'ing/hsub'ing. И вот мы с самой производительной версией простейшего обнаружения столкновений для 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;
}
Я сомневаюсь, что вы можете оптимизировать это дальше. Я использую его для обнаружения столкновений автомобильных гонок, управляемых нейронной сетью, для обработки миллионов миллионов итераций.
' 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
Если вы найдете расстояние между центром сферы (так как это 3D, я предполагаю, что вы имеете в виду сферу, а не окружность) и линией, то проверьте, меньше ли это расстояние, чем радиус, который сделает трюк.
Точка столкновения, очевидно, является ближайшей точкой между линией и сферой (которая будет вычислена при расчете расстояния между сферой и линией).
Расстояние между точкой и линией:
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html
Я создал эту функцию для 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;
}
Еще один в C# (частичный класс Circle). Проверено и работает как шарм.
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://stackru.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://stackru.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;
}Если координаты линии - Ax, Ay и Bx, By и центр окружностей - 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, и его решения - это точки пересечения (если они есть). Если вы получите значение меньше 0 или больше 1, это не решение, но оно показывает, что линия "указывает" на направление круга.
Вот мое решение в TypeScript, следуя идее, предложенной @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;
}
Эта функция 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;
}
Мне просто нужно было это, поэтому я придумал это решение. Язык maxscript, но он должен быть легко переведен на любой другой язык. sideA, sideB и CircleRadius являются скалярами, остальные переменные являются точками как [x,y,z]. Я предполагаю, что z=0, чтобы решить на плоскости 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)
)
Решение на python, основанное на @Joe Skeen
def check_line_segment_circle_intersection(line, point, radious):
""" Checks whether a point intersects with a line defined by two points.
A `point` is list with two values: [2, 3]
A `line` is list with two points: [point1, point2]
"""
line_distance = distance(line[0], line[1])
distance_start_to_point = distance(line[0], point)
distance_end_to_point = distance(line[1], point)
if (distance_start_to_point <= radious or distance_end_to_point <= radious):
return True
# angle between line and point with law of cosines
numerator = (math.pow(distance_start_to_point, 2)
+ math.pow(line_distance, 2)
- math.pow(distance_end_to_point, 2))
denominator = 2 * distance_start_to_point * line_distance
ratio = numerator / denominator
ratio = ratio if ratio <= 1 else 1 # To account for float errors
ratio = ratio if ratio >= -1 else -1 # To account for float errors
angle = math.acos(ratio)
# distance from the point to the line with sin projection
distance_line_to_point = math.sin(angle) * distance_start_to_point
if distance_line_to_point <= radious:
point_projection_in_line = math.cos(angle) * distance_start_to_point
# Intersection occurs whent the point projection in the line is less
# than the line distance and positive
return point_projection_in_line <= line_distance and point_projection_in_line >= 0
return False
def distance(point1, point2):
return math.sqrt(
math.pow(point1[1] - point2[1], 2) +
math.pow(point1[0] - point2[0], 2)
)
Возможно, есть другой способ решить эту проблему, используя поворот системы координат.
Обычно, если один сегмент является горизонтальным или вертикальным, что означает параллельность оси x или y, довольно легко найти точку пересечения, поскольку мы уже знаем одну координату пересечения, если таковая имеется. Остальные, очевидно, находят другую координату, используя уравнение круга.
Вдохновленные этой идеей, мы могли применить вращение системы координат, чтобы направление одной оси совпадало с направлением сегмента.
Возьмем пример круга
x^2+y^2=1 и сегмент
P1-P2с P1(-1,5,0,5) и P2(-0,5,-0,5) в системе xy. И следующие уравнения, чтобы напомнить вам о принципах вращения, где
theta - угол против часовой стрелки, x'-y'- система после поворота:
x'= x * cos(тета) + y * sin(тета)
y '= - x * sin (тета) + y* cos(тета)
и наоборот
x = x' * cos(тета) - y' * sin(тета)
y = x '* sin (тета) + y' * cos(тета)
Учитывая сегмент
P1-P2 направление (45° с точки зрения -x), мы могли бы взять
theta=45°. Преобразуя вторые уравнения вращения в уравнение круга в системе xy:
x^2+y^2=1 и после несложных операций мы получаем "то же самое" уравнение в системе x'-y':
x'^2+y'^2=1.
Конечные точки сегмента становятся в системе x'-y'с использованием первых уравнений вращения => P1(-sqrt(2)/2, sqrt(2)), P2(-sqrt(2)/2, 0).
Принимая пересечение как P. В x'-y' Px = -sqrt(2)/2. Используя новое уравнение круга, мы получаем Py = +sqrt(2)/2. Преобразуя P в исходную систему xy, мы в итоге получаем P(-1,0).
Чтобы реализовать это численно, мы могли бы сначала взглянуть на направление сегмента: горизонтальное, вертикальное или нет. Если это относится к первым двум случаям, все просто, как я сказал. В последнем случае примените описанные выше алгоритмы.
Чтобы определить, есть ли пересечение, мы могли бы сравнить решение с координатами конечных точек, чтобы увидеть, есть ли между ними один корень.
Я считаю, что этот метод можно применить и к другим кривым, если у нас есть его уравнение. Единственная слабость состоит в том, что мы должны решать уравнение в системе x'-y'для другой координаты, что может быть трудным.
Вот решение, написанное на голанге. Метод похож на некоторые другие ответы, опубликованные здесь, но не совсем так. Это легко реализовать и было проверено. Вот шаги:
- Переведите координаты так, чтобы круг находился в начале координат.
- Выразите отрезок как параметризованные функции t для координат x и y. Если t равно 0, значения функции являются одной конечной точкой сегмента, а если t равно 1, значения функции являются другой конечной точкой.
- Решите, если возможно, квадратное уравнение, полученное в результате ограничения значений t, которые дают координаты x, y с расстояниями от начала координат, равными радиусу круга.
- Выбросьте решения, где t < 0 или> 1 ( <= 0 или>= 1 для открытого сегмента). Эти пункты не содержатся в сегменте.
- Перевести обратно на исходные координаты.
Здесь выводятся значения для 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.
Вот код Голанга для функции:
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, но не оба.
Другое решение, в первую очередь рассмотрим случай, когда вам не важно местоположение столкновения. Обратите внимание, что эта конкретная функция построена с учетом векторного ввода для xB и yB, но ее можно легко изменить, если это не так. Имена переменных определяются в начале функции
#Line segment points (A0, Af) defined by xA0, yA0, xAf, yAf; circle center denoted by xB, yB; rB=radius of circle, rA = radius of point (set to zero for your application)
def staticCollision_f(xA0, yA0, xAf, yAf, rA, xB, yB, rB): #note potential speed up here by casting all variables to same type and/or using Cython
#Build equations of a line for linear agents (convert y = mx + b to ax + by + c = 0 means that a = -m, b = 1, c = -b
m_v = (yAf - yA0) / (xAf - xA0)
b_v = yAf - m_v * xAf
rEff = rA + rB #radii are added since we are considering the agent path as a thin line
#Check if points (circles) are within line segment (find center of line segment and check if circle is within radius of this point)
segmentMask = np.sqrt( (yB - (yA0+yAf)/2)**2 + (xB - (xA0+xAf)/2)**2 ) < np.sqrt( (yAf - yA0)**2 + (xAf - xA0)**2 ) / 2 + rEff
#Calculate perpendicular distance between line and a point
dist_v = np.abs(-m_v * xB + yB - b_v) / np.sqrt(m_v**2 + 1)
collisionMask = (dist_v < rEff) & segmentMask
#return True if collision is detected
return collisionMask, collisionMask.any()
Если вам нужно местоположение столкновения, вы можете использовать подход, описанный на этом сайте, и установить скорость одного из агентов на ноль. Этот подход хорошо работает и с векторными входами: http://twobitcoder.blogspot.com/2010/04/circle-collision-detection.html
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
}
}
Вы можете взять X равномерно распределенных точек из линии, и если они находятся внутри круга, происходит столкновение
Хотя я думаю, что с помощью пересечения линии и окружности проверка, находятся ли точки пересечения между конечными точками, лучше и, вероятно, дешевле, я хотел бы добавить это более наглядное решение.
Мне нравится думать о проблеме как о «проблеме точки в колбасе», которая должна работать в любом количестве измерений без изменения алгоритма. Это решение не найдет точки пересечения.
Вот что я придумал:
(Я использую «меньше чем», но «меньше или равно» также можно использовать в зависимости от того, что мы тестируем.)
- Убедитесь, что Circle_Point меньше расстояния Radius от бесконечной линии. (Используйте любимый метод здесь).
- Рассчитайте расстояние от обоих Segment_Points до Circle_Point.
- Проверьте, меньше ли большее расстояние Circle_Point-Segment_Point, чем sqrt(Segment_Length^2+Radius^2). (Это расстояние от точки сегмента до теоретической точки, которое равно радиусу-расстоянию от другой точки сегмента и бесконечной линии (прямого угла). См. изображение.)
- 3т. Если верно: Circle_Point находится внутри колбасы.
- 3F. Если false: если меньшее расстояние Circle_Point-Segment_Point меньше радиуса, то Circle_Point находится внутри колбасы.
function boolean pointInSausage(sp1,sp2,r,c) {
if ( !(pointLineDist(c,sp1,sp2) < r) ) {
return false;
}
double a = dist(sp1,c);
double b = dist(sp2,c);
double l;
double s;
if (a>b) {
l = a;
s = b;
} else {
l = b;
s = a;
}
double segLength = dist(sp1,sp2);
if ( l < sqrt(segLength*segLength+r*r) ) {
return true;
}
return s < r;
}
Сообщите, если будут обнаружены какие-либо проблемы, и я отредактирую или отзову их.