Форум программистов, компьютерный форум, киберфорум
Наши страницы
Геометрия
Войти
Регистрация
Восстановить пароль
 
chpokemon
0 / 0 / 0
Регистрация: 24.02.2017
Сообщений: 2
#1

Найти радиус наименьшей окружности, содержащей треугольник на плоскости - Геометрия

24.02.2017, 17:32. Просмотров 391. Ответов 9
Метки нет (Все метки)

Доброго времени суток! Ребята, помогите, подкиньте решение для задачи! Нужно найти радиус наименьшей окружности, содержащей треугольник на плоскости. А именно Частный случай треугольника: остроугольный (с остальными понятно). И еще найти радиус наименьшей окружности, содержащий четырехугольник: параллелограмм, трапеция, ромб, прямоугольник.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.02.2017, 17:32
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Найти радиус наименьшей окружности, содержащей треугольник на плоскости (Геометрия):

Найти радиус вписанной окружности в треугольник
В круг радиуса r вписан равнобедренный треугольник, один из углов при основании...

Найти медиану, биссектрису, радиус вписанной в треугольник окружности.
1)В прямоугольном треугольнике катеты равны 3 и 4. Найдите длины Медиан 2)В...

Радиус описанной около прямоугольного треугольника окружности. Радиус вписанной в прямоугольный треугольник ок
Доказать обе формулы Нужно написать доказательство к формулам R=a:2 и r=P/2-a,...

Составить уравнение плоскости и найти координаты центра и радиус окружности
Дано уравнение сферы S. ...

Найдите радиус окружности, вписанной в треугольник
Окружность радиуса R касается катета PM прямоугольного треугольника MPN в точке...

Найдите радиус окружности, вписанной в треугольник
Боковые стороны KL и MN трапеции KLMN равны 10 и 26 соответственно. Отрезок,...

9
tarasso
486 / 408 / 37
Регистрация: 13.05.2012
Сообщений: 877
24.02.2017, 21:15 #2
Другими словами данные фигуры нужно вписать в окружность. Условия, в которых данные фигуры можно вписать в окружность есть в теоремах элементарной геометрии. Подумайте, а что не понятно сформулируйте...
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4385 / 2360 / 655
Регистрация: 18.10.2014
Сообщений: 4,002
25.02.2017, 05:42 #3
Цитата Сообщение от tarasso Посмотреть сообщение
Условия, в которых данные фигуры можно вписать в окружность есть в теоремах элементарной геометрии.
В данной задаче не требуется именно вписать эти фигуры в окружность, по каковой причине проверять "условия, в которых данные фигуры можно вписать в окружность" нет никакой необходимости.
0
chpokemon
0 / 0 / 0
Регистрация: 24.02.2017
Сообщений: 2
25.02.2017, 12:58  [ТС] #4
Требуется не найти радиус ОПИСАННОЙ окружности. А найти наименьшую, с минимальным радиусом окружность(и радиус соответственно), которая просто бы содержала треугольник или четырехугольник, НЕ описывала. То есть, чтобы данная фигура находилась в окружности, не обязательно описывался ею.
0
tarasso
486 / 408 / 37
Регистрация: 13.05.2012
Сообщений: 877
25.02.2017, 23:36 #5
рисунок сможете нарисовать?
0
mathidiot
Эксперт по математике/физике
2646 / 2350 / 1011
Регистрация: 14.01.2014
Сообщений: 5,025
25.02.2017, 23:52 #6
Вот, например (три точки многоугольника на окружности, а другие - внутри)
0
Миниатюры
Найти радиус наименьшей окружности, содержащей треугольник на плоскости  
tarasso
486 / 408 / 37
Регистрация: 13.05.2012
Сообщений: 877
25.02.2017, 23:57 #7
интересно, в таком случае действительно присутствует критерий оптимальности
0
Байт
Эксперт C
17777 / 11802 / 2453
Регистрация: 24.12.2010
Сообщений: 23,728
26.02.2017, 11:28 #8
Имхо, для многих точек задачу можно решить простым перебором. Перебираются все возможные тройки точек. По каждой тройке строится описанная окружность. Из тех окружностей, которые включают в себя все точки, выбирается окружность с минимальным радиусом.
Просто несложно показать, что требуемая окружность должна проходить как минимум через 3 точки. Ибо, если на окружности точек меньше 3-х (а остальные лежат внутри), то можно построить окружность меньшего радиуса.
Детальное доказательство этого факта видится несколько занудливым, но факт, имхо, интуитивно очевиден.

