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