Форум программистов, компьютерный форум CyberForum.ru

Окружность и прямая - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.87
des1ner
1 / 1 / 0
Регистрация: 13.05.2011
Сообщений: 12
22.07.2011, 17:47     Окружность и прямая #1
Помогите написать программу на чистом Си. Вот условие:"Дана окружность с координатами Xо,Yo и радиусом r. Дана прямая с координатами x1,y1-x2,y2. Определить координаты точек пересечения прямой с окружостью"
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.07.2011, 17:47     Окружность и прямая
Посмотрите здесь:

C++ Определить, пересекаются ли прямая и окружность
Прямая и окружность C++
Квадрат и прямая C++
Параллельная прямая C++
Круг и прямая C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
22.07.2011, 18:22     Окружность и прямая #2
Уравнение прямой в общем виде y = kx + b,
где k - угловой коэффициент, равный http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{{y}_{2}-{y}_{1}}{{x}_{2}-{x}_{1}}
А b находится, зная координаты точки на этой прямой, как y - kx.
Уравнение окружности http://www.cyberforum.ru/cgi-bin/latex.cgi?{r}^{2} = {x}^{2}+{y}^{2}
Вся задача сводится к решению квадратного уравнения
http://www.cyberforum.ru/cgi-bin/latex.cgi?{x}^{2}({k}^{2}+1)+2xkb+{b}^{2}-{r}^{2}=0
корни которого и будут абсцисами точек пересечения, а ординаты из уравнения прямой найдёте.
Вроде так, если ничего не перепутал...
Поправка - рассчёт на то, что центр окружности - начало координат. Если это не так, проще их (координаты) пересчитать сначала... И ещё есть отдельный случай, когда b = 0.
des1ner
1 / 1 / 0
Регистрация: 13.05.2011
Сообщений: 12
25.07.2011, 00:51  [ТС]     Окружность и прямая #3
Цитата Сообщение от easybudda Посмотреть сообщение
Уравнение прямой в общем виде y = kx + b,
где k - угловой коэффициент, равный http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{{y}_{2}-{y}_{1}}{{x}_{2}-{x}_{1}}
А b находится, зная координаты точки на этой прямой, как y - kx.
Уравнение окружности http://www.cyberforum.ru/cgi-bin/latex.cgi?{r}^{2} = {x}^{2}+{y}^{2}
Вся задача сводится к решению квадратного уравнения
http://www.cyberforum.ru/cgi-bin/latex.cgi?{x}^{2}({k}^{2}+1)+2xkb+{b}^{2}-{r}^{2}=0
корни которого и будут абсцисами точек пересечения, а ординаты из уравнения прямой найдёте.
Вроде так, если ничего не перепутал...
Поправка - рассчёт на то, что центр окружности - начало координат. Если это не так, проще их (координаты) пересчитать сначала... И ещё есть отдельный случай, когда b = 0.
А сам код программы можете помочь написать?
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
25.07.2011, 00:59     Окружность и прямая #4

Не по теме:

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



А сам код программы можете помочь написать?
помочь - да. но не написать самим.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
25.07.2011, 02:25     Окружность и прямая #5
Цитата Сообщение от des1ner Посмотреть сообщение
А сам код программы можете помочь написать?
Помочь или написать?
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
25.07.2011, 05:45     Окружность и прямая #6
Цитата Сообщение от easybudda Посмотреть сообщение
Уравнение окружности http://www.cyberforum.ru/cgi-bin/latex.cgi?{r}^{2} = {x}^{2}+{y}^{2}
Цитата Сообщение от easybudda
Поправка - рассчёт на то, что центр окружности - начало координат.
Цитата Сообщение от des1ner
Дана окружность с координатами Xо,Yo
wiki. уравнение окружности
уравнение с любым центром

Цитата Сообщение от easybudda
Уравнение прямой в общем виде y = kx + b,
где k - угловой коэффициент, равный
А b находится, зная координаты точки на этой прямой, как y - kx.
wiki. уравнение прямой
через определитель

сначала нужно проверить расстояние центра окружности от прямой:
- могут не пересекаться
- прямая может быть касательной
- могут пересекаться

набросок системы уравнений окружности и прямой даёт квадратное уравнение

