Xpoint
   [напомнить пароль]

Нахождение вершин многоугольника по внутренней точке

Метки: [без меток]
2006-05-15 00:10:27 [обр] Тимур+[досье]

НАХОЖДЕНИЕ ВЕРШИН МНОГОУГОЛЬНИКА ПО ВНУТРЕННЕЙ ТОЧКЕ
Здравствуйте!
Такой вопрос.

На экране имеются множество закрашенных многоугольников,
при нажатии мышкой на один из этих многоугольников, необходимо
найти его вершины. Многоугольник любой: выпуклый, вогнутый.
Мне нужен принцип решения задачи (экран и мышка не важно),
просто допустим массив точек - закрашенный многоугольник и
по данной точке в многоугольнике найти вершины. Про многоугольник
неизвестно НИЧЕГО.
Буду благодарен за помощь

спустя 1 час 21 минуту [обр] Алексей В. Иванов(3/2861)[досье]
Для начала Вам бы shift на клавиатуре почнить.
-
Что мы имеем? Матрицу NxM пикселей? У них пикселей какие состояния могут быть? 1/0 или полная "палитра"?
Вам зачем, если не серкрет, нужны вершины?
спустя 8 минут [обр] Тимур+[досье]
Имеется Bitmap NxM, многоугольник закрашен одним цветом, по одной из точек этого
многугольника необходимо его найти вершины.
Я пишу программу - карту города N..., есть электронный вариант карты этого города,
только мне я добавляю свои навороты. Рисовать каждый дом долго и нудно,
а так просто тыкнул на дом((многоугольник), и он готов (его вершины записаны в мою базу данных).
Так что?
спустя 9 минут [обр] Алексей В. Иванов(3/2861)[досье]
А после что делать с этими вершинами? Вы так и не ответили.
Простите моё занудство, но не хочется, как часто бывает, тратить своё драгоценное время, ради того, что бы узнать, что было кривое условие и задача решалась на день-два быстрее.
спустя 6 минут [обр] Тимур+[досье]
С этими вершинами я сам дальше разбирусь :)
мне главное их найти.
Так вы знаете как это сделать ?
спустя 1 минуту [обр] Тимур+[досье]
Буду очень признателен
спустя 35 минут [обр] Алексей В. Иванов(3/2861)[досье]
А Вы уверены, что в этом "электронном варианте карты города" дома внесены растровыми картинками?
спустя 10 минут [обр] Евгений Петров(0/1055)[досье]
Эээээ... А что - научились распознавать цвет в любой точке монитора?
спустя 2 минуты [обр] Тимур+[досье]
Какого фига?
спустя 2 минуты [обр] Тимур+[досье]
Не парь мозги, напиши по делу что-нибудь, если сможешь
спустя 7 минут [обр] Евгений Петров(0/1055)[досье]
Вы, дорогой, не грубите, а ответьте на простой вопрос - как распознать цвет на растровой кртинке в месте клика?
спустя 8 часов [обр] Владимир Палант(27/4445)[досье]
! Тимур[досье] получает предупреждение в досье за хамство и неуважительное отношение к участникам форума. Также рекомендую отучиться писать в верхнем регистре — в сети это не приветствуется. Заголовок темы исправлен.
спустя 1 час 22 минуты [обр] Тимур+[досье]
ПОШЛИ НА ХРЕН ВСЕ ДЕМОНЮГИ И ЗАДТРОТЫ!
спустя 27 минут [обр] Даниэль Алиевский(1/125)[досье]
Задача, судя по всему, не очень сложная, из области сканиновария периметра на изображении. Но, конечно, после последней фразы отвечать расхотелось.
спустя 54 секунды [обр] Даниэль Алиевский(1/125)[досье]
Как это меня угораздило? :) "Сканирования", конечно.
спустя 1 час 3 минуты [обр] Тимур+[досье]
Не выпендривайся
спустя 19 минут [обр] Алексей Севрюков(0/1292)[досье]
Три плюса в студию!!! Нафик нам такое счастье здесь.
спустя 1 час 57 минут [обр] Alexander O(17/469)[досье]
Евгений Петров[досье]
> Эээээ... А что - научились распознавать цвет в любой точке монитора?
WinAPI умеет. Но, конечно, для программы-карты это способ, как удаление гланд через задницу
спустя 1 час 31 минуту [обр] 30-ый(0/584)[досье]

