Question

Этот вопрос относится к:

Как определить точку пересечения двух линий в GDI +? (отличное объяснение алгебры, но без кода)
Как определить, где пересекаются два отрезка? (принятый ответ на самом деле не работает)

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

совпадает, но не перекрывается
касание только точек и совпадение
подсегмент / совпадающий подсегмент линии

Например, мы могли бы разработать функцию C # следующим образом:

public static PointF[] Intersection(PointF a1, PointF a2, PointF b1, PointF b2)

где (a1, a2) - один отрезок, а (b1, b2) - другой.

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

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

Jared Updike · Answer 1 · 13 февраля 2010

    // port of this JavaScript code with some changes:
    //   http://www.kevlindev.com/gui/math/intersection/Intersection.js
    // found here:
    //   http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/563240#563240

public class Intersector
{
    static double MyEpsilon = 0.00001;

    private static float[] OverlapIntervals(float ub1, float ub2)
    {
        float l = Math.Min(ub1, ub2);
        float r = Math.Max(ub1, ub2);
        float A = Math.Max(0, l);
        float B = Math.Min(1, r);
        if (A > B) // no intersection
            return new float[] { };
        else if (A == B)
            return new float[] { A };
        else // if (A < B)
            return new float[] { A, B };
    }

    // IMPORTANT: a1 and a2 cannot be the same, e.g. a1--a2 is a true segment, not a point
    // b1/b2 may be the same (b1--b2 is a point)
    private static PointF[] OneD_Intersection(PointF a1, PointF a2, PointF b1, PointF b2)
    {
        //float ua1 = 0.0f; // by definition
        //float ua2 = 1.0f; // by definition
        float ub1, ub2;

        float denomx = a2.X - a1.X;
        float denomy = a2.Y - a1.Y;

        if (Math.Abs(denomx) > Math.Abs(denomy))
        {
            ub1 = (b1.X - a1.X) / denomx;
            ub2 = (b2.X - a1.X) / denomx;
        }
        else
        {
            ub1 = (b1.Y - a1.Y) / denomy;
            ub2 = (b2.Y - a1.Y) / denomy;
        }

        List<PointF> ret = new List<PointF>();
        float[] interval = OverlapIntervals(ub1, ub2);
        foreach (float f in interval)
        {
            float x = a2.X * f + a1.X * (1.0f - f);
            float y = a2.Y * f + a1.Y * (1.0f - f);
            PointF p = new PointF(x, y);
            ret.Add(p);
        }
        return ret.ToArray();
    }

    private static bool PointOnLine(PointF p, PointF a1, PointF a2)
    {
        float dummyU = 0.0f;
        double d = DistFromSeg(p, a1, a2, MyEpsilon, ref dummyU);
        return d < MyEpsilon;
    }

    private static double DistFromSeg(PointF p, PointF q0, PointF q1, double radius, ref float u)
    {
        // formula here:
        //http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html
        // where x0,y0 = p
        //       x1,y1 = q0
        //       x2,y2 = q1
        double dx21 = q1.X - q0.X;
        double dy21 = q1.Y - q0.Y;
        double dx10 = q0.X - p.X;
        double dy10 = q0.Y - p.Y;
        double segLength = Math.Sqrt(dx21 * dx21 + dy21 * dy21);
        if (segLength < MyEpsilon)
            throw new Exception("Expected line segment, not point.");
        double num = Math.Abs(dx21 * dy10 - dx10 * dy21);
        double d = num / segLength;
        return d;
    }