Цитата Сообщение от easybudda
Вся задача сводится к решению квадратного уравнения
окружность сместил, а прямую не сместил
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
25.07.2011, 11:00     Окружность и прямая #7
Цитата Сообщение от accept Посмотреть сообщение
сначала нужно проверить расстояние центра окружности от прямой:
Можно, но в принципе незачем:
Цитата Сообщение от accept Посмотреть сообщение
могут не пересекаться
дискриминант меньше 0
Цитата Сообщение от accept Посмотреть сообщение
прямая может быть касательной
равен 0
Цитата Сообщение от accept Посмотреть сообщение
могут пересекаться
больше 0

Цитата Сообщение от accept Посмотреть сообщение
окружность сместил, а прямую не сместил
вот этого не понял - куда сместил?
Цитата Сообщение от easybudda Посмотреть сообщение
центр окружности - начало координат. Если это не так, проще их (координаты) пересчитать сначала...
Если про это, так все, конечно, координаты нужно пересчитывать. Если центр координат переносить в центр круга, то и координаты точек, через которые проходит прямая, нужно изменять. Ну или усложнять уравнение...
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
25.07.2011, 11:18     Окружность и прямая #8
Цитата Сообщение от easybudda
Если центр координат переносить в центр круга
центр окружности переносится в начало координат

Цитата Сообщение от easybudda
Можно, но в принципе незачем:
тогда можно применять разные алгоритмы для вычислений
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
25.07.2011, 11:31     Окружность и прямая #9
Цитата Сообщение от accept Посмотреть сообщение
тогда можно применять разные алгоритмы для вычислений
На сколько я понимаю, у этой задачи вообще много решений. Вон чуть выше совсем другой подход был предложен... Я самое простое написал, как в школах учат...
-=ЮрА=-
Заблокирован
Автор FAQ
25.07.2011, 12:32     Окружность и прямая #10
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот моё решение на С. Математические выкладки в миниатюре. Для решения как и говорил easybudda использую совместное решение уравнения прямой и круга методом подстановки и решаю итоговое квадратное уравнение x^2 + (kx+b)^2 = R^2. Вариантов ответов может быть 3
1 - D < 0 прямая и круг не пересекаются
2 - D == 0 прямая - касательная, точка пересечения одна
3 - 0 < D прямая пересекает круг
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#include <math.h>
 
float line(float x1, float x2, float y1, float y2, float x); 
 
int main()
{
    float x1,x2,y1,y2,x0,y0,r,X1,X2,Y1,Y2;
    printf("\tEnter parameters of line\r\n");
    printf("x1 = ");scanf("%g",&x1);
    printf("x2 = ");scanf("%g",&x2);
    printf("y1 = ");scanf("%g",&y1);
    printf("y2 = ");scanf("%g",&y2);
    printf("\tEnter parameters of cicule\r\n");
    printf("x0 = ");scanf("%g",&x0);
    printf("y0 = ");scanf("%g",&y0);
    printf("r  = ");scanf("%g",&r);
 
    float k = (y2 - y1)/(x2 - x1);
    float b = (y2*x1 - y1*x2)/(x1 - x2);
 
    float D = pow(2*b*k,2) + 4*(1 + pow(k,2))*(pow(r,2) - pow(b,2));
    if(0 <= D)
    {
        switch(int(D)){
        case 0:
            X1 = -2*b*k/(2*(1 + pow(k,2))*(pow(r,2) - pow(b,2)));
            Y1 = line(x1,x2,y1,y2,X1);
            printf("\tline is tangent line to circule\r\n");
            break;
        default:
            X1 = (-2*b*k - sqrt(D))/(2*(1 + pow(k,2))*(pow(r,2) - pow(b,2)));
            Y1 = line(x1,x2,y1,y2,X1);
            X2 = (-2*b*k + sqrt(D))/(2*(1 + pow(k,2))*(pow(r,2) - pow(b,2)));
            Y2 = line(x1,x2,y1,y2,X2);
            printf("\tline cross circle in two points\r\n");
            break;
        };
        printf("coord point of intersection P1(%lf;%lf)\r\n",X1,Y1);
        if(D != 0)
            printf("coord point of intersection P2(%.2f;%.2f)\r\n",X2,Y2);
    }
    else
        printf("line not cross circule\r\n");
    return 0;
}
 
float line(float x1, float x2, float y1, float y2, float x)
{
    float y = y1 + (y2 - y1)*(x - x1)/(x2 - x1);
    return y;
}
Миниатюры
Окружность и прямая   Окружность и прямая  
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
25.07.2011, 12:51     Окружность и прямая #11
-=ЮрА=-, попробуй то же самое, но при r == 2
-=ЮрА=-
Заблокирован
Автор FAQ
25.07.2011, 13:20     Окружность и прямая #12
В программе реализовывал следующую логику, сейчас проверю код возможно где то что то потерял в знаках...
Изображения
 
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
25.07.2011, 18:41     Окружность и прямая #13
-=ЮрА=-, дискриминант неправильно посчитал. Должно быть
(2kb)^2 плюс дальше всё то же, а не (2kbx)^2
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
26.07.2011, 01:57     Окружность и прямая #14
вот -=ЮрА=- и попался в ловушку от easybudda
сместив центр окружности в начало координат, даже получив (x1; y1) и (x2; y2), он забыл их сместить обратно
получился "типа правильный" ответ

Цитата Сообщение от easybudda
На сколько я понимаю, у этой задачи вообще много решений. Вон чуть выше совсем другой подход был предложен... Я самое простое написал, как в школах учат...
не, я про то, что если не надо составлять систему, то и не надо её составлять

есть, например, алгоритм, который может быстрее определить, что окружность и прямая не пересекаются, тогда зачем составлять громадную систему, если можно просто вывести, что они не пересекаются
есть, например, алгоритм, который может быстрее определить, в какой точке прямая касается окружности, тогда зачем составлять громадную систему, если можно быстрее вычислить эту точку
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
26.07.2011, 04:14     Окружность и прямая #15
Цитата Сообщение от accept Посмотреть сообщение
вот -=ЮрА=- и попался в ловушку от easybudda
Да никаких ловушек, просто недоработка...

Цитата Сообщение от accept Посмотреть сообщение
есть, например, алгоритм, который может быстрее определить, что окружность и прямая не пересекаются, тогда зачем составлять громадную систему, если можно просто вывести, что они не пересекаются
есть, например, алгоритм, который может быстрее определить, в какой точке прямая касается окружности, тогда зачем составлять громадную систему, если можно быстрее вычислить эту точку
Да говорю же - вариантов море... Можно например провести через центр окружности прямую, перпендикулярную данной. Считая, что центр у нас всё-таки чудесным образом совпадает с началом координат, уравнение получится незатейливое http://www.cyberforum.ru/cgi-bin/latex.cgi?y=-\frac{x}{k}
Находим абсцису точки пересечения прямых, что в общем проще, чем квадратное уравнение: http://www.cyberforum.ru/cgi-bin/latex.cgi?x = \frac{kb}{{k}^{2}-1}, находим ординату и собственно расстояние от центра до точки пересечения. Если оно больше радиуса - прямая окружность не пересекает, если равно - прямая является касательной, если меньше - ищем точки пересечения... При достаточно большом количестве испытаний эффективность использования этих предварительных пируэтов будет обратно пропорциональна количеству случаев с двумя точками пересечения. Если таких по классике наберётся примерно треть (один вариант из трёх возможных), то в принципе смысл есть...
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
26.07.2011, 04:31     Окружность и прямая #16
Цитата Сообщение от easybudda
Можно например провести через центр окружности прямую, перпендикулярную данной. Считая, что центр у нас всё-таки чудесным образом совпадает с началом координат
Цитата Сообщение от easybudda
Находим абсцису точки пересечения прямых, что в общем проще, чем квадратное уравнение: , находим ординату и собственно расстояние от центра до точки пересечения.
есть готовая формула нахождения расстояния от точки до прямой
мало того, при переносе окружности нужно переносить и данную прямую
иначе, как у -=ЮрА=-, получится неправильное расстояние

система:
http://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
\begin{cases}<br />
 & \text (x - x_0)^2 + (y - y_0)^2 = r^2\\ <br />
 & \text Ax + By + C = 0  <br />
\end{cases}<br />

прямая:
http://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
\begin{vmatrix}<br />
 x & y & 1\\ <br />
 x_1& y_1 & 1\\ <br />
 x_2& y_2 & 1<br />
\end{vmatrix} = 0<br />
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
26.07.2011, 04:55     Окружность и прямая #17
Цитата Сообщение от accept Посмотреть сообщение
при переносе окружности нужно переносить и данную прямую
Так я ж про это говорил уже. Но в любом случае, если центр окружности совпадает с началом координат, считать будет значительно легче, так, что, есть смысл сдвинуть всё, потом вернуть...

Цитата Сообщение от accept Посмотреть сообщение
система:
Мудрёно как-то очень... Есть проще способ понять, прийдётся две точки высчитывать, или нет: считаем точки пересечения прямой с осями координат (x; 0) и (0; y). Если |х| или |у| получится меньше радиуса - уже есть две точки... Если оба больше - находим высоту треугольника, образованного этими точками и центром координат: http://www.cyberforum.ru/cgi-bin/latex.cgi?h = \frac{|x||y|}{\sqrt{{x}^{2}+{y}^{2}}} и снова сравниваем с радиусом...
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
26.07.2011, 08:12     Окружность и прямая #18
Окружность и прямая
там ссылка на wiki, где уже написана формула нахождения расстояния от точки до прямой
берёшь прямую и точку, подставляешь в формулу, получаешь расстояние
если расстояние меньше радиуса или равно ему, то решаем систему

Цитата Сообщение от easybudda
Мудрёно как-то очень...
x0, y0, r - известны
A, B, C - вычисляются по заданным точкам
потом надо получить квадратное уравнение с x
после нахождения x1, x2 подставить их в уравнение прямой, чтобы найти y1, y2
-=ЮрА=-
Заблокирован
Автор FAQ
26.07.2011, 10:21     Окружность и прямая #19
Вчера не мог зайти, кстати так и не понял почему с 12 до 19 форум был недоступен???Но не в этом дело, итак по порядку:
1 easybudda, в нахождении дискриминанта х лишний, это не более чем описка, в коде х нет, посмотри листинг алгоритма
2 при нахождении корней я сам напутал и вместо того чтобы делить на 2а делил на 2ас, тут признаю огрех, хотя как раз этого то никто и не заметил, в итоге сам себя и поправил
3 соглашусь с accept-ом, да вначале не учёл координаты центра окружности, ниже код и математические соображения по переходу от х-х0 к обычному квадратному уравнению, вкратце скажу что этого достигаю переходом к Х = х-х0 и У=у-у0 и соответсвующим обратным преобразованием х = Х + х0, у = У+у0
4 единственное мое но - считаю, что если уж и юзать какую либо формулу - её сначала нужно хотябы для себя доказать, в вики в ряде случаев приведены уже конечные преобразования, в которых иногда сокрыт большой объём преобразований и выкладок, и по сути полагаемся на корректность математики автора статьи...
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#include <math.h>
 
float line(float k, float x, float b);
 
int main()
{
    float x1,x2,y1,y2,x0,y0,r,X1,X2,Y1,Y2;
    printf("\tEnter parameters of line\r\n");
    printf("x1 = ");scanf("%g",&x1);
    printf("y1 = ");scanf("%g",&y1);
    printf("x2 = ");scanf("%g",&x2);
    printf("y2 = ");scanf("%g",&y2);
    printf("\tEnter parameters of cicule\r\n");
    printf("x0 = ");scanf("%g",&x0);
    printf("y0 = ");scanf("%g",&y0);
    printf("r  = ");scanf("%g",&r);
 
    float k = (y2 - y1)/(x2 - x1);
    float b = (y2*x1 - y1*x2)/(x1 - x2);
 
    b += (k*x0 - y0); 
 
    float D = pow(2*b*k,2) + 4*(1 + pow(k,2))*(pow(r,2) - pow(b,2));
    if(0 <= D)
    {
        X1 = (-2*b*k - sqrt(D))/(-2*(1 + pow(k,2)));
        Y1 = line(k,X1,b);
        printf("coord point of intersection P1(%lf;%lf)\r\n",X1 + x0,Y1 + y0);
        if(D == 0)
            printf("\tline is tangent line to circule\r\n");
        else
        {
            X2 = (-2*b*k + sqrt(D))/(-2*(1 + pow(k,2)));
            Y2 = line(k,X2,b);
            printf("coord point of intersection P2(%.2f;%.2f)\r\n",X2 + x0,Y2 + y0);
            printf("\tline cross circle in two points\r\n");
        }
    }
    else
        printf("line not cross circule\r\n");
    return 0;
}
 
float line(float k, float x, float b)
{
    return (k*x + b);
}
Миниатюры
Окружность и прямая   Окружность и прямая  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.07.2011, 14:16     Окружность и прямая
Еще ссылки по теме:

Определить, пересекаются ли прямая и окружность, и найти точки пересечения C++
C++ Структуры (Создайте структуру Прямая с элементами x1, y1, x2, y2 – координаты двух точек, через которые проходит прямая)
C++ Определить, сколько точек пересечения имеют прямая и окружность и найти координаты этих точек

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
des1ner
1 / 1 / 0
Регистрация: 13.05.2011
Сообщений: 12
26.07.2011, 14:16  [ТС]     Окружность и прямая #20
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Вчера не мог зайти, кстати так и не понял почему с 12 до 19 форум был недоступен???Но не в этом дело, итак по порядку:
1 easybudda, в нахождении дискриминанта х лишний, это не более чем описка, в коде х нет, посмотри листинг алгоритма
2 при нахождении корней я сам напутал и вместо того чтобы делить на 2а делил на 2ас, тут признаю огрех, хотя как раз этого то никто и не заметил, в итоге сам себя и поправил
3 соглашусь с accept-ом, да вначале не учёл координаты центра окружности, ниже код и математические соображения по переходу от х-х0 к обычному квадратному уравнению, вкратце скажу что этого достигаю переходом к Х = х-х0 и У=у-у0 и соответсвующим обратным преобразованием х = Х + х0, у = У+у0
4 единственное мое но - считаю, что если уж и юзать какую либо формулу - её сначала нужно хотябы для себя доказать, в вики в ряде случаев приведены уже конечные преобразования, в которых иногда сокрыт большой объём преобразований и выкладок, и по сути полагаемся на корректность математики автора статьи...
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#include <math.h>
 
float line(float k, float x, float b);
 
int main()
{
    float x1,x2,y1,y2,x0,y0,r,X1,X2,Y1,Y2;
    printf("\tEnter parameters of line\r\n");
    printf("x1 = ");scanf("%g",&x1);
    printf("y1 = ");scanf("%g",&y1);
    printf("x2 = ");scanf("%g",&x2);
    printf("y2 = ");scanf("%g",&y2);
    printf("\tEnter parameters of cicule\r\n");
    printf("x0 = ");scanf("%g",&x0);
    printf("y0 = ");scanf("%g",&y0);
    printf("r  = ");scanf("%g",&r);
 
    float k = (y2 - y1)/(x2 - x1);
    float b = (y2*x1 - y1*x2)/(x1 - x2);
 
    b += (k*x0 - y0); 
 
    float D = pow(2*b*k,2) + 4*(1 + pow(k,2))*(pow(r,2) - pow(b,2));
    if(0 <= D)
    {
        X1 = (-2*b*k - sqrt(D))/(-2*(1 + pow(k,2)));
        Y1 = line(k,X1,b);
        printf("coord point of intersection P1(%lf;%lf)\r\n",X1 + x0,Y1 + y0);
        if(D == 0)
            printf("\tline is tangent line to circule\r\n");
        else
        {
            X2 = (-2*b*k + sqrt(D))/(-2*(1 + pow(k,2)));
            Y2 = line(k,X2,b);
            printf("coord point of intersection P2(%.2f;%.2f)\r\n",X2 + x0,Y2 + y0);
            printf("\tline cross circle in two points\r\n");
        }
    }
    else
        printf("line not cross circule\r\n");
    return 0;
}
 
float line(float k, float x, float b)
{
    return (k*x + b);
}
не хочет она у меня работать, ввожу координаты, а потом она зависает и выдаёт ошибку
Yandex
Объявления
26.07.2011, 14:16     Окружность и прямая
Ответ Создать тему
Опции темы

Текущее время: 02:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru