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

Question

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

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

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

Так, например, назовите линии (Ax, Ay)-(Bx, By) и (Cx, Cy)-(Dx, Dy)

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

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

45

algorithm performance math intersection lines

Источник

22 дек '08 в 01:20

9 ответов

Другие вопросы по тегам algorithm performance math intersection lines

user47707 22 дек '08 в 09:42 2008-12-22 09:42 · Answer 1 · 2008-12-22 09:42

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

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

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

выразить прямые линии в виде y = ax + b (прохождение линии A,B) и y = cx + d (прохождение линии C,D)
посмотрим, находятся ли C и D на одной стороне от y = ax + b
посмотрим, находятся ли А и В на одной и той же стороне y = cx + d
если ответ на вышеприведенный ответ отрицательный, то существует пересечение. в противном случае пересечения нет.
найти пересечение, если оно есть.

Примечание: чтобы выполнить шаг 2, просто проверьте, имеют ли (Cy - a(Cx) - b) и (Dy - a(Dx) - b) одинаковый знак. Шаг 3 похож. Шаг 5 - просто стандартная математика из двух уравнений.

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

user2635 22 дек '08 в 02:29 2008-12-22 02:29 · Answer 2 · 2008-12-22 02:29

Если у вас есть такая возможность, вам стоит проверить Библию Collision Detection, "Real Time Collision Detection", если вы планируете делать что-то нетривиальное. Я не профессиональный программист игр, и я понял и смог применить концепции без особых проблем.

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

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

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

user47064 22 дек '08 в 01:45 2008-12-22 01:45 · Answer 3 · 2008-12-22 01:45

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

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

16

Источник

user47064 22 дек '08 в 01:45

user3834 22 дек '08 в 01:30 2008-12-22 01:30 · Answer 4 · 2008-12-22 01:30

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

user9611 22 дек '08 в 01:45 2008-12-22 01:45 · Answer 5 · 2008-12-22 01:45

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

user976 22 дек '08 в 09:09 2008-12-22 09:09 · Answer 6 · 2008-12-22 09:09

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

user1936386 29 дек '12 в 12:36 2012-12-29 12:36 · Answer 7 · 2012-12-29 12:36

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

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

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

user19816 22 дек '08 в 02:29 2008-12-22 02:29 · Answer 8 · 2008-12-22 02:29

Ну, математика и скалярные произведения могут помочь в этом.
- Скажем, вы хотите пересечь сегменты [AB] и [CD]
- Предположим, что пересечение линий линий - это 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

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

user791601 09 июн '11 в 19:25 2011-06-09 19:25 · Answer 9 · 2011-06-09 19:25

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