2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Алгоритм поиска точек на границе фигуры
Сообщение22.02.2015, 01:40 
Аватара пользователя


12/05/12
604
Оттуда
Здравствуйте. Пусть своими точками задана некоторая фигура (2- или 3-мерная ), и что важно, точки могут быть как вершинами, так и просто находиться на стороне или грани, или просто быть внутренними точками. Необходим алгоритм, который находит все точки, которые находятся на границе фигуры. Алгоритм поиска выпуклой оболочки отпадает, так как не учитывает точек, которые находятся на сторонах или гранях, а отдельно ловить эти точки проблематично. Подскажите, слышали ли Вы о существовании такого алгоритма? (язык сейчас не принципиален). Если нет, то как посоветуете ловить такие точки, если уже известна выпуклая оболочка?

Задача прикладная, возникла из численного моделирования, а именно, из аппроксимации условия Робина.

 Профиль  
                  
 
 Re: Алгоритм поиска точек на границе фигуры
Сообщение22.02.2015, 02:29 
Аватара пользователя


31/12/13
148
Изображение в студию.
Не очень понятно как фигура, задаваемая точками, может содержать эти точки внутри себя. Получается, что она задается не точками, а еще чем-то.

 Профиль  
                  
 
 Re: Алгоритм поиска точек на границе фигуры
Сообщение22.02.2015, 14:19 
Аватара пользователя


12/05/12
604
Оттуда
По хорошему, это означает, что есть некоторое ограничение, которому удовлетворяют точки как границы, так и внутренние.
Изображение
Но говорить, что задано уравнением, нельзя.

На картинке как раз та ситуация, о которой я говорил. Выпуклая оболочка выдаст вершины, а не точки, которые лежат на сторонах

 Профиль  
                  
 
 Re: Алгоритм поиска точек на границе фигуры
Сообщение22.02.2015, 15:17 
Аватара пользователя


31/12/13
148
cool.phenon в сообщении #981187 писал(а):
Но говорить, что задано уравнением, нельзя.

Но чем-то же оно задано?
Всяко проще с ним работать, чем с россыпью точек.
Например точки 3, где тогда граница?

 Профиль  
                  
 
 Re: Алгоритм поиска точек на границе фигуры
Сообщение22.02.2015, 15:29 
Аватара пользователя


12/05/12
604
Оттуда
electric_retard
Я бы не хотел входить в тонкости задачи, здесь именно россыпь точек. Границей мы считаем границу выпуклой оболочки, но на сторонах границы тоже могут быть точки, вот я к чему. Алгоритм поиска выпуклой оболочки этих точек не учитывает.

 Профиль  
                  
 
 Re: Алгоритм поиска точек на границе фигуры
Сообщение22.02.2015, 16:49 
Аватара пользователя


31/12/13
148
cool.phenon
Тогда в 2d случае вот решение, при условии, что вы перед этим выпуклый контур отыскали. Задаетесь точностью и вперед:
код: [ скачать ] [ спрятать ]
Используется синтаксис Matlab M
x = rand(1,100);
y = rand(1,100);
eps = .1;

plot(x,y,'.'),axis equal, hold on

k = convhull(x,y);
plot(x(k),y(k))

for i = 2:numel(k)
    z = complex(    x - x(k(i-1)),          y - y(k(i-1))       );
        complex(    x(k(i)) - x(k(i-1)),    y(k(i)) - y(k(i-1)) );
       
    abs(z-ans*min(1,max(0,real(z/ans))));
   
    idx = ans-eps<=0;
   
    plot(x(idx),y(idx),'o')
end
 

Изображение

 Профиль  
                  
 
 Re: Алгоритм поиска точек на границе фигуры
Сообщение22.02.2015, 17:11 
Аватара пользователя


12/05/12
604
Оттуда
Я понял, то есть, этот алгоритм находит точки, которые находятся на расстоянии от заданной линии не более чем $\varepsilon$, а в моём случае это отрезки выпуклой оболочки. Это как раз то, чего не хватало, спасибо!

 Профиль  
                  
 
 Re: Алгоритм поиска точек на границе фигуры
Сообщение22.02.2015, 17:34 
Заслуженный участник


