Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Точки пересечения окружностей, алгоритм / 25 сообщений из 30, страница 1 из 2
  1  все
20.11.2009, 13:09
    #36322126
reZFedor
reZFedor
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
Добрый день.

Нашел по гуглу
www.gamedev.ru, cNoNimВообще все такие вумники..
чел хочет найти точки пересечения а не столкнулись или нет...
а там звиняйте меня все сводится к квадратному уровнению... :)
все знают такие?
берем уравнения двух окружностей
{(x + a1)^2+(у+b1)^2=r1^2;(1)
{(x + a2)^2+(у+b2)^2=r2^2;(2)
решаем систему в (1) выражаем y через x
y=sqrt(r1^2-(x + a1)^2)/a1;(3)
подставляем в (2)
(x + a2)^2+(sqrt(r1^2-(x + a1)^2)/a1+b2)^2=r2^2
решаем это простенькое уровнение :) и все окей находи x их может быть либо 0 либо 1 либо 2 либо infinity
подставляем в (3) и все ОК
Если я неправильно не понял, то a1 и b1 это координаты центра окружности.
Или все же не все же?

Заранее спасиб за коммент
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.11.2009, 13:32
    #36322192
reZFedor
reZFedor
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
reZFedorДобрый день...
...решаем систему в (1) выражаем y через x
y=sqrt(r1^2-(x + a1)^2)/a1;(3)...
Чета мне плоха(
А разве из
(x + a1)^2+(у+b1)^2=r1^2
не
y=sqrt(r1^2-(x + a1)^2)-b1
получится???
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.11.2009, 13:46
    #36322248
алчность
алчность
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
неправильно , там должна быть разность
(x-a), (y-b),

a и b -координаты центра. Теорема Пифагора
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.11.2009, 13:49
    #36322257
reZFedor
reZFedor
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
Я чота совсем заболель)
Даже если я выражу x, мне один хрен в коные решать квадратное уравнений, есс?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.11.2009, 14:20
    #36322355
reZFedor
reZFedor
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
алчностьнеправильно , там должна быть разность
(x-a), (y-b),

a и b -координаты центра. Теорема Пифагора
Т.е.
Код: plaintext
1.
(x - a1)^ 2  + (у - b1)^ 2 =r1^ 2 
(x - a2)^ 2  + (у - b2)^ 2 =r2^ 2
?
Ок, тогда начинаем выражать из первого уравнения y
Код: plaintext
1.
2.
(у - b1)^ 2 =r1^ 2  - (x - a1)^ 2 
у - b1=sqrt(r1^ 2  - (x - a1)^ 2 )
y=sqrt(r1^ 2  - (x - a1)^ 2 ) + b1
Прально?
Далее подставляем вместо y во второе
Код: plaintext
(x - a2)^ 2  + (sqrt(r1^ 2  - (x - a1)^ 2 ) + b1 - b2)^ 2 =r2^ 2
вот теперь ваааааще жопа)
Тперь че, надо из этого долго и нуууудно x выразить???!!!!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.11.2009, 14:29
    #36322380
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
Для начала нужно сесть с бумагой и ручкой и покумекать, а какие собсно решения существуют.

1) Нет решений. Радиусы в сумме дают меньшее расстояние чем расстояние между центрами или одна окружность находится "внутри" другой. Тривиально.
2) Бесконечное число решений. Окружности совпадают по всем параметрам. Тривиально.
3) Одно решение. Окружности касаются одной точкой. Тривиально.
4) Два решения. Находим характеристики равнобедренных треугольников, образованных радиусами и центрами. Здесь могу ошибаться, но по моему здесь всё находится без уравнений 2 степени.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.11.2009, 14:52
    #36322452
reZFedor
reZFedor
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
maytonДля начала нужно сесть с бумагой и ручкой и покумекать, а какие собсно решения существуют.

