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

Может кто сталкивался с такой задачей или знает какой примерно лучше использовать алгоритм?

За ранее благодарна!

Либо условие неполное, либо одно из двух. В общем, не сформулирован критерий отделения контурных точек от внутренних.


Множество точек не бывает ни выпуклым, ни впуклым. Это свойство есть только у контуров.

Идеального решения при таких расплывчатых условиях, видимо нет. Вот неидеальное. Будет работать только для более-менее выпуклых фигур. 

Соединить каждую точку с каждой. Получится некая "звезда". Как определить лежит ли точка внутри фигуры (звезде в данном случае) или на ее периметре на этом форуме когда-то уже было описано. 
Ощибки будут следующие:

1. Точки периметра, лежащие на вогнутой части контура будут рассматриваться как внутренние.
2. Внутренние точки, лежащие очень близко к контуру, при условии, что контур в этом районе точками не представлен, будут рассматриваться как лежащие на контуре.

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

Получится выпуклый описывающий контур с кучей отрезков внутри.

Именно так, хотя ограничение на длину соединений позволит получить некоторые "вогнутости". 

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

_Y_, предлагаю дождаться ТС...

Точек оч.оч.оч. много,более 2000.Они располагаются к друг друга близко
например,некоторые точки
0.46605139 0.039221156 -0.42925035,
0.47014663 0.046391322 -0.44258687,
0.47360408 0.038873176 -0.43728157,
0.45986243 0.0454406 -0.42990745,

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

Shket, всё-таки будьте любезны уточнить задачу и ликвидировать разночтения и двусмысленности.
А заодно уточните количество измерений и смысл приведённых характеристик точек.

Shket, представь себе спиральку от комаров ;) Вот такую фигуру и стоит попробовать описать точками. Сразу станет понятно в каком месте описание задачи будет глючить.

То, что точного результата Вы не получите - это уж точно  

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

Если же Ваши точки заполняют фигуру более-менее плотно, а отдельностоящих точек нет, алгоритм, по идее должен работать сносно.

Наложить сетку с некоторым шагом на эти точки. Подсчитать число точек попавших в соответствующие ячейки. Получим картинку в градациях серого применить алгоритм для выделения границ. Для выделения границ использовать алгоритм Кэнни или разность Гаусиан.

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

Спасибо за советы!!!
Буду штудировать литературу...Идея про то,чтобы сначала получить картинку в градации серого очень понравилась...
Я все пыталась найте решение в теории графов...
Еще раз спосибо