Эффективный математический алгоритм для расчета пересечений

Большинство ответов здесь, похоже, следуют общей идее, что:

1. найти пересечение двух прямых, проходящих через заданные точки.
2. определить, принадлежит ли пересечение обоим линейным сегментам.

Но когда пересечение случается нечасто, лучше, вероятно, поменять эти шаги в обратном порядке:

1. выразите прямые линии в виде y = ax + b (линия, проходящая через A, B) и y = cx + d (линия, проходящая через C, D)
2. проверьте, находятся ли C и D на одной стороне от y = ax + b
3. проверьте, находятся ли A и B на одной стороне от y = cx + d
4. если оба ответа на оба вопроса - нет, значит, имеется перекресток. иначе нет пересечения.
5. найти пересечение, если оно есть.

Примечание: чтобы выполнить шаг 2, просто проверьте, имеют ли (C.y - a (C.x) - b) и (D.y - a (D.x) - b) одинаковый знак. Шаг 3 аналогичен. Шаг 5 - это просто стандартная математика из двух уравнений.

Кроме того, если вам нужно сравнить каждый сегмент линии с (n-1) другими сегментами линии, предварительное вычисление шага 1 для всех линий сэкономит ваше время.

Если у вас есть шанс, вам действительно стоит проверить библию обнаружения столкновений, «Обнаружение столкновений в реальном времени», если вы планируете делать что-нибудь нетривиальное. Я не профессиональный программист игр, понимал и мог без труда применить изложенные в ней концепции.

Amazon - обнаружение столкновений в реальном времени

По сути, выполнение набора тестов на пересечение линий стоит дорого, несмотря ни на что. Что вы делаете, так это используете такие вещи, как ограничивающие рамки (выровненные или ориентированные по оси) над вашими сложными многоугольниками. Это позволит вам быстро выполнить проверку O (N ^ 2) столкновения между каждым «объектом» в худшем случае. Затем вы можете ускорить процесс еще больше, используя пространственные деревья (Binary Partitioning или QuadTrees), проверяя только пересечения объектов, расположенных близко друг к другу.

Это позволяет сократить множество тестов на столкновение. Лучшая оптимизация - это вообще ничего не делать. Только после столкновения между ограничивающими рамками вы делаете дорогостоящие пересечения линий, чтобы определить, действительно ли объекты пересекаются или нет. Это позволяет увеличивать количество объектов, сохраняя при этом разумную скорость.

float x12 = x1 - x2;
float x34 = x3 - x4;
float y12 = y1 - y2;
float y34 = y3 - y4;

float c = x12 * y34 - y12 * x34;

if (fabs(c) < 0.01)
{
  // No intersection
  return false;
}
else
{
  // Intersection
  float a = x1 * y2 - y1 * x2;
  float b = x3 * y4 - y3 * x4;

  float x = (a * x34 - b * x12) / c;
  float y = (a * y34 - b * y12) / c;

  return true;
}

Формулы взяты из:
Линия-пересечение линии - Википедия

Простая оптимизация, которая может сэкономить вам много времени, - это проверить выровненные по оси ограничивающие прямоугольники линий, прежде чем переходить к расчету пересечения.
Если ограничивающие прямоугольники полностью не пересекаются, вы можете быть уверены, что пересечения нет.
Конечно, это зависит от имеющихся у вас данных. если пересечение очень вероятно при каждой проверке, которую вы делаете, вы можете потратить время на проверку, которая всегда верна.

public struct PointD
{
    public double X { get; set; }
    public double Y { get; set; }
}

