Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 25.03.2009, 12:25
Новичок

Отправить личное сообщение для AndreyGL/D3D Посмотреть профиль Найти все сообщения от AndreyGL/D3D
 
Регистрация: 25.03.2009
Адрес: Москва
Сообщений: 6

Построение невыпуклой оболочки.
Привет всем.
Задача дан массив или несколько массивов точек.
Точки в массиве образуют замкнутую область. Т.е. если последовательно соединить их ребрами будет ограничивающий контур. Список массивов может иметь пересечения, замкнутость внутри себя. Список точек может иметь дублирующие значения как близко стоящие так и с шагом.
т.е.

Point[i] == Point[i - 1];
Point[i] == Point[i +1];
Point[i] == Point[i - n] так и Point[i] == Point[i + n]


Это уже решено посредством удаления циклов через алгоритм на графах графах.

Теперь в результате несколько списков без повторов и дублей образующих контуры

Теперь по полученным данным требуется построить не выпуклую оболочку.

На данный момент она строится если список контуров всего один.
В случае нескольких контуров результат разные - контур с пересечениями либо он один но не охватывающий все точки.

Какое решение оптимальное? пусть оно будет не самым быстрым.
  #2  
Старый 25.03.2009, 17:15
гость

 
Сообщений: n/a

Что вы имеете ввиду под невыпуклой оболочкой?
  #3  
Старый 26.03.2009, 09:40
Новичок

Отправить личное сообщение для AndreyGL/D3D Посмотреть профиль Найти все сообщения от AndreyGL/D3D
 
Регистрация: 25.03.2009
Адрес: Москва
Сообщений: 6

>Что вы имеете ввиду под невыпуклой оболочкой?
представьте себе букву пятиконечную звезду или быкву "П"- это не выпуклый многоугольник. Внутри нее есть еще точки. Нужно найти конур звезды.
  #4  
Старый 26.03.2009, 10:12
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Вероятно, нужные вам задачи решены в одной из подобных библиотек: http://www.cs.man.ac.uk/~toby/alan/software/
  #5  
Старый 27.03.2009, 08:34
гость

 
Сообщений: n/a

Т.е. нужно построить какую-нибудь оболочку, содержащую все точки, без самопересечений и т.п.? И без дополнительных критериев?
Если это так, то есть задача построения простого многоугольника для заданного мн-ва точек. Алгоритмов с полудюжины наипростейших и еще столько же через вып. оболочки.
Других вариантов алгоритма слишком много, чтобы начинать.
  #6  
Старый 28.03.2009, 11:31
Новичок

Отправить личное сообщение для AndreyGL/D3D Посмотреть профиль Найти все сообщения от AndreyGL/D3D
 
Регистрация: 25.03.2009
Адрес: Москва
Сообщений: 6

Сообщение от MBo Посмотреть сообщение
Вероятно, нужные вам задачи решены в одной из подобных библиотек: http://www.cs.man.ac.uk/~toby/alan/software/
Эта библиотека не совсем подходит, она может давать несколько контуров. И нужно находить общий. Она не дает 1 и самый большой, который как раз будет ограничивающим Уже были попытки ее использовать.
Сообщение от гость Посмотреть сообщение
Т.е. нужно построить какую-нибудь оболочку, содержащую все точки, без самопересечений и т.п.? И без дополнительных критериев?
Что подразумевается под критерием?
Сообщение от гость Посмотреть сообщение
Если это так, то есть задача построения простого многоугольника для заданного мн-ва точек. Алгоритмов с полудюжины наипростейших и еще столько же через вып. оболочки.
Других вариантов алгоритма слишком много, чтобы начинать.
Вы наверное не поняли алгоритм из простейших если оболочка выпуклая, но она может быть не выпуклой, что уже сложнее.

Последний раз редактировалось AndreyGL/D3D, 28.03.2009 в 11:33.
  #7  
Старый 28.03.2009, 15:25
гость

 
Сообщений: n/a

--- Что подразумевается под критерием?
Т.к. Ваша задача имеет бесконечное множество решений (не оговорено даже, что нельзя вставлять новые точки), то желательно скомпенсировать это критерием вроде минимальной площади etc. чтобы выбрать единственное решение, как в случае если критерий - это вып. оболочка.
--- Вы наверное не поняли алгоритм из простейших если оболочка выпуклая, но она может быть не выпуклой, что уже сложнее.
Отсутствие запятых во фразе создает двусмысленность. Рискну предположить, что это как раз Вы не поняли. Речть идет о задаче построения мн-ка через все(!) точки, он не будет выпуклым и строго говоря это одно из решений, которое Вы ожидаете. И в каком смысле искомый "сложнее" выпуклой оболочки? Уж прям такой хитрый.
  #8  
