|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
04.10.2007, 09:14
|
#1
|
☭
Регистрация: 26.09.2006
Сообщений: 6,035
Написано 1,474 полезных сообщений (для 2,707 пользователей)
|
Геометрия
Все в рисунке.
|
(Offline)
|
|
04.10.2007, 17:29
|
#2
|
|
Re: Геометрия
1) ищем точки пересечения отрезка с окружностью
в инете куча мануалов - поискать думаю не составит труда
получаем точки A и B
случаи когда тока одна точка или их нет - отпадают
2) берем середину AB
и ещем ближайшую точку на кругу к полученой точки
точка на кругу = X
|
|
|
04.10.2007, 18:12
|
#3
|
Модератор
Регистрация: 13.09.2005
Сообщений: 1,835
Написано 6 полезных сообщений (для 10 пользователей)
|
Re: Геометрия
1) по известным данным легко пишутся уровнения отрезка и окружности.
получаем систему из 2-ух уровнений.
находим точки пересечения Х1 и Х2(расматриваем тока случай с 2-мя точками, остальные варианты очевидны).
2) берём середину (S) отрезка образованного точками Х1 и Х2.
середина и центр окружности составляют прямую.
3) пересечение этой прямой с окружностью (аналогично действию номер 1) даст 2 точки.
ближняя точка к S и будет ответом.
|
(Offline)
|
|
04.10.2007, 23:44
|
#4
|
Элита
Регистрация: 02.10.2005
Сообщений: 1,789
Написано 132 полезных сообщений (для 252 пользователей)
|
Re: Геометрия
хух, ну и слава богу, а то я уж думал свое извращение предложить
|
(Offline)
|
|
05.10.2007, 00:08
|
#5
|
☭
Регистрация: 26.09.2006
Сообщений: 6,035
Написано 1,474 полезных сообщений (для 2,707 пользователей)
|
Re: Геометрия
ZanoZa, предложи.
а то я чо то все равно ничо не понял.
надо максимальное быстродейтсвие.
у меня идея такая, как-нибудь (не знаю я) надо найти точку - пересечения линии и ее нормали к центру.
если ее найти, то решив несложную пропорцию найдем ту точку.
|
(Offline)
|
|
05.10.2007, 00:18
|
#6
|
Элита
Регистрация: 02.10.2005
Сообщений: 1,789
Написано 132 полезных сообщений (для 252 пользователей)
|
Re: Геометрия
пересечение нормали( к прямой), и самой прямой?
|
(Offline)
|
|
05.10.2007, 00:38
|
#7
|
☭
Регистрация: 26.09.2006
Сообщений: 6,035
Написано 1,474 полезных сообщений (для 2,707 пользователей)
|
Re: Геометрия
0x01
|
(Offline)
|
|
05.10.2007, 00:43
|
#8
|
Знающий
Регистрация: 12.07.2006
Сообщений: 283
Написано 16 полезных сообщений (для 32 пользователей)
|
Re: Геометрия
http://algolist.ru/maths/geom/ - думаю будет полезно.
Могу предложить как вариант: построить уравнение окружности и отрезка, и с помощью обычных формул всё находится. Как быстро это будет работать - хз
|
(Offline)
|
|
05.10.2007, 01:25
|
#9
|
Модератор
Регистрация: 13.09.2005
Сообщений: 1,835
Написано 6 полезных сообщений (для 10 пользователей)
|
Re: Геометрия
Сообщение от alex-mad
1) по известным данным легко пишутся уровнения отрезка и окружности получаем систему из 2-ух уровнений.
находим точки пересечения Х1 и Х2(расматриваем тока случай с 2-мя точками, остальные варианты очевидны).
2) берём середину (S) отрезка образованного точками Х1 и Х2.
середина и центр окружности составляют прямую.
3) пересечение этой прямой с окружностью (аналогично действию номер 1) даст 2 точки.
ближняя точка к S и будет ответом.
|
HolyDel, ты сказал что пересечение находить можешь, следовательно знаешь точки Х1 и Х2.
координаты точки S определить не составит труда.
2 точки описывают прямую, и опять же нужно найти пересечение прямой и окружности (это ты умеешь).
из 2-ух точек определить ближнюю тоже не сложно.
это я к тому что это типичное задание по школьной геометрии и алгоритм я предоставил самый примитивный и доступный пониманию
|
(Offline)
|
|
07.10.2007, 11:28
|
#10
|
Элита
Регистрация: 02.10.2005
Сообщений: 1,789
Написано 132 полезных сообщений (для 252 пользователей)
|
Re: Геометрия
а пересечение x1x2 с OX чисто математически находите, или графически, или уравнение OX известно?
если математически то дайте алгоритм посмотреть, а то интересно очень.
|
(Offline)
|
|
07.10.2007, 18:03
|
#11
|
☭
Регистрация: 26.09.2006
Сообщений: 6,035
Написано 1,474 полезных сообщений (для 2,707 пользователей)
|
Re: Геометрия
я незнаю точки, я тока могу сказать пересекается / непересекается.
|
(Offline)
|
|
09.10.2007, 00:35
|
#12
|
Элита
Регистрация: 02.10.2005
Сообщений: 1,789
Написано 132 полезных сообщений (для 252 пользователей)
|
Re: Геометрия
так что задачка решена? или как?
|
(Offline)
|
|
09.10.2007, 00:47
|
#13
|
Знающий
Регистрация: 05.01.2007
Сообщений: 229
Написано 5 полезных сообщений (для 3 пользователей)
|
Re: Геометрия
Значит так, если пересекается, то:
берешь вектор, перпендикулярный к своей прямой, строишь вдоль него на окружности две точки - это будет точка S и точка центрально-симметричная ей.
Почему: потомучто прямая А1А2 идентична с Х1Х2. Х - середина Х1Х2. ОХ1=ОХ2=радиусу окружности. => Треугольники ОХХ1 и ОХХ2 подобны по двум сторона и одной общей, вообще говоря они равны.Жто возможно только когда угол ОХХ# прямой.
Из двух точек, S - ближайшая к A1, A2. Можно сравнивать не по сумме квадратов, а по сумме модулей разностей координат между точками А1 - S и S - A2.
Почему:
Точка, ближайшая к Х1 и Х2 одновременно, и является точкой S - это очевидно.
Дальше алгебра: если квадрат разности для одной пары чисел больше, чем для другой, то и модуль разности для первой пары тоже больше, чем для второй. Значит можно не возводить в квадрат разночти координат а брать их модули при вычислении расстояния между точками... так как на интересует не величина расстояния, а соотношение расстояний (больше/меньше).
Алгоритм:
1) VectorA = A2-A1 = {Vx,Vy} - вычитаем координаты точек между собой соответстенно.
2) Radius = {Vy,Vx}
3) S1 = O+Radius; S2=O-Radius
4) L1=abs(X1x-S1x)+abs(X1y-S1y); L2=...аналогично.
5) L1>L2 => S=S2, иначе S=S1
|
(Offline)
|
|
09.10.2007, 08:57
|
#14
|
|
Re: Геометрия
хм, а если так :
angle1 = atan2(x1_y - o_y,x1_x - o_x)
angle2 = atan2(x2_y - o_y,x2_x - o_x)
x_x = cos(angle1 + angle2) * radius + o_x
x_y = sin(angle1 + angle2) * radius + o_y
это тормозно ?
|
|
|
09.10.2007, 22:02
|
#15
|
☭
Регистрация: 26.09.2006
Сообщений: 6,035
Написано 1,474 полезных сообщений (для 2,707 пользователей)
|
Re: Геометрия
Вот решение:
Circle - простой пример
VPP - для чего мне ето соьнсо надо было
Vpp2 - вариация
Да, нужна будет моя либа, ищите в теме про секционную разбивку.
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 13:01.
|