    // this is the general case. Really really general
    public static PointF[] Intersection(PointF a1, PointF a2, PointF b1, PointF b2)
    {
        if (a1.Equals(a2) && b1.Equals(b2))
        {
            // both "segments" are points, return either point
            if (a1.Equals(b1))
                return new PointF[] { a1 };
            else // both "segments" are different points, return empty set
                return new PointF[] { };
        }
        else if (b1.Equals(b2)) // b is a point, a is a segment
        {
            if (PointOnLine(b1, a1, a2))
                return new PointF[] { b1 };
            else
                return new PointF[] { };
        }
        else if (a1.Equals(a2)) // a is a point, b is a segment
        {
            if (PointOnLine(a1, b1, b2))
                return new PointF[] { a1 };
            else
                return new PointF[] { };
        }

        // at this point we know both a and b are actual segments

        float ua_t = (b2.X - b1.X) * (a1.Y - b1.Y) - (b2.Y - b1.Y) * (a1.X - b1.X);
        float ub_t = (a2.X - a1.X) * (a1.Y - b1.Y) - (a2.Y - a1.Y) * (a1.X - b1.X);
        float u_b = (b2.Y - b1.Y) * (a2.X - a1.X) - (b2.X - b1.X) * (a2.Y - a1.Y);

        // Infinite lines intersect somewhere
        if (!(-MyEpsilon < u_b && u_b < MyEpsilon))   // e.g. u_b != 0.0
        {
            float ua = ua_t / u_b;
            float ub = ub_t / u_b;
            if (0.0f <= ua && ua <= 1.0f && 0.0f <= ub && ub <= 1.0f)
            {
                // Intersection
                return new PointF[] {
                    new PointF(a1.X + ua * (a2.X - a1.X),
                        a1.Y + ua * (a2.Y - a1.Y)) };
            }
            else
            {
                // No Intersection
                return new PointF[] { };
            }
        }
        else // lines (not just segments) are parallel or the same line
        {
            // Coincident
            // find the common overlapping section of the lines
            // first find the distance (squared) from one point (a1) to each point
            if ((-MyEpsilon < ua_t && ua_t < MyEpsilon)
               || (-MyEpsilon < ub_t && ub_t < MyEpsilon))
            {
                if (a1.Equals(a2)) // danger!
                    return OneD_Intersection(b1, b2, a1, a2);
                else // safe
                    return OneD_Intersection(a1, a2, b1, b2);
            }
            else
            {
                // Parallel
                return new PointF[] { };
            }
        }
    }


}

