Алгоритм поиска точек на границе фигуры

[cool.phenon]

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

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

[electric_retard]

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

[cool.phenon]

По хорошему, это означает, что есть некоторое ограничение, которому удовлетворяют точки как границы, так и внутренние.

Но говорить, что задано уравнением, нельзя.

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

[electric_retard]

cool.phenon в сообщении #981187 писал(а):

Но говорить, что задано уравнением, нельзя.

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

[cool.phenon]

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

[electric_retard]

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
 

[cool.phenon]

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

[slavav]

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

[cool.phenon]

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

[cool.phenon]

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

[slavav]

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

[electric_retard]

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

[slavav]

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.

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

[cool.phenon]

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

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