Подгонка максимально выпуклой оболочки к внутренней части набора точек

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

Я искал совсем немного и не нашел решения. Заранее спасибо.


geometry curve-fitting convex-hull
person Mark Allen Neil    schedule 01.05.2013    source источник
comment
Не могли бы вы опубликовать пример или два того, как могут выглядеть точки?   -  person Nuclearman    schedule 02.05.2013
comment
Вы можете посмотреть граф Габриэля. По крайней мере, это должно быть в состоянии ограничить вас наиболее важными краями. Если вы ответите на приведенный выше вопрос, я, вероятно, смогу расширить его до ответа.   -  person Nuclearman    schedule 02.05.2013
comment
Я разместил изображение для справки - оно не совсем то, что я описал, но похоже достаточно. В итоге я не использовал альфа-формы, так как связь между точками зависит от выбранной альфы. Слишком маленькая альфа может не закрывать форму. Слишком большая альфа будет исключать действительные точки. В итоге я замаскировал данные, которые мне не нужны, умножив их на кольцевую маску, отразив точки на внешнем краю кольца, подогнав выпуклую оболочку, а затем снова отразив эту выпуклую оболочку вокруг кольцевого кольца. Работает отлично.   -  person Mark Allen Neil    schedule 04.05.2013
comment
Ах, это наихудший случай, который я мог придумать для чего-то подобного. Я бы предложил другой подход, но если я что-то не упустил, то мой вариант не будет более эффективным (O(N log N)). Кроме того, возможно, это не дало именно то, что вы ищете. Тем не менее, вы можете рассмотреть возможность ответа на свой вопрос с более подробным объяснением вашего подхода, поскольку это может быть полезно для других.   -  person Nuclearman    schedule 06.05.2013

Ответы (1)


arrow_upward
0
arrow_downward

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

Теория была разработана Эдельбруннером. Это хорошее начало: http://www.mpi-inf.mpg.de/~jgiesen/tch/sem06/Celikik.pdf

Для расчета необходимо: вычислить триангуляцию Делоне и/или диаграмму Вороного, затем выбрать точки, удовлетворяющие одному условию.

Пример альфа-формы:

введите здесь описание изображения

На самом деле это вогнутая оболочка, и она может игнорировать выбросы.

person kiriloff    schedule 01.05.2013
comment
Не совсем то, что я искал, но я смог использовать эту стратегию, чтобы получить что-то достаточно близкое к тому, что мне нужно. Большое спасибо за то, что направили меня в этом направлении. Я нашел следующий веб-сайт действительно бесценным для понимания альфа-форм - апплет Java показывает вам, как все работает довольно хорошо. cgm.cs.mcgill.ca/~godfried/teaching/ проекты97/белэр/ - person Mark Allen Neil; 02.05.2013