Расчет пересечений между сегментами линии

Здесь много вопросов о пересечениях сегментов линии здесь, в stackoverflow, и вот еще один! Извините, но мне нужна помощь, чтобы понять, как рассчитать пересечения. Я прочитал несколько вопросов здесь и рассмотрел несколько примеров на других сайтах, но я все еще смущен и не понимаю! Мне не нравится копировать и вставлять код, не работая.

До сих пор я знаю, что я собираюсь сравнить точки каждого сегмента линии, такие как Ax, Ay, Bx, By, Cx, Cy, Dx, Dy. Может кто-нибудь объяснить мне, что я собираюсь рассчитать, каков будет результат вычисления, если есть пересечение?

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

   public static Point lineIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
  double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
  if (denom == 0.0) { // Lines are parallel.
     return null;
  }
  double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3))/denom;
  double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3))/denom;
    if (ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) {
        // Get the intersection point.
        return new Point((int) (x1 + ua*(x2 - x1)), (int) (y1 + ua*(y2 - y1)));
    }

  return null;
  }

Нужно ли также вычислять среднее значение, как в этом примере кода?

For lines through points (x0,y0) and (x1,y1), let xm = (x0+x1)/2, ym = (y0+y1)/2 (median of line segment). 
Then a = (y1-y0) and b = (x0-x1). 
If you evaluate c = a(x-xm)+b(y-ym), c=0 for (x,y) on the line, and the sign(c) tells you which side a point is on

Ответ 1

Первый фрагмент кода, который вы показываете, основан на векторном кросс-продукте, который был объяснен здесь Как вы обнаруживаете, где пересекаются два сегмента линии? в отличном деталь.

ИМО, более простой способ понять это - решить систему уравнений. Сначала посмотрите на линии, а затем вырезайте сегменты из них. Ниже я использую обозначения для заданных сегментов ((x1, x2), (y1, y2)) и ((x3, x4), (y3, y4)).

Проверьте, не вертикальна ли какая-либо из строк (x1 == x2 или x3 == x4).

а. Если оба являются вертикальными и x1 != x3, то нет пересечения.

б. Если оба являются вертикальными и x1 == x3, проверьте, перекрываются ли (y1, y2) и (y3, y4).

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

д. Если нет, продолжайте.
Используйте координаты точек для построения уравнений линий в форме y = a*x + b (например, здесь).
```
a1 = (y2-y1)/(x2-x1)
b1 = y1 - a1*x1 
a2 = (y4-y3)/(x4-x3)
b2 = y3 - a2*x3
```
Проверьте, параллельны ли строки (одинаковый наклон a). Если да, проверьте, имеют ли они один и тот же перехват b. Если да, проверьте, перекрываются ли 1D сегменты (x1, x2) и (x3, x4). Если да, ваши сегменты перекрываются. Случай, когда линии параллельны, может быть неоднозначным. Если они перекрываются, вы можете рассматривать это как пересечение (это даже может быть один пункт, если их концы касаются), или нет. Примечание: если вы работаете с поплавками, это будет немного сложнее, я считаю, вы хотели бы проигнорировать это. Если у вас есть только целые числа, проверяющие, соответствует ли a1 = a2:
```
if((y2-y1)*(x4-x3) == (x2-x1)*(y4-y3))
```
Если строки не параллельны. Точка пересечения эквивалентна решению системы уравнений, представляющих две линии. Действительно, пересечение y = a1*x + b1 и y = a2*x + b2 в основном означает, что оба этих уравнения выполнены. Решите эту систему, приравнивая две правые части, и она даст вам точку пересечения. На самом деле вам нужна только x координата пересечения (нарисуйте его, и вы увидите, почему):
```
x0 = -(b1-b2)/(a1-a2)
```
Последний шаг - проверить, находится ли точка пересечения x0 внутри обоих сегментов. То есть min(x1, x2) < x0 < max(x1, x2) и min(x3, x4) < x0 < max(x3, x4). Если да, ваши строки пересекаются!

Ответ 2

public void fixData()
{
    slope = (p2.getY() - p1.getY()) / (p2.getX() - p1.getX());
    yInt = p1.getY() - slope * p1.getX();
    xInt = (-yInt) / slope;
}

Ответ 3

Я действительно @sashkello отвечаю и считаю, что это более интуитивно понятно и проще объяснить, чем реализация вектора. Особенно при добавлении такого кода в базу кода.

Я предостерег, сказав, что вы можете использовать вспомогательный метод Java Line2D.

Line2D.linesIntersect(double x1, double y1,
                      double x2, double y2,
                      double x3, double y3,
                      double x4, double y4)

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

Например, следующие строки считаются пересекающимися, потому что они разделяют точку (1,1).

L1 = [(0,0),(1,1)]
L2 = [(1,1),(2,3)]

Если это проблема, вы можете добавить 4 проверки, чтобы убедиться, что точки равны.

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

Если ни один из этих случаев краев не влияет на вас, тогда Line2D.linesIntersect для вас.:)