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

miksoftmiksoft1) перебором найти две самые далеко отстоящие друг от друга точки.Тоже можно оптимизировать - проверять только те точки, которые находятся в пределах внешнего квадрата, но не находятся в пределах внутреннего квадрата. Внешний квадрат образова координатами самых крайних точек по каждой из осей. Внутренний меньше внешнего в (корень из 2) раз.
интерестно. нужно попробовать теперь это все в кучу собрать.
Спасибо!

miksoftNezarТем более, мне кажется, возможен вариант когда единственно возможная минимальная окружность может быть постоена только по двум точкам.Хм. Да, вы правы, посыпаю свою голову пеплом. :)

Хотя есть мысль как это исправить:
1) перебором найти две самые далеко отстоящие друг от друга точки. Это даст нам окружность с центром посередине между этими точками.
2) перебором искать третью точку, которая дает минимальный радиус описанной окружности треугольника.
3) если третья точка получилась в пределах окружности из пункта 1, то результатом будет окружность из пункта 1. Иначе - окружность из пункта 2.

Можно попытаться оптимизировать - в пункте 2 учитывать сразу только точки, лежащие вне окружности из пункта 1.

По ходу вопрос - описанная окружность всегда будет проходить через две самые удаленные друг от друга точки?

авторПроверим решение для (1,0) (0,1) и (2,1) - тогда центр должен иметь координаты (1,1)
x1 = 1, x2 = 0, x3 = 2, y1 = 0 , y2 = 1, y3 = 1
D = (0-1)(1-0) - (2-1)(1-0) = -1 - 1 = -2
x2^2 + y2^2 = 1, x1^2 + y1^2 = 1, x3^2+y3^2 = 5
2Dx0 = (1-0) - 5 = -4
2Dy0 = -1 + 5(0-1) + 2 = -4
x0 = 1, y0 =1
Таким образом имеем формулы для определения (x0,y0) по трем точкам.

Подскажите а каким "таким образом"
Как получилось что x0 = 1, y0 =1 ?

мне нужно решить эту задачу с одной целью - автоматизировать вписывание картинок в круг )
приблизительное решение может и подойдет - вопрос только в том - на сколько оно приблизительное.
И еще вопрос - может получится разобрать алгоритм, который приведен на предыдущей странице. В принципе я в нем только пару строк не понимаю, напрмер
dot(u,v) ((u).x * (v).x + (u).y * (v).y) - что здесь находится? тем более что сюда посылается один параметр для u и v...

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

исходник - некая картинка (думаю не больше 120x120 пикселей) в формате png, которая имеет прозрачные участки.
одной программкой я записываю в текстовый файл параметры каждого пикселя
выдираю от сюда координаты непрозрачных пикселей и собственно с ними начинаю работать.

когда получаю чентр описанного круга (эх...)
расширяю холст, сдвигаю картинку и вуаля (это уже работает)
.....
посему чем меньше будет охватывающий круг - тем крупнее будет картинка - что есть - главное.

miksoft,

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

такой способ уже проверил (написал код)- и он работает - если конечно можно описать окружность по двум точкам, а так можно - далеко не всегда сделать.

miksoft,

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

miksoftNezar,

можете показать пример исходной и конечной картинки?

Вы то соглашаетесь со мной, что конечным результатом будет прямоугольная картинка, то опять хотите круг. Совсем меня запутали...

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

про пики согласен - но это уже оптимизация, а оптимизировать пока нечего ((

пример не знаю как выкладывать картинки - поэтому самый простой вариант.

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

прикрепил
1.png пример исходной картинки
ex.png - картинка которая получилось в результате работы уже работающей программы

вот такое нужно проделать с большим количеством разнообразных картинок

Nezar,

к сожалению я не матиматик, а... вообщето водитель ), поэтому все эти выпуклости никогда не пойму)

из того что я за 2 дня начитал я понял что мне нужно уйти от фигур и просто описать набор точек - это проще всего (наверное)
а самое обидное что я нашел три алгоритма как это делается но все они на С++ что для меня темный лес и кучу непонятных теоретических описаний.

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

Nezar,

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

mayton,

Хорошо. Давайте впишем "сердце" в окружность. Две самые удаленные точки ничего не дадут.
Искать круг только по двум точкам - тоже не верно т.к. есть вариант когда такого круга просто не существует - пример - равносторонний треугольник (да вообще треугольник)

щас попробую совместить поиск путем одновременного перебора окружностей по двум и трем точкам - но сложность алгоритма будет N в 4 степени что оочень долго, но.... вобщем пока пробую это.

mayton,

Видимо я чтото не понял.
Что такое - "поперечник"
для рисунка в виде сердца он где будет?