Как узнать пересечение линий?

Question

[Тимофей Ланевич]

Пишу код на с++. Вводятся точки х, у и последовательно они соедены(выходит ламаная линия). Нужно узнать сколько раз она сама себя пересекает.

В коде я нахожу уравнения линии (например) АВ и потом для CD (например первая с второй не сравниваються, только после). Нахожу определитель и т.д. пока не нахожу точки пересечения линий.
Проблема в том что EF не пересекает CD и CB, но она как бы продолжает сама себя, а если продолжает то пересекнет.
Как это исправить? Может нужно найти её длину ? Предложения можно своими словами или математически, кодом не нужно, сам напишу. Заранье спасибо.

Answer 1

[abcd0x00]

Вот тебе псевдокод для определения, пересекаются ли отрезки.

Код

программа пересечение двух отрезков <вх:ax,ay,bx,by,cx,cy,dx,dy:R>:Q
 дано    : | концы первого отрезка (ax, ay) и (bx, by)
           | концы второго отрезка (cx, cy) и (dx, dy)
 получить: | ответ = отрезки пересекаются да/нет
 ____________
  | A(ax, bx) B(bx, by) C(cx, cy) D(dx, dy)
  v1x := bx - ax | вектор AB
  v1y := by - ay
  v2x := cx - ax | вектор AC
  v2y := cy - ay
  v3x := dx - ax | вектор AD
  v3y := dy - ay
  v4x := dx - cx | вектор CD
  v4y := dy - cy
  v5x := bx - cx | вектор CB
  v5y := by - cy
  v6x := ax - cx | вектор CA
  v6y := ay - cy
  coord1 := v1x * v2y - v1y * v2x | [AB, AC]
  coord2 := v1x * v3y - v1y * v3x | [AB, AD]
  coord3 := v4x * v5y - v4y * v5x | [CD, CB]
  coord4 := v4x * v6y - v4y * v6x | [CD, CA]
  ответ := (coord1 * coord2 <= 0 и coord3 * coord4 <= 0)
конец программы

Comments

[Тимофей Ланевич]

Это мне подходит, проверил и все правильно . Всем спасибо.

Answer 2

[Максим Мосейчук]

Верно мыслите. Находите точки пересечения прямых. А затем проверяете эти точки на принадлежность отрезку. Т.е. координаты точки должны принадлежать диапазону координат отрезка. min(A.x, B.x) <= x <= max(A.x, B.x). Для ординаты аналогично.

Comments

[Тимофей Ланевич]

Ааааа, спасибо .

[abcd0x00]

fshp: не, так не получится.

[Максим Мосейчук]

abcd0x00: почему?

[abcd0x00]

fshp: это известная задача, она так не решается. Можешь подыскать два отрезка, которые не пересекаются, но располагаются так, что попадают в твоё условие.

[Максим Мосейчук]

abcd0x00: algolist.manual.ru/maths/geom/intersect/lineline2d.php
Вполне решается. Немного другой способ, значения нормализованы. Но смысл тот же.

[Максим Мосейчук]

abcd0x00: ну а вообще хотелось бы контрпримера.

[abcd0x00]

fshp:

Немного другой способ, значения нормализованы.

Это не немного другой способ - это система уравнений с векторами.

Вот твой пример
min(A.x, B.x) <= x <= max(A.x, B.x)

Вот так не прокатит. Хоть по условию отрезки соединены последовательно, но мы можем рассматривать, допустим, первый и пятый, которые могут быть расположены как угодно по отношению друг к другу. И, значит, они имеют такие координаты: два отрезка AB и CD.

AB A(0; 0) B(10;10)
CD C(5; 4) D(9; 0)

У них нет точки пересечения, но точка пересечения прямых - X(4.5; 4.5), вот она попадает в твоё условие.

[Максим Мосейчук]

abcd0x00: Она не попадает под условие для CD по ординате. 0 <= 4.5 <= 4. Это неверно.

[Максим Мосейчук]

abcd0x00: да и по абсцисе неравенство не выполняется. Так, как точка принадлежит прямой, достаточно проверить лишь одну координату, либо x либо y, но для обоих отрезков.

[abcd0x00]

fshp:

Она не попадает под условие для CD по ординате. 0 <= 4.5 <= 4. Это неверно.

Тут ещё неясно, как ты определяешь максимальные и минимальные концы. Где вот ты взял 0 и 4, как ты понял, что именно их надо брать? Так что, если код такой простой, то ты сможешь без труда его накидать мне, чтобы я его мог поломать координатами.

[Максим Мосейчук]

abcd0x00: https://gist.github.com/fshp/c5d72202b8a3d1c4dfb5b...
функция cross

"Тут ещё неясно, как ты определяешь максимальные и минимальные концы."
Дана прямая "a", построенная по точкам A и B.
Дана точка C, принадлежащая прямой "a".
Нужно проверить принадлежность точки C отрезку AB.

Для этого достаточно проверить принадлежность абсциссы точки C отрезку, построенному по точкам (A.x, 0) (B.x, 0).
Либо проверить принадлежность ординаты C отрезку, построенному по точкам (0, A.y) (0, B.y). Это делается тривиально.

[Максим Мосейчук]

abcd0x00: Лучше сказать принадлежность проекции точки на ось x/y. Но это уже детали.

[Максим Мосейчук]

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

[abcd0x00]

fshp:
Ясно, я понял: ты ищешь точку пересечения прямых, которым принадлежат отрезки, а потом координаты точки пересечения прямых сравниваешь сначала с координатами концов первого отрезка, а потом - с координатами концов второго отрезка.

Но ошибку у тебя нашёл одну всё равно

[guest@localhost crossfunc]$ echo "0 0 5 5   0 0 -2 -2" | ./crossfunc 
Прямые параллельные
[guest@localhost crossfunc]$

Тут у отрезков одна общая точка - X(0; 0).

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

[Максим Мосейчук]

abcd0x00: да легко сделать. Можно даже найти пересечение отрезков, лежащих на одной прямой и имеющих более 1 общей точки. В этом случае это так же отрезок будет.

Answer 3

[Ocelot]

Есть способ проще: e-maxx.ru/algo/segments_intersection_checking (через ориентированные площади треугольников), но он не находит саму точку пересечения, только говорит, пересекаются отрезки или нет.