Форум Flasher.ru - минимальная окружность

Страница 1 из 3

Показывать 40 сообщений этой темы на одной странице

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- Флейм (http://www.flasher.ru/forum/forumdisplay.php?f=53)

- - минимальная окружность (http://www.flasher.ru/forum/showthread.php?t=214299)

undefined

04.06.2017 11:12

минимальная окружность

Имеется облако точек x[i],y[i].Требуется найти минимальную окружность,охватывающую все точки.
NB:Сложность алгоритма не должна зависеть от расположения точек.

Tails

04.06.2017 16:02

1. Найти среднее арифметическое (позицию) точек dx и dy.
2. Найти максимальный радиус среди точек до этих dx, dy.
Два прохода по массиву. Вроде, должно работать.

ZackMercury

04.06.2017 16:34

Tails, неверно :3
https://pp.userapi.com/c639723/v6397...4koAaegyWA.jpg

ZackMercury

04.06.2017 16:47

Вложений: 1

Среднее арифметическое точек(оранжевый круг)

Test.swf (16.7 Кб)

undefined

04.06.2017 17:08

Цитата:

Tails, неверно :3

Да, окружность выходит неминимальная.

ZackMercury

04.06.2017 17:09

Окружность вообще не выходит, ибо 1) центр не найден 2) радиус не найден.

(если что, если через 5 точек возможно провести окружность, то только одну)

undefined

04.06.2017 17:23

Вложений: 1

Цитата:

Сообщение от ZackMercury (Сообщение 1200862)

Окружность вообще не выходит, ибо 1) центр не найден 2) радиус не найден.

Алгоритм Tails даст вполне конкретный центр и радиус.Другой вопрос что они неверные будут,кстати, неминимальность хорошо видна если точки раскидать по эллипсу
Вложение 32807

undefined

04.06.2017 17:25

Цитата:

(если что, если через 5 точек возможно провести окружность, то только одну)

Требование чтоб окружность проходила через все точки не стоит :)

ZackMercury

04.06.2017 17:34

Ну тогда условие задачи некорректно. "Содержащую точки" буквально означает, что все точки должны принадлежать этой окружности.

undefined

04.06.2017 17:41

Думал и так ясно что невозможно провести окружность через произвольные n точек.
ПС:для однозначного задания окружности достаточно 3 точки,а не 5.
ПС2: поправил условие.

Часовой пояс GMT +4, время: 19:13.

Страница 1 из 3

Показывать 40 сообщений этой темы на одной странице

Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.