Круговой алгоритм обнаружения коллизий линейного сегмента?

Здесь вам понадобится немного математики:

Предположим, 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, используя решение (я) для альфы, вы получите точки пересечения , если таковые существуют.

Если координаты линии 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, то это не решение, но оно показывает, что линия «указывает» в направлении круга.

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, то это не решение, но оно показывает, что линия «указывает» в направлении круга.

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, то это не решение, но оно показывает, что линия «указывает» в направлении круга.

, если вы подставите формулы x и y прямой в формулу окружностей, вы получите уравнение второго порядка для t, и его решениями являются точки пересечения (если таковые имеются). Если вы получите значение, которое меньше 0 или больше 1, то это не решение, но оно показывает, что линия «указывает» в направлении круга.

, если вы подставите формулы x и y прямой в формулу окружностей, вы получите уравнение второго порядка для t, и его решениями являются точки пересечения (если таковые имеются). Если вы получите значение, которое меньше 0 или больше 1, то это не решение, но оно показывает, что линия «указывает» в направлении круга.

Если вы найдете расстояние между центром сферы (поскольку она трехмерна, я предполагаю, что вы имеете в виду сферу, а не круг) и линией, то проверьте, меньше ли это расстояние, чем радиус, который будет сделайте трюк.

Точка столкновения, очевидно, является ближайшей точкой между линией и сферой (которая будет вычислена, когда вы вычисляете расстояние между сферой и линией)

Расстояние между точкой и линией :
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

Вы можете найти точку на бесконечной прямой, ближайшую к центру окружности, проецируя вектор 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
  }
}

РЕДАКТИРОВАТЬ: добавлен код для проверки, действительно ли найденные точки пересечения находятся в пределах сегмента линии.

Хорошо, я не буду давать вам код, но поскольку вы отметили этот алгоритм , Я не думаю, что это будет иметь для вас значение. Во-первых, вам нужно получить вектор, перпендикулярный линии.

У вас будет неизвестная переменная в y = ax + c ( c будет неизвестна )
Чтобы решить эту проблему, вычислите ее значение, когда линия проходит через центр круга.

То есть
Подставьте местоположение центра круга в уравнение прямой и решите относительно c .
Затем вычислите точку пересечения исходной линии и ее нормали.

Это даст вам ближайшую точку на прямой к окружности.
Вычислите расстояние между этой точкой и центром круга (используя величину вектора).
Если он меньше радиуса круга - вуаля, у нас есть пересечение!

Похоже, никто не рассматривает проекцию, я совсем не в курсе?

Спроецируйте вектор AC на AB . Спроецированный вектор AD дает новую точку D .
Если расстояние между D и C меньше (или равно) R , мы имеем пересечение.

Примерно так:

Другой метод использует формулу площади треугольника 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 отличается of B и длина сегмента не равна нулю, если это может произойти в вашем приложении.

Я бы использовал алгоритм для вычисления расстояния между точкой (центром круга) и линией (линия 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

Эта функция 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;
}