1) Нет решений. Радиусы в сумме дают меньшее расстояние чем расстояние между центрами или одна окружность находится "внутри" другой. Тривиально.
2) Бесконечное число решений. Окружности совпадают по всем параметрам. Тривиально.
3) Одно решение. Окружности касаются одной точкой. Тривиально.
4) Два решения. Находим характеристики равнобедренных треугольников, образованных радиусами и центрами. Здесь могу ошибаться, но по моему здесь всё находится без уравнений 2 степени.
Вот и щас наше решение более построительное, по крайней мерее без дискриминантов.
Потестю выложу
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.11.2009, 15:37
    #36322630
reZFedor
reZFedor
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
Вот чо нашел
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
Пусть нужно найти пару точек P3 пересечения, если они существуют.

Для начала найдем расстояние между центрами окружностей. d = || P1 - P0 ||. Если d > r0 + r1, тогда решений нет: круги лежат отдельно. Аналогично в случае d < || r0 - r1 || - тогда нет решений, так как одна окружность находится внутри другой.

Рассмотрим два треугольника P0P2P3 и P1P2P3. Имеем

a^ 2  + h^ 2  = r0^ 2  and b^ 2  + h^ 2  = r1^ 2 

Используя равенство d = a + b, мы можем разрешить относительно a:

a = (r0^ 2  - r1^ 2  + d^ 2  ) / ( 2  d)

В случае соприкосновения окружностей, это, очевидно, превратится в r0, так как: d = r0 + r1

Решим относительно h, подставив в первое уравнение h^ 2  = r0^ 2  - a^ 2 
Итак,

P2 = P0 + a ( P1 - P0 ) / d

Таким образом, получаем координаты точек P3 = (x3,y3):

x3 = x2 +- h ( y1 - y0 ) / d

y3 = y2 -+ h ( x1 - x0 ) / d
Рисунов внизу
Но тока вот на
Код: plaintext
Решим относительно h, подставив в первое уравнение h^ 2  = r0^ 2  - a^ 2
у меня мягко говоря засада.
Обясните мне глупому, как всетаки выразить h?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.11.2009, 15:43
    #36322652
reZFedor
reZFedor
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
Или рассчитать сначала a, а уж потом в h^2 = r0^2 - a^2 засовывать?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.11.2009, 17:26
    #36323078
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
человек! я надеюсь ты в школе учился и эта достаточно простая геометрическая задачка не вызывает у тебя вопросов или ты откровенно стебешься.

4 8 15 16 23 42
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.11.2009, 17:53
    #36323151
Nixxx
Nixxx
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
Ёперный театр, я тоже надеюсь что это стёб)))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.11.2009, 14:12
    #36323788
reZFedor
reZFedor
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
NixxxЁперный театр, я тоже надеюсь что это стёб)))
Харош, может веть человек запарится, когда спрашивал честно о другом думал
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.11.2009, 14:25
    #36323797
reZFedor
reZFedor
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
Aklinчеловек! я надеюсь ты в школе учился и эта достаточно простая геометрическая задачка не вызывает у тебя вопросов или ты откровенно стебешься.

4 8 15 16 23 42
Ты конечно извини, но твои оскорбительные и ненаполненные смыслом посты меня порядком подъза..ли. Если ты считаешь, что реализация кодом решения системы уравнений
Код: plaintext
1.
(x - a1)^ 2  + (у - b1)^ 2 =r1^ 2 
(x - a2)^ 2  + (у - b2)^ 2 =r2^ 2
это детские забавы, то напиши решение. Поверь я им пользоватся не буду, так как выяснилось что мне больше подходит решение которое я описал ниже. Если же ответа от тебя не последует, то мне не остается ничего, кроме как сделать вывод о твоей завышенной самооценке и призрении к менее опытным людям. Также при отсутствии ответа на данный вопрос, и при появлении твоих коментариев хотябы еще на один мой пост, мне придется обратится к модератору с просьбой оградить меня (или данную ветку) от твоего присутствия. Я не стукач и не дятел, просто нет возможности поговорить с тобой при личной встрече и возможно убедится что я в тебе ошибаюсь, а твои выражения в мой адрес меня просто бесят, потому как я привык к контсруктивной критике, а не к словам "я надеюсь ты в школе учился" и "эта достаточно простая геометрическая задачка..."
Я действительно жду твоего ответа.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.11.2009, 19:57
    #36326924
