www.boolean.name

www.boolean.name (http://forum.boolean.name/index.php)
-   Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)
-   -   Геометрия (http://forum.boolean.name/showthread.php?t=4646)

HolyDel 04.10.2007 05:14

Геометрия
 
Вложений: 2
Все в рисунке.

jimon 04.10.2007 13:29

Re: Геометрия
 
1) ищем точки пересечения отрезка с окружностью
в инете куча мануалов - поискать думаю не составит труда
получаем точки A и B
случаи когда тока одна точка или их нет - отпадают
2) берем середину AB
и ещем ближайшую точку на кругу к полученой точки
точка на кругу = X :-)

alex-mad 04.10.2007 14:12

Re: Геометрия
 
1) по известным данным легко пишутся уровнения отрезка и окружности.
получаем систему из 2-ух уровнений.
находим точки пересечения Х1 и Х2(расматриваем тока случай с 2-мя точками, остальные варианты очевидны).
2) берём середину (S) отрезка образованного точками Х1 и Х2.
середина и центр окружности составляют прямую.
3) пересечение этой прямой с окружностью (аналогично действию номер 1) даст 2 точки.
ближняя точка к S и будет ответом.

ZanoZa 04.10.2007 19:44

Re: Геометрия
 
хух, ну и слава богу, а то я уж думал свое извращение предложить

HolyDel 04.10.2007 20:08

Re: Геометрия
 
ZanoZa, предложи.
а то я чо то все равно ничо не понял.

надо максимальное быстродейтсвие.

у меня идея такая, как-нибудь (не знаю я) надо найти точку - пересечения линии и ее нормали к центру.
если ее найти, то решив несложную пропорцию найдем ту точку.

ZanoZa 04.10.2007 20:18

Re: Геометрия
 
пересечение нормали( к прямой), и самой прямой?

HolyDel 04.10.2007 20:38

Re: Геометрия
 
0x01

Render 04.10.2007 20:43

Re: Геометрия
 
http://algolist.ru/maths/geom/ - думаю будет полезно.

Могу предложить как вариант: построить уравнение окружности и отрезка, и с помощью обычных формул всё находится. Как быстро это будет работать - хз :)

alex-mad 04.10.2007 21:25

Re: Геометрия
 
Цитата:

Сообщение от alex-mad
1) по известным данным легко пишутся уровнения отрезка и окружности получаем систему из 2-ух уровнений.
находим точки пересечения Х1 и Х2(расматриваем тока случай с 2-мя точками, остальные варианты очевидны).
2) берём середину (S) отрезка образованного точками Х1 и Х2.
середина и центр окружности составляют прямую.
3) пересечение этой прямой с окружностью (аналогично действию номер 1) даст 2 точки.
ближняя точка к S и будет ответом.



HolyDel, ты сказал что пересечение находить можешь, следовательно знаешь точки Х1 и Х2.
координаты точки S определить не составит труда.
2 точки описывают прямую, и опять же нужно найти пересечение прямой и окружности (это ты умеешь).
из 2-ух точек определить ближнюю тоже не сложно.

это я к тому что это типичное задание по школьной геометрии и алгоритм я предоставил самый примитивный и доступный пониманию

ZanoZa 07.10.2007 07:28

Re: Геометрия
 
а пересечение x1x2 с OX чисто математически находите, или графически, или уравнение OX известно?
если математически то дайте алгоритм посмотреть, а то интересно очень. :)

HolyDel 07.10.2007 14:03

Re: Геометрия
 
я незнаю точки, я тока могу сказать пересекается / непересекается.

ZanoZa 08.10.2007 20:35

Re: Геометрия
 
так что задачка решена? или как?

Serendipity 08.10.2007 20:47

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

jimon 09.10.2007 04:57

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

это тормозно ?

HolyDel 09.10.2007 18:02

Re: Геометрия
 
Вложений: 2
Вот решение:

Circle - простой пример

VPP - для чего мне ето соьнсо надо было
Vpp2 - вариация

Да, нужна будет моя либа, ищите в теме про секционную разбивку.


Часовой пояс GMT +1, время: 22:49.

vBulletin® Version 3.6.5.
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Перевод: zCarot