Пересечение фигур.

Добры день. Такой вопрос.
Имеется изображение. На нём отрисовано несколько фигур произвольной формы. Должна отрисоваться есчо одна фигура, таким образом, чтобы другие фигуры не пересекала. Тоесть нужно определить факт пересечения фигур. Интересует алгоритм, или хотябы общая модель решения. Спасибо.

 

В данной области не сильно разбираюсь. Но вроде только эвристика.

 

Pavia
Эвристика ?

 

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

 

Заворачивать все фигуры окружность, квадрат нэ? Или проблема в распознавании фигур?

Какая точность у алгоритма должна быть, как хранятся данные, какие данные? С маленькой точность, я уже назвал. Хотите с высокой? Можно пересекающиеся окружности. Все сводится в основном к окружностям или другим примитивам.

Есть принципиально другой способ: анализ "пустого" места. Можно находить его, а потом смотреть, какое место подходит для отрисовки новой фигуры.

Ну еще есть области ИИ, куда лучше не лезть. Хотя, можно настроить простенький перцептрон

Почти все находится в Google

 

qqwe
Найти пространство не занятое фигурами это выполнить заливку ?



На скрине серый фон это свободное пространство. Рисуется есчо одна фигура(синий) и она выходит за пределы этого свободного пространства, что показано красным. Но как определить что фигура выходит за пределы серого ?
Разумеется можно выполнить заливку фона(серый) и заливку вставляемой фигуры(синий), сохранив координаты каждого пикселя, затем выполнить проверку. Этот способ очень не эффективный, хочется более оптимального алго.

 

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

Если необходимо искать именно свободное место, то можно сначала найти сферу "свободного" пространства. Потом рисовать туда. Банальная проверка на суммы радиуса новой сферы с расстоянием от центр оной до центра "свободного" пространства и радиуса "свободного" пространства даст результат о правильности расположения.

С пикселями работать не удобно, поэтому надо уходить от этого. Пиксельное представление изображений - вынужденное зло в угоду полиграфии. Хотя есть и векторные плоттеры, но это дорого и вообще применяется в специфических областях.

 

hivemind
Фигуры совершенно произвольной формы, просто для примера взял окружности.

 

gaeprust
Так в чем проблема? Создал структурку из радиуса и точкой-центром. Описал около своих фигур (структура хранится только в памяти): у тебя готова аппроксимация всех объектов в виде кружков. А потом уже ищешь пересечения между своими окружностями. Сумма радиусов должна быть меньше, чем расстояние между центрами. Метод ошибается в бОльшую сторону, то есть он перестрахуется.

Или вопрос в том, как определить на основе растра его векторное представление? Тогда в Google!

 

Смотрите скрин:

Фигуры совершенно произвольной формы, похоже на амёб. Красным выделено место, где фигуры пересекаются.

 

gaeprust
Тебе обязательно нужно анализ на основе растра делать или можно его сначала оттрассировать, а потом обработать? Тебе скорость или точность нужна. Ссылки на инфу в гугле я уже выложил.

Повторюсь снова, если будешь анализировать растр - получишь систему, которая еле дышит, но с высокой точностью. Будешь делать растр->вектор, а уже работать с векторным представлением, то будешь делать быстро, но не точно. Тебе что надо?

UPD
Можно вообще сделать гибридный метод: помещать свои каракули в прямоугольники, впихивать их в свободные места, с точностью 10%-15%, а потом смотреть, на сколько подвинуть надо прямоугольник, чтобы влезло. И по новому кругу.

Точное задание можно увидеть иначе сложно очень говорить?

 

hivemind
Есть два точечных рисунка. При наложении друг на друга фигуры пересекаются. Нужно определить однозначно факт пересечения фигур. Точность - каждый пиксель.

 

gaeprust
Если задача такая, то дело швах! Способ медленный, но работает с точностью почти 100%. Берем растры. Сверяем массив пикселей. Если какой-нибудь пиксель в обоих массивах не равен пикселю фона - наложение. Значит пересеклись.