Вот код теста:

    public class IntersectTest
    {
        public static void PrintPoints(PointF[] pf)
        {
            if (pf == null || pf.Length < 1)
                System.Console.WriteLine("Doesn't intersect");
            else if (pf.Length == 1)
            {
                System.Console.WriteLine(pf[0]);
            }
            else if (pf.Length == 2)
            {
                System.Console.WriteLine(pf[0] + " -- " + pf[1]);
            }
        }

        public static void TestIntersect(PointF a1, PointF a2, PointF b1, PointF b2)
        {
            System.Console.WriteLine("----------------------------------------------------------");
            System.Console.WriteLine("Does      " + a1 + " -- " + a2);
            System.Console.WriteLine("intersect " + b1 + " -- " + b2 + " and if so, where?");
            System.Console.WriteLine("");
            PointF[] result = Intersect.Intersection(a1, a2, b1, b2);
            PrintPoints(result);
        }

        public static void Main()
        {
            System.Console.WriteLine("----------------------------------------------------------");
            System.Console.WriteLine("line segments intersect");
            TestIntersect(new PointF(0, 0),
                          new PointF(100, 100),
                          new PointF(100, 0),
                          new PointF(0, 100));
            TestIntersect(new PointF(5, 17),
                          new PointF(100, 100),
                          new PointF(100, 29),
                          new PointF(8, 100));
            System.Console.WriteLine("----------------------------------------------------------");
            System.Console.WriteLine("");

            System.Console.WriteLine("----------------------------------------------------------");
            System.Console.WriteLine("just touching points and lines cross");
            TestIntersect(new PointF(0, 0),
                          new PointF(25, 25),
                          new PointF(25, 25),
                          new PointF(100, 75));
            System.Console.WriteLine("----------------------------------------------------------");
            System.Console.WriteLine("");

            System.Console.WriteLine("----------------------------------------------------------");
            System.Console.WriteLine("parallel");
            TestIntersect(new PointF(0, 0),
                          new PointF(0, 100),
                          new PointF(100, 0),
                          new PointF(100, 100));
            System.Console.WriteLine("----------------------------------------------------------");
            System.Console.WriteLine("");

            System.Console.WriteLine("----");
            System.Console.WriteLine("lines cross but segments don't intersect");
            TestIntersect(new PointF(50, 50),
                          new PointF(100, 100),
                          new PointF(0, 25),
                          new PointF(25, 0));
            System.Console.WriteLine("----------------------------------------------------------");
            System.Console.WriteLine("");

            System.Console.WriteLine("----------------------------------------------------------");
            System.Console.WriteLine("coincident but do not overlap!");
            TestIntersect(new PointF(0, 0),
                          new PointF(25, 25),
                          new PointF(75, 75),
                          new PointF(100, 100));
            System.Console.WriteLine("----------------------------------------------------------");
            System.Console.WriteLine("");

            System.Console.WriteLine("----------------------------------------------------------");
            System.Console.WriteLine("touching points and coincident!");
            TestIntersect(new PointF(0, 0),
                          new PointF(25, 25),
                          new PointF(25, 25),
                          new PointF(100, 100));
            System.Console.WriteLine("----------------------------------------------------------");
            System.Console.WriteLine("");

            System.Console.WriteLine("----------------------------------------------------------");
            System.Console.WriteLine("overlap/coincident");
            TestIntersect(new PointF(0, 0),
                          new PointF(75, 75),
                          new PointF(25, 25),
                          new PointF(100, 100));
            TestIntersect(new PointF(0, 0),
                          new PointF(100, 100),
                          new PointF(0, 0),
                          new PointF(100, 100));
            System.Console.WriteLine("----------------------------------------------------------");
            System.Console.WriteLine("");

            while (!System.Console.KeyAvailable) { }
        }

    }

и вот вывод:

----------------------------------------------------------
line segments intersect
----------------------------------------------------------
Does      {X=0, Y=0} -- {X=100, Y=100}
intersect {X=100, Y=0} -- {X=0, Y=100} and if so, where?

{X=50, Y=50}
----------------------------------------------------------
Does      {X=5, Y=17} -- {X=100, Y=100}
intersect {X=100, Y=29} -- {X=8, Y=100} and if so, where?

{X=56.85001, Y=62.30054}
----------------------------------------------------------

----------------------------------------------------------
just touching points and lines cross
----------------------------------------------------------
Does      {X=0, Y=0} -- {X=25, Y=25}
intersect {X=25, Y=25} -- {X=100, Y=75} and if so, where?

{X=25, Y=25}
----------------------------------------------------------

----------------------------------------------------------
parallel
----------------------------------------------------------
Does      {X=0, Y=0} -- {X=0, Y=100}
intersect {X=100, Y=0} -- {X=100, Y=100} and if so, where?

Doesn't intersect
----------------------------------------------------------

----
lines cross but segments don't intersect
----------------------------------------------------------
Does      {X=50, Y=50} -- {X=100, Y=100}
intersect {X=0, Y=25} -- {X=25, Y=0} and if so, where?

Doesn't intersect
----------------------------------------------------------

----------------------------------------------------------
coincident but do not overlap!
----------------------------------------------------------
Does      {X=0, Y=0} -- {X=25, Y=25}
intersect {X=75, Y=75} -- {X=100, Y=100} and if so, where?

Doesn't intersect
----------------------------------------------------------

----------------------------------------------------------
touching points and coincident!
----------------------------------------------------------
Does      {X=0, Y=0} -- {X=25, Y=25}
intersect {X=25, Y=25} -- {X=100, Y=100} and if so, where?

{X=25, Y=25}
----------------------------------------------------------

