Область, которая содержит точки?

Question

Кто-нибудь знает, есть ли алгоритм для этого? У меня есть несколько 2D точек. Мне нужно найти список точек, которые, когда вы рисуете линию от точки n до точки n + 1, вы получаете область, которая содержит все точки. Если бы я мог прикрепить изображение, я мог бы объяснить себя лучше. Заранее спасибо.

Answer 1

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

Answer 2

То, что вы просите, звучит как то, что называется выпуклой оболочкой. Google, что для большого количества информации.

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

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

Answer 3

Если вы кодируете на C / C ++ (или понимаете их), это отличный источник геометрических алгоритмов - и источник, и объяснение.