Найти окружность проходящую через три точки на плоскости

@artibmstu · Регистрация: 04.12.2015

Студворк — интернет-сервис помощи студентам

Задано множество точек на плоскости. Найти такую окружность, которая проходит через три точки и разница между количеством точек внутри и снаружи минимальна

@vdm_mar · 29.02.2016, 00:18

Тяжелый вариант, тупо напрямую, делать комбинации троек точек, определять для них окружность и потом проверять все точки. Формулу окружности по трем точкам высчитывал "ручками", мог и ошибиться.

Python
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
data = [(1, 1), (-1, 3), (5, 3), (-3, -4), (6, 0), (1, 5), (-2, 0), (3, 3), (0, 0)]
minimum = {}
points = [[data[i], data[j], data[k]] for i in range(len(data)-2) for j in range(i+1, len(data)-1) for k in range(j+1, len(data))]
for z in points:
    x1, y1 = z[0]
    x2, y2 = z[1]
    x3, y3 = z[2]
    try:
        y0 = (2*(x1-x3)*(y2**2 - y1**2 - x1**2 + x2**2) + 2*(x1-x2)*(x1**2 - x3**2 - y3**2 + y1**2)) / (4*(y2-y1)*(x1-x3) - 4*(x1-x2)*(y3-y1))
    except ZeroDivisionError:
        continue
    if x1 - x3 != 0:
        x0 = ((x1**2 - x3**2 - y3**2 + y1**2) + 2*y0*(y3-y1))/ (2*(x1-x3))
    if x1 - x2 != 0:
        x0 = ((x1**2 - x2**2 - y2**2 + y1**2) + 2*y0*(y2-y1))/ (2*(x1-x2))
    R = ((x0 - x1)** 2 + (y0 - y1)** 2) ** (1/2)
 
    n1, n2, n3 = 0, 0, 0
 
    for t in data:
        if (t[0] - x0) ** 2 + (t[1] - y0) ** 2 < R ** 2:
            n1 += 1
        elif (t[0] - x0) ** 2 + (t[1] - y0) ** 2 == R ** 2:
            n3 += 1
        else:
            n2 += 1
        minimum[abs(n1 - n2)] = ['(x - {:.1f}) ** 2 + (y - {:.1f}) ** 2 = {:.1f} ** 2'.format(x0, y0, R).replace('- -', '+ '), z[0], z[1], z[2], n1, n2, n3]
 
print('Окружность:', minimum[min(minimum)][0])
print('Три точки, определяющие окружность:', str(minimum[min(minimum)][1]) + ',',  str(minimum[min(minimum)][2]) + ',', minimum[min(minimum)][3])
print('Всего кол-во точек, принадлежащих окружности:', minimum[min(minimum)][6])
print('Кол-во точек внутри круга:', minimum[min(minimum)][4])
print('Кол-во точек вне круга:', minimum[min(minimum)][5])

Добавлено через 22 минуты
Блин, если в массиве точек будут точки с большими координатами, то при подсчете точек влияет точность, придется делать round

Python
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
data = [(1, 1), (-1, 3), (5, 3), (-3, -4), (6, 0), (1, 5), (-2, 0), (3, 3), (0, 0), (100, -100), (1, 100)]
minimum = {}
points = [[data[i], data[j], data[k]] for i in range(len(data)-2) for j in range(i+1, len(data)-1) for k in range(j+1, len(data))]
for z in points:
    x1, y1 = z[0]
    x2, y2 = z[1]
    x3, y3 = z[2]
    try:
        y0 = (2*(x1-x3)*(y2**2 - y1**2 - x1**2 + x2**2) + 2*(x1-x2)*(x1**2 - x3**2 - y3**2 + y1**2)) / (4*(y2-y1)*(x1-x3) - 4*(x1-x2)*(y3-y1))
    except ZeroDivisionError:
        continue
    if x1 - x3 != 0:
        x0 = ((x1**2 - x3**2 - y3**2 + y1**2) + 2*y0*(y3-y1))/ (2*(x1-x3))
    if x1 - x2 != 0:
        x0 = ((x1**2 - x2**2 - y2**2 + y1**2) + 2*y0*(y2-y1))/ (2*(x1-x2))
    R = ((x0 - x1)** 2 + (y0 - y1)** 2) ** (1/2)
 
    n1, n2, n3 = 0, 0, 0
 
    for t in data:
        if round((t[0] - x0) ** 2 + (t[1] - y0) ** 2, 3) < round(R ** 2, 3):
            n1 += 1
        elif round((t[0] - x0) ** 2 + (t[1] - y0) ** 2, 3) > round(R ** 2, 3):
            n2 += 1
        else:
            n3 += 1
    minimum[abs(n1 - n2)] = ['(x - {:.1f}) ** 2 + (y - {:.1f}) ** 2 = {:.1f} ** 2'.format(x0, y0, R).replace('- -', '+ '), z[0], z[1], z[2], n1, n2, n3]
 
print('Окружность:', minimum[min(minimum)][0])
print('Три точки, определяющие окружность:', str(minimum[min(minimum)][1]) + ',',  str(minimum[min(minimum)][2]) + ',', minimum[min(minimum)][3])
print('Всего кол-во точек, принадлежащих окружности:', minimum[min(minimum)][6])
print('Кол-во точек внутри круга:', minimum[min(minimum)][4])
print('Кол-во точек вне круга:', minimum[min(minimum)][5])

@Marinero · 29.02.2016, 01:40

