Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / C++ Новый топик    Ответить
 Точки пересечения окружности и прямой, алгоритм  [new]
reZFedor
Member

Откуда:
Сообщений: 516
Доброго всем дня.

Никто не связывался с задачей нахождения точек (точки, или их(её) отсутствия) персечения окружности и прямой? Прямая задана парой точек, окружность точкой центра и радиусом.
Покопал гуглого, но там не так много вариантов. Вот например
#include<conio.h>
#include<stdio.h>
#include<iostream.h>
#include<math.h> 

void prover(float x,float y,float k,float b,float r)
{ 
 //находим дискременант квадратного уравнения      
 float d=(pow((2*k*b-2*x-2*y*k),2)-(4+4*k*k)*(b*b-r*r+x*x+y*y-2*y*b));   

 //если он равен 0, уравнение не имеет решения     
 if(d<0) {cout<<"\n\nПрямая и окружность не пересекаются";return;}    

 //иначе находим корни квадратного уравнения     
 float x1=((-(2*k*b-2*x-2*y*k)-sqrt(d))/(2+2*k*k));     
 float x2=((-(2*k*b-2*x-2*y*k)+sqrt(d))/(2+2*k*k)); 

 //если абсциссы точек совпадают, то пересечение только в одной точке         
 if (x1==x2)  
 {
  printf("\n\nПрямая и окружность имеют точку касания:(%.2f,%.2f)",x1,y1);
  return;
 } 

 //иначе находим ординаты точек пересечения      
 float y1=k*x1+b;     
 float y2=k*x2+b;     
 printf("\n\nПрямая и окружность пересекаются в точках: (%.2f,%.2f),(%.2f,%.2f)",x1,y1,x2,y2);      
 return;
}
Все остальное по большей части на параметрическое задание прямой и окружность в начале координат. Я понимаю, что всегда можно получить из двух точек параметрическое уравнение, а цнтр окружности скорректировать, кароче выкрутиться всегда можно, но зачем?
Мож кто видел какойнить простой в плане понимания и читабельности код?

Заранее спасибо.

P.S. Ща на бумажке пытаюсь найти построительным путем (без формул), мож че выдет.
18 ноя 09, 12:50    [7944513]     Ответить | Цитировать Сообщить модератору
 Re: Точки пересечения окружности и прямой, алгоритм  [new]
Aklin
Member [скрыт]

Откуда:
Сообщений: 47873
а чем не нравится предложенное решение?

reZFedor
Все остальное по большей части на параметрическое задание прямой и окружность в начале координат. Я понимаю, что всегда можно получить из двух точек параметрическое уравнение, а цнтр окружности скорректировать, кароче выкрутиться всегда можно, но зачем?
Мож кто видел какойнить простой в плане понимания и читабельности код?

готовые решения для всех типов задач существуют только в борланде и они не работают.
что мешает вам сделать свое решение? написать красивый с вашей точки зрения код?
18 ноя 09, 12:58    [7944579]     Ответить | Цитировать Сообщить модератору
 Re: Точки пересечения окружности и прямой, алгоритм  [new]
reZFedor
Member

Откуда:
Сообщений: 516
Вроде получилось.

У меня в программе есть две процедуры (которые я использую и на них висит половина рассчетов):
1) определение точки основания перпендикуляра опущенного из точки на прямую (достаточно простая)
2) возведение перпендикуляра относительно прямой из точки на опр. расстояние налево и направо от этой прямой прямой
Если каринка все таки прикрепится, то там с помощью этих двух вункций все в три действия (кода не сильно много)
1) Из точки О опускаем перпендикуляр на прямую AB => получаем точку C (основание перпендикуляра).
2) По Пифагору находим расстояние d от точки С до точки пересечения прямой и окружности. До обоих точек расстояние будет одинаковым.
3) Воостанавливаем перпендикуляр из точки С от прямой OC на расстояние d в одну (точка X) и другую (точка Y) стороны.
Вот в принципе и все.
Поправьте если чо попутал.

К сообщению приложен файл. Размер - 2Kb
18 ноя 09, 13:39    [7944901]     Ответить | Цитировать Сообщить модератору
 Re: Точки пересечения окружности и прямой, алгоритм  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 26521

reZFedor пишет:

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

Далее, точка пересечения будет находится достаточно
просто (0, R) или что-то в этом роде.

Потом после нахождения делаете обратный поврот
координат и находите координаты точки пересечения.

Posted via ActualForum NNTP Server 1.4

18 ноя 09, 17:44    [7946825]     Ответить | Цитировать Сообщить модератору
 Re: Точки пересечения окружности и прямой, алгоритм  [new]
reZFedor
Member

Откуда:
Сообщений: 516
MasterZiv
reZFedor пишет:
Так а что там сложного ? Делаете поворот координат,
чтобы центр был в центе окружности, а одна из осей
направлена по данной прямой (я не знаю, какая лучше).

Поаорот "делаете" как?
Это надо преобразовывать с помощью матрицы поворота, а ее что просто получить? Да тем более
чтобы
MasterZiv
одна из осей направлена по данной прямой

Это как минимум +2 действия для определения угла:
1) определений (например) синуса угла
2) определение знака синуса угла (для углов больше 180 градусов)
MasterZiv
Далее, точка пересечения будет находится достаточно
просто (0, R) или что-то в этом роде.

Согласен, пересечение это семачки.
MasterZiv
Потом после нахождения делаете обратный поврот
координат и находите координаты точки пересечения.

Мне лично кажется сложновато. Если изначально возводить "правильную" математику преобразований, то конечно ваш вариант приемлем. Но если проект не стоит таких усили?
Мой метод разве не подходит?
19 ноя 09, 09:56    [7948697]     Ответить | Цитировать Сообщить модератору
 Re: Точки пересечения окружности и прямой, алгоритм  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 26521