26/05/14
981
Выпуклые оболочки (ВО) можно разделить на "тонкие" и "толстые". "Тонкая" ВО содержит минимальное число вершин - только те в которых граница ВО делает поворот. "Толстая" ВО перечисляет все вершины лежащие на границе ВО, включая те в которых граница не поворачивает. Любой алгоритм построения ВО может быть настроен для построения любой "тонкости" оболочки.

 Профиль  
                  
 
 Re: Алгоритм поиска точек на границе фигуры
Сообщение22.02.2015, 18:27 
Аватара пользователя


12/05/12
604
Оттуда
slavav
Я это только сейчас узнаю :-) ведь программирование, на самом деле, -- не мой профиль, но приходится узнавать в силу того, насколько прикладным он является

 Профиль  
                  
 
 Re: Алгоритм поиска точек на границе фигуры
Сообщение22.02.2015, 23:56 
Аватара пользователя


12/05/12
604
Оттуда
С 2d разобрался, теперь нужно переходить к 3d. Ясно, что теперь вместо каждой прямой, до которой считалось расстояние, нужно взять плоскость. Но для разных треугольников выпуклой оболочки могут попадаться одни и те же плоскости, то есть, этот алгоритм будет "перерабатывать" -- учитывать некоторые точки несколько раз.

 Профиль  
                  
 
 Re: Алгоритм поиска точек на границе фигуры
Сообщение23.02.2015, 01:11 
Заслуженный участник


26/05/14
981
Вопрос-намёк: а как вы учитывали эту ситуацию в 2d? Одна внутренняя точка может быть близка к нескольким отрезкам. Иначе говоря, при любом способе проверки точек относительно элементов оболочки надо удалять дубликаты.

 Профиль  
                  
 
 Re: Алгоритм поиска точек на границе фигуры
Сообщение23.02.2015, 15:17 
Аватара пользователя


31/12/13
148
slavav
А по-английски эти "толстые" оболочки как правильно зовутся?
В MATLAB такого функционала нет, по крайней мере в функции convhull. Можно ещё посмотреть библиотеку CGAL.
cool.phenon
Одни и те же точки попадаются и в 2d случае, складируйте их индексы в отдельной переменной и исключайте из рассмотрения.
В 3d случае нужно заменить алгоритм поиска расстояния от отрезка до точки на алгоритм поиска расстояния от треугольника до точки.
Но правильней всего было бы найти реализацию поиска "толстой" выпуклой оболочки.

 Профиль  
                  
 
 Re: Алгоритм поиска точек на границе фигуры
Сообщение23.02.2015, 18:01 
Заслуженный участник


26/05/14
981
electric_retard в сообщении #981607 писал(а):
slavav
А по-английски эти "толстые" оболочки как правильно зовутся?
В MATLAB такого функционала нет, по крайней мере в функции convhull. Можно ещё посмотреть библиотеку CGAL.


Как зовутся они зовутся по-английски я не знаю, к сожалению.
А код convhull есть? Тогда можно посмотреть как его модифицировать.

Например в алгоритме заворачивания подарка вы по текущему ребру строите следующее. Для этого вы отыскиваете точку, которая реализует минимальный поворот. Если таких точек несколько и вы из них выбираете самую далёкую, то вы строите "тонкую" ВО. Напротив, если из этих точек вы выбираете самую близкую, то получится "толстая" ВО.
http://en.wikipedia.org/wiki/Gift_wrapping_algorithm:
Цитата:
The algorithm may be easily modified to deal with collinearity, including the choice whether it should report only extreme points (vertices of the convex hull) or all points that lie on the convex hull.


Я упомянул алгоритм заворачивания подарка, так как он легко поднимается в пространство. Там вы по грани и её ребру ищете точки, которые реализуют минимальный угол поворота вокруг ребра. Рассмотрим все такие точки плюс два конца ребра, вокруг которого мы вращались. Всё это множество лежит в одной плоскости. Если вы в этой плоскости построите ВО, то она будет гранью ВО в пространстве. Важно, что пока вы искали новую грань, вы узнали все точки исходного множества, которые принадлежат этой грани.

 Профиль  
                  
 
 Re: Алгоритм поиска точек на границе фигуры
Сообщение23.02.2015, 18:33 
Аватара пользователя


12/05/12
604
Оттуда
slavav
electric_retard
Дубликаты точек немного увеличивают время вычисления, но сейчас для меня это не принципиально, главное, что идея работает. Оптимизацией займусь уже после того, как отлажу :D

Случайно так получилось, что я именно в MATLAB и работаю :-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group