Да цвет ерунда. Сама задача по определению углов видится мне не очень простой.

Т.е. для выпуклых многоугольников - вроде все просто.

  1. От точки внути разводим во частям света прямые до пересечения с границей объекта. Получаем набот точек.
  2. По поведению расстояния между парными точками мы сможем найти те, что лежат ближе к краю грани. Соединяем - Получаем набор прямых.
  3. (опционально) С некоторой точностью объединяем прямые. Т.е. если например прямые проходят под углом менее 10% друг к другу - считаем, что это одна прямая.
  4. Теперь находим точки пересечения прямых - многоугольник готов.

Теперь что делать с вогнутыми?
- При анализе расстояния между парными точками на этапе 2 надо искать неестественные всплески. Т.е. неожиданно большое расстояние между парами. Тут вероятно есть грань не попавшая в расчет (была в тени другой грани)
- Эти две точки соединяем отрезком и его середину рекурсивно прогоняем через алгоритм еще раз.
- Посмею утверждать, что так мы найдем все прямые в составе многоугольника.

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

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

В общем - работы на добрую неделю, плюс еще неделя чтения учебника по аналитической геометрии.

спустя 33 минуты [обр] 30-ый(0/584)[досье]

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

В общем я наверное погорячился с неделей... тут больше работы.

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

спустя 27 минут [обр] Thirteensmay(0/157)[досье]
А может проcто загнать в векторизатор ?
спустя 9 минут [обр] Тимур+[досье]

Спасибо за идеи!
Я, кажется, нашел решение.

Допустип, вогнутый многоугольник.
Находим все точки, принадлежащие граням. Это можно сделать
простым перебором: многоугольник находится в Bitmap-е,
прохожу по каждой строке битмепа, если цвет меняется от цвета
окружающей среды на любой другой или, наоборот, с любого цвета на цвет окружающей, значит
в этом месте находится грань (ребро).
У нас теперь есть массив точек, принадлежащих только ребрам.

Далее, берем из массива какую-нибудь точку, затем еще одну,
немного удаленную от первой, предполагая, что они принадлежат одной прямой.
По этим двум точкам вычисляем уравнение прямой вида y=kx+b. Пробегаем
по всему массиву и отбираем тольчко те точки, которые удовлетворяют этому уравнению.
Получается массив точек, принадлежащих одному из ребер многоугольника.
Но может быть и такая ситуация, когда те две точки для вычисления уравнения прямой были выбраны неправильно,

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

Ну и потом находим крайние точки полученной прямой, а это и есть две вершины. И так со всеми точками массива.

спустя 1 час 29 минут [обр] Даниэль Алиевский(1/125)[досье]

Ну-ну... Это же нарисованный прямоугольник. Ну какие там уравнения прямой? Там алгоритм Брезенхема, в лучшем случае (если прямоугольник именно нарисован на bitmap, а, скажем, не отсканирован). Решение задачи - это некоторая задача оптимизации на множестве точек периметра, да и то при условии, что можно точно найти все пограничные пикселы "нарисованного дома". Если нельзя, то задача сложнее, а решение требует уточнения условий.

И все-таки, мне кажется, тему надо удалить как противоречащую правилам форума. Фраза, гм, "ПОШЛИ НА ХРЕН ВСЕ ДЕМОНЮГИ И ЗАДТРОТЫ!", не может расцениваться как вежливая просьба о помощи.