Или я не понял задачу?

 

hivemind
Вы предлагаете выполнить заливку двух фигур(или фона, без разницы). Я уже сказал в #6 что это медленно, нужен другой способ.

 

gaeprust
А чем аппроксимирующая трассировка не устраивает? Она однозначно может сказать, что рисунки не пересекаются. Можно даже посчитать вероятность пересечения: берем отношения площади фигуры к описанному векторному представлению и перемножаем. Чем не способ?

Алсо, тут одно из двух, или скорость или точность. Можно, конечно, немного повысить скорость, сделав гибрид между векторной и растровой, отсеев часть изображения с помощью помещения основных фигур в векторные контейнеры путем трассировки растра, но я уже все это писал. Но если важен КАЖДЫЙ пиксель, то будет МЕДЛЕННО

 

hivemind
Очевидно следует рассмотреть вхождение границы фигуры с фоном в область тестируемой фигуры. Каждый пиксель фигура вероятно не нужно рассматривать. А чтоб вычислить площадь фигуры нужна всё таже заливка. Медленно это если каждый пиксель проверять.

 

При таких ограничениях будет медленно в любом случае. Растр не приспособлен для нормальной обработки.

Можно повысить скорость, если предварительно оттрассировать растр в векторы(линии). Но тогда могут появиться ложные сообщения о пересечении. Это если брать чисто векторный способ.

Если брать гибридный, то разбиваем с помощью трассировки не на одну линию, а 10, например. Смотрим, сколько линий из разных фигур пересеклись между собой. Если больше одной, то уже в рамках этого проводим сравнение попиксельно. Выигрыш будет, только если не будут постоянно менять входное изображение, ибо трассировка - тоже время. Обо всем этом я уже писал. Чем не устраивает такой подход?

 

gaeprust
Алсо, покажите код, которым вы "заливаете". Уверен, это можно сделать за один проход и будет вполне быстро!

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

 

hivemind
Не построчная заливка с затравкой

Наверно не будет.Рассмотрим произвольную фигуру:

Серым цветом выделана фигура, белым фон, чёрным - граница фигуры с фоном, назовём её поверхностью. Начнём мысленно описывать поверхность, начиная с точки M двигаясь вниз. Стрелками показано направление(назовём его вектором) описания поверхности в точках её, выделенных жёлтым цветом. Если поверхность описывается некоторой функцией, то вектором будет являться знак проекции касательной на оси X и Y. Таким образом каждая точка функции(поверхности) будет определяться четырьмя координатами: координаты точки на плоскости, тоесть X и Y и двумя векторами, спроецированными на оси X и Y, которые могут принимать только единичные значения(Vx = Sign(dX) и Vy = Sign(dY)).
Можно постулировать, что все точки фигуры, лежащие на одной горизонтальной прямой(ось X) между точками поверхности, в которых вектор принимает значение -dY для левой(Pl) точки поверхности и +dY для правой(Pr) точки поверхности, принадлежат фигуре. Это можно доказать математически, опустим это и теоремы отсюда вытекающие. Рассмотрим пример:
Номер точки. Sign(dYl) Sign(dYr) Принадлежность фигуре.
1 - + Да
2 + - Нет
3 - + Да
4 - + Да
5 + - Нет
6 - + Да
7 - + Да
8 - + Да
9 + - Нет
10 - + Да
11 ? - Нет
12 ? ? Нет
Следствием постулата выше является то, что для определения принадлежности точки P фигуре не нужно рассматривать прилегающие к ней точки, тоесть принадлежность фигуре всего множества точек лежащих на одной прямой определяется только двумя координатами точек границы и двумя векторами в этих точках. Таким образом, можно убрать из рассмотрения все внутренние точки фигуры, оставив только её поверхность. Эта поверхность и описывает всю фигуру, причём вследствие того, что число точек составляющих поверхность фигуры много меньше числа точек составляющих фигуру, то это приводит с значительному ускорению при определении принадлежности точки фигуре.

 

gaeprust

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