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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 5.00
LuBu
4 / 4 / 0
Регистрация: 03.12.2009
Сообщений: 71
#1

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

05.11.2010, 16:34. Просмотров 3554. Ответов 6
Метки нет (Все метки)

Здравствуйте! Помогите пожалуйста с заданием!

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


Иными словами вы должны ввести любое кол-во точек и надо найти минимальный радиус и центр окружности, проходящей через любые 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];
}
Вопросы:

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


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

Заранее спаисбО!)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2010, 16:34     Окружность по 3-ём точкам
Посмотрите здесь:

перемещать квадрат по точкам - C++
ребят,помогите пожалуйста,есть код программы где квадрат перемещается по сетке,а нужно чтоб по точкам,где и на что исправить? class SETKA...

Найти интеграл по точкам - C++
Программа должна считать интеграл по точкам #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; double f(double x); ...

Уравнение прямой по двум точкам - C++
#include &lt;iostream&gt; using namespace std; void main() { setlocale (LC_ALL, &quot;rus&quot;); int x1, y1, x2, y2, x, y, line; cout &lt;&lt;...

построение графика по заданным точкам - C++
Доброго времени суток! Очень нужна помощь: вывести на экран график по заданным координатам точек из файла..строить нужно в консоли. ...

Определить тип треугольника по его точкам - C++
Что-то никак не получается :( На вход программы даются три наруральных числа a, b, c. Если не существует невырожденного треугольника...

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

Рисование отрезка по точкам (ошибки в работе) - C++
Есть программа, которая требует ввести точки начала и конца отрезка и рисует этот отрезок. Но она не работает. При попытке ввода значений...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nick Alte
Эксперт С++
1607 / 999 / 118
Регистрация: 27.09.2009
Сообщений: 1,926
Завершенные тесты: 1
05.11.2010, 17:41     Окружность по 3-ём точкам #2
Очевидно, что все три стороны треугольника являются хордами круга. Центр круга лежит на пересечении серединных перпендикуляров - достаточно взять любые две стороны. Всё остальное - в учебнике линейной алгебры.
QWAN
58 / 57 / 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
Эксперт С++
3042 / 1687 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
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-ём точкам
Еще ссылки по теме:

Постройка графика по точкам в консоли Dev C++ - C++
Задание стоит так - разработка класса &quot;Построение интерполяционного полинома&quot; с использованием разных видов конструкторов. Я написал...

Построить прямоугольник по двум заданным точкам - C++
Построить прямоугольник по двум заданным точкам: левому верхнему и правому нижнему углам. Обе точки указываются с клавиатуры, а именно:...

Построение графика функции по точкам (Dev-C ) - C++
Подскажите как построить график по точкам(Dev-C++), какая это библиотека и где можно почитать основные команды?

Нахождения перимтров нескольких трапеций заданных по точкам - C++
Вот сама задача.&quot;На вход подается некоторое количество трапеций (координаты вершин). Отсортировать и вывести их по возрастанию периметров. ...

Создание в BitMap окружности заданного радиуса по точкам - C++
Добрый день! Подскажите, пожалуйста, как нарисовать окружность в BitMap заданного радиуса по точкам, если можно с примером. Заранее...


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

Или воспользуйтесь поиском по форуму:
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-ём точкам
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru