Лабораторный практикум по информатике


Задача 5. «Пересечение отрезков»



бет74/83
Дата06.01.2022
өлшемі1.1 Mb.
#15674
түріПрактикум
1   ...   70   71   72   73   74   75   76   77   ...   83
Задача 5. «Пересечение отрезков». Дано n отрезков. Реализовать программу, находящую все их пересечения между собой. Отобразить решение графически.

На плоскости заданы два отрезка a и b, a – точками A1(A1 ,A1 )

x y

и A2(A2 ,A2 ), b – точками B1(B1 ,B1 ) и B2(B2 ,B2 ). Найти и напечатать



x y x y x y

возможную точку их пересечения C(Cx,Cy). Рассмотрим первый отрезок

a. Уравнение прямой, на которой он лежит, можно записать так:

xa = A1 + ta (A2 – A1 )


x

x

x

ya = A1 + ta (A2 – A1 )


y

y

y


Здесь A1 ,A1 ,A2 ,A2 – константы, x ,y

– точки, принадлежащие



x y x y a a

отрезку, при ta изменяющемся от 0 до 1. Аналогично для отрезка b:

xb = B1 + tb (B2 – B1 )
x

x

x

yb = B1 + tb (B2 – B1 )


y

y

y

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

A1 + t (A2 – A1 ) = B1 + t (B2 – B1 )


  1. a x x x b x x

A1 + t (A2 – A1 ) = B1 + t (B2 – B1 )

  1. a y y y b y y

После разрешения системы относительно ta,tb получаем:

ta (A1 – A2 ) + t (B2 – B1 ) = A1 – B1


x

x

b

x

x

x

x

ta (A1 – A2 ) + t (B2 – B1 ) = A1 – B1


y

y

b

y

y

y

y

А это есть система из двух линейных уравнений относительно ta, tb.

Известно, что система: a1 x + b1 y = c1

a2 x + b2 y = c2

имеет следующее решение:


x = dx/d y = dy/d,

где d – определитель матрицы,

d = a1b2 – a2b1, dx = c1b2 – c2b1, dy = a1c2 – a2c1.

В нашей системе относительно ta,tb:


x


a1 = A1 b1 = B2 c1 = A1
x

x

x

a2 = A1 b2 = B2 c2 = A1


y

y

y


  • A2

  • B1
    x


  • B1
    x


  • A2
    y


  • B1
    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).

  1. Меняем местами элемент a[i] с наименьшим элементом, который: а) находится правее a[i];

б) больше, чем a[i].

В нашем случае меняем 3 и 4.



  1. Все элементы, стоящие за a[i], сортируем. В нашем случае нужно отсортировать число 4, но это единственный элемент, следовательно, так его и оставляем.

В результате выполнения этих трех шагов получаем следующую по алфавиту перестановку 1243.

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





Достарыңызбен бөлісу:
1   ...   70   71   72   73   74   75   76   77   ...   83




©emirsaba.org 2022
әкімшілігінің қараңыз

    Басты бет