Slip
Slip
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
reZFedor...реализация кодом решения системы уравнений
Код: plaintext
1.
(x - a1)^ 2  + (у - b1)^ 2 =r1^ 2 
(x - a2)^ 2  + (у - b2)^ 2 =r2^ 2
это детские забавы...
конечно, детские забавы;) вычесть из первого ур-я второе, получится линейная связь x и y, выразить из нее то, что выражается, да и подставить в первое уравнение. получится квадратное ур-е на x или на y (смотря что выразил). решаем его, находим координаты точек пересечения (ну, или убеждаемся, что их нет). находим вторые координаты точек пересечения из линейной связи. вот и вся задачища;)))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.11.2009, 19:59
    #36326927
Slip
Slip
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
а Alkin прав про школу.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
24.11.2009, 10:46
    #36327677
reZFedor
reZFedor
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
Slip...вычесть из первого ур-я второе, получится линейная связь x и y, выразить из нее то, что выражается, да и подставить в первое уравнение. получится квадратное ур-е на x или на y (смотря что выразил). решаем его, находим координаты точек пересечения (ну, или убеждаемся, что их нет). находим вторые координаты точек пересечения из линейной связи...
Спасибо, хоть мне это уже и не надо, сам не допер
Slipа Alkin прав про школу.
А я прав в том, что твой пост, в отличии от его поста это помощь, а не сарказм и насмешки, и сли бы я действительно хотел "откровенно постебаться", то зашел бы на соответсетвующий ресурс.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
01.08.2016, 03:32
    #39283589
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
Для двух окружностей все довольно просто. А если у нас есть 20 окружностей, как на практике решают подобные задачи? В голову приходит только метод Монте-Карло, но он ресурсоёмок
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.08.2016, 04:26
    #39283592
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
И если не ошибаюсь, с помощью Монте-Карло мы найдем только площадь пересечения n окружностей, а не какие-то конкретные координаты
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.08.2016, 04:59
    #39283594
m_Sla
m_Sla
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
SashaMercuryДля двух окружностей все довольно просто. А если у нас есть 20 окружностей, как на практике решают подобные задачи? В голову приходит только метод Монте-Карло, но он ресурсоёмок1) находим точки пересечения для 2-х окружностей
2) проверяем лежат ли найденные точки на оставшихся 18 окружностях
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.08.2016, 06:05
    #39283601
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
m_SlaSashaMercuryДля двух окружностей все довольно просто. А если у нас есть 20 окружностей, как на практике решают подобные задачи? В голову приходит только метод Монте-Карло, но он ресурсоёмок1) находим точки пересечения для 2-х окружностей
2) проверяем лежат ли найденные точки на оставшихся 18 окружностях

Я говорю об области пересечения, а не об одной точке. Но даже если бы точка пересечения была бы единственной, не всё было бы так просто
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.08.2016, 10:13
    #39283668
kealon(Ruslan)
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
SashaMercury,
очень сложно понять что ты хочешь
если точка принадлежит нескольким окружностям, то вполне очевидно, что она входит в область их пересечения
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.08.2016, 10:22
    #39283675
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
Берем первую, находим по очереди ее пересечения с 19-ю остальными, 2-ю с 18-ю и т.д.
В итоге (N -1)*(N-2) сравнений.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.08.2016, 10:23
    #39283676
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
С новым годом друзья.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.08.2016, 10:38
    #39283686
Изопропил
Изопропил
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
хороший конь, сферический.

а почему в R 2 ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.08.2016, 14:08
    #39283927
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Точки пересечения окружностей, алгоритм
Dima TБерем первую, находим по очереди ее пересечения с 19-ю остальными, 2-ю с 18-ю и т.д.
В итоге (N -1)*(N-2) сравнений.

Дело в том, что 20 окружностей могут вовсе не пересекаться в одной точке. Мне нужно каким-то образом получить область пересечения (пусть нам заранее известно, что 20 окружностей имеют таковую)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Точки пересечения окружностей, алгоритм / 25 сообщений из 30, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]