reZFedor пишет:

> Мой метод разве не подходит?

Не знаю, не читал.

Матрица преобразования же должна получаться
легко. Центр окружности должен быть задан,
поэтому смещение в эту точку получается легко.
Поворот тоже, поскольку прямая должна быть
задана точкой и коэффициентом наклона.

Posted via ActualForum NNTP Server 1.4

19 ноя 09, 11:23    [7949322]     Ответить | Цитировать Сообщить модератору
 Re: Точки пересечения окружности и прямой, алгоритм  [new]
reZFedor
Member

Откуда:
Сообщений: 516
MasterZiv
Матрица преобразования же должна получаться
легко.

Это предположение?
MasterZiv
Центр окружности должен быть задан,
поэтому смещение в эту точку получается легко.

Согласен.
MasterZiv

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

А вот тут нет: у меня трехмерная графика, но пока используются только две координаты, и точки прямой (отрезка) у меня естественно есть (как тогда еще их отрисовывать), а вот уравнения прямой нет, сл-но его надо находить, а это как с матрицей поворота.
Мне кажется что последовательность действий в вашем варианте должна быть следующей:
1) Формирование матрицы переноса начала системы координат в центр окружности
2) Перенос системы координат в центр окружности с помощью матрицы
3) Формирование (получение) коэфицента наклона прямой или уравнения прямой в параметрическом виде с целью получения угла поворота окружности
4) Формирование матрицы поворота окружности по углу
5) Поворот окружности к углу с помощью матрицы
6) Нахождение пересечение (самое простое)
7) Применение к найденной точке преобразований обратных повороту и смещению
Если что то не так то напиши.
Если все нормально то мне кажется мрачновата перспектива)
В принципе можно и без матриц: сформировать и запомнить вектор переноса, посчитать и запомнить угол поворота. Но это отбросит всего два пункта из семи
19 ноя 09, 12:50    [7950159]     Ответить | Цитировать Сообщить модератору
 Re: Точки пересечения окружности и прямой, алгоритм  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 26521

reZFedor пишет:

> А вот тут нет: у меня трехмерная графика, но пока используются только
> две координаты, и точки прямой (отрезка) у меня естественно есть (как
> тогда еще их отрисовывать), а вот уравнения прямой нет, сл-но его надо
> находить, а это как с матрицей поворота.

Вспомни теорему Пифагора, и вычисли быстро уравнение прямой.

> 1) Формирование матрицы переноса начала системы координат в центр окружности
> 2) Перенос системы координат в центр окружности с помощью матрицы
> 3) Формирование (получение) коэфицента наклона прямой или уравнения
> прямой в параметрическом виде с целью получения угла поворота окружности
> 4) Формирование матрицы поворота окружности по углу

Можно один раз матрицу сформировать.

> 5) Поворот окружности к углу с помощью матрицы
> 6) Нахождение пересечение (самое простое)
> 7) Применение к найденной точке преобразований обратных повороту и смещению

> Если все нормально то мне кажется мрачновата перспектива)

Да, можно легче. Можно найти или придумать самому (вывести)
соответствующие формы (это в линейной алгебре должно быть).
Я ещё раз написал что в голову взбрело.

Posted via ActualForum NNTP Server 1.4

19 ноя 09, 15:02    [7951351]     Ответить | Цитировать Сообщить модератору
 Re: Точки пересечения окружности и прямой, алгоритм  [new]
reZFedor
Member

Откуда:
Сообщений: 516
MasterZiv
...
Вспомни теорему Пифагора, и вычисли быстро уравнение прямой.
...

Только щас понял)
MasterZiv
...
Можно один раз матрицу сформировать.
...

Я так понял одну матрицу преобразования для поворота+смещения?
Если такое возможно, то ессессно да.
...
MasterZiv
...
Да, можно легче. Можно найти или придумать самому (вывести)
соответствующие формы (это в линейной алгебре должно быть).
Я ещё раз написал что в голову взбрело.

Я рассчитываю по своей методе. Пока никаких граблей.
Но всеравно большое спасибо за дискуссию.
20 ноя 09, 12:40    [7955934]     Ответить | Цитировать Сообщить модератору
 Re: Точки пересечения окружности и прямой, алгоритм  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 26521

reZFedor wrote:
> Я так понял одну матрицу преобразования для поворота+смещения?
> Если такое возможно, то ессессно да.

Возможно.

Posted via ActualForum NNTP Server 1.4

20 ноя 09, 15:12    [7957121]     Ответить | Цитировать Сообщить модератору
Между сообщениями интервал более 1 года.
 Re: Точки пересечения окружности и прямой, алгоритм  [new]
Silder
Member

Откуда:
Сообщений: 2
Решение проще некуда Х1,2=Х1 (+/-) d/sqrt(1+k^2)
X1,2 это иксы точек пересечения
к^2 это квадрат углового коэффициента прямой
d расстояние от точки С до точек пересечения(использовал рисунок который выше приводили)
У1,2 можно будет найти из уравнения прямой
1 мар 13, 23:14    [14001711]     Ответить | Цитировать Сообщить модератору
 Re: Точки пересечения окружности и прямой, алгоритм  [new]
Silder
Member

Откуда:
Сообщений: 2
Забыл упомянуть что в формуле Х1 это икс от точки С взятый
1 мар 13, 23:16    [14001716]     Ответить | Цитировать Сообщить модератору
Все форумы / C++ Ответить
 
Лучший учебный центр Microsoft!
Новейшие курсы Microsoft SQL Server 2014!
ОЧЕНЬ привлекательные цены на курсы Oracle — от 26 тыс.руб.!
Все курсы по базам данных: Microsoft SQL Server 2014, Oracle, IBM DB2, Access, MySql