«Пересечение отрезков»

«Пересечение отрезков». Дано n отрезков. Реализовать
программу, находящую все их пересечения между собой. Отобразить
решение графически.
На плоскости заданы два отрезка a и b, a – точками A1
(A1
x,A1
y)

и A2
(A2
x,A2
y), b – точками B1
(B1
x,B1
y) и B2
(B2
x,B2
y). Найти и напечатать
возможную точку их пересечения C(Cx,Cy). Рассмотрим первый отрезок
a. Уравнение прямой, на которой он лежит, можно записать так:

xa = A1
x + ta (A2
x – A1
x)

ya = A1
y + ta (A2
y – A1
y)

Здесь A1
x,A1
y,A2
x,A2
y – константы, xa,ya – точки, принадлежащие
отрезку, при ta изменяющемся от 0 до 1. Аналогично для отрезка b:

xb = B1
x + tb (B2
x – B1
x)

yb = B1
y + tb (B2
y – B1
y)

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

равенства:
A1
x + ta (A2
x – A1
x) = B1
x + tb (B2
x – B1
x)

A1
y + ta (A2
y – A1
y) = B1
y + tb (B2
y – B1
y)

После разрешения системы относительно ta,tb получаем:
ta (A1
x – A2
x) + tb (B2
x – B1
x) = A1
x – B1
x

ta (A1
y – A2
y) + tb (B2
y – B1
y) = A1
y – B1
y

А это есть система из двух линейных уравнений относительно ta, tb.
Известно, что система:
a1 x + b1 y = c1
a2 x + b2 y = c2
имеет следующее решение:

117

x = dx/d
y = dy/d,

где d – определитель матрицы,
d = a1b2 – a2b1,
dx = c1b2 – c2b1,
dy = a1c2 – a2c1.
В нашей системе относительно ta,tb:
a1 = A1
x – A2
x
b1 = B2
x – B1
x
c1 = A1
x – B1
x
a2 = A1
y – A2
y
b2 = B2
y – B1
y
c2 = A1
y – B1
y

откуда легко находится d,dx,dy. Если d отличен от нуля, то система име-
ет единственное решение. Правда, следует помнить, что искомые ta, tb

параметрически задают отрезки, только если они лежат в диапазоне

[0,1], в противном случае – точка пересечения прямых, на которых ле-
жат отрезки, находится вне этих самых отрезков.

Если d равен нулю, а хотя бы один из dx,dy отличен от нуля, то от-
резки лежат на параллельных прямых, или, как говорят математики, они

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

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

Одним из важных элементов комбинаторики являются переста-
новки. Перестановки без повторений – комбинаторные соединения,

которые могут отличаться друг от друга лишь порядком входящих в них
элементов. Число таких перестановок определяется как n!.
Для числа 3 количество перестановок будет равно 3!=3 * 2 * 1=6.
Для четырех: 4! = 4 * 3 * 2 * 1 = 24.
Часто для генерации перестановок используется алгоритм Дейкстры
для получения всех перестановок по алфавиту. Разберем этот алгоритм.

Пусть у нас есть первая перестановка (например, 1234). Для нахо-
ждения следующей перестановки выполняем три шага.

1. Двигаясь с предпоследнего элемента перестановки, ищем эле-
мент a[i], удовлетворяющий неравенству a[i] < a[i + 1]. Для перестанов-
ки 1234, это число 3, т. к. (3 < 4).

118

2. Меняем местами элемент a[i] с наименьшим элементом, который:
а) находится правее a[i];
б) больше, чем a[i].
В нашем случае меняем 3 и 4.
3. Все элементы, стоящие за a[i], сортируем. В нашем случае нужно
отсортировать число 4, но это единственный элемент, следовательно,
так его и оставляем.
В результате выполнения этих трех шагов получаем следующую по
алфавиту перестановку 1243.

Выполнять эти шаги нужно циклически до тех пор, пока в переста-
новке не будет находиться искомый в первом шаге элемент a[i], т. е. по-
ка перестановка не станет отсортированной по убыванию: 4321.

Перестановки с повторениями – комбинаторные соединения,
в которых среди образующих элементов имеются одинаковые. В таких

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

0

Очень интересно, но ничего не понятно.

0

согласна

0