----------------------------------------------------------
overlap/coincident
----------------------------------------------------------
Does      {X=0, Y=0} -- {X=75, Y=75}
intersect {X=25, Y=25} -- {X=100, Y=100} and if so, where?

{X=25, Y=25} -- {X=75, Y=75}
----------------------------------------------------------
Does      {X=0, Y=0} -- {X=100, Y=100}
intersect {X=0, Y=0} -- {X=100, Y=100} and if so, where?

{X=0, Y=0} -- {X=100, Y=100}
----------------------------------------------------------

Eric Lippert · Answer 2 · 13 февраля 2010

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

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

Я был бы более склонен использовать систему типов, чтобы было намного яснее, что делает этот метод.

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

Во-вторых, я бы определил абстрактный базовый тип "Локус" и производные типы EmptyLocus, PointLocus, LineSegmentLocus и, возможно, UnionLocus, если вам нужно представить локус, который представляет собой объединение двух или более локусов. Пустой локус - это просто одиночная точка, точечный локус - это просто одна точка и т. Д.

Теперь подпись вашего метода становится намного более понятной:

static Locus Intersect(LineSegment l1, LineSegment l2)

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

Обратите внимание, что вы можете обобщить этот метод. Вычислить пересечение отрезка линии с отрезком линии довольно сложно, но вычислить пересечение отрезка линии с точкой, или точки с точкой, или чего-либо с пустым локусом - easy . И нетрудно распространить пересечение на произвольные объединения локусов. Следовательно, вы могли бы написать:

static Locus Intersect(Locus l1, Locus l2)

И, эй, теперь становится ясно, что Intersect может быть методом расширения в locus:

static Locus Intersect(this Locus l1, Locus l2)

Добавьте неявное преобразование из PointF в PointLocus и LineSegment в LineSegmentLocus, и вы можете сказать что-то вроде

var point = new PointF(whatever);
var lineseg = new LineSegment(somepoint, someotherpoint);
var intersection = lineseg.Intersect(point);
if (intersection is EmptyLocus) ...

Использование системы типов хорошо может значительно улучшить читаемость программы.

Agnel Kurian · Answer 3 · 05 августа 2010

@ Джаред, Отличный вопрос и отличный ответ.

Эту проблему можно упростить, представив положение точки вдоль линии как функцию от одного параметра, как объяснено в FAQ по CGA Джозефа О'Рурка здесь .

Позвольте r быть параметром, чтобы указать P's расположение вдоль линии, содержащей AB, со следующим значением:
      r=0      P = A
      r=1      P = B
      r<0      P is on the backward extension of AB
      r>1      P is on the forward extension of AB
      0<r<1    P is interior to AB

Думая по этим направлениям, для любой точки C (cx, cy) мы вычисляем r следующим образом:

double deltax = bx - ax;
double deltay = by - ay;
double l2 = deltax * deltax + deltay * deltay;
double r = (ay - cy) * (ay - by) - (ax - cx) * (bx - ax) / l2;

Это должно облегчить вычисление перекрывающегося сегмента.

Обратите внимание, что мы избегаем брать квадратные корни, потому что требуется только квадрат длины.

Ed S. · Answer 4 · 13 февраля 2010

Это действительно очень просто. Если у вас есть две строки, вы можете найти два уравнения в виде y = mx + b. Например:

y = 2x + 5
y = x - 3

Итак, две линии пересекаются, когда y1 = y2 в одной и той же координате x, поэтому ...

2x + 5 = x - 3 
x + 5 = -3
x = -8

Когда x = -8 y1 = y2 и вы нашли точку пересечения. Это должно быть очень тривиально, чтобы перевести в код. Если нет точки пересечения, то наклон m каждой линии будет равен, и в этом случае вам даже не нужно выполнять вычисление.

Обнаружение совпадающего подмножества двух совпадающих отрезков

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 4 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Обнаружение совпадающего подмножества двух совпадающих отрезков

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 4 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы