Внешние граничные точки изображения/фигуры с использованием C#

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

Теперь мой вопрос: как нарисовать точный многоугольник вокруг точек внешнего края? Я использовал алгоритм сканирования Грэма, о котором читал, для создания выпуклой оболочки по краям, но это не помогло. Кажется, это не работает для объектов с вогнутостями. Например:

http://i48.tinypic.com/4s0lna.png

С помощью этого метода изображение слева заполняется изображением справа. Как видите, он слишком много «заполняет».

Я предполагаю, что должен быть какой-то другой алгоритм или подход, который можно использовать для решения этой проблемы, но я не уверен, где искать или как он может называться. Может ли кто-нибудь указать мне в правильном направлении? Я использую C#/.net и надеюсь, что уже существует что-то, что могло бы работать в этом направлении.


c# geometry drawing polygon
person plone    schedule 18.06.2012    source источник
comment
Да, слишком рано нажать Enter, лихорадочно печатая — что за дурак!   -  person plone    schedule 19.06.2012
comment
Это очень распространенная проблема при создании игр и попытках обнаружить столкновения между объектами. Чаще всего это решается с помощью трассировки лучей.   -  person JDB still remembers Monica    schedule 19.06.2012
comment
Я не понимаю. Вы хотите, чтобы ваш многоугольник был ТОЧНЫМ представлением всего, что не является прозрачным (по альфе)? Для чего вы будете это использовать? Это просто для рисования или что-то еще? Могут быть другие (возможно, более простые) способы сделать то, что вам нужно.   -  person Ani    schedule 19.06.2012
comment
@ananthonline да, верно. Как вы можете видеть на изображении, на которое я ссылаюсь, я в основном хотел бы получить «контур» самого венчика и не уверен, как лучше всего это сделать!   -  person plone    schedule 19.06.2012
comment
Как насчет расчета региона oldskool? bobpowell.net/region_from_bitmap.htm. Учитывая, что вам придется переписать структуру региона и некоторые ее методы, но это довольно просто.   -  person Ani    schedule 19.06.2012
comment
Спасибо! Я посмотрел, но, похоже, он дает только ограничивающий прямоугольник, который легко вычислить, даже не используя регион. К сожалению, это все равно оставило бы меня с попыткой подогнать многоугольник к внешним границам объекта :(   -  person plone    schedule 19.06.2012

Ответы (2)


arrow_upward
2
arrow_downward

Я думаю, что алгоритм 2D «Альфа-фигуры» будет для вас правильным выбором.

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_2/Chapter_main.html

Альфа-формы можно рассматривать как обобщение алгоритма "выпуклой оболочки", позволяющего генерировать более общие формы.

Используя альфа-формы, вы сможете контролировать уровень детализации результирующей формы, изменяя значение альфа-параметра.

Вы можете попробовать Java-апплет здесь: http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html

чтобы лучше понять, делает ли этот алгоритм.

person Moustafa Alzantot    schedule 27.10.2012
comment
Недавно я представил реализацию на С# двумерных альфа-форм здесь. - person John Silence; 28.11.2018

arrow_upward
1
arrow_downward

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

Start in the corner, checking that it does have zero alpha.
Check the neighbours for zero alpha and iterate until we have no unchecked neighhours.

Это дает вам маску для изображения, которое будет состоять из двух просто соединенных областей, внутренней и внешней.

Набор, который вы ищете, состоит из:

   all the points in the exterior which are on the boundary of the interior.

Затем вы можете превратить это в многоугольник:

Take an initial polygon that consists of all the points in the edge set
Remove redundant vertices that lie along straight edges.
person Keith    schedule 19.06.2012