Поиск окружностей

← →
QwertyKz © (2006-01-11 19:38) [0]

Доброго времени суток. Имеется такая задача: нужно найти координаты центров 2ух окружностей с определенным диаметром. Какие есть алгоритмы для поиска окружности? Может у кого есть подобные наработки?

← →
Джо © (2006-01-11 19:40) [1]

> Имеется такая задача: нужно найти координаты центров 2ух
> окружностей с определенным диаметром

Это шутка?

← →
QwertyKz © (2006-01-11 19:43) [2]

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

← →
ferr © (2006-01-11 19:49) [3]

а гду хоть слово про картинку?

← →
iZEN_ (2006-01-11 19:51) [4]

Две хорды.
Два срединных перпендикуляра к хордам.
Точка пересечения перпендикуляров — центр окружности.

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

← →
QwertyKz © (2006-01-11 19:52) [5]

> а гду хоть слово про картинку?

Есть черно-белое изображение (BitMap), на нем есть две окружности (одинакового диаметра). Нужно найти координаты этих окружностей
:)

← →
ferr © (2006-01-11 19:57) [6]

а что мешает построить на них квадраты?

← →
QwertyKz © (2006-01-11 20:01) [7]

а что мешает построить на них квадраты?
А подробнее можно :)

← →
Джо © (2006-01-11 20:06) [8]

Ничего не понимаю совершенно? Какие координаты окружностей? Ну, есть радиус, допустим 10 попугаев. Как он может влиять на координаты центра окружности? Я окружность радиусом в 10 попугаев могу разместить где угодно.

← →
ferr © (2006-01-11 20:10) [9]

> А подробнее можно :)

А может тебе лучше поподробнее..

← →
QwertyKz © (2006-01-11 20:17) [10]

> Ничего не понимаю совершенно? Какие координаты окружностей?
> Ну, есть радиус, допустим 10 попугаев. Как он может влиять
> на координаты центра окружности? Я окружность радиусом в
> 10 попугаев могу разместить где угодно.

Чего тут непонятного? Есть два круга, нужно найти координаты центров этих кругов, известен только диаметр каждого круга. И чего тут не ясно :) ?

← →
ferr © (2006-01-11 20:18) [11]

НИЧЕГО не ясно!

P.S. не знаю как другим...

← →
QwertyKz © (2006-01-11 20:19) [12]

> а что мешает построить на них квадраты?

И зачем на них квадраты строить? Что Вы под этим имеет ввиду? Может треугольники построить? ЛОЛ

>
> > А подробнее можно :)
>
> А может тебе лучше поподробнее..

Зачем тогда оставлять "непонятные" ответы?

← →
Kerk © (2006-01-11 20:20) [13]

Да ясно все.
Есть битмап. На нем окружности. Радиус окружностей известен. Надо найти координаты центра этих окружностей на битмапе.

← →
ferr © (2006-01-11 20:20) [14]

какие вопросы, такие и ответы

← →
QwertyKz © (2006-01-11 20:21) [15]

Школа У/O ?

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

← →
QwertyKz © (2006-01-11 20:22) [16]

> Да ясно все.
> Есть битмап. На нем окружности. Радиус окружностей известен.
> Надо найти координаты центра этих окружностей на битмапе.
>

Да :) )

← →
Kerk © (2006-01-11 20:22) [17]

QwertyKz © (11.01.06 20:21) [15]
Школа У/O ?

Не обращай внимания, здесь так принято себя вести.

← →
ferr © (2006-01-11 20:24) [18]

> Не обращай внимания, здесь так принято себя вести.

как?

← →
QwertyKz © (2006-01-11 20:27) [19]

>
> > Не обращай внимания, здесь так принято себя вести.
>
> как?

Как ученик школы У/O

← →
serrrrgggg (2006-01-11 20:28) [20]

Можно пробежаться по изображению маской, соответствующей этим окружностям. Считать совпавшие точки. Два максимума и будут центрами.

← →
Kerk © (2006-01-11 20:28) [21]

Ну хватит оффтопа :)

Не думаю, что сложная задача. Сейчас понимающие тему люди придут и наверно помогут. :)

← →
Джо © (2006-01-11 20:36) [22]

Решение.
Берется листок с рисунком и несется к ближайщему геодезическому пункту с известными координатами. Листок размещается так, чтобы центр окружности совпадал с центром пункта. Смотрим в каталог пунктов и выписываем его координату. Она и будет являться координатами центра окружности.
П.С. Радиус можно не измерять — он бесполезен.
П.П.С. Листик никуда не двигать, иначе координаты центра окружности изменятся.

Задача, поставленная в [0] решена.

← →
QwertyKz © (2006-01-11 20:39) [23]

ГЫ-ГЫ?

← →
ferr © (2006-01-11 20:41) [24]

может так:
найти самую левую, правую, нижнюю и верхнюю точки на битмапе.

П.С. в свете недавно выяснившеяйся "отсканированности", данный способ, не очень подходит.

← →
Джо © (2006-01-11 20:42) [25]

> [23] QwertyKz © (11.01.06 20:39)
> ГЫ-ГЫ?

ГЫ-ГЫ был в [0], до сих пор отсмеяться не могу.

← →
QwertyKz © (2006-01-11 20:48) [26]

Что было, то прошло :) Так что ниукого нет мыслей по этому поводу :( ?

← →
serrrrgggg (2006-01-11 20:49) [27]

> Можно пробежаться по изображению маской, соответствующей
> этим окружностям. Считать совпавшие точки. Два максимума
> и будут центрами.

А вот я и не шутил.

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

← →
begin...end © (2006-01-11 20:57) [28]

> QwertyKz © (11.01.06 20:19) [12]
> QwertyKz © (11.01.06 20:21) [15]

Хам.

> Хам.

Мне все равно... Я задал конеретный вопрос, получил ответ (6), попросил разъяснить, на что сам получил хамство.

Способов много, вот ещё один: находим строку и столбец с наибольшим количеством чёрных точек идущих подряд.

Хотя этот способ также не очень подойдёт для сканированного изображения, но он лучше.

P.S. Я не претендую на то что мои решения хорошо работают или вообще работают, я не разбираюсь в этой области человеческих знаний, но пытаюсь вам помочь. В свою очередь вы задав чёрт знает как свой вопрос, и указав лишь в СЕРЕДИНЕ обсуждения что картинка отсканированная оскорбляете меня. Для вас это нормально?

> Хам.

Лучше бы что-нибудь по теме сказали, а не ХАМили сами. На себя смотреть сначало нужно, а не пальцем тыкать на других

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

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

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

> полокружности не видно к примеру

урра товарищи! новое условие

> ferr © (11.01.06 21:20) [34]
>
> > полокружности не видно к примеру
>
> урра товарищи! новое условие

Мде, читать внимательнее нужно, пост №2

> Мде, читать внимательнее нужно, пост №2

извиняюсь, не заметил.

> serrrrgggg (11.01.06 20:49) [27]

Спасибо, наверное так и буду делать

а чем не нравится?
находим строку и столбец с наибольшим количеством чёрных точек идущих подряд

> ferr © (11.01.06 21:31) [38]
> а чем не нравится?
> находим строку и столбец с наибольшим количеством чёрных
> точек идущих подряд

Тоже спасибо за помощь :)
Долго будет работать ИМХО
Хотя все равно все проверю и более быстрый рабочий вариант возьму :)
Всем спасибо кто ответил

долго? O(2*M*N) = O(M*N) = O(N^2)

Поиск окружностей Найти похожие ветки