Форум программистов, компьютерный форум, киберфорум
Геометрия
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
12 / 8 / 6
Регистрация: 10.07.2011
Сообщений: 369
Записей в блоге: 1
1

Проверка: Является ли замкнутая ломаная n-угольником

09.08.2014, 07:50. Показов 686. Ответов 5
Метки нет (Все метки)

Имеется ломаная, т.е. упорядоченные пары координат точек https://www.cyberforum.ru/cgi-bin/latex.cgi?<a_1, a_2>, <a_2, a_3>..., <a_{n-1}, a_n>, <a_n, a_1>, где https://www.cyberforum.ru/cgi-bin/latex.cgi?a_i = <x_i, y_i>. Я хочу определить, образует ли эта ломаная n-угольник, т.е. отсутствуют ли в ней самопересечения. Подскажите, как это можно сделать?
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.08.2014, 07:50
Ответы с готовыми решениями:

Как правильно обозначается замкнутая ломаная?
Обычная ломаная обозначается указанием ее вершин, например: ABCD А вот как обозначается замкнутая...

Замкнутая ломаная и пересечение отрезков
Есть задача - тыкая мышкой на экран, построить замкнутую ломаную линию без самопересечений и...

Верно ли, что замкнутая ломаная p1,p2,…pn не имеет самопересечений?
Даны координаты 15 точек p1,p2,…pn на плоскости с координатами x1,....x15, y1,....y15. Верно ли,...

создать функцию, рисующую окружность с вписаным 6-ти угольником
ПОМОГИТЕ создать функцию на языке лисп.Рисующую окружность с вписаным 6-ти угольником, координаты...

5
266 / 192 / 50
Регистрация: 16.06.2014
Сообщений: 424
09.08.2014, 12:25 2
Bohes2013, эта тема обсуждается
ссылка

Добавлено через 22 минуты
Тогда цитата
"1. Сортируем все концы по возрастанию X.

2. Последовательно идём по этим точкам - для левых концов добавляем отрезок в AVL/RB дерево, для правых - удаляем. Отрезки отсортированы по Y их начальных точек.

Утверждается, что после каждого добавления и перед каждым удалением достаточно проверить на пересечение с предыдущим и следующим отрезком в порядке этого AVL/RB дерева."
0
12 / 8 / 6
Регистрация: 10.07.2011
Сообщений: 369
Записей в блоге: 1
21.08.2014, 11:39  [ТС] 3
Цитата Сообщение от Iriini Посмотреть сообщение
проверить на пересечение с предыдущим и следующим отрезком в порядке этого AVL/RB дерева
Каким образом проверять-то?
Цитата Сообщение от Iriini Посмотреть сообщение
Отрезки отсортированы по Y их начальных точек.
А из чего это следует и как доказывается?

Кто автор данного алгоритма?
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
12 / 8 / 6
Регистрация: 10.07.2011
Сообщений: 369
Записей в блоге: 1
21.08.2014, 12:06  [ТС] 5
Цитата Сообщение от Iriini Посмотреть сообщение
Если хоть одно несовпадение, то невыпуклый
Хм, но в задаче не имеет значение тип многоугольника, главное, определить существование пересечения его сторон, либо отсутствие такового.
0
266 / 192 / 50
Регистрация: 16.06.2014
Сообщений: 424
21.08.2014, 12:20 6
определить существование пересечения его сторон
Действительно, в этом случае надо проверить попарно все отрезки.
1. Берем сторону (отрезок, заданный координатами концов).
2. Рассматриваем все остальные отрезки (стороны многоугольника). Ищем факт пересечения данного в п.1 отрезка каким -либо из остальных.
Два отрезка пересекаются тогда и только тогда, когда концы одного отрезка лежат по разные стороны другого и наоборот.
Здесь что-то есть об этом.
http://habrahabr.ru/post/144571/
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.08.2014, 12:20

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Рекурсивное разбиение прямоугольной области правильным n-угольником
Имеется алгоритмический язык.Помогите реализовать на паскале. алг RectangleDraw(арг цел...

Построение сечения 3D фигуры (пирамида с 6-угольником в основании)
Как на C# можно эту программу написать, что можно использовать? Получится ли на MonoGame или Unity?

Рекурсивное разбиение прямоугольной области правильным n-угольником
Имеется алгоритмический язык.Помогите реализовать на паскале. алг RectangleDraw(арг цел...

1C ломаная
Всем привет бьюсь уже неделю с 1С никак немогу установить, а вернее установил, но перед входом...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.