спустя 42 минуты [обр] 30-ый(0/584)[досье]

Тимур[досье], все не так просто. Если вы будете брать соседние точки, что у вас получится только четыре типа прямых. А именно вверх, вбок и две диагонали. Маловероятно, что вас устоит подобный результат.

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

Тут правда есть еще один подводный камень. Если прямые пересекаются под очень плоским углом (т.н. дом-книжка), понять где заканчивается одна прямая и начинается другая будет не просто. Как следствие - найденную вершину не сможете использовать как отправную точку для следующей грани. Иначе рискуете довольно сильно промахнуться. Этот промах даст погрешность при следующем поиске и так весь дом разъедется. Т.е. после нахождения прямых вам таки придется решать систему уравнений для нахождения точки пересечения.

Теперь главное. Этот метод будет работать только если у вас все отрезки контрастные и резкие. Если картинка отресайзена или сохранена в JPEG, вы не сможете найти грань вашим методом. Тут придется вернуться к моему решению и вести из центра линии наружу. Проверять вдоль линии яркость точек и фиксировать грань на экстреммуме яркости (темности).

спустя 17 минут [обр] 30-ый(0/584)[досье]

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

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

спустя 4 минуты [обр] Тимур+[досье]
Всымсле, с заданными вершинами (на счет скрытия невидимых граней) ?
спустя 14 минут [обр] 30-ый(0/584)[досье]

Не очень понял вопроса. Эта была классическая задача по скрытию невидимых граней в трехмерном пространстве. Эта задача прекрасно решалась еще на 40-а мегагерцовом 386DX, я у меня тормозила на 166-ом пентиуме. Я привел этот пример к тому, что о производительности тут надо думать сразу иначе можно поплатится полной переделкой алгоритма.

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

спустя 6 минут [обр] Тимур+[досье]
А вообще на каком языке программируешь ?
Давно занимаешься?
спустя 1 минуту [обр] Тимур+[досье]
icq 258-646-675
спустя 3 часа 25 минут [обр] Тимур+[досье]
Что это значит ?
спустя 8 часов [обр] Даниэль Алиевский(1/125)[досье]
30-ый[досье] Я занимался. Один прямоугольный или многоугольный объект можно распознать практически мгновенно, даже если использовать "тяжелые" переборные алгоритмы.
спустя 6 часов [обр] Владимир Палант(27/4445)[досье]
! Тимур[досье]
Предупреждение делаю плюсом, чтобы вас теперь было видно издалека. Если вы и сейчас не поймете, что на этом форуме принят вежливый стиль общения — забаним.
спустя 1 час 54 минуты [обр] Николай Бубело(0/113)[досье]

Задача, собственно, разделяется на две:

  1. Построение контура многоугольника.
  2. Определение вершин.

На возможные сложности при решении первой задачи уже указал 30-ый[досье].
Ее решение будет сильно зависеть от исходных битмапов. В любом случае, для того, чтобы определить, какие, возможно, будут необходимы методы фильтрации и/или сглаживания — нужно увидеть исходный материал. Впрочем, в благоприятном случае алгоритм будет несложным — он будет аналогичен простейшим алгоритмам заливки типа Paint-овского.

Предположим, однако, что мы построили хороший и "правильный" контур нашего многоугольника.
А дальше на него можно посмотреть немного по-другому — не как на множество точек, а как на множество векторов, соединяющих точки, представленные пикселами на контуре. Каждый вектор будет иметь наклон к любой из координатных осей прямоугольной системы координат, кратный 45 градусам. И, далее, если мы начнем обходить контур по этим мини-векторам, то нам достаточно анализировать — на какой угол изменил свое направление следующий вектор относительно предыдущего. Если изменил на значение более, чем 45 градусов (90 или 135) — то это и есть вершина.
Сразу видно, что такой алгоритм найдет только острые и прямые углы. Тупые углы (а также "закругленные") он не найдет. Однако, после первого прохода можно применить следующую итерацию: объединить каждую пару начального множества векторов в один (попросту сложить попарно эти вектора), и пройтись по новому контуру. При этом проходе проверять: если следующий вектор изменил свое направление относительно предыдущего на более, чем 22.5 градуса — мы нашли очередной угол (правда, с бОльшей погрешностью, чем на первом проходе). При этом будут найдены те углы, которые меньше или равны 135 градусов. Аналогичные итерации можно повторять и дальше.

