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

Question

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

Пара точек представляет конечные точки линии, проведенной между ними. Учитывая две пары точек, пересекаются ли нарисованные линии, и если да, то в какой точке?

Так, например, назовите линии (A.x, A.y) - (B.x, B.y) и (C.x, C.y) - (D.x, D.y)

Кто-нибудь может придумать решение? Решение на любом языке подойдет.

Редактировать: Точка, которую я должен был прояснить, алгоритм должен возвращать false, если точка пересечения находится за пределами длины отрезков.

Answer 1

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

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 для всех линий экономит ваше время.

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

Answer 6

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

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

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

Answer 7

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

Answer 8

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

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

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

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

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

Answer 9

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