/// <summary>
/// Find the intersection point between two lines.
/// </summary>
/// <param name="IntersectPoint">The intersection point. A <see cref="Esteem.Geometry.PointD">PointD</see> structure.</param>
/// <param name="L1StartPoint">The starting point of first line. A PointD structure.</param>
/// <param name="L1EndPoint">The end point of first line. A PointD structure.</param>
/// <param name="L2StartPoint">The starting point of second line. A PointD structure.</param>
/// <param name="L2EndPoint">The end point of second line. A PointD structure.</param>
/// <param name="L1IntersectPos">The intersection position at first line.</param>
/// <param name="L2IntersectPos">The intersection position at second line.</param>
/// <returns>Returns a boolean. True if there is intersection, false otherwise.</returns>
/// <remarks>The formula is taken from comp.graphics.algorithms Frequently Asked Questions.</remarks>
public static bool LineIntersect(out PointD IntersectPoint, PointD L1StartPoint, PointD L1EndPoint, PointD L2StartPoint, PointD L2EndPoint, out double L1IntersectPos, out double L2IntersectPos) 
{
    IntersectPoint = new PointD();
    double ay_cy, ax_cx, px, py;
    double dx_cx = L2EndPoint.X - L2StartPoint.X,
        dy_cy = L2EndPoint.Y - L2StartPoint.Y,
        bx_ax = L1EndPoint.X - L1StartPoint.X,
        by_ay = L1EndPoint.Y - L1StartPoint.Y;

    double de = (bx_ax) * (dy_cy) - (by_ay) * (dx_cx);
    //double tor = 1.0E-10;     //tolerance


    L1IntersectPos = 0;      L2IntersectPos = 0;
    if (Math.Abs(de)<0.01)
        return false;
    //if (de > -tor && de < tor) return false; //line is in parallel

    ax_cx = L1StartPoint.X - L2StartPoint.X;
    ay_cy = L1StartPoint.Y - L2StartPoint.Y;
    double r = ((ay_cy) * (dx_cx) - (ax_cx) * (dy_cy)) / de;
    double s = ((ay_cy) * (bx_ax) - (ax_cx) * (by_ay)) / de;
    px = L1StartPoint.X + r * (bx_ax);
    py = L1StartPoint.Y + r * (by_ay);

    IntersectPoint.X = px;  //return the intersection point
    IntersectPoint.Y = py;  //return the intersection position
    L1IntersectPos = r;      L2IntersectPos = s;

    return true; //indicate there is intersection
}

Чтобы проверить, не выходит ли точка пересечения за пределы исходной длины линии, просто убедитесь, что 0<r<1 и 0<s<1

Ниже показано пересечение моих линий и линий, как описано в MathWorld. Для общего обнаружения столкновений / пересечений вы можете посмотреть теорему о разделении осей. Я нашел этот учебник по SAT очень информативным.

    /// <summary>
    /// Returns the intersection point of the given lines. 
    /// Returns Empty if the lines do not intersect.
    /// Source: http://mathworld.wolfram.com/Line-LineIntersection.html
    /// </summary>
    public static PointF LineIntersection(PointF v1, PointF v2, PointF v3, PointF v4)
    {
        float tolerance = 0.000001f;

        float a = Det2(v1.X - v2.X, v1.Y - v2.Y, v3.X - v4.X, v3.Y - v4.Y);
        if (Math.Abs(a) < float.Epsilon) return PointF.Empty; // Lines are parallel

        float d1 = Det2(v1.X, v1.Y, v2.X, v2.Y);
        float d2 = Det2(v3.X, v3.Y, v4.X, v4.Y);
        float x = Det2(d1, v1.X - v2.X, d2, v3.X - v4.X) / a;
        float y = Det2(d1, v1.Y - v2.Y, d2, v3.Y - v4.Y) / a;

        if (x < Math.Min(v1.X, v2.X) - tolerance || x > Math.Max(v1.X, v2.X) + tolerance) return PointF.Empty;
        if (y < Math.Min(v1.Y, v2.Y) - tolerance || y > Math.Max(v1.Y, v2.Y) + tolerance) return PointF.Empty;
        if (x < Math.Min(v3.X, v4.X) - tolerance || x > Math.Max(v3.X, v4.X) + tolerance) return PointF.Empty;
        if (y < Math.Min(v3.Y, v4.Y) - tolerance || y > Math.Max(v3.Y, v4.Y) + tolerance) return PointF.Empty;

        return new PointF(x, y);
    }

    /// <summary>
    /// Returns the determinant of the 2x2 matrix defined as
    /// <list>
    /// <item>| x1 x2 |</item>
    /// <item>| y1 y2 |</item>
    /// </list>
    /// </summary>
    public static float Det2(float x1, float x2, float y1, float y2)
    {
        return (x1 * y2 - y1 * x2);
    }

(Я бы оставил это как комментарий, но я еще не понял, как это сделать.)

Я просто хотел бы добавить, в качестве альтернативы / дополнения к тесту ограничивающего прямоугольника, вы также можете проверить, превышает ли расстояние между средними точками линий половину общей длины линий. Если так, то линии не могут пересекаться.

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

Что ж, математика и скалярные произведения могут в этом помочь.
- Допустим, вы хотите пересечь отрезки [AB] и [CD]
- Предположим, что прямое пересечение прямых равно M

M находится внутри отрезка [ÅB] тогда и только тогда, когда
Vector (AB). Вектор (AM)> = 0
и
Вектор (AB). Вектор (МБ)> = 0

Где точка "." обозначает скалярное произведение: u. v = ux * vx + uy * vy

Итак, ваш алгоритм:
- найти M
- M находится внутри обоих сегментов тогда и только тогда, когда 4 уравнения ниже верны
Vector (AB). Вектор (AM)> = 0
Вектор (AB). Вектор (MB)> = 0
Вектор (CD). Вектор (CM)> = 0
Вектор (CD). Вектор (MD)> = 0

Надеюсь это поможет