А это ничего, что через 3 точки можно провести одну (и только 1) единственную окружность, центр которой лежит на перпендикулярах к серединам сторон вписанного треугольника?

@vdm_mar · 29.02.2016, 01:43

Мне легче было набросать формулу. 5 мин. А по треугольникам лезть в гугл, искать уравнение перпендикуляра. А что? все-таки ошибся?

@Marinero · 29.02.2016, 01:49

Нет. Просто условие какое-то непонятное…

@dondublon · 29.02.2016, 11:11

Сообщение от vdm_mar

Мне легче было набросать формулу. 5 мин. А по треугольникам лезть в гугл, искать уравнение перпендикуляра.

Вы вообще поняли, что вам сказали?
Ясен пень, перпендикуляр вам понадобится, никуда не от него денетесь.

@vdm_mar · 29.02.2016, 11:17

Сообщение от dondublon

перпендикуляр вам понадобится

Уже не понадобился

@vdm_mar · 29.02.2016, 11:34

любопытства ради прикрутил модуль random, он набирает массив точек, вот, например:

[(39, 49), (96, 17), (84, 69), (86, 62), (77, 100), (44, 83), (25, 79), (28, 51), (62, 8), (25, 23), (37, 75), (21, 74), (99, 4), (77, 38), (98, 41), (17, 59), (0, 96), (9, 52), (58, 87), (60, 0)]

Окружность: (x - 55.7) ** 2 + (y - 42.1) ** 2 = 42.3 ** 2
Три точки, определяющие окружность: (98, 41), (17, 59), (60, 0)
Всего кол-во точек, принадлежащих окружности: 3
Кол-во точек внутри круга: 8
Кол-во точек вне круга: 9

А вот график (некоторые точки закрылись табличками):

@dondublon · 29.02.2016, 12:39

vdm_mar, кажется, понял, что имелось в виду

Интересно, как вы находите центр окружности без перпендикуляра. (В код вникать неохота.)

@vdm_mar · 29.02.2016, 12:41

Сообщение от dondublon

как вы находите центр

Система трех уравнений, набросал "от руки" в блокнотике, подставил в код. Пяти минут не заняло.
На деление на "ноль" только нарвался, это когда три точки на одной прямой. Но поставил исключение.

@dondublon · 29.02.2016, 13:15

Сообщение от vdm_mar

Система трех уравнений, набросал "от руки" в блокнотике, подставил в код.

Ну так уравнения-то, наверное, перпендикуляров?

@vdm_mar · 29.02.2016, 13:24

Сообщение от dondublon

наверное, перпендикуляров?

уравнение окружности (x - x0) ** 2 + (y - y0) ** 2 = R ** 2

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases} & \text{(x1 - x0) ** 2 + (y1 - y0) ** 2 = R ** 2 } \\ & \text{(x2 - x0) ** 2 + (y2 - y0) ** 2 = R ** 2 } \\ & \text{(x3 - x0) ** 2 + (y3 - y0) ** 2 = R ** 2 } \end{cases}$

Отсюда вывел зависимости y0, x0, R от координат трех точек и поставил в код

@dondublon · 29.02.2016, 13:46

Хитро, признаю.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@artibmstu 0 / 0 / 0 Регистрация: 04.12.2015 Сообщений: 16

	Найти окружность проходящую через три точки на плоскости 28.02.2016, 21:57. Показов 9240. Ответов 12 Метки нет (Все метки) Задано множество точек на плоскости. Найти такую окружность, которая проходит через три точки и разница между количеством точек внутри и снаружи минимальна 0

@Marinero 2796 / 2039 / 682 Регистрация: 02.03.2015 Сообщений: 6,509
	29.02.2016, 01:40
	А это ничего, что через 3 точки можно провести одну (и только 1) единственную окружность, центр которой лежит на перпендикулярах к серединам сторон вписанного треугольника? 0

@vdm_mar 39 / 39 / 25 Регистрация: 25.10.2015 Сообщений: 102
	29.02.2016, 01:43
	Мне легче было набросать формулу. 5 мин. А по треугольникам лезть в гугл, искать уравнение перпендикуляра. А что? все-таки ошибся? 0

@Marinero 2796 / 2039 / 682 Регистрация: 02.03.2015 Сообщений: 6,509
	29.02.2016, 01:49
	Нет. Просто условие какое-то непонятное… 0

@vdm_mar 39 / 39 / 25 Регистрация: 25.10.2015 Сообщений: 102
	29.02.2016, 11:34
	любопытства ради прикрутил модуль random, он набирает массив точек, вот, например: [(39, 49), (96, 17), (84, 69), (86, 62), (77, 100), (44, 83), (25, 79), (28, 51), (62, 8), (25, 23), (37, 75), (21, 74), (99, 4), (77, 38), (98, 41), (17, 59), (0, 96), (9, 52), (58, 87), (60, 0)] Окружность: (x - 55.7) 2 + (y - 42.1) 2 = 42.3 ** 2 Три точки, определяющие окружность: (98, 41), (17, 59), (60, 0) Всего кол-во точек, принадлежащих окружности: 3 Кол-во точек внутри круга: 8 Кол-во точек вне круга: 9 А вот график (некоторые точки закрылись табличками): Миниатюры 0

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	29.02.2016, 12:39
	vdm_mar, кажется, понял, что имелось в виду Интересно, как вы находите центр окружности без перпендикуляра. (В код вникать неохота.) 0

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	29.02.2016, 13:46
	Хитро, признаю. 0

Опции темы