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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

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

	Найти окружность проходящую через три точки на плоскости 28.02.2016, 21:57. Показов 9359. Ответов 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 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	29.02.2016, 12:39
	vdm_mar, кажется, понял, что имелось в виду Интересно, как вы находите центр окружности без перпендикуляра. (В код вникать неохота.) 0

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

Опции темы