Старый 01.04.2009, 19:32
Новичок

Отправить личное сообщение для AndreyGL/D3D Посмотреть профиль Найти все сообщения от AndreyGL/D3D
 
Регистрация: 25.03.2009
Адрес: Москва
Сообщений: 6

Сообщение от гость
-- Что подразумевается под критерием?
Т.к. Ваша задача имеет бесконечное множество решений (не оговорено даже, что нельзя вставлять новые точки), то желательно скомпенсировать это критерием вроде минимальной площади etc. чтобы выбрать единственное решение, как в случае если критерий - это вып. оболочка.
Про площадь это уже близко
Сообщение от гость
--- Вы наверное не поняли алгоритм из простейших если оболочка выпуклая, но она может быть не выпуклой, что уже сложнее.
Отсутствие запятых во фразе создает двусмысленность. Рискну предположить, что это как раз Вы не поняли. Речть идет о задаче построения мн-ка через все(!) точки, он не будет выпуклым и строго говоря это одно из решений, которое Вы ожидаете. И в каком смысле искомый "сложнее" выпуклой оболочки? Уж прям такой хитрый.
Повторю с запятыми:
Вы наверное не поняли, алгоритм из простейших, если оболочка выпуклая, но она может быть не выпуклой, что уже сложнее.
Т.е. алгоритм будет сложным с той точки зрения, что непонятно какую оболочку строить выпуклую(если действительно данные корректны для такого построения) или нет. Ведь насколько мне известно что если получиться из списка точек выпуклая оболочка, то результат будет верным - можно строить выпуклую. Если пытаться сразу строить выпуклую то это будет неверно. К примеру пятиконечная звезда.
Вот тут сложнее все обстоит. Ну и сам алгоритм построения не выпуклой оболочки сложнее чем выпуклой т.к. он основан на нем + нужны критерии к примеру минимальная площадь или еще что. Вот это я смутно представляю.
Да к все таки как это реализовать?
  #9  
Старый 02.04.2009, 01:53
гость

 
Сообщений: n/a

Площадь полигона, содержащего заданные точки, можно как угодно близко приблизить к нулю (даже нулем сделать, если допустить вырожденные полигоны). Вы уверены что вам такой полигон нужен?

А если минимизировать не площадь, а периметр - то минимальным полигоном будет как раз выпуклая оболочка.
  #10  
Старый 02.04.2009, 11:23
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Некоторые умозрительные рассуждения:
Нарисуем пятиконечную звезду. Пронумеруем вершины и точки пересечения последовательно по ходу рисования, причем точки пересечения нумеруются дважды (не рассматриваем сложные случаи с совпадением отрезков и пересечением трех и более отрезков в одной точке). Таким образом, вершины получают номера 0, 9, 3, 12, 6 (если начинать сверху, по часовой стрелке), а точки пересечения 1/8, 2/10, 4/11, 5/13, 7,14. Начнем обход с верхней вершины в направлении по часовой стрелке
0 - 1.
из 1 переходим в парную 8, и выбираем направление движения так, чтобы вектор от 8 образовывал наименьший положительный угол относительно прошлого вектора 0-1. При этом выбор идет из соседних с 8 по номеру вершин , т.е. 7 и 9. Подходит 9, направление положительное, 9 не точка пересечения, значит, просто переходим в 10.
Из 10 в парную 2, далее выбираем 3 и т.д.
В результате маршрут
0-1/8-9-10/2-3-4/11-12-13/5-6-6/14-0

Для данной фигуры направление движения (по индексам) оказалось всегда положительное, т.е. в большую сторону, в общем случае это будет не так.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Построение изолиний midi Математические алгоритмы 3 09.12.2008 00:13
Построение триангуляционной сети hungry_Duck Реализация, исходники, языки 0 21.05.2008 20:52
Построение окружностей. гость Вычислительная геометрия 4 21.05.2008 14:26
Принадлежность точки выпуклой оболочки 3d vladScr Вычислительная геометрия 6 15.05.2008 13:17
Построение сечения Mozilla Вычислительная геометрия 1 10.01.2008 00:29