Обвод вершин кривой

beginner
Сообщений: 8
Зарегистрирован: 30 сен 2010, 21:00

Обвод вершин кривой

Сообщение beginner » 06 окт 2010, 16:45

Ну это больше походит на алгоритм поиска замкнутой области (которую можно обвести кривой). Данный алгоритм я уже реализовал и он работает. Проблема в том что последовательность точек которую мы получаем идёт не в том порядке в котором нужно зачёркивать (a для библиотеки которая производит обвод и зачёркивание области - это принципиально важно!).
Вот один пример. Точки в той последовательности в которой их выплюнул алгоритм поиска области: (3,2) (2,1) (1,1) (0,1) (1,2) (2,3) (3,1) (3,3) (0,2) (0,0).

И вот как оно в итоге закрашено:
Изображение

A должно быть по идее так:
Изображение

т.e. по сути последовательность точек должна быть такой:
(0,0) (0,1) (0,2) (1,2) (2,3) (3,3) (3,2) (3,1) (2,1) (1,1) (0,0) (движение начиная c самой верхней левой точки вправо).


12d3 писал(а):Source of the post
P.S. A это случайно не игра "точки"?

Она родимая Давно уже мечтаю реализовать, только до сих пор всё никак руки не доходили.
Последний раз редактировалось beginner 29 ноя 2019, 14:59, всего редактировалось 1 раз.
Причина: test

beginner
Сообщений: 8
Зарегистрирован: 30 сен 2010, 21:00

Обвод вершин кривой

Сообщение beginner » 08 окт 2010, 21:52

Попробую переформулировать задачу. Допустим, имеется список вершин многоугольника. Существуют-ли какие-нибудь методики определения очереди прохождения через каждую вершину так что-бы в итоге получился многоугольник, в котором нет пересекающихся между собой сторон?
По сути это-бы решило проблему.
Последний раз редактировалось beginner 29 ноя 2019, 14:59, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
Casual
Сообщений: 19
Зарегистрирован: 28 сен 2010, 21:00

Обвод вершин кривой

Сообщение Casual » 08 окт 2010, 22:12

Вот посмотрите здесь в разделе построение выпуклой оболочки набора точек:

[url=http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%...%BC%D0%BE%D0%B2]http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%...%BC%D0%BE%D0%B2[/url]

может найдете, что подходящие.
Последний раз редактировалось Casual 29 ноя 2019, 14:59, всего редактировалось 1 раз.
Причина: test

beginner
Сообщений: 8
Зарегистрирован: 30 сен 2010, 21:00

Обвод вершин кривой

Сообщение beginner » 08 окт 2010, 23:10

Чуть выше писал что в моем случае многоугольник - далеко не обязательно будет выпуклой оболочкой.. Потому эти алгоритмы, к сожалению, не подходят.
Последний раз редактировалось beginner 29 ноя 2019, 14:59, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
alekcey
Сообщений: 465
Зарегистрирован: 12 сен 2009, 21:00

Обвод вершин кривой

Сообщение alekcey » 09 окт 2010, 19:24

beginner писал(а):Source of the post
Чуть выше писал что в моем случае многоугольник - далеко не обязательно будет выпуклой оболочкой.. Потому эти алгоритмы, к сожалению, не подходят.

Безотносительно к выпуклости. Порядок соединения точек задаётся перестановкой. Последняя точка соединяется c первой. Для каждой перестановки идёт проверка на пересечение отрезков, точки соединяющие. Как только есть пересечение, переходим к новой перестановке. B случае полного отсутствия пересечений имеем нужный результат. Считать будет долго…
Последний раз редактировалось alekcey 29 ноя 2019, 14:59, всего редактировалось 1 раз.
Причина: test


Вернуться в «Дискретная математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 33 гостей