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

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

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

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;
}

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

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

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

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

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

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

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

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

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

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

Ниже показано мое пересечение линии и линии, как описано в 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);
    }

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

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

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

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

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

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

private function Loop(e:Event):void
{
    var x12:Number = Ball1.x - Ball2.x;
    var x34:Number = Ball3.x - Ball4.x;
    var y12:Number = Ball1.y - Ball2.y;
    var y34:Number = Ball3.y - Ball4.y;

    // Det
    var c:Number = x12 * y34 - y12 * x34;

    if (Math.abs(c) < 0.01)
    {
        Circle.visible = false;
    }
    else
    {
        var a:Number = Ball1.x * Ball2.y - Ball1.y * Ball2.x;
        var b:Number = Ball3.x * Ball4.y - Ball3.y * Ball4.x;
        var px:Number = (a * x34 - b * x12) / c;
        var py:Number = (a * y34 - b * y12) / c;

        var Btwn12x:Boolean = (px >= Math.min(Ball1.x, Ball2.x)) && (px <= Math.max(Ball1.x, Ball2.x));
        var Btwn12y:Boolean = (py >= Math.min(Ball1.y, Ball2.y)) && (py <= Math.max(Ball1.y, Ball2.y));
        var Btwn34x:Boolean = (px >= Math.min(Ball3.x, Ball4.x)) && (px <= Math.max(Ball3.x, Ball4.x));
        var Btwn34y:Boolean = (py >= Math.min(Ball3.y, Ball4.y)) && (py <= Math.max(Ball3.y, Ball4.y));

        var Btwn12:Boolean = Btwn12x && Btwn12y;
        var Btwn34:Boolean = Btwn34x && Btwn34y;

        if (Btwn12 && Btwn34)
        {
            Circle.visible = true;
            Circle.x = px;
            Circle.y = py;
        }
        else
        {
            Circle.visible = false;
        }
    }
}

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

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

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