Алгоритм для реализации инструмента выбора лассо?
Я разрабатываю приложение Mac OS X, которое, как часть он - UI, отобразит много визуальных элементов в, он - основное представление, которое может быть выбрано. Эти элементы могут быть расположены действительно где угодно в рамках представления. UI будет поддерживать различные способы выбрать элементы: прямоугольный выбор пунктирной рамки, эллиптический выбор пунктирной рамки и 'бесплатный' выбор лассо.
У меня уже есть прямоугольная и эллиптическая работа выбора пунктирной рамки. Алгоритм довольно прост; элемент считают 'выбранным', если область элемента пересекается с областью прямоугольника/эллипса.
Выбор лассо будет работать, как он делает в современных приложениях обработки изображения как Photoshop; пользователь может перетащить путь, который закроет себя, и элементы, содержавшие в оттянутом пути, будут выбраны.
Этот алгоритм, вероятно, будет намного более сложным, чем прямоугольный/эллиптический выбор, так как форма выбора неограниченна. Я задаюсь вопросом, есть ли у кого-либо опыт при записи чего-то вроде этого, или если можно указать на меня в правильном направлении относительно того, какие методы программирования необходимы, и что является самым эффективным способом, которым может работать этот алгоритм.
Заранее спасибо.
2 ответа
Единственный способ, который я могу придумать, это относиться к контуру лассо как к многоугольнику. Затем вы можете использовать любой стандартный тест point-inside-polygon , чтобы проверить, какие элементы выбрать.
Вы должны будете принять решение, что делать, когда полигон пересекается сам с собой (например, рисунок 8).
При построении полигона, чтобы он не получил слишком много точек, может быть, вы можете пропустить точки, которые слишком близки к предыдущей точке (может быть, 3 пиксела или около того, в зависимости от вашего приложения).
Вы смотрите на точку в проблеме полигона: http://en.wikipedia.org/wiki/Point_in_polygon Если вы можете гарантировать, что многоугольник выпуклый (маловероятно), алгоритм становится более простым.