Добавлено через 22 минуты
Кажись, я погорячился. Возьмем параллелограмм. Наименьший радиус - пол большой диагонали. А радиус окружности, описанной вокруг тупоугольной его половины побольше будет...
1
kabenyuk
1719 / 1298 / 308
Регистрация: 19.11.2012
Сообщений: 2,541
02.03.2017, 06:01 #9
Цитата Сообщение от chpokemon Посмотреть сообщение
А именно Частный случай треугольника: остроугольный (с остальными понятно).
Сначала замечаем, что для любого треугольника окружность наименьшего радиуса находится среди двух: одна с центром в середине наибольшей стороны, другая описанная. Для треугольника с тупым углом - это первая из них, для прямоугольного они одинаковы, для остроугольного - это описанная.
1
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4385 / 2360 / 655
Регистрация: 18.10.2014
Сообщений: 4,002
03.03.2017, 22:40 #10
Если речь идет только о треугольниках и четырехугольниках, то задача решается достатчоно тривиально рассмотрением набора предзаданных комбинаций.

Для решения общей задачи, т.е. задачи для произвольной свалки точек, существует алгорим Эмо Велзла (https://en.wikipedia.org/wiki/Emo_Welzl) (не уверен, что правильно транслитерирую его фамилию). Оригинальная статья: https://www.inf.ethz.ch/personal/emo...LNCS555_91.pdf или http://www.stsci.edu/~RAB/Backup%20O...RSTML/Bob1.pdf

Так как подмена произвольной свалки точек ее выпуклой оболочкой ничего не меняет (и алгоримы построения выпуклой оболочки эффективны) ясно, что и для задачи произвольного выпуклого многоугольника скорее всего придется использовать общий алгорим.

------

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

Кликните здесь для просмотра всего текста
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
#include <cassert>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <set>
#include <iostream>
 
struct Point
{
  double x, y;
 
  Point() : x{}, y{}
    {}
 
  Point(double x, double y) : x{x}, y{y} 
    {}
 
  double radius2() const
    { return x * x + y * y; }
 
  double radius() const
    { return std::sqrt(radius2()); }
 
  Point ccw() const
    { return { -y, x }; }
 
  Point operator /(double rhs) const
    { return { x / rhs, y / rhs }; }
 
  friend Point operator +(const Point &lhs, const Point &rhs)
    { return { lhs.x + rhs.x, lhs.y + rhs.y }; }
 
  friend Point operator -(const Point &lhs, const Point &rhs)
    { return { lhs.x - rhs.x, lhs.y - rhs.y }; }
 
  friend double operator *(const Point &lhs, const Point &rhs)
    { return lhs.x * rhs.y - lhs.y * rhs.x; }
 
  friend bool operator <(const Point &lhs, const Point &rhs)
    { return lhs.y < rhs.y || (lhs.y == rhs.y && lhs.x < rhs.x); }
 
  friend double distance(const Point &a, const Point &b)
    { return (a - b).radius(); }
 
  friend std::ostream &operator <<(std::ostream &lhs, const Point &rhs)
    { return lhs << "(" << rhs.x << ", " << rhs.y << ")"; }
};
 
Point intersect(const Point &a1, const Point &b1, const Point &a2, const Point &b2)
{
  Point d1 = a1 - b1, d2 = a2 - b2;
 
  double cp1 = a1 * b1, cp2 = a2 * b2;
 
  double 
    numx = cp1 * d2.x - cp2 * d1.x,
    numy = cp1 * d2.y - cp2 * d1.y;
 
  double den = d1 * d2; 
  assert(abs(den) > 0.00001);
 
  return { numx / den, numy / den };
}
 
struct Circle
{
  Point c;
  double r;
 
  Circle() : c{}, r(-1)
    {}
 
  Circle(const Point &c, double r = 0) : c{c}, r{r}
    {}
 
  bool contains(const Point &p) const
    { return r >= 0 && (p - c).radius2() <= r * r; }
 
  friend std::ostream &operator <<(std::ostream &lhs, const Circle &rhs)
    { return lhs << "c = " << rhs.c << ", r = " << rhs.r; }
};
 
Circle circle(const Point &a, const Point &b)
{
  return { (a + b) / 2, distance(a, b) / 2 };
}
 
Circle circle(Point a, Point b, Point c)
{
  double ab = distance(a, b), ac = distance(a, c), bc = distance(b, c);
  if (ac > ab)
  {
    std::swap(b, c);
    std::swap(ab, ac);
  }
 
  if (bc > ab)
  {
    std::swap(a, c);
    std::swap(ab, bc);
  }
 
  Circle d = circle(a, b);
  if (d.contains(c))
    return d;
 
  Point mac1 = (a + c) / 2, mbc1 = (b + c) / 2;
  Point mac2 = mac1 + (a - c).ccw(), mbc2 = mbc1 + (b - c).ccw();
 
  Point o = intersect(mac1, mac2, mbc1, mbc2);
 
  return { o, distance(o, c) };
}
 
/****************************************************************************************/
 
typedef std::set<Point> Points;
 
Circle B_MD(const Points &R)
{
  assert(R.size() <= 3);
 
  auto it = R.begin();
  if (it == R.end())
    return {};
 
  Point a = *it++;
  if (it == R.end())
    return { a };
 
  Point b = *it++;
  if (it == R.end())
    return circle(a, b);
 
  Point c = *it++;
  return circle(a, b, c);
}
 
Circle B_MINIDISK(Points P, Points R = {})
{
  assert(R.size() <= 3);
 
  Circle D;
 
  if (P.empty() || R.size() == 3)
    D = B_MD(R);
  else
  {
    Point p = *P.begin();
 
    P.erase(p);
    D = B_MINIDISK(P, R);
 
    if (!D.contains(p))
    {
      R.insert(p);
      D = B_MINIDISK(P, R);
    }
  }
 
  return D;
}
 
/****************************************************************************************/
 
int main()
{
  std::srand((unsigned) std::time(NULL));
 
  Points S;
 
  for (unsigned n = 20; n > 0; --n)
  {
    Point p{ rand() % 100 - 50., rand() % 100 - 50. };
    std::cout << p << std::endl;
    S.insert(p);
  }
 
  Circle D = B_MINIDISK(S);
 
  std::cout << std::endl << D << std::endl;
}


Усердно не тестировал, но вот, например, результат для 20 случайных точек

Код
(-17, -38)
(-34, 19)
(-32, -1)
(-8, 23)
(-16, 48)
(5, 19)
(1, -20)
(27, 31)
(-16, 6)
(35, -5)
(-19, 17)
(10, -7)
(42, -7)
(49, 40)
(-20, -32)
(-42, -9)
(15, 47)
(-13, 14)
(44, -15)
(48, 33)

c = (7.38043, 8.29348), r = 52.321
1
Миниатюры
Найти радиус наименьшей окружности, содержащей треугольник на плоскости  
03.03.2017, 22:40
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.03.2017, 22:40
Привет! Вот еще темы с решениями:

Найти радиус R описанной и радиус r вписанной окружности для данных вершин треугольника
2) Известны три точки - вершины треугольника АВС - А(20;15), В(-16;0),...

Даны 3 точки. Радиус наименьшей окружности, содержавшей эти точки
Добрый день. Подкиньте пожалуйста идею для решения следующей задачи: мне даны 3...

Найти радиус окружности
Остроугольный треугольник ABC вписан в окружность W. Продолжения высот...

Найти радиус окружности.
По известным хорде и высоте дуги необходимо найти радиус окружности. Как сие...


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

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