Обшая идея, надеюсь, ясна.
Сам алгоритм, конечно, нуждается в доводке и "рихтовке" (особенно, если еще и попытаться минимизировать погрешности в определении "тупоугольных" вершин, увеличивающиеся на каждом шаге итерации; плюс, обязательно надо исключить возможность "повторного" определения вершины, уже найденной на предыдущих итерациях), но у него, как мне кажется, есть определенные достоинства. Исхитрившись, я думаю, что его можно запрограммировать без использования операций с плавающей запятой, т.е., он достаточно экономичен. Плюс к этому — сможет находить и "закругленные" углы.

В общем, дерзайте!

спустя 17 минут [обр] 30-ый(0/584)[досье]

Николай Бубело[досье] в вашем алгоритме есть все тот же недостаток, что и в методе автора. Все будет работать только из предположения качественной картинки. Попробуйте нарисовать многоугольник и сделать ему четырехкратное уменьшение. А потом попробуйте подобрать параметры заливки так, чтобы у вас хотя бы просто рукой и естественным интеллектом удалось четко нарисовать контур по контуру заливки. Там с очень большой вероятностью будут очень "рваные" края.

Таким образом я настаиваю, что в общем случае обе части должны решаться одновременно. И никакого попиксельного анализа. Пикселы должны сканироваться только группой вдоль прямой и только для нахождения экстреммума яркости. Отдельные пиксеры не должны играть роли в расчете.

спустя 1 минуту [обр] Алексей В. Иванов(3/2861)[досье]
Не понимаю.
Какого фига, господа?
Вас говном какой-то "прыщавый подросток" поливает, а вы еще и помогаете?
спустя 16 минут [обр] 30-ый(0/584)[досье]

Алексей В. Иванов[досье], Даниэль Алиевский[досье], Евгений Петров[досье], Владимир Палант[досье] и все-все-все. Я вижу тут ждут моего ответа.

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

Кроме всего прочего вы ведете себя просто отвратительно. Пересмотрите первые реплике. Мы там видем желание помочь - если бы! Там у нас фразы типа "а вы уверены, что это надо", "а неужели у вас получится", "а с каких это пор это технически возможно", "а зачем вам вообще понадобилось". И это несмотря на несколько вежливых просьб писать по существу! Если мне кто-нибудь скажет, что это сильно приличнее, чем назвать всех "демонюгами" - я не поверю!

Стыдно, господа. Просто стыдно!

спустя 22 минуты [обр] Николай Бубело(0/113)[досье]

30-ый[досье], дык, я ж сразу оговорился, что алгоритм применим лишь при наличии определенных исходных условий:

 Предположим, однако, что мы построили хороший и "правильный" контур нашего многоугольника...

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

Алексей В. Иванов[досье], "подросток" сам по себе неинтересен. Интересен вопрос. Как сказал 30-ый[досье],

 Мне интересно обсудить интересную проблему с умными людьми.
спустя 14 часов [обр] Старынин Валерий(0/57)[досье]

Николай Бубело[досье] В начале было сказано вот так:

есть электронный вариант карты этого города

т.е. картинка, по идее, будет качественная.
Тимур[досье] Не могу сказать точно, но может быть быстрее разобрать старую программу и вытянуть данные из нее?

спустя 17 минут [обр] Тимур+[досье]
параллельно работаю над этим вопросом...
спустя 4 часа 47 минут [обр] Даниэль Алиевский(1/125)[досье]

30-ый[досье] Ладно, допустим. Вам я отвечу с удовольствием. Хотя вроде бы Ваш упрек в некрасивых фразах ко мне не очень относится.

Рассмотренная задача - одна из тех, которыми я занимаюсь по роду деятельности.

Я бы сделал так.

Будем исходить из сравнительно скромного предположения, что объект "дом" мы выделить, в принципе, можем - т.е. найти все его точки. (Иначе говоря, пикселы дома заметно отличаются по яркости/цвету от пикселов за его пределами.) Предположение, вообще-то, не обязательное, но полезное для получения большей скорости и надежности.

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

Введем некоторую "функцию качества", определенную на множестве всех прямых ax+by=d, где a=cos(fi), b=sin(fi). Иначе говоря, прямая описывается направлением своей нормали (угол fi) и расстоянием до начала координат (d). Обозначим функцию качества q(fi,d). Для каждой прямой (fi,d) рассмотрим отрезок L(fi,d), получающийся в пересечении этой прямой и найденного нами объекта "дом" (предположительно известного нам множества пикселов).

Будем придумывать функцию качества так, чтобы она была тем больше, чем лучше соответствующий отрезок L(fi,d) "похож" на стену дома. Так, если прямая вовсе не пересекает дом, q(fi,d) = минус_бесконечность. А если пересекает, то вариантов много. Я бы начал с процентили всех поперечных градиентов на отрезке L. Т.е. прошелся бы по всем точкам отрезка с шагом step (1-2 пиксела, возможно, больше, если картинка очень крупномасштабная), взял бы для каждой точки отрезка яркости b1 и b2 двух пикселов на исходной картинке, расположенных по разные стороны от прямой L на небольшом расстоянии delta от данной точки, вычислил бы модуль разности |b1-b2| - "градиент", и затем в массиве всех найденных градиентов взял бы, скажем, процентиль 10% или 20% (ведь на настоящей границе дома большинство точек будут обладать большим поперечным градиентом). Естественно, функцию качества надо подбирать в зависимости от картинки.

Затем будем перебирать, с некоторым шагом, все возможные fi и d, при которых прямая пересекает дом, и вычислять для каждой пары функцию качества q(fi,d). Шаг по fi можно выбрать, допустим, 2 градуса, шаг по d - порядка 0.01 общих "габаритов" дома - итого порядка 20 тысяч вариантов. Проанализировав набор полученных пар (fi,d), выберем среди них достаточно качественные локальные максимумы - т.е. такие отрезки L, на которых функция качества высока и при этом лучше всех "смежных" (fi,d). Более того, можно предварительно для каждой пары (fi,d) выполнить, уже с меньшими шагами, покоординатный подъем к ближайшему локальному максимуму q(fi,d) - это позволит обойтись менее "густой" сеткой пар (fi,d), т.е. перебирать их с более крупным шагом. Все это можно проделать почти мгновенно - ведь расчет одной функции качества, на нормальном Pentium с частотой несколько гигагерц, займет считанные микросекунды.

Найденные локальные максимумы, очевидно, соответствуют стенам дома - точнее, любым длинным прямым участкам с большими поперечными градиентами. Остаются детали. В идеали мы найдем стены и только стены, а точки пересечения будут углами дома. Но если будут ложные срабатывания (чересчур сложная и некачественная карта) - можно добавить дополнительную эмпирическую информацию. Скажем, у каждой прямой должна быть параллельная ей - локальные максимумы, не удовлетворяющие этому критерию, можно сразу отбросить. И т.п.

спустя 3 дня [обр] Danechka[досье]
"безотносительно к", но спасибо за обсуждение
у меня хоть и не настолько нечеткая задача, но это обсуждение подвигло на правильные мысли.
еще раз спасибо
Powered by POEM™ Engine Copyright © 2002-2005