Информатика
Найти все точки самопересечения разноцветной
Найти все точки самопересечения разноцветной замкнутой линии, заданной на плоскости координатами своих вершин в порядке обхода ломаной. Данные о ломаной представляются таблицей:
х | у |
0 | 1 |
1 | 0 |
0 | 1 |
1 | 1 |
Особенность этой задачи - большое число частных случаев, связанных с возможным вырождением или наложением отрезков ломанной линии. Именно эти ситуации и составляют содержание тестов, на которых большинство программ дают неправильные результаты.
Приведем проверочные тесты:
Tecт1.
(Основной случай)
0 | 0 |
0 | 1 |
1 | 0 |
1 | 1 |
Правильные результаты:
точки пересечения
0.5 0.5
Тест 2. (Основной случай)
0 | 0 |
0 | 1 |
1 | 1 |
1 | 0 |
Правильные результаты:
точки пересечения:
отсутствуют
Тест3. (Наложение вершины)
0 | 0 |
0 | 1 |
0.5 | 0 |
1 | 1 |
1 | 0 |
Правильные результаты:
точки пересечения
0.5 0
Тест4. (Наложение ребра)
0 | 0 |
0 | 1 |
0.2 | 0 |
0.8 | 0 |
1 | 1 |
1 | 0 |
Правильные результаты:
отрезок пересечения:
[0.2, 0] - [0.8, 0]
Для систематического конструирования алгоритмов и программы необходима разработка сценария диалога и описание метода решения поставленной геометрической задачи.
Сценарий
<k>: <x> <у>
точки пересечения:
отрезок: <1> - <1+1>
точка: <х> <у>
………
Метод решения данной задачи может быть основан на вычислении точек пересечения отрезков (х1, у1) - (x2, у2) и (х3, y3) - (х4, y4) как точек пересечения линий, проходящих через заданные отрезки, с помощью системы уравнений:
