Алгоритм реализации инструмента выбора лассо?

Question

Я занимаюсь разработкой приложения для Mac OS X, которое, как часть его пользовательского интерфейса, будет отображать множество визуальных элементов в своем основном виде, которые можно выбрать. Эти элементы могут быть расположены в любом месте в представлении. Пользовательский интерфейс будет поддерживать различные способы выбора элементов: выделение прямоугольной области, выделение эллиптической области и «свободное» выделение лассо.

У меня уже есть выбор прямоугольной и эллиптической области выделения. Алгоритм довольно прост; элемент считается «выбранным», если область элемента пересекается с областью прямоугольника / эллипса.

Выбор лассо будет работать так же, как и в современных приложениях для обработки изображений, таких как Photoshop; пользователь может щелкнуть и перетащить путь, который закроется сам, и элементы, содержащиеся в нарисованном пути, будут выбраны.

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

Заранее спасибо.

Answer 1

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

Вам нужно будет решить, что делать, когда многоугольник пересекает себя (например, рисунок 8).

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

Answer 2

Вы смотрите на точку в проблеме многоугольника: http://en.wikipedia.org/wiki/Point_in_polygon Если вы можете гарантировать, что многоугольник выпуклый (маловероятно), алгоритм упрощается.

Answer 3

Для инструмента лассо от руки вы можете воспользоваться этим очень простым решением: сохранить все точки границы выделения в словаре. С x в качестве ключа и (y1, y2) в качестве значения, где y1 <= y2. Затем переберите все x' и посмотрите, есть ли запись в dict. Если это так, все точки, где x' = x и y >= y1 and y <= y2, находятся в выборе.

Возможно, это не лучшее решение, но оно должно работать.