Алгоритм выбора внешних точек на графе (богатая выпуклая оболочка)

Я не думаю, что есть какие-то стандартные алгоритмы, которые дадут вам то, что вы хотите. Вам придется проявить творческий подход. Предполагая, что ваши точки встроены в двумерное евклидово пространство, вот несколько идей:

1. Итеративно вычислить несколько выпуклых оболочек. Например, вычислить выпуклую оболочку, сохранить точки, являющиеся частью выпуклой оболочки, а затем вычислить другую выпуклую оболочку, игнорируя точки исходной выпуклой оболочки. Продолжайте делать это до тех пор, пока у вас не будет достаточного количества точек, по сути, выщипывая точки по периметру для каждой итерации. Единственная проблема с этим подходом заключается в том, что он не будет хорошо работать для вогнутостей в вашем наборе данных (например, в нижней части вашего образца, который вы разместили).

2. Сопоставьте гауссиан с вашими данными и держите все > N стандартных отклонений от среднего (где N — значение, которое вам нужно выбрать). Это должно работать очень хорошо, если ваши данные являются гауссовыми. Если это не так, вы всегда можете смоделировать его с помощью нескольких гауссиан (вместо одного) и оставить точки с общей вероятностью меньше некоторого порога. Использование нескольких гауссианов, вероятно, позволит прилично обрабатывать вогнутости.
   Ссылки:
   http://en.wikipedia.org/wiki/Gaussian_function
   Как подогнать гауссиану к данным в matlab/octave?\

3. Используйте Оценку плотности ядра. Если вы создаете поверхность плотности ядра, вы можете разрезать поверхность на некоторой высоте (например, превратив ее в плато), получив форму периметра. (форма плато) вокруг точек. Хитрость заключается в том, чтобы разрезать его в нужном месте, потому что вы можете не получить никаких точек за пределами фигуры, но при правильном выборе вы можете легко получить зеленую фигуру, которую нарисовали. Этот подход будет работать хорошо и даст вам зеленую форму в вашем примере, если вы правильно выберете точку среза (что может быть трудно сделать). Большим недостатком этого подхода является то, что он требует больших вычислительных ресурсов. Дополнительная информация: http://en.wikipedia.org/wiki/Multivariate_kernel_density_estimation

4. Используйте альфа-фигуры, чтобы получить общую форму, плотно огибающую внешний периметр набора точек. Затем немного размойте форму, чтобы вытеснить некоторые точки за пределы формы. У меня нет большого опыта работы с альфа-формами, но этот подход также будет довольно затратным в вычислительном отношении. Дополнительная информация: http://doc.cgal.org/latest/Alpha_shapes_2/index.html