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

Окружность по 3-ём точкам - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 5.00
LuBu
4 / 4 / 0
Регистрация: 03.12.2009
Сообщений: 71
05.11.2010, 16:34     Окружность по 3-ём точкам #1
Здравствуйте! Помогите пожалуйста с заданием!

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


Иными словами вы должны ввести любое кол-во точек и надо найти минимальный радиус и центр окружности, проходящей через любые 3 точки!

вот часть моего кода


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include "stdafx.h"
#include <iostream>;
#include <complex>;
 
using namespace std;
 
int main ()
{   
    int n,i,x[20],y[20];
    cout<<"Vvedite kol-vo tochek: "<<endl;
    cin>>n;
for( i=0; i<=n;i++)
{
    cout<<"Vvediye koordinatu tochki: "<<endl;
    cout<<"Koordinata x: "<<endl;
    cin>>x[i];
    cout<<"Koordinata y: "<<endl;
    cin>>y[i];
}
Вопросы:

Я вот решил сделать так, вводим координаты точек, потом он считает длину между точек, что бы найти длины сторон треугольника через которые вычислить радиус!
токо вот это не логично по моему...


Какие вы можете предложить способы? желательно если у вас к вашим предложениям есть формулы буду оч признателен!))

Заранее спаисбО!)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
05.11.2010, 17:41     Окружность по 3-ём точкам #2
Очевидно, что все три стороны треугольника являются хордами круга. Центр круга лежит на пересечении серединных перпендикуляров - достаточно взять любые две стороны. Всё остальное - в учебнике линейной алгебры.
QWAN
56 / 55 / 1
Регистрация: 02.09.2008
Сообщений: 181
05.11.2010, 17:57     Окружность по 3-ём точкам #3
1) Три точки лежат на окружности.
2) Три точки (допустим точки А,Б,С) образуют треугольник (вписанный). Пусть точка Б - вершина треугольника напротив самой длинной грани нашего треугольника.
3) Каждая грань треугольника, это хорда нашей окружности.
4) Если взять две грани треугольника и провести из их центров прямые (перпендикулярные к этим граням), они пересекутся в центре окружности (О).
5) Сравниваем длины отрезков (от центра до любой из точек нашего треугольника) и находим самый маленький радиус.

Пока думал как написать уже ответили.
LuBu
4 / 4 / 0
Регистрация: 03.12.2009
Сообщений: 71
06.11.2010, 19:42  [ТС]     Окружность по 3-ём точкам #4
Спасибо! буду реализовывать!))))

Добавлено через 19 часов 46 минут
токо вопрос!!! как реализовать функцию, которая позволяет вычислять координаты пересечения перпендикуляров ???

вот я нашёл координаты центров хорд! а дальше как мне из них пустить перпендикуляры и найти координату пересечения?

