1 | |
Проверка: Является ли замкнутая ломаная n-угольником09.08.2014, 07:50. Показов 1275. Ответов 5
Метки нет (Все метки)
Имеется ломаная, т.е. упорядоченные пары координат точек , где . Я хочу определить, образует ли эта ломаная n-угольник, т.е. отсутствуют ли в ней самопересечения. Подскажите, как это можно сделать?
0
|
09.08.2014, 07:50 | |
Ответы с готовыми решениями:
5
Как правильно обозначается замкнутая ломаная? Замкнутая ломаная и пересечение отрезков Верно ли, что замкнутая ломаная p1,p2,…pn не имеет самопересечений? создать функцию, рисующую окружность с вписаным 6-ти угольником |
266 / 192 / 50
Регистрация: 16.06.2014
Сообщений: 424
|
|
09.08.2014, 12:25 | 2 |
Bohes2013, эта тема обсуждается
ссылка Добавлено через 22 минуты Тогда цитата "1. Сортируем все концы по возрастанию X. 2. Последовательно идём по этим точкам - для левых концов добавляем отрезок в AVL/RB дерево, для правых - удаляем. Отрезки отсортированы по Y их начальных точек. Утверждается, что после каждого добавления и перед каждым удалением достаточно проверить на пересечение с предыдущим и следующим отрезком в порядке этого AVL/RB дерева."
0
|
266 / 192 / 50
Регистрация: 16.06.2014
Сообщений: 424
|
|
21.08.2014, 11:54 | 4 |
Вот еще вариант...
В цикле. 1.Рассчитываем уравнение прямой для каждой стороны (пары точек) вида a*x+b*y+c=0. 3.Если остальные вершины лежат по одну сторону от данной прямой, т.е. axi+byi+c одного знакаи, то многоугольник выпуклый. Если хоть одно несовпадение, то невыпуклый.
0
|
266 / 192 / 50
Регистрация: 16.06.2014
Сообщений: 424
|
|
21.08.2014, 12:20 | 6 |
1. Берем сторону (отрезок, заданный координатами концов). 2. Рассматриваем все остальные отрезки (стороны многоугольника). Ищем факт пересечения данного в п.1 отрезка каким -либо из остальных. Два отрезка пересекаются тогда и только тогда, когда концы одного отрезка лежат по разные стороны другого и наоборот. Здесь что-то есть об этом. http://habrahabr.ru/post/144571/
0
|
21.08.2014, 12:20 | |
21.08.2014, 12:20 | |
Помогаю со студенческими работами здесь
6
Рекурсивное разбиение прямоугольной области правильным n-угольником Построение сечения 3D фигуры (пирамида с 6-угольником в основании) Рекурсивное разбиение прямоугольной области правильным n-угольником 1C ломаная Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |