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

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

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

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

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

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

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

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

Amazon - Оперативное Обнаружение коллизий

В основном, выполнение ряда тестов на пересечение строки является дорогим несмотря ни на что. То, что Вы делаете, использовать вещи как Ограничительные рамки (ось, выровненная или ориентированная) по Вашим сложным полигонам. Это позволит Вам быстро делать худший случай O (N^2) проверка коллизии между каждым "объектом". Можно тогда ускорить вещи еще больше при помощи пространственных деревьев (Двоичное Разделение или 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

, М является внутренним сегментом [Г … B] если и только если
Вектор (AB). Векторный AM> = 0
и
Вектор (AB). Вектор (МБ)> = 0

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

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

Hope это помогает