помогите пожалуйста!!!!
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,656
07.11.2010, 13:09     Окружность по 3-ём точкам #5
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
//////////////////////////////////////////////////////////////////////////////////////
//Определить радиус и центр окружности минимального радиуса, проходящей хотя бы через 
//три различные точки заданного множества точек на плоскости.
//////////////////////////////////////////////////////////////////////////////////////
#include <complex>
#include <iostream>
#include <limits>
#include <set>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef double                 T_coord;
typedef std::complex<T_coord>  T_point;
typedef std::vector<T_point>   T_points;
//////////////////////////////////////////////////////////////////////////////////////
struct  T_less_for_points
{
    bool  operator() (T_point  A, T_point  B)
    {
        return A.real() == B.real() ? A.imag() < B.imag() : A.real() < B.real();
    }
};
//////////////////////////////////////////////////////////////////////////////////////
typedef std::set<T_point, T_less_for_points>  T_points_set;
//////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  equal_to_for_real(T a, T b) 
{
    const T  coef = 10;
    return abs(a - b) < std::numeric_limits<T>::epsilon() * coef;
}
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  greater_for_real(T a, T b) 
{
    return a > b
           && !equal_to_for_real(a, b);
}
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  less_for_real(T a, T b) 
{
    return a < b
           && !equal_to_for_real(a, b);
}
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  greater_equal_for_real(T a, T b) 
{
    return !less_for_real(a, b);
}
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  less_equal_for_real(T a, T b) 
{
    return !greater_for_real(a, b);
}
/////////////////////////////////////////////////////////////////////////////////////
T_point  vect(T_point A, T_point B)
{
    return B - A;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  successfully_get_circumcircle_R
    (
        T_point   A, 
        T_point   B, 
        T_point   C, 
        T_coord&  R
    )
{
    T_point  BC = vect(B, C);
    T_point  AB = vect(A, B);
    T_point  AC = vect(A, C);
 
    //По теореме синусов:
    T_coord  alpha      = abs(arg(AB / AC));
    T_coord  sin_alpha  = sin(alpha);
    bool     res        = !equal_to_for_real(sin_alpha, 0.0);
    if(res)
    {
        R = abs(BC) / (2 * sin(alpha));
    }
    return  res;
}
//////////////////////////////////////////////////////////////////////////////////////
T_point  get_circumcircle_center(const T_points&  circle_min_points)
{
    T_point  A = circle_min_points[0]; 
    T_point  B = circle_min_points[1]; 
    T_point  C = circle_min_points[2]; 
 
    //Повернем плоскость с отрезком AB относительно начала координат таким образом, 
    //чтобы он стал горизонтальным. Очевидно для этого нужно разделить каждую из его точек
    //на число vect(A, B) / abs(vect(A, B)):
    T_point  divider_AB  = vect(A, B) / abs(vect(A, B));
    T_point  A_hor       = A / divider_AB;
    T_point  B_hor       = B / divider_AB;
 
    //Зададим двумя точками вертикальную прямую линию, делящую пополам 
    //отрезок (A_hor, B_hor):
    T_points  H_ab;
    H_ab.push_back((A_hor + B_hor) / 2.0);
    H_ab.push_back(H_ab.back() + T_point(0, 1));
 
    //Умножим точки этой прямой на divider_AB, чтобы повернуть ее обратно 
    //на тот же угол (в состояние, перпендикулярное AB).
    H_ab.front() *= divider_AB;
    H_ab.back()  *= divider_AB;
 
    //Теперь повернем плоскость с отрезком AC и прямой H_ab вокруг начала координат 
    //таким образом, чтобы отрезок AC стал горизонтальным. Очевидно для этого нужно 
    //разделить каждую из точек на число vect(A, C) / abs(vect(A, C)):
    T_point  divider_AC  = vect(A, C) / abs(vect(A, C));
    T_point  AA_hor      = A / divider_AC;
    T_point  CC_hor      = C / divider_AC;
    H_ab.front() /= divider_AC;
    H_ab.back()  /= divider_AC;
 
    //Найдем точку M на прямой H_ab, абсцисса которой лежит между абсциссами 
    //точек AA_hor и CC_hor из уравнения 
    //M = P + (Q - P) * k.                                 (1)
    //Проецируя это уравнение на ось абсцисс, получим:
    //Mx = Px + (Qx - Px) * k, откуда                      (2)
    //k = (Mx - Px)/(Qx - Px),                             (3)
    //где Mx - абсцисса точки M, 
    //Px и Qx - абсциссы точек P и Q прямой H_ab, 
    //k - искомый множитель.     
    T_point  Q = H_ab.front();
    T_point  P = H_ab.back();        
    
    T_point  Qx = Q.real();
    T_point  Px = P.real();
    T_point  Mx = (AA_hor.real() + CC_hor.real()) / 2.0;
 
    //Из (3) получим:
    T_point  k_point = (Mx - Px)/(Qx - Px);
    T_coord  k = k_point.real();
 
    //Вычисляем точку M согласно (1):
    T_point  M = P + (Q - P) * k;
    //Чтобы получить искомый центр center описанной окружности, поворачиваем 
    //точку M обратно на тот же угол (чтобы прямая H_ab снова стала перпендикулярна AB), 
    //умножив на divider_AC:
    T_point  center = M * divider_AC;
    return center;
}
//////////////////////////////////////////////////////////////////////////////////////
void  print_min_circle(const T_points_set  points_set)
{
    const T_coord  R_MIN_EMPTY = -1;
    T_coord        R_min = R_MIN_EMPTY;
    T_points       circle_min_points;
    T_points       points(points_set.begin(), points_set.end());
    for(T_points::const_iterator  A_it = points.begin(); A_it != points.end(); ++A_it)
    {
        for(T_points::const_iterator  B_it = A_it + 1; B_it != points.end(); ++B_it)
        {
            for(T_points::const_iterator  C_it = B_it + 1; C_it != points.end(); ++C_it)
            {                
                T_coord  R_cur = 0;
                if(!successfully_get_circumcircle_R(*A_it, *B_it, *C_it, R_cur))
                {
                    continue;
                }
                if(equal_to_for_real(R_min, R_MIN_EMPTY)
                   ||less_for_real(R_cur, R_min))
                {
                    R_min = R_cur;
                    circle_min_points.clear();
                    circle_min_points.push_back(*A_it);
                    circle_min_points.push_back(*B_it);
                    circle_min_points.push_back(*C_it);                
                }
            }        
        }    
    }
    if(equal_to_for_real(R_min, R_MIN_EMPTY))
    {
        std::cout << "Нет окружностей."
                  << std::endl;        
    }
    else
    {
        std::cout << "Окружность с наименьшим радиусом "
                  << R_min
                  << " имеет центр в точке "
                  << get_circumcircle_center(circle_min_points)
                  << std::endl;      
    }
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));   
    int  n;
    do
    {
        std::cout << "Введите количество точек >= 1: ";
        std::cin >> n;
    }while(n < 1);
 
    T_points_set  points_set;
    std::cout << "Введите координаты "
              << n
              << " различных точек:"
              << std::endl;
 
    do
    {
        std::cout << std::endl
                  << "X"
                  << points_set.size() + 1
                  << " = ";
        
        T_coord  X;
        std::cin >> X;
 
        std::cout << "Y"
                  << points_set.size() + 1
                  << " = ";
        
        T_coord  Y;
        std::cin >> Y;
        points_set.insert(T_point(X, Y));
    }while(static_cast<int>(points_set.size()) < n); 
    print_min_circle(points_set);
}
LuBu
4 / 4 / 0
Регистрация: 03.12.2009
Сообщений: 71
07.11.2010, 15:14  [ТС]     Окружность по 3-ём точкам #6
ОГО!!!!!!!!!!!!!!

спасибо огромное!!!!!!!!!!!!!!

нереально крутой код!! буду изучать и сдавать!)))
благодарю!!!!!!!!!!!!!!!!!!!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2010, 15:20     Окружность по 3-ём точкам
Еще ссылки по теме:

C++ Рисование отрезка по точкам (ошибки в работе)
Полином Лагранжа - Сделать интерполяцию по точкам C++
Найти интеграл по точкам C++

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

Или воспользуйтесь поиском по форуму:
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.11.2010, 15:20     Окружность по 3-ём точкам #7
Реши относительно x,y,r как систему уравнение окружности с подставленными в него координатами
(x1-x)*(x1-x)+(y1-y)*(y1-y)=r*r
(x2-x)*(x2-x)+(y2-y)*(y2-y)=r*r
(x3-x)*(x3-x)+(y3-y)*(y3-y)=r*r
Yandex
Объявления
07.11.2010, 15:20     Окружность по 3-ём точкам
Ответ Создать тему
Опции темы

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