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

Ответ 1

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

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

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

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

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

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

Ответ 2

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

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

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

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

Ответ 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;
}

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

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

Ответ 8

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

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

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

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

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

Ответ 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;
        }
    }
}