Chris Maunder Ответов: 16

Задача кодирования: наименьший круг, окружающий набор точек

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

Бонусные баллы начисляются за использование интересного языка. Или интересное использование языка.

Что я уже пробовал:

Чтобы немного отдохнуть.

Последний вызов[^] победителем стал Джон Макки, но только в том случае, если он пообещает никогда больше этого не делать. Джон: напишите Шону ваши контактные данные, и что-нибудь подходящее будет выслано в ответ.

Jon McKee

"Бонусные баллы начисляются за использование интересного языка". "только если он пообещает никогда больше этого не делать".: (хорошо...: P

Rajesh R Subramanian

Мистер Маундер, не могли бы вы исправить форматирование в моем сообщении о решении? :(

Ralf Meier

Вы могли бы сделать это сами.
Используйте функцию "улучшить решение", и вы сможете изменить то, что написали ...

Rajesh R Subramanian

Ах, спасибо. Прошло так много времени с тех пор, как я писал на форумах вопросов и ответов, что я действительно забыл об этом. :смеяться:

0x01AA

"Или интересное использование языка": что вы думаете о Schwizerdütsch? Швейцарский Немецкий - Википедия[^]

PIEBALDconsult

Есть образцы данных и результаты тестов?

Jon McKee

Я думаю, что на этот раз все зависит от нас.

PIEBALDconsult

Увы.

Graeme_Grant

Я разместил электронную таблицу excel, где вы можете разместить точки и визуализировать результаты. Это вам поможет? ;)

Patrice T

Похоже, что официальные образцы наборов данных были бы хорошей идеей, чтобы избежать неправильных решений.

Graeme_Grant

Они могут использовать это сводная таблица[^] чтобы [вручную] ввести баллы и результаты и посмотреть, как они проходят.

Patrice T

Да, я знаю, но они не знают.
См. Решение 12
вы его уже видели.

Graeme_Grant

Я видел и комментировал. Я поделился [ручной] электронной таблицей (с визуальным пособием), поскольку, похоже, у них нет способа проверить результаты.

Kornfeld Eliyahu Peter

Допустимо ли размещать статью в качестве ответа? Я просто сделал много изображений и математических объяснений, которыми хотел бы поделиться...

Chris Maunder

Абсолютно

16 Ответов

Рейтинг:
76

PIEBALDconsult

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

WITH [points] AS
(
  SELECT 0.50 [X] , 0.75 [Y]
  UNION ALL
  SELECT 1.25 [X] , 0.85 [Y]
  UNION ALL
  SELECT 3.86 [X] , 2.19 [Y]
  UNION ALL
  SELECT 2.11 [X] , 4.65 [Y]
  UNION ALL
  SELECT 1.17 [X] , 2.01 [Y]
  UNION ALL
  SELECT 3.19 [X] , 1.63 [Y]
)
SELECT A.[X] 
, A.[Y] 
, B.[Xmid]
, B.[Ymid]
, SQRT(POWER(A.[X]-B.[Xmid],2)+POWER(A.[Y]-B.[Ymid],2)) [Radius] 
FROM [points] A
CROSS JOIN (
  SELECT (MIN([X])+MAX([X]))/2.0 [Xmid] , (MIN([Y])+MAX([Y]))/2.0 [Ymid]
  FROM [points]
) B
ORDER BY [Radius] DESC
OFFSET 0 ROWS
FETCH FIRST 1 ROW ONLY


X    Y    Xmid     Ymid     Radius
0.50 0.75 2.180000 2.700000 2.5738881094562


(Мужчина должен знать свои ограничения.)

Patrice T

Привет,
Боюсь, ваше решение неверно.
Центр окружности равен {1.73, 2.53}, а радиус-2.16.
На круге есть минимум 2 точки.

PIEBALDconsult

Я сказал "неоптимально", есть ли какие-то точки за пределами круга?

Patrice T

Хорошо Но является ли это решением проблемы кодирования ?

PIEBALDconsult

Да, просто не оптимальный вариант, и я это знаю.

Chris Maunder

Величественный в своем ужасе.

Graeme_Grant

Хорошая попытка PIEBALDconsult. Я не запускал ваш код, но, глядя на вашу формулу, вы не получите правильный наименьший окружающий круг для этих точек: (0.5,0.75), (1.25,0.85), (3.86,2.19), (11,7), (1.17,2.01), (15,1.63), (4.87,10). Вы можете проверить это с помощью этого сводная таблица[^]

PIEBALDconsult

Это потому, что я не очень старался. Это вне моей зоны комфорта.

Graeme_Grant

Мой тоже, но мой сын помешан на математике,так что командные усилия... Было весело изучать Powershell & F#. Powershell теперь я буду использовать гораздо больше, но F# - это еще одна игра в мяч.

Maciej Los

Мне это нравится!

Stefan_Lang

Мне нравится идея использования движка базы данных для решения математической задачи - в конце концов, движки баз данных обычно очень оптимизированы. Хотя ваше решение не обеспечивает оптимального решения, это проблема используемого вами алгоритма, а не ограничение SQL. Интересно, насколько хорошо оптимальное решение SQL будет сравниваться с решением , написанным, скажем, на C++, C# или подобном.

PIEBALDconsult

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

Stefan_Lang

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

Это ограниченное количество шагов, так что это должно быть выполнимо.

конечно, вам нужно указать формулу для прямого вычисления центра и диапазона круга, определенного 3 точками, что технически не сложно, но может привести к некоторым длинным формулам. Но я верю, что вы можете определить функции в SQL для такого рода вещей?[/редактировать]

Рейтинг:
71

Patrice T

Мое решение - это не программное решение: я просто использовал Excel и решатель. Это считается ?

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

Sheet:
A1= "Points X"
B1= "Points Y"
C1= "Distance"
D1= "Center X"
E1= "Center Y"
F1= "Radius"
F2= MAX(C2:C7)

Data set
A2=0.5
B2=0.75
C2=SQRT((D$2-A2)^2+(E$2-B2)^2)
...

Solver
Minimize: F2
Variables: D2:E2


Набором данных:
{ { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } }
Центр круга: {1.73, 2.53}
Радиус: 2,16
Обратите внимание, что 3 точки в наборе данных находятся на краю окружности.

Набором данных:
{ { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 }, {4.87, 5.39}}
Центр круга: {2.69, 3.06}
Радиус: 3.19
Обратите внимание, что 2 точки в наборе данных находятся на краю окружности.

Graeme_Grant

Вы уверены, что ваши результаты верны? Центр окружности и радиус не могут быть одинаковыми, если второй набор данных включает 4,87, 5,39. Точка 4.87, 5.39 находится в углу ограничивающего прямоугольника и вне круга. Здесь[^] является то, что она должна выглядеть.

** Обновление: проверьте мое решение. Я добавил ссылку на электронную таблицу Excel с диаграммами в реальном времени для визуализации результатов.

Patrice T

Упс, слишком быстрая операция копирования / вставки для второго набора данных.
Хороший улов. Спасибо,что заметили.
У меня также есть график в моем листе Excel.

Patrice T

- Вы уверены ?
Я получаю 2 очка на круге.

Patrice T

Какая проблема имеет мое решение ?

Patrice T

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

Graeme_Grant

Я удалил свои комментарии после того, как поближе посмотрел на Excel Solver. Подход "грубой силы" интересен, но он делает работу за вас, немного похож на просьбу кого-то другого сделать вашу работу/домашнее задание, как решение 4. ;)

Рейтинг:
62

Graeme_Grant

Вот мой C# (6.0) & VB.Net вклад, который вычисляет как центр, так и радиус наименьшей окружности вокруг набора 2D-точек в 2 строках кода благодаря Linq!
Обновление: Просто для удовольствия я также добавил версию C# 7.0, используя новые кортежи, и это очень круто! Превращает спагетти C#6 во что-то очень легкое для чтения. Не могу дождаться официального релиза!

Вот решение с 5 версии на 4 разных языках на языке C# (6.0 &амп; 7.0 версии), VB.Net язык F#, &ампер; усилитель; оболочки PowerShell (Ф# &ампер; усилитель; оболочки PowerShell узнали сегодня на лету!). :) Используемая процедура расчета проверки основана на приведенной выше формуле Артура В. Ратца...


class Program
{
    static void Main(string[] args)
    {
        var points = new List<Tuple<double, double>>()
    {
        new Tuple<double, double>(0.5, 0.75 ),
        new Tuple<double, double>(1.25, 0.85),
        new Tuple<double, double>(3.86, 2.19),
        new Tuple<double, double>(2.11, 4.65),
        new Tuple<double, double>(1.17, 2.01),
        new Tuple<double, double>(3.19, 1.63),
        new Tuple<double, double>(4.87,5.39)
    };

        var center = new Tuple<double, double>((points.Min(v => v.Item1) + points.Max(v => v.Item1)) / 2, (points.Min(v => v.Item2) + points.Max(v => v.Item2)) / 2);

        var radius = points.Max(pt => Math.Round(Math.Sqrt(Math.Pow(pt.Item1 - center.Item1, 2) + Math.Pow(pt.Item2 - center.Item2, 2)), 5));

        var IsInCircle = new Func<Tuple<double, double>, bool>((pt) => Math.Pow(pt.Item1 - center.Item1, 2) + Math.Pow(pt.Item2 - center.Item2, 2) <= Math.Pow(radius, 2));

        Console.WriteLine($"RADIUS: {radius}  Center: ({center.Item1},{center.Item2})\r\n");

        foreach (var pt in points)
            Console.WriteLine($"({pt.Item1},{pt.Item2}) is {(IsInCircle(pt) ? "inside" : "outside")} the circle");

        Console.WriteLine("\r\n-- Press any key to exit --");
        Console.ReadKey();
    }
}

** Обновление №2: Добавлена версия C# 7.0 (RC)
[Примечание: требуется VS 2017 RC & System. ValueTuple Nuget]

class Program
{
    static void Main(string[] args)
    {
        var points = new List<(double x, double y)>() { (0.5, 0.75), (1.25, 0.85), (3.86, 2.19), (2.11, 4.65), (1.17, 2.01), (3.19, 1.63), (4.87, 5.39) };

        (double x, double y) center = ((points.Min(v => v.x) + points.Max(v => v.x)) / 2, (points.Min(v => v.y) + points.Max(v => v.y)) / 2);
        double radius = points.Max(pt => Math.Round(Math.Sqrt(Math.Pow(pt.x - center.x, 2) + Math.Pow(pt.y - center.y, 2)), 5));

        var IsInCircle = new Func<(double x, double y), bool>((pt) => Math.Pow(pt.x - center.x, 2) + Math.Pow(pt.y - center.y, 2) <= Math.Pow(radius, 2));

        Console.WriteLine($"RADIUS: {radius}  Center: ({center.x},{center.y})\r\n");

        foreach (var pt in points)
            Console.WriteLine($"({pt.x},{pt.y}) is {(IsInCircle(pt) ? "inside" : "outside")} the circle");

        Console.WriteLine("\r\n-- Press any key to exit --");
        Console.ReadKey();
    }
}

** Обновление №1: добавлена версия VB

Sub Main()

    Dim points = New List(Of Tuple(Of Double, Double)) _
({
    New Tuple(Of Double, Double)(0.5, 0.75),
    New Tuple(Of Double, Double)(1.25, 0.85),
    New Tuple(Of Double, Double)(3.86, 2.19),
    New Tuple(Of Double, Double)(2.11, 4.65),
    New Tuple(Of Double, Double)(1.17, 2.01),
    New Tuple(Of Double, Double)(3.19, 1.63),
    New Tuple(Of Double, Double)(4.87, 5.39)
})

    Dim center As New Tuple(Of Double, Double)((points.Min(Function(v) v.Item1) + points.Max(Function(v) v.Item1)) / 2, (points.Min(Function(v) v.Item2) + points.Max(Function(v) v.Item2)) / 2)

    Dim radius = points.Max(Function(pt) Math.Round(Math.Sqrt(Math.Pow(pt.Item1 - center.Item1, 2) + Math.Pow(pt.Item2 - center.Item2, 2)), 5))

    Dim IsInCircle = New Func(Of Tuple(Of Double, Double), Boolean)(Function(pt) Math.Pow(pt.Item1 - center.Item1, 2) + Math.Pow(pt.Item2 - center.Item2, 2) <= Math.Pow(radius, 2))

    Console.WriteLine($"RADIUS: {radius}  Center: ({center.Item1},{center.Item2}){vbCrLf}")

    For Each pt In points
        Console.WriteLine($"({pt.Item1},{pt.Item2}) is {(If(IsInCircle(pt), "inside", "outside"))} the circle")
    Next

    Console.WriteLine($"{vbCrLf}-- Press any key to exit --")
    Console.ReadKey()

End Sub


** Обновление №4: версия F#
[Примечание: благодаря Джону Макки я окунулся в F#, и это стало результатом моего ускоренного курса по изучению второго нового языка за один день. Поэтому, пожалуйста, простите меня, если есть лучший способ...]
open System

    let points = [(0.5, 0.75);
                  (1.25, 0.85); 
                  (3.86, 2.19); 
                  (2.11, 4.65); 
                  (1.17, 2.01); 
                  (3.19, 1.63); 
                  (4.87, 5.39)]

        let minx,miny,maxx,maxy = 
            points |> List.fold (fun (mx,my,Mx,My) (ax,ay) -> 
                 min mx ax, min my ay,
                 max Mx ax, max My ay) (999.0,999.0,-999.0,-999.0)

        let center:float*float = (minx + maxx) / 2.0, (miny + maxy) / 2.0

        let radius = 
            points |> List.fold (fun (mx) (ax, ay) ->
                max mx (System.Math.Round(sqrt((ax - fst center)**2.0 + (ay - snd center)**2.0), 5))) (0.0)

        let ReportResults =
           printfn "RADIUS %A  Center %A\r\n" radius center
           for pt in points do
                printfn "%A is %s the circle" pt (if ((fst pt - fst center)**2.0 + (snd pt - snd center)**2.0 <= radius**2.0) then "inside" else "outside")

[<EntryPoint>]
let main argv = 

    printfn"\r\n-- Press any key to exit --";
    Console.ReadKey() |> ignore;
    0

Выходы:
RADIUS: 3.18695  Center: (2.685,3.07)

(0.5,0.75) is inside the circle
(1.25,0.85) is inside the circle
(3.86,2.19) is inside the circle
(2.11,4.65) is inside the circle
(1.17,2.01) is inside the circle
(3.19,1.63) is inside the circle
(4.87,5.39) is inside the circle

-- Press any key to exit --


** Обновление №3: версия Powershell
[Примечание: это моя первая попытка использовать Powershell, поэтому, пожалуйста, простите меня, если есть более быстрый способ...] 

$points = [System.Tuple]::Create(0.5, 0.75),
          [System.Tuple]::Create(1.25, 0.85),
          [System.Tuple]::Create(3.86, 2.19),
          [System.Tuple]::Create(2.11, 4.65),
          [System.Tuple]::Create(1.17, 2.01),
          [System.Tuple]::Create(3.19, 1.63),
          [System.Tuple]::Create(4.87, 5.39)
$minX = 9999.0; $minY = 9999.0

$points | foreach {$minX=[math]::Min($minX, $_.item1); $maxX=[math]::Max($maxX, $_.item1); $minY=[math]::Min($minY, $_.item2); $maxY=[math]::Max($maxY, $_.item2)}

$center = [System.Tuple]::Create(($minX + $maxX) / 2,($minY + $maxY) / 2)

$points | foreach {$radius=[math]::Max($radius, [math]::round([math]::sqrt([math]::pow($_.item1 - $center.item1,2)+[math]::pow($_.item2 - $center.item2,2)),5))}

echo "RADIUS: $radius  Center: $center"
$points | foreach {$t=[math]::pow($_.item1-$center.item1,2)+[math]::pow($_.item2-$center.item2,2) -le [math]::pow($r,2); if($t) {$p="inside"} else {$p="outside"}; echo "$_ is $p the circle"}

Выходы:
RADIUS: 3.18695  Center: (2.685, 3.07)
(0.5, 0.75) is inside the circle
(1.25, 0.85) is inside the circle
(3.86, 2.19) is inside the circle
(2.11, 4.65) is inside the circle
(1.17, 2.01) is inside the circle
(3.19, 1.63) is inside the circle
(4.87, 5.39) is inside the circle


** Обновление 5: Версия Excel с графической диаграммой для визуализации результатов
Вот такой ссылка на электронную таблицу[^] где вы можете проверить и визуализировать формулы, используемые в приведенных выше решениях.

Jon McKee

Оооо, сделайте следующую версию F#! =D (просто шутка =P)

Graeme_Grant

Ржунимагу! Спасибо за предложение... Я действительно думал об этом, но на самом деле у меня нет времени, чтобы обернуть голову вокруг F# atm... :)

Jon McKee

У тебя есть еще неделя, никаких отговорок! Лол =)

Graeme_Grant

Я работаю над очень большим проектом ATM... Может быть, я смогу найти время, чтобы выучить машинопись... :)

Jon McKee

Удачи вам в проекте! Я собирался изучить Powershell с тех пор, как услышал, что это в основном Batch++, так что эта версия мне очень интересна =)

Graeme_Grant

Я был таким же до сегодняшнего дня ... Я нашел его очень мощным и не могу дождаться, чтобы провести с ним больше времени. :)

Graeme_Grant

Укусил пулю и сделал версию F# только для тебя. Это был небольшой вызов, но он был принят и сделан. ;)

Graeme_Grant

Вот и версия Excel тоже... Скриншот из Формулы &усилитель; выход[^]

** Обновление: я разместил ссылку на обновленную электронную таблицу, где вы можете играть с цифрами и видеть результаты визуально в режиме реального времени. Наслаждайтесь! :)

Arthur V. Ratz

Боюсь, что ваше решение имеет ряд недостатков: во-первых, оно позволяет найти только один круг, а во-вторых, любые точки из набора данных не должны находиться внутри границы круга, чего вы никогда не добьетесь с помощью своего алгоритма. Формула" геометрического среднего", на которую опирается ваш алгоритм, не позволяет найти желаемое приближение, и поэтому невозможно найти соответствующий радиус окружности, охватывающей все точки внутри и *не* на ее границе.

Недавно я внес некоторые улучшения в свой код, так что он всегда позволяет найти круг, который окружает все точки в наборе данных. Правильное значение радиуса *не * 3.18695, * но * r = 3.30, чтобы охватить все точки, и это лучшее приближение. Мне очень жаль, но я голосую 3 за оба ваших решения 5 и 7. Спасибо, что прочитали мой комментарий.

Graeme_Grant

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

Решение 7 - это более точная версия, которая не имеет погрешности, найденной в этом решении.

Arthur V. Ratz

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

Arthur V. Ratz

А также смотрите мою графическую диаграмму, которая иллюстрирует правильное решение этой проблемы: http://imgur.com/a/Oo0ah

Graeme_Grant

Пожалуйста, найдите время, чтобы перечитать вызов. Очень многое позволено.

Arthur V. Ratz

Извините, вы правы, так как "круг может пересекать точки в наборе"...

Graeme_Grant

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

Graeme_Grant

Решение 7 правильно дает наименьший круг для всех наборов данных, примененных к нему. Заслуживает лучшего, чем "3". Я считаю, что из моего собственного тестирования это единственное решение, которое в настоящее время работает. Я думаю, что вы можете сказать, что я немного предвзят. ;)

Graeme_Grant

Задача гласит:" определите центр и радиус наименьшего круга "и"круг может пересекать точки в наборе". Вызов является единственным, а не множественным запросом, и пересечение допускается.

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

- Дьявол кроется в деталях..."

Arthur V. Ratz

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

Graeme_Grant

Это говорит о том, что ваша погрешность очень велика. Как было сказано выше, окружности имеют фиксированный радиус, поэтому допустим только один охватывающий наименьший круг. Т. е.: вы можете вращать круг, но радиус и центр остаются прежними. :)

Другое дело, если бы нас попросили использовать овалы....

Arthur V. Ratz

Моя погрешность не очень велика, так как вы вряд ли могли бы найти круг с меньшим радиусом, чем тот, который показан здесь: http://imgur.com/a/Oo0ah, имеющий радиус 3,3.

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

Об эллипсах мы просто не говорим.

Graeme_Grant

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

Рейтинг:
28

Richard MacCutchan

очевидное решение:

Пожалуйста, сэр, посмотрите мою проблему, описанную по адресу Задача кодирования: наименьший круг, окружающий набор точек[^]. Мне нужен код uregent для моего проекта.

Извини, не удержался.

Tachyonx

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

Chris Maunder

Ты получаешь пол-очка.

Jon McKee

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

Patrice T

Мы не делаем тебе домашнее задание ... :-)
Я тоже не мог устоять.

Graeme_Grant

Мне определенно казалось, что мы делаем чью-то домашнюю работу...

Patrice T

ЛОЛ

CPallini

5. извините, не удержался.

Graeme_Grant

Жаль, что, поскольку это "вызов кодированию", "никакого кода "и" только юмор " не подходят...

Рейтинг:
2

JohnLBevan

Действительно простое решение PowerShell:

$Coords = @(
    @(100,50)
    ,@(50,50)
    ,@(10,30)
    ,@(100,30)
    ,@(102,90)
    ,@(80,60)
    ,@(40,110)
)

$center = $Coords | %{
    $a = $_
    $Coords | %{
        $b = $_
        $x = $a[0] - $b[0]
        $y = $a[1] - $b[1]
        $d = [Math]::Pow([Math]::Pow($x,2) + [Math]::Pow($y,2),1/2)
        (new-object -TypeName PSObject -Property @{
            Distance = $d
            X = ($a[0] + $b[0]) / 2.0
            Y = ($a[1] + $b[1]) / 2.0
        })
    }
} | sort Distance -descending | select -First 1



#code to draw this
[reflection.assembly]::LoadWithPartialName("System.Windows.Forms") | out-null
[reflection.assembly]::LoadWithPartialName("System.Drawing") | out-null
$container = new-object Drawing.SolidBrush green
$point = new-object Drawing.SolidBrush black
$form = New-Object Windows.Forms.Form
$formGraphics = $form.createGraphics()
$form.add_paint({
    $formGraphics.FillEllipse($container, ($center.X - $center.Distance/2), ($center.Y - $center.Distance/2), $center.Distance, $center.Distance) #adjust to use upper left instead of center of circle
    $Coords | %{$formGraphics.FillEllipse($point, ([int]$_[0]), ([int]$_[1]), 10, 10)}
})
$form.ShowDialog()

Рейтинг:
2

Vladislav Kulikov

В зависимости от данных круг "решения" будет определяться либо
а) две точки (эти две точки определяют диаметр окружности) [^]
Б) или три точки (эти три точки находятся на круге "решение") [^]

Это говорит о том, что мы можем сделать следующее:

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

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

Код ниже будет читать, разделенных пробелами, данные точки и выведите через пробел кружок в центре X и Y и радиус окружности :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct point {
    double  x, y;
} point_t;

static int err ( const char *msg, int code ) {
    fputs ( msg, stderr );
    return code;
}

static double distance ( point_t *p1, point_t *p2 ) {
    double dx = p1->x - p2->x;
    double dy = p1->y - p2->y;
    return sqrt(dx*dx + dy*dy);
}

// this one will find a pair of points with a maximum
// distance between them, storing their indicies into
// i1 and i2 respectively
static double search_max_distance (
    point_t *points,
    size_t n,
    size_t *_i,
    size_t *_j
) {
    size_t  i, j;
    double  max_d = 0.0;
    *_i = *_j = 0;
    for ( i = 0; i < n; i++ )
    for ( j = i+1; j < n; j++ ) {
        double  d = distance(points+i, points+j);
        if ( d > max_d ) {
            max_d = d;
            *_i = i;
            *_j = j;
        }
    }
    return max_d;
}

// circle through 3 points voodoo
// http://mathforum.org/library/drmath/view/54323.html
// returns radius of a circle, fills 'center' point
static double circle_vvv (
    point_t *p1,
    point_t *p2,
    point_t *p3,
    point_t *center,
    double  line_threshold
) {
    double x1=p1->x, x2=p2->x, x3=p3->x;
    double y1=p1->y, y2=p2->y, y3=p3->y;
    double temp = x2*x2 + y2*y2;
    double bc = (x1*x1 + y1*y1 - temp) / 2.0;
    double cd = (temp - x3*x3 - y3*y3) / 2.0;
    double det = (x1-x2)*(y2-y3) - (x2-x3)*(y1-y2);
    if ( fabs(det) < line_threshold ) {
        // assume they are on a single line
        return 0.0;
    }
    center->x = (bc*(y2-y3) - cd*(y1-y2)) / det;
    center->y = ((x1-x2)*cd - (x2-x3)*bc) / det;
    return distance(center, p1);
}

int main() {
    double line_threshold = 1e-7, min_radius;
    point_t *points = NULL, min_center, p;
    size_t n = 0, n_alloc = 0, i, j, k, l, n_circles;

    // read all points into dynamically allocated memory
    while ( scanf ( " %lE %lE", &p.x, &p.y ) == 2 ) {
        if ( n == n_alloc ) {
            n_alloc += 1000;
            points = realloc ( points, sizeof*points * n_alloc );
            if ( !points ) return err ( "no memory?!!", 1 );
        }
        points[n] = p;
        n++;
    }

    // PART ZERO: couple of corner cases
    if ( n == 0 ) return err ( "no points", 2 );
    else if ( n == 1 ) {
        min_center = points[0];
        min_radius = 0.0;
        goto success;   // I am going to regret this after seeing comments...
    }

    // PART I: look for a 'two point win' - get two most distant points, assume
    // we've found a circle diameter and check if all other points are within
    // this particular circle
    min_radius = search_max_distance ( points, n, &i, &j ) / 2.0;
    min_center.x = (points[i].x + points[j].x) / 2.0;
    min_center.y = (points[i].y + points[j].y) / 2.0;
    for ( k = 0; k < n; k++ ) {
        if ( k == i || k == j ) continue;
        if ( distance(&min_center, points+k) > min_radius ) break;
    }
    if ( k == n ) goto success; // I just can't help myself...

    // PART II: continue with probing all circles defined by a set of
    // circles defined by point triplets
    n_circles = 0;
    for ( i = 0; i < n; i++ )
    for ( j = i+1; j < n; j++ )
    for ( k = j+1; k < n; k++ ) {
        point_t center;
        double  radius = circle_vvv (
            points+i,
            points+j,
            points+k,
            ¢er,
            line_threshold
        );
        if ( radius == 0.0 ) continue;  // skip an undefined circle
        for ( l = 0; l < n; l++ ) {
            if ( l == i || l == j || l == k ) continue;
            if ( distance(¢er, points+l) > radius ) break;
        }
        if ( l != n ) continue; // no fit
        if ( !n_circles || radius < min_radius ) {
            min_radius = radius;
            min_center = center;
            n_circles++;
        }
    }
    if ( !n_circles ) return err ( "weird, no solution found", 3 );
success:
    printf ( "% E  % E  % E\n", min_center.x, min_center.y, min_radius );
    return 0;
}


Учитывая привкус грубой силы в приведенном выше коде, можно фактически рассмотреть возможность объединения обеих фаз в один поиск (где 2-точечный случай рассматривается как угловой случай для 3-точечной фазы оценки кандидата). Приведенный ниже код реализует эту идею "единого потока" (конечно, будучи менее эффективным, чем вышеприведенная версия, когда дело доходит до поиска 2-точечного решения). На самом деле это первое, что я написал для вызова:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct point {
    double  x, y;
} point_t;

static int err ( const char *msg, int code ) {
    fputs ( msg, stderr );
    return code;
}

int main() {
    double line_threshold = 1e-7, min_radius;
    struct point *points = NULL, min_center, p;
    size_t n = 0, n_alloc = 0, i, j, k, l, n_circles = 0;

    // read all points into dynamically allocated memory
    while ( scanf ( " %lE %lE", &p.x, &p.y ) == 2 ) {
        if ( n == n_alloc ) {
            n_alloc += 1000;
            points = realloc ( points, sizeof*points * n_alloc );
            if ( !points ) return err ( "no memory?!!", 1 );
        }
        points[n] = p;
        n++;
    }

    // couple of corner cases
    if ( n == 0 ) return err ( "no points", 2 );
    else if ( n == 1 ) {
        min_center = points[0];
        min_radius = 0.0;
        goto success;   // I am going to regret this after seeing comments...
    }

    // brutforcing the challenge and merging a two-point and three-point
    // cases into one program flow
    for ( i = 0; i < n; i++ ) {
        for ( j = i+1; j < n; j++ ) {
            for ( k = j; k < n; k++ ) {
                double x1=points[i].x, x2=points[j].x, x3=points[k].x;
                double y1=points[i].y, y2=points[j].y, y3=points[k].y;
                double dx, dy, radius;
                struct point center;
                if ( k == j ) {
                    // minimal diameter circle through on two points
                    // (these two points define diameter in this case)
                    center.x = (x1+x2)/2.0;
                    center.y = (y1+y2)/2.0;
                } else {
                    // circle through 3 points black magic
                    // http://mathforum.org/library/drmath/view/54323.html
                    // inlined math loks weird...
                    double temp = x2*x2 + y2*y2;
                    double bc = (x1*x1 + y1*y1 - temp) / 2.0;
                    double cd = (temp - x3*x3 - y3*y3) / 2.0;
                    double det = (x1-x2)*(y2-y3) - (x2-x3)*(y1-y2);
                    double dx, dy;
                    if ( fabs(det) < line_threshold ) {
                        // assume they are on a single line and have been
                        // either covered or will be covered in future by
                        // a two point case OR it was some crazy corner case
                        continue;
                    }
                    center.x = (bc*(y2-y3) - cd*(y1-y2)) / det;
                    center.y = ((x1-x2)*cd - (x2-x3)*bc) / det;
                }
                dx = x1 - center.x;
                dy = y1 - center.y;
                radius = sqrt ( dx*dx + dy*dy );

                // check if all points are within candidate circle
                // (assume that i,j,k points are already within)
                for ( l = 0; l < n; l++ ) {
                    if ( l == i || l == j || l == k ) continue;
                    dx = points[l].x - center.x;
                    dy = points[l].y - center.y;
                    if ( dx*dx + dy*dy > radius*radius ) break;
                }
                if ( l != n ) continue;
                //fprintf ( stderr, "%E %E %E\n", center.x, center.y, radius );
                if ( !n_circles || radius < min_radius ) {
                    min_radius = radius;
                    min_center = center;
                    n_circles++;
                }
            }
        }
    }
    if ( !n_circles ) return err ( "weird, no circle found", 3 );
success:
    printf ( "% lE  % lE  % lE\n", min_center.x, min_center.y, min_radius );
    return 0;
}


Доверяй, но проверяй, правда? Обе версии представляют собой инструменты командной строки, читающие stdin и записывающие stdout. Вот тестовый стенд, использующий вызов 'system ()' для вызова двоичного файла 'circle', снабжающего его случайными точками, захватывая его выходные данные и проверяя, все ли сгенерированные точки находятся внутри круга. Кстати, это не из-за проблем с точностью, связ

Рейтинг:
2

Kornfeld Eliyahu Peter

Может быть, немного опоздал на вечеринку, но я много работал...
Задача Кодирования: Задача Наименьшего Круга[^]

Graeme_Grant

Близко, но самый маленький круг 3-го набора меньше, чем ваши результаты. Вот что мы нашли:

--------------------------------------------------------
** Тест: 3 & gt; Корнфельд Элияху Питер-Набор 3-5 локаций ....

Радиус: 5 Центр: (5,2)

(2,-2) находится на круге
(5,1) находится внутри круга
(4,3) находится внутри круга
(2,2) находится внутри круга
(8,6) находится на круге

Kornfeld Eliyahu Peter

Если вы будете следовать логике статьи, то увидите, что логика там приведет к вашему решению... точно, однако у меня есть какая-то ошибка в точке удаления функциональности и одна из внутренних точек не удалена... Я проверю его и обновлю вас и код...

Graeme_Grant

Ваш метод очень похож на наш. Я надеюсь, что вы найдете свою проблему. У меня есть несколько дополнительных наборов данных (решение 7), которые вы можете протестировать.

Kornfeld Eliyahu Peter

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

Graeme_Grant

Рад видеть, что вы исправили свою проблему! :)

Рейтинг:
2

Ralf Meier

Вот мое решение в VB :

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

Hypothenuse
треугольника) - самая длинная гипотенуза дает минимальный радиус для окружающего круга

Module Calculate_Points

    Dim myPoints As PointF() = {New PointF(1, 1), New PointF(3, 7), New PointF(5, 2), New PointF(-3, -2), New PointF(5, 5), New PointF(2, 2)}
    Dim myPoints2 As PointF() = {New PointF(0, 0), New PointF(10, 0), New PointF(0, 10), New PointF(10, 10), New PointF(5, 5), New PointF(2, 2)}

    Function GetSurroundingRadius(xyPoints As PointF()) As Double
        Dim xMin As Double = xyPoints(0).X
        Dim yMin As Double = xyPoints(0).Y
        Dim xMax As Double = xyPoints(0).X
        Dim yMax As Double = xyPoints(0).Y

        For i As Integer = 1 To xyPoints.Length - 1
            xMin = Math.Min(xyPoints(i).X, xMin)
            xMax = Math.Max(xyPoints(i).X, xMax)
            yMin = Math.Min(xyPoints(i).Y, yMin)
            yMax = Math.Max(xyPoints(i).Y, yMax)
        Next

        Dim myWidth As Double = xMax - xMin
        Dim myHeight As Double = yMax - yMin
        Dim myCenter As New PointF(myWidth / 2 + xMin, myHeight / 2 + yMin)

        Dim myRadius As Double = 0.0

        Dim AK As Double = 0.0
        Dim GK As Double = 0.0
        Dim Hyp As Double = 0.0

        For i As Integer = 0 To xyPoints.Length - 1
            GK = Math.Abs(myCenter.Y - xyPoints(i).Y)
            AK = Math.Abs(myCenter.X - xyPoints(i).X)
            Hyp = Math.Sqrt(GK ^ 2 + AK ^ 2)
            myRadius = Math.Max(Hyp, myRadius)
        Next

        Return myRadius
    End Function

    Sub Test()
        Dim r As Single = GetSurroundingRadius(myPoints2)
        Dim a = 1
    End Sub

End Module


Я постарался сделать это проще ... ;-)

tom1443

Я думаю, вы близки. Пересечение диагоналей ограничивающего прямоугольника действительно находит центр точек. Но вам нужно вычислить расстояние от этого центра до каждой точки, используя формулу расстояния, и сохранить самую длинную в качестве радиуса окружности. Если сделать радиус круга равным половине самой длинной диагонали, то получится слишком большой круг.

Ralf Meier

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

Graeme_Grant

Знаете ли вы, что для приведенного выше кода: 1. возвращает только радиус и нет центральной точки для наименьшего круга; 2. Ваш первый набор данных возвращает неправильный радиус 6.02079725, а не 5.830952; 3. 2-й (коробочный) набор данных проходит?

Рейтинг:
2

Rajesh R Subramanian

  1. Мы пытаемся найти наименьшую ограничивающую окружность произвольного числа точек на двумерной плоскости.
  2. Две точки, наиболее удаленные от центра круга, должны находиться на окружности самого круга.
  3. Это означает, что радиус окружности равен половине расстояния между точками, наиболее удаленными друг от друга.
  4. А это значит, что центр окружности является также центром этой линии, соединяющей две наиболее удаленные друг от друга точки.


#include "stdafx.h"

#include <iostream>
#include <cmath>
#include <unordered_set>

using namespace std;

class point
{
public:
	double x, y;
	point(std::unordered_set<double,double>::const_iterator &it){}
	point(double d1 =0.0, double d2=0.0) : x(d1), y(d2) {};
	point(const point& ref) :x(ref.x), y(ref.y) {}
};

bool operator==(const point& lhs, const point& rhs)
{
	return (lhs.x == rhs.x && lhs.y == rhs.y);
}

namespace std
{
	template <> struct std::hash<point>
	{
		size_t operator()(point const & x) const noexcept
		{
			return static_cast<size_t>((15 + std::hash<double>()(x.x) * 15 + std::hash<double>()(x.y)));
		}
	};
}

double dist(const point &p1, const point &p2) noexcept //computes the distance between two 2d points.
{
	return std::sqrt( fabs(p1.x - p2.x) * fabs(p1.x - p2.x) + fabs(p1.y - p2.y) * fabs(p1.y - p2.y)	);
}

int main()
{
	unordered_set<point> points{ point(0, 0), point(4, 4) };
	double result = 0.0, temp = 0.0;
	point centre;

	for (auto it = points.begin(); it != points.end(); it++)
	{
		for (auto it2 = it; it2 != points.end(); it2++)
		{
			temp = dist(*it, *it2);
			if (temp > result)
			{
				centre.x = fabs((it->x + it2->x) / 2);
				centre.y = fabs((it->x + it2->y) / 2);
				result = temp;
			}
		}
	}

	std::cout << "Radius of minimum bounding circle = " << result / 2 << endl;
	std::cout << "Centre of circle = " << centre.x << "," << centre.y << endl;
	return 0;
}

Rob Philpott

Слегка обеспокоенный тем, что я занимаюсь этой проблемой, но...

Я совершенно уверен, что утверждения 3 и 4 неверны.

Разрежьте квадрат пополам по диагонали, чтобы получился треугольник, самые дальние точки находятся на гипотенузе, так что центральная точка будет на полпути вдоль нее. Нарисуйте здесь круг r=h/2, и все 3 точки соприкоснутся с ним. Теперь немного отодвиньте острие треугольника. Он находится за пределами круга, но не влияет на самые дальние точки...

Rajesh R Subramanian

Привет, Роб, спасибо, что нашли время, чтобы прокомментировать. Вы могли бы быть здесь на 100% правы, но, исходя из того, что я понял из вашего комментария, часть «немного срезать треугольник». Если треугольник выровнен, значит, точки переместились, поэтому расчет будет недействительным. Под «окантовкой», если вы имеете в виду вращение по оси центральной точки, тогда все точки, которые уже находятся на окружности, будут вращаться ПО окружности окружности. Я также не упоминал в исходном решении, но на окружности круга могло быть больше двух точек. Однако я думаю, что это не повлияет на решение, поскольку расстояние до этой точки от центра все равно будет таким, как мы рассчитали.

Rob Philpott

Ах, было бы лучше, если бы у компьютеров были ручки, а не клавиатуры!

На половине квадратного треугольника, который имеет все три точки на окружности, переместите только точку не на гипотенузе, так что она находится вне окружности. Остальные 2 точки остаются там, где они есть. Это небольшое изменение не повлияет на две точки, наиболее удаленные друг от друга, но круг, центрированный на полпути между ними, больше не содержит всех 3 точек.

Rajesh R Subramanian

Кажется, теперь я понимаю, о чем ты. :(

Теперь у меня есть еще одна мысль. Спасибо, что заговорил об этом, Роб. Ты потрясающая!

Rob Philpott

Да, говоря, что все просто неправильно, не предлагая никакого альтернативного решения и не беспокоя свой собственный мозг о том, как это может быть решено, я думаю, что мне следует перейти в управление. Удачи вам!

Rajesh R Subramanian

Я взял прямоугольный треугольник в качестве тестового примера и хотел убедиться, что он работает правильно. Координаты равны 0,0 и 4,4. Вывод программы был следующим: радиус минимальной ограничивающей окружности = 2,82843
Центр окружности = 2,2

Я проверил это с помощью Wolfram Alpha, и результаты, похоже, те же: https://www.wolframalpha.com/input/?i=distance+от+(2,2)+до+(0,0)

Patrice T

Боюсь, что пункт 2 тоже ошибочен. В зависимости от набора данных, это 2 или 3 точки На краю круга.

Rajesh R Subramanian

Спасибо за сообщение. Вы правы на 100%. Я понял это после некоторого размышления после сообщения Роба. :-)

Stefan_Lang

Предположения 2, 3 и 4 все неверны: рассмотрим набор точек с 1000 точками внутри единичного круга и двумя точками в точках (999,0, 0,0) и (1000,0, 0,0). Последние две точки находятся дальше всего от средней точки, которая находится где-то очень близко или даже внутри единичного круга, но только последняя точка может находиться на оптимальной границе круга. Кроме того, предположения 3 и 4 с треском проваливаются в этом примере.

Рейтинг:
2

J-Monson

GitHub-jm97/Circles: этот проект был создан в ответ на вызов кодирования CodeProject.[^]

Типичный расчет грубой силы. Найдите все окружности для всех точек на основе двойников и кортежей. Затем найдите все круги, содержащие все точки, и отдайте трофей кругу из группы с наименьшим радиусом.

Бонус в репо: повторяйте несколько случайных наборов точек до тех пор, пока наименьший радиус случайного набора не станет меньше произвольного порога. Итак, для декартовой сетки,охватывающей от -1000, -1000 до 1000,1000, генерируйте случайные наборы произвольных размеров выборки до тех пор, пока радиус наименьшего круга привязки не станет меньше, скажем, 50% максимального радиуса, разрешенного декартовой сеткой.

Рейтинг:
2

Member 12941311

Лемма: предположим, что окружность в декартовой плоскости с центром (a,b) и радиусом D. рассмотрим точку (x, y), которая находится вне этой окружности. Тогда расстояние между (a, b) и (x,y) больше, чем D.

Предположим (х,у) значений баллы начисляются. Легко (см. ниже) написать код для обнаружения двух точек (a,b) и (c,d), таких, что расстояние D между ними меньше или равно расстоянию между любой другой парой точек. Согласно вышеприведенной лемме, окружность, центрированная на (a,b) радиусом D, охватывает все точки (x, y). (Некоторые могут лежать на окружности.)

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

Patrice T

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

[no name]

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

Member 12941311

Извинения. Позже я понял, что мое "решение" было в лучшем случае первоначальным подходом, а не решением. Я еще подумаю над этим. Интересно, однако, возможно ли аналитическое решение или только вычислительное.

Patrice T

Используйте Ответить кнопка справа от имени участника, чтобы ответить на комментарий.
Преимущество: член замечен.

Member 12941311

Лучшие умы, чем мои, придумали пару алгоритмических (и, следовательно, вычислительных) решений, которые решают проблему в линейном времени (то есть линейную функцию числа точек). Видишь https://en.m.wikipedia.org/wiki/Smallest-circle_problem

Рейтинг:
129

Graeme_Grant

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

Довольный своими усилиями, я поделился кодом и таблицей с сыном и, как типичный клиент, смог найти изъян в используемой формуле. Итак, за обедом я сел со своим университетским сыном, и мы исследовали математику и обнаружили, что проблема более сложна, чем это первоначально казалось.

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

Я включил 7 тестов - первые 3 идут от простого к сложному. 4-й тест представляет собой круг. Таким образом, радиус и центр, поставляемые для расчета точек для теста, должны равняться расчетным значениям. Все 4 теста проходят с 2 или более баллами по наименьшему результату круга. Процедура проверки округляется до 4 знаков после запятой, но не имеет дополнительной погрешности для математики с плавающей запятой, но, похоже, выполняет эту работу.

Обновление: добавлено VB.Net версии & AMP; Powershell

using System;
using System.Collections.Generic;
using System.Linq;

namespace SmallestCircle
{
    class Program
    {
        static void Main(string[] args)
        {
            var tests = new List<Tuple<string, List<Tuple<float, float>>>>()
            {
                new Tuple<string, List<Tuple<float, float>>>("Triangle", Test1()),
                new Tuple<string, List<Tuple<float, float>>>("Box", Test2()),
                new Tuple<string, List<Tuple<float, float>>>("Cluster", Test3()),
                new Tuple<string, List<Tuple<float, float>>>("Spread", Test4()),
                new Tuple<string, List<Tuple<float, float>>>("Circle", Test5()),
                new Tuple<string, List<Tuple<float, float>>>("Ellispe", Test6()),
                new Tuple<string, List<Tuple<float, float>>>("Random", Test7())
            };

            for (int i = 0; i < tests.Count; i++)
            {
                var points = tests[i].Item2;

                Console.WriteLine("--------------------------------------------------------");
                Console.WriteLine($"** TEST: {i + 1} > {tests[i].Item1} - {points.Count} locations ....\r\n");
                if (points.Count > 50) Console.WriteLine("... this may take a little while...");

                var circle = SmallestCircle(points);
                var circlePos = new Func<Tuple<float, float>, string>((pt) =>
                {
                    float cpt = (float)Math.Round(Math.Pow(pt.Item1 - circle.Item2.Item1, 2) + Math.Pow(pt.Item2 - circle.Item2.Item2, 2), 4);
                    float crd = (float)Math.Round(Math.Pow(circle.Item1, 2), 4);
                    return cpt < crd ? "inside" : cpt == crd ? "on" : "outside";
                });

                Console.WriteLine($"RADIUS: {circle.Item1}  Center: ({circle.Item2.Item1},{circle.Item2.Item2})\r\n");

                foreach (var pt in points)
                    Console.WriteLine($"({pt.Item1},{pt.Item2}) is {circlePos(pt)} the circle");
            }
            Console.WriteLine("\r\n--------------------------------------------------------");
            Console.WriteLine($"{tests.Count} Test run. Scroll up to see results.");
            Console.WriteLine("\r\n-- Press any key to exit --");
            Console.ReadKey();
        }

        private static Tuple<float, Tuple<float, float>> SmallestCircle(List<Tuple<float, float>> points)
        {
            var angVal = new Func<Tuple<float, float>, Tuple<float, float>, float>((t1, t2) =>
            {
                float dx = t2.Item1 - t1.Item1, ax = Math.Abs(dx),
                        dy = t2.Item2 - t1.Item2, ay = Math.Abs(dy),
                        t = ax + ay == 0 ? 40f : dy / (ax + ay);
                if (dx < 0) t = 2 - t; else if (dy < 0) t = 4 + t;
                return t * 90;
            });

            var enclosesPts = new Func<Tuple<float, float>, float, IEnumerable<Tuple<float, float>>, bool>
                ((tc, tr, xpts) =>
                {
                    foreach (var pt in xpts)
                        if (Math.Pow(tc.Item1 - pt.Item1, 2) + Math.Pow(tc.Item2 - pt.Item2, 2) > tr)
                            return false;
                    return true;
                });

            var intersection = new Func<List<Tuple<Tuple<float, float>, Tuple<float, float>>>, Tuple<float, float>>((spts) =>
            {
                var da = new Tuple<float, float>(spts[0].Item2.Item1 - spts[0].Item1.Item1, spts[0].Item2.Item2 - spts[0].Item1.Item2);
                var db = new Tuple<float, float>(spts[1].Item2.Item1 - spts[1].Item1.Item1, spts[1].Item2.Item2 - spts[1].Item1.Item2);
                var d = (da.Item2 * db.Item1 - da.Item1 * db.Item2);
                if (d == 0) return new Tuple<float, float>(float.NaN, float.NaN); // nope...
                float e = ((spts[0].Item1.Item1 - spts[1].Item1.Item1) * db.Item2 + (spts[1].Item1.Item2 - spts[0].Item1.Item2) * db.Item1) / d;
                return new Tuple<float, float>(spts[0].Item1.Item1 + da.Item1 * e, spts[0].Item1.Item2 + da.Item2 * e);
            });

            var findCircle = new Func<List<Tuple<float, float>>, Tuple<float, Tuple<float, float>>>((triple) =>
            {
                var p1 = new Tuple<float, float>((triple[1].Item1 + triple[0].Item1) / 2, (triple[1].Item2 + triple[0].Item2) / 2);
                var d1 = new Tuple<float, float>(-(triple[1].Item2 - triple[0].Item2), triple[1].Item1 - triple[0].Item1);
                var p2 = new Tuple<float, float>((triple[2].Item1 + triple[1].Item1) / 2, (triple[2].Item2 + triple[1].Item2) / 2);
                var d2 = new Tuple<float, float>(-(triple[2].Item2 - triple[1].Item2), triple[2].Item1 - triple[1].Item1);
                var fc = intersection(new List<Tuple<Tuple<float, float>, Tuple<float, float>>>()
                {
                    new Tuple<Tuple<float, float>, Tuple<float, float>>(p1, new Tuple<float, float>(p1.Item1 + d1.Item1, p1.Item2 + d1.Item2)),
                    new Tuple<Tuple<float, float>, Tuple<float, float>>(p2, new Tuple<float, float>(p2.Item1 + d2.Item1, p2.Item2 + d2.Item2))
                });
                return new Tuple<float, Tuple<float, float>>((float)Math.Pow(fc.Item1 - triple[0].Item1, 2) + (float)Math.Pow(fc.Item2 - triple[0].Item2, 2), fc);
            });

            // calc outer points (trapezoid)
            Tuple<float, float> ul = points[0], ur = ul, bl = ul, br = ul;
            points.ForEach(pt =>
            {
                br = -pt.Item1 - pt.Item2 > -br.Item1 - br.Item2 ? br : pt;
                bl = pt.Item1 - pt.Item2 > bl.Item1 - bl.Item2 ? bl : pt;
                ur = -pt.Item1 + pt.Item2 > -ur.Item1 + ur.Item2 ? ur : pt;
                ul = pt.Item1 + pt.Item2 > ul.Item1 + ul.Item2 ? ul : pt;
            });

            // inner box
            var xmin = ul.Item1;
            var ymin = ul.Item2;

            var xmax = ur.Item1;
            if (ymin < ur.Item2) ymin = ur.Item2;

            if (xmax > br.Item1) xmax = br.Item1;
            var ymax = br.Item2;

            if (xmin < bl.Item1) xmin = bl.Item1;
            if (ymax > bl.Item2) ymax = bl.Item2;

            // remove inner unwanted points
            var pts = points.Where(pt => pt.Item1 <= xmin || pt.Item1 >= xmax || pt.Item2 <= ymin || pt.Item2 >= ymax).ToList();

            // find point with smallest y value (and x value if tie) & add to pts
            Tuple<float, float> minPt = null;
            points.ForEach(pt => minPt = (minPt == null) || (pt.Item2 < minPt.Item2 || ((pt.Item2 == minPt.Item2) && (pt.Item1 < minPt.Item1))) ? pt : minPt);
            // Find outer points to find smallest circle
            var region = new List<Tuple<float, float>>() { minPt };
            pts.Remove(minPt);

            float ang1 = 0;
            while (true)
            {
                if (pts.Count == 0) break;

                var pt = region[region.Count - 1];
                minPt = points[0];
                float ang2 = 3600;

                points.ForEach(p =>
                {
                    var t = angVal(pt, p);
                    if (t >= ang1 && ang2 > t)
                    {
                        ang2 = t;
                        minPt = p;
                    }
                });

                var ang = angVal(pt, region[0]);
                if (ang >= ang1 && ang2 >= ang) break;

                region.Add(minPt);
                pts.Remove(minPt);
                ang1 = ang2;
            }

            // now fit smallest circle
            var radius = float.MaxValue;
            var center = region[0];

            // first try for float points on circle
            for (int i = 0; i < region.Count; i++)
            {
                var pt1 = region[i];
                region.Skip(i + 1).ToList().ForEach(pt2 =>
                {
                    var tc = new Tuple<float, float>((pt1.Item1 + pt2.Item1) / 2f, (pt1.Item2 + pt2.Item2) / 2f);
                    var dtc = new Tuple<fl
Рейтинг:
1

Patrice T

Мое решение с реальной программой. Язык клипера (в основном FoxPro)
Метод:
1) найдите самые дальние 2 точки друг от друга.
2) попробуйте 2 точки На круге решения, центр находится в середине 2 точек.
3) если точка а дальше радиуса, то решение из 2 точек не работает.
4) переключатель на 3 очка по решению круга.
5) Найдите 3 самые дальние точки от центра.
6) переместите центр ближе к самой дальней точке.
7) Повторите упражнение на 5 до тех пор, пока 3 самые дальние точки не окажутся на одинаковом расстоянии.

*   CCCP Code Challenge Code Project
* Circle surounding dataset in plane
clear
CircleFit({ { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } })

CircleFit({ { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 }, {4.87, 5.39} })

return

function Circlefit(data)
	clear
	@ 2, 0 say "CCCP Code Challenge Code Project"
	@ 3, 0 say "Circle surrounding dataset in plane"
	dist= array(len(data))
	
	tours=0
	* Solve 2 Points
	* trouver les 2 points les + eloignes
	d1= 0
	p3= 0
	for scan1=1 to len(data)-1
		for scan2=scan1+1 to len(data)
			tmp= sqrt((data[scan1,1]-data[scan2,1])^2+(data[scan1,2]-data[scan2,2])^2)
			if tmp > d1
				p1= scan1
				p2= scan2
				d1= tmp
			endif
		next
	next
	bestx= (data[p1,1]+ data[p2,1])/2
	besty= (data[p1,2]+ data[p2,2])/2
	bestr= Calc_Rad(data, bestx, besty, dist)
	if bestr - d1/2 > 0.0001
		* Solve 3 Points
		sol= "3 points"
		while .T.
			tours ++
			p1= 0
			d1= 0
			p2= 0
			d2= 0
			p3= 0
			d3= 0
			*	chercher les 3 points les + eloignes du centre
			for scan=1 to len(data)
				if dist[scan] > d1
					p3=p2
					d3=d2
					p2=p1
					d2=d1
					p1=scan
					d1=dist[scan]
				elseif dist[scan] > d2
					p3=p2
					d3=d2
					p2=scan
					d2=dist[scan]
				elseif dist[scan] > d3
					p3=scan
					d3=dist[scan]
				endif
			next
			aff()
			* converge vers p1
			bestx= bestx+ (data[p1,1]-bestx)*(d1-d3)/d1/2
			besty= besty+ (data[p1,2]-besty)*(d1-d3)/d1/2
			bestr= Calc_Rad(data, bestx, besty, dist)
			if d1-d3 < 0.0001
				exit
			endif
		enddo
		sol= "Solution a 3 points"
	else
		sol= "Solution a 2 points"
	endif
	aff()
	return

procedure aff()
	@ 5, 0 say bestx picture "@E 99.9999"
	@ 5,10 say besty picture "@E 99.9999"
	@ 5,20 say bestr picture "@E 99.9999"
	@ 5,30 say tours picture "999"
	@ 5,40 say sol
	for scan=1 to len(data)
		@ 6+scan, 0 say data[scan,1] picture "@E 99.99"
		@ 6+scan,10 say data[scan,2] picture "@E 99.99"
		if scan= p1
			@ 6+scan,18 say "1"
		elseif scan= p2
			@ 6+scan,18 say "2"
		elseif scan= p3
			@ 6+scan,18 say "3"
		else
			@ 6+scan,18 say " "
		endif
		@ 6+scan,20 say dist[scan] picture "@E 99.9999"
	next
	inkey(0)
	return

function Calc_Rad(data, cx, cy, dist)
	*	calcul des rayons
	cr= 0
	for scan=1 to len(data)
		dist[scan]= sqrt((cx-data[scan,1])^2+(cy-data[scan,2])^2)
		if cr < dist[scan]
			cr= dist[scan]
		endif
	next
	return cr

[Обновление]
Результаты:
набор данных 1
{ { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } }
Решение - 3 точки на окружности
Центр - {1.7276, 2.5255} радиус os 2.1586 с 16 итерациями

набор данных 2
{ { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 }, {4.87, 5.39} }
Решение - 2 точки на окружности
Центр - {2.6850, 3.0700} радиус os 3.1869

[Обновление] Вот дамп дисплея для полного решения 3-х комплектов
CCCP Code Chalenge Code Project
Circle surounding dataset in plane

 1,3050    2,7000    2,6054     0       2 points

 0,50      0,75   1  2,1096
 1,25      0,85      1,8508
 3,86      2,19      2,6054
 2,11      4,65   2  2,1096
 1,17      2,01      0,7031
 3,19      1,63      2,1675

 1,3050    2,7000    2,6054     1       3 points

 0,50      0,75   3  2,1096
 1,25      0,85      1,8508
 3,86      2,19   1  2,6054
 2,11      4,65      2,1096
 1,17      2,01      0,7031
 3,19      1,63   2  2,1675

 1,5481    2,6515    2,3575     2       3 points

 0,50      0,75   2  2,1712
 1,25      0,85      1,8260
 3,86      2,19   1  2,3575
 2,11      4,65   3  2,0760
 1,17      2,01      0,7446
 3,19      1,63      1,9337

 1,6861    2,6239    2,2178     3       3 points

 0,50      0,75   1  2,2178
 1,25      0,85      1,8267
 3,86      2,19   2  2,2168
 2,11      4,65   3  2,0699
 1,17      2,01      0,8020
 3,19      1,63      1,8026

 1,6466    2,5615    2,2444     4       3 points

 0,50      0,75   2  2,1439
 1,25      0,85      1,7568
 3,86      2,19   1  2,2444
 2,11      4,65   3  2,1393
 1,17      2,01      0,7289
 3,19      1,63      1,8027

 1,6984    2,5528    2,1918     5       3 points

 0,50      0,75   2  2,1648
 1,25      0,85      1,7608
 3,86      2,19   1  2,1918
 2,11      4,65   3  2,1372
 1,17      2,01      0,7575
 3,19      1,63      1,7540

 1,7253    2,5483    2,1760     6       3 points

 0,50      0,75   1  2,1760
 1,25      0,85      1,7635
 3,86      2,19   2  2,1645
 2,11      4,65   3  2,1367
 1,17      2,01      0,7734
 3,19      1,63      1,7287

 1,7142    2,5320    2,1729     7       3 points

 0,50      0,75   2  2,1563
 1,25      0,85      1,7449
 3,86      2,19   1  2,1729
 2,11      4,65   3  2,1547
 1,17      2,01      0,7541
 3,19      1,63      1,7296

 1,7232    2,5306    2,1638     8       3 points

 0,50      0,75   2  2,1602
 1,25      0,85      1,7459
 3,86      2,19   1  2,1638
 2,11      4,65   3  2,1544
 1,17      2,01      0,7596
 3,19      1,63      1,7212

 1,7278    2,5298    2,1622     9       3 points

 0,50      0,75   1  2,1622
 1,25      0,85      1,7465
 3,86      2,19   2  2,1591
 2,11      4,65   3  2,1543
 1,17      2,01      0,7625
 3,19      1,63      1,7169
 
 1,7256    2,5266    2,1608    10       3 points

 0,50      0,75   2  2,1583
 1,25      0,85      1,7427
 3,86      2,19   1  2,1608
 2,11      4,65   3  2,1579
 1,17      2,01      0,7586
 3,19      1,63      1,7171

 1,7270    2,5264    2,1594    11       3 points

 0,50      0,75   2  2,1589
 1,25      0,85      1,7429
 3,86      2,19   1  2,1594
 2,11      4,65   3  2,1579
 1,17      2,01      0,7595
 3,19      1,63      1,7158

 1,7277    2,5262    2,1592    12       3 points

 0,50      0,75   1  2,1592
 1,25      0,85      1,7430
 3,86      2,19   2  2,1586
 2,11      4,65   3  2,1579
 1,17      2,01      0,7600
 3,19      1,63      1,7151

 1,7273    2,5257    2,1589    13       3 points

 0,50      0,75   2  2,1586
 1,25      0,85      1,7423
 3,86      2,19   1  2,1589
 2,11      4,65   3  2,1585
 1,17      2,01      0,7593
 3,19      1,63      1,7151

 1,7275    2,5257    2,1587    14       3 points

 0,50      0,75   2  2,1587
 1,25      0,85      1,7424
 3,86      2,19   1  2,1587
 2,11      4,65   3  2,1585
 1,17      2,01      0,7594
 3,19      1,63      1,7149

 1,7276    2,5256    2,1587    15       3 points

 0,50      0,75   1  2,1587
 1,25      0,85      1,7424
 3,86      2,19   2  2,1586
 2,11      4,65   3  2,1585
 1,17      2,01      0,7595
 3,19      1,63      1,7148

 1,7276    2,5256    2,1587    16       3 points

 0,50      0,75   2  2,1586
 1,25      0,85      1,7423
 3,86      2,19   1  2,1587
 2,11      4,65   3  2,1586
 1,17      2,01      0,7594
 3,19      1,63      1,7148

 1,7276    2,5255    2,1586    16       Solution a 3 points

 0,50      0,75   2  2,1586
 1,25      0,85      1,7423
 3,86      2,19   1  2,1586
 2,11      4,65   3  2,1586
 1,17      2,01      0,7594
 3,19      1,63      1,7148

CCCP Code Chalenge Code Project
Circle surounding dataset in plane

 2,6850    3,0700    3,1869     0       Solution a 2 points

 0,50      0,75   1  3,1869
 1,25      0,85      2,6434
 3,86      2,19      1,4680
 2,11      4,65      1,6814
 1,17      2,01      1,8490
 3,19      1,63      1,5260
 4,87      5,39   2  3,1869

CCCP Code Chalenge Code Project
Circle surounding dataset in plane

 7,7500    1,1900    9,2688     0       2 points

 0,50      0,75   1  7,2633
 1,25      0,85      6,5089
 3,86      2,19      4,0165
11,00      7,00      6,6572
 1,17      2,01      6,6309
15,00      1,63   2  7,2633
 4,87     10,00      9,2688

 7,7500    1,1900    9,2688     1       3 points

 0,50      0,75   2  7,2633
 1,25      0,85      6,5089
 3,86      2,19      4,0165
11,00      7,00      6,6572
 1,17      2,01      6,6309
15,00      1,63   3  7,2633
 4,87     10,00   1  9,2688

 7,4384    2,1431    8,2661     2       3 points

 0,50      0,75   3  7,0769
 1,25      0,85      6,3221
 3,86      2,19      3,5787
11,00      7,00      6,0228
 1,17      2,01      6,2698
15,00      1,63   2  7,5790
 4,87     10,00   1  8,2661

 7,2537    2,7082    7,8210     3       3 points

 0,50      0,75   3  7,0319
 1,25      0,85      6,2847
 3,86      2,19      3,4330
11,00      7,00      5,6968
 1,17      2,01      6,1236
15,00      1,63   1  7,8210
 4,87     10,00   2  7,6715

 7,6445    2,6538    7,8526     4       3 points

 0,50      0,75   3  7,3938
 1,25      0,85      6,6440
 3,86      2,19      3,8128
11,00      7,00      5,4908
 1,17      2,01      6,5064
15,00      1,63   2  7,4264
 4,87     10,00   1  7,8526

 7,5634    2,8685    7,6232     5       3 points

 0,50      0,75   3  7,3743
 1,25      0,85      6,6282
 3,86      2,19      3,7651
11,00      7,00      5,3740
 1,17      2,01      6,4508
15,00      1,63   2  7,5390
 4,87     10,00   1  7,6232

 7,5195    2,9849    7,6023     6       3 points

 0,50      0,75   3  7,3667
 1,25      0,85      6,6230
 3,86      2,19      3,7448
11,00      7,00      5,3137
 1,17      2,01      6,4239
15,00      1,63   1  7,6023
 4,87     10,00   2  7,4987

 7,6354    2,9639    7,5600     7       3 points

 0,50      0,75   3  7,4709
 1,25      0,85      6,7262
 3,86      2,19      3,8539
11,00      7,00      5,2546
 1,17      2,01      6,5354
15,00      1,63   2  7,4845
 4,87     10,00   1  7,5600

 7,6191    3,0054    7,5155     8       3 poi

Graeme_Grant

Прошло уже более 20 лет с тех пор, как я программировал в Clipper, и мне было любопытно посмотреть, как работает ваша формула, поэтому я портировал ее на C#. Результаты, которые я получил, были немного неправильными:

[правка: исправлена незначительная ошибка, результат все еще неверен]

-----------------------------------

bestx: 1.305
besty: 2.7
bestr: 2.605403
туры: 0

... Решение а 2 балла:
(0.5, 0.75) 1 D: 2.109627
(1.25, 0.85) - Д: 1.850817
(3.86, 2.19) - Д: 2.605403
(2.11, 4.65) 2 D: 2.109627
(1.17, 2.01) - Д: 0.7030826
(3.19, 1.63) - Д: 2.167516

-----------------------------------

bestx: 2.685
лучший: 3.07
bestr: 3.186946
туры: 0

... Решение а 2 балла:
(0.5, 0.75) 1 D: 3.186946
(1.25, 0.85) - Д: 2.643411
(3.86, 2.19) - Д: 1.468
(2.11, 4.65) - Д: 1.681376
(1.17, 2.01) - Д: 1.849006
(3.19, 1.63) - Д: 1.525983
(4.87, 5.39) 2 D: 3.186946

Вы видите то же самое?

Graeme_Grant

Вот преобразованный код C#, используемый:

using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            CircleFit(new List<Point>()
            {
                new Point(0.5f, 0.75f),
                new Point(1.25f, 0.85f),
                new Point(3.86f, 2.19f),
                new Point(2.11f, 4.65f),
                new Point(1.17f, 2.01f),
                new Point(3.19f, 1.63f)
            });

            CircleFit(new List<Point>()
            {
                new Point(0.5f, 0.75f),
                new Point(1.25f, 0.85f),
                new Point(3.86f, 2.19f),
                new Point(2.11f, 4.65f),
                new Point(1.17f, 2.01f),
                new Point(3.19f, 1.63f),
                new Point(4.87f, 5.39f)
            });

            CircleFit(new List<Point>()
            {
                new Point(0.5f, 0.75f),
                new Point(1.25f, 0.85f),
                new Point(3.86f, 2.19f),
                new Point(11f, 7f),
                new Point(1.17f, 2.01f),
                new Point(15f, 1.63f),
                new Point(4.87f, 10f)
            });
        }

        static int tours = 0;
        static int p1 = 0, p2 = 0, p3 = 0;
        static float d1 = 0, d2 = 0, d3 = 0;
        static List<float> dist;
        static float bestx;
        static float besty;
        static float bestr;

Patrice T

Ничего очевидного.
Вы уверены насчет /2 ? разве это не должно быть /2.0 ?

Graeme_Grant

Проверил это, и это не имеет никакого значения для первого теста-дисперсия равна -6.29564762 для "if (bestr-d1 / 2 > 0.0001)". Я не тратил время на выяснение причин. [править] второй тест проходит. Только 3 точки На круге кажутся неудачными (то же самое с 3-м тестом, который я включил.)

Graeme_Grant 

        private static void CircleFit(List<Point> data)
        {
            string sol = "";
            dist = new List<float>();

            tours = 0;
            p1 = p2 = p3 = 0;
            d1 = d2 = d3 = 0;

            for (int scan1 = 0; scan1 < data.Count-1; scan1++)
            {
                for (int scan2 = scan1+1; scan2 < data.Count; scan2++)
                {
                    var tmp = (float)Math.Sqrt(Math.Pow(Math.Pow(data[scan1].X - data[scan2].X, 2) + Math.Pow(data[scan1].Y - data[scan2].Y, 2), 2));
                    if (tmp > d1)
                    {
                        p1 = scan1;
                        p2 = scan2;
                        d1 = tmp;
                    }
                }
            }
            bestx = (data[p1].X + data[p2].X) / 2;
            besty = (data[p1].Y + data[p2].Y) / 2;
            bestr = CalcRadius(data, bestx, besty);

            if (bestr - d1 / 2 > 0.0001)
            {
                sol = "3 points";
                while (true)
                {
                    tours++;
                    p1 = p2 = p3 = 0;
                    d1 = d2 = d3 = 0;

                    for (int scan = 0; scan < data.Count; scan++)
                    {
                        if (data[scan].X > d1)
                        {
                            p3 = p2;
                            d3 = d2;
                            p2 = p1;
                            d2 = d1;
                            p1 = scan;
                            d1 = dist[scan];
                        }
                        else if (dist[scan] > d2)
                        {
                            p3 = p2;
                            d3 = d2;
                            p2 = scan;
                            d2 = dist[scan];
                        }
                        else if (dist[scan] > d3)
                        {
                            p3 = scan;
                            d3 = dist[scan];
                        }
                    }
                    aff(sol, data);
                    bestx = bestx + (data[p1].X - bestx) * (d1 - d3) / d1 / 2;
                    besty = besty + (data[p1].Y - besty) * (d1 - d3) / d1 / 2;
                    bestr = CalcRadius(data, bestx, besty);
                    if (d1 - d3 < 0.0001) break;
                }
                sol = "Solution a 3 points";
            }
            else
            {
                sol = "Solution a 2 points";
            }
            aff(sol, data);
        }

Graeme_Grant 

        class Point
        {
            public Point(float x, float y)
            {
                X = x;
                Y = y;
            }
            public float X { get; set; }
            public float Y { get; set; }
        }

        private static void aff(string sol, List<Point> data)
        {
            Console.WriteLine("-----------------------------------");
            Console.WriteLine("");
            Console.WriteLine($"bestx: {bestx}");
            Console.WriteLine($"besty: {besty}");
            Console.WriteLine($"bestr: {bestr}");
            Console.WriteLine($"tours: {tours}");
            Console.WriteLine("");
            Console.WriteLine($"...  {sol}: ");

            for (int i = 0; i < data.Count; i++)
            {
                Console.Write($"    ({data[i].X}, {data[i].Y})");
                if (i == p1) Console.Write(" 1");
                else if (i == p2) Console.Write(" 2");
                else if (i == p3) Console.Write(" 3");
                else Console.Write(" -");
                Console.WriteLine($"   D: {dist[i]}");
            }
            Console.WriteLine("");
            Console.ReadKey();
        }

        private static float CalcRadius(List<Point> data, float cx, float cy)
        {
            dist.Clear(); // reset before calc
            float cr = 0;
            for (int scan = 0; scan < data.Count; scan++)
            {
                dist.Add((float)Math.Sqrt(Math.Pow(cx - data[scan].X, 2) + Math.Pow(cy - data[scan].Y, 2)));
                if (cr < dist[scan])
                    cr = dist[scan];
            }
            return cr;
        }
    }

Patrice T

Это дист.Добавить замена значений в dist ?

Graeme_Grant

Да, только что обнаружил это сам - мои искренние извинения.

Однако после исправления 3-й тест, который я предоставил, провалился.

-----------------------------------

bestx: 7,75
лучший: 1.19
bestr: 9.268792
туры: 0

... Решение а 2 балла:
(0.5, 0.75) 1 D: 7.26334
(1.25, 0.85) - Д: 6.508886
(3.86, 2.19) - Д: 4.016479
(11, 7) - D: 6.657222
(1.17, 2.01) - Д: 6.630898
(15, 1.63) 2 D: 7.26334
(4.87, 10) - D: 9.268792

Должно быть:

** Тест: 3 & gt; спред - 7 локаций ....

Радиус: 7.49485 центр: (7.638026, 3.03503)

(0.5, 0.75) находится на круге
(1.25, 0.85) находится внутри круга
(3.86, 2.19) находится внутри круга
(11,7) находится внутри круга
(1.17, 2.01) находится внутри круга
(15,1. 63) находится на круге
(4.87, 10) находится на круге

--------------------------------------------------------

Patrice T

Я получаю правильное решение для набора 3

Graeme_Grant

Ваша переменная scope сделала его интересным для порта, но, насколько я вижу, порт на C# теперь корректен, и я вижу, что первый и третий тесты терпят неудачу. Кто-нибудь еще видел то же самое?

Patrice T

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

Graeme_Grant

Это было исправлено (см. код выше). Вы пробовали использовать 3-й набор данных, поставляемый с вашей версией Clipper? [редактировать] Я хочу дать ему 5 звезд, если все тесты пройдут.

Patrice T

Обратите внимание, что я использую Windows-инкарнацию Clipper
Я использую xHabour, witch также предоставляет утилиту под названием xPrompt witch allow scripting.
Еще одно воплощение, которое в последнее время выглядит более активным, - это гавань.

Patrice T

Вы видели мое последнее обновление в решении ?
Вы нашли, почему ваша программа идет не так ?

Graeme_Grant

Только что видел вашу записку. Нет, не успели провести дальнейшее расследование. Просто проработал всю ночь (сейчас 6: 45 утра), быстро выполнил очередное задание и собрался ложиться спать. Проверю это еще раз позже сегодня (в субботу).

Рейтинг:
1

Arthur V. Ratz

- Привет, Крис. Вот мое решение проблемы code challenge:

<pre>#include <cmath>
#include <ctime>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef struct tagPoint
{
	double x;
	double y;
} PT;

typedef struct tagCircle
{
	double coord_x;
	double coord_y;
	double radius;
} CR;

const double precision_r = 0.1;
const double precision_pt = 0.01;
const double dim_x = 10, dim_y = 10;

std::vector<PT> points = { { 0.5, 0.75 }, { 1.25, 0.85 }, \
	{ 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } };

int main(int argc, char* argv[])
{
	double radius_min = -1;
	double radius = precision_r;
	clock_t time_start = std::clock();
	while (radius < dim_x && radius < dim_y)
	{
		for (double coord_x = 0; coord_x < dim_x; coord_x += precision_pt)
			for (double coord_y = 0; coord_y < dim_y; coord_y += precision_pt)
			{
				bool inside = true;
				for (auto it = points.begin(); it != points.end() && inside; it++)
					inside = ((std::pow(it->x - coord_x, 2.0) + \
						std::pow(it->y - coord_y, 2.0)) >= std::pow(radius, 2.0)) ? 0 : 1;

				if (inside == true)
				{
					if ((radius < radius_min) || (radius_min == -1))
						radius_min = radius;
				}
			}
	
		radius += precision_r;
	}

	printf("radius_min = %f\n", radius_min);

	std::vector<CR> circles;
	for (double coord_x = 0; coord_x < dim_x; coord_x += precision_pt)
		for (double coord_y = 0; coord_y < dim_y; coord_y += precision_pt)
		{
			bool inside = true;
			for (auto it = points.begin(); it != points.end() && inside; it++)
				inside = ((std::pow(it->x - coord_x, 2.0) + \
					std::pow(it->y - coord_y, 2.0)) >= std::pow(radius_min, 2.0)) ? 0 : 1;

			if (inside == true)
			{
				CR circle = { 0, 0, 0 };
				circle.radius = radius_min;
				circle.coord_x = coord_x; circle.coord_y = coord_y;
				circles.push_back(circle);
			}
		}


	for (auto it = circles.begin(); it != circles.end(); it++)
		if (it->coord_x > 0 && it->coord_y > 0 && it->radius == radius_min)
		{
			bool inside = true;
			for (auto it2 = points.begin(); it2 != points.end() && inside; it2++)
				inside = ((std::pow(it2->x - it->coord_x, 2.0) + \
					std::pow(it2->y - it->coord_y, 2.0)) >= std::pow(radius_min, 2.0)) ? 0 : 1;

			std::cout << "coord_x = " << it->coord_x << " " << "coord_y = " << it->coord_y << " " << "radius = " << it->radius;
			std::cout << " check..." << ((inside == true) ? "okey" : "wrong") << endl;
		}

	double w_time = (std::clock() - time_start) / (double)CLOCKS_PER_SEC;

	std::cout << "Time Elapsed: " << w_time << endl;
	std::cin.get();

    return 0;
}


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

radius_min = 2.200000
coord_x = 1.69 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.69 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.69 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.69 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.69 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.69 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.56 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.57 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.58 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.59 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.56 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.57 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.58 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.56 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.57 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.58 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.56 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.57 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.56 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.56 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.77 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.77 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.77 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.77 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.77 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.77 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.77 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.78 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.78 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.78 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.78 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.78 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.78 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.79 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.79 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.79 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.79 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.79 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.79 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.8 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.8 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.8 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.8 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.8 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.81 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.81 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.81 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.81 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.82 coord_y = 2.47 radius = 2.2 check...okey
coord_x = 1.82 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.82 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.82 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.82 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.83 coord_y = 2.47 radius = 2.2 check...okey
coord_x = 1.83 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.83 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.83 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.84 coord_y = 2.47 radius = 2.2 check...okey
coord_x = 1.84 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.84 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.85 coord_y = 2.47 radius = 2.2 check...okey
coord_x = 1.85 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.86 coord_y = 2.47 radius = 2.2 check...okey
coord_x = 1.87 coord_y = 2.47 radius = 2.2 check...okey
Time Elapsed: 70.419


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

Чтобы избежать каких-либо сомнений в правильности моего кода, а также ненужного обсуждения того, точно ли мой код решает эту проблему, я решил графически интерпретировать результаты, полученные с помощью моего кода. Вот ссылка: https://i.imgur.com/A4Ew6H3.png.

Это все.

Patrice T

Боюсь, ваш круг ошибается !
С вашим набором данных я получаю центр вокруг (1.75, 2.5) с радиусом около 2.2

Arthur V. Ratz

Привет, пполиморф. Извините, * НО * Я не понимаю ваш комментарий: что это значит, что вы получаете центр «вокруг» (1,75, 2,5) с радиусом «вокруг» 2,2 ??? Мой код обычно гарантирует, что вы найдете все круги с центром в (координаты_x; координаты_y) и конкретным значением radius_min, содержащим все эти точки в моем наборе данных. Просто чтобы проверить, правда ли это, вы можете взять одну или несколько точек из набора данных, например, точку (3.86; 2.19) и координаты круга, такие как (2.29; 2.98) с радиусом 3, взятым из выходных данных, и проверить, соответствует ли следующая точка заключен в круг с использованием следующего уравнения (x - Coord_x) ^ 2 + (y - Coord_y) ^ 2 <= radius ^ 2. И, очевидно, мы получаем (3,86 - 2,29) ^ 2 + (2,19 - 2,98) ^ 2 <= 3 ^ 2, что составляет 1,57 ^ 2 + (-0,79) ^ 2 <= 3 ^ 2 <= 9, 2,4649 + 0,6241 < = 9, 3,089 <= 9.

Patrice T

Я решил задачу графически,поэтому значения аппроксимируются.

Arthur V. Ratz

ppolymorphe, если у вас есть еще вопросы, просто оставьте свой комментарий, так что я с удовольствием отвечу на ваши вопросы.

Ralf Meier

Я ввел ваши ценности в свой расчет - я не совсем согласен с ppolymorphe, но и мои ценности немного отличаются от ваших.
У меня есть центральная точка в (2.18, 2.7) и радиус 2.573888 (с вашими точками)

Arthur V. Ratz

Но какие именно точки из набора данных: { { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } }; вы действительно прошли этот тест. В своем комментарии Вы указали только центральные точки окружности и радиуса. Если вы возьмете любую точку из набора данных, она должна точно работать. Пример вычисления я уже опубликовал в качестве ответа на комментарий ppolymorphe (см. выше).

Arthur V. Ratz

Вот несколько быстрых шагов для тестирования наборов центральных точек и радиусов окружности из выходных данных, которые должны охватывать все точки в наборе данных ( { { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } } ):

1) Возьмите произвольную точку из набора данных, например (3.86; 2.19);
2) Возьмите любую из центральных точек и радиусов, указанных в выводе моего кода, например окружность в точке (2.29; 2.98) с радиусом 3;
3) Выполните вычисление, используя следующую формулу, чтобы определить, заключена ли точка, взятая из набора данных на шаге 1, в заданную окружность с координатами и радиусом, взятыми на Шаге 2:

(3.86 - 2.29)^2 + (2.19 - 2.98)^2 <= 3^2, что равно 1.57^2 + (-0.79)^2 <= 3^2 <= 9, 2.4649 + 0.6241 <= 9, 3.089 <= 9.

И сейчас, неужели вы все еще не понимаете мою идею о том, как решить эту конкретную проблему ??

Patrice T

Привет Артур,
Наличие всех точек внутри окружности - это только часть условий.
Если у вас есть по крайней мере 2 круга, которые окружают все точки, есть еще один круг с меньшим радиусом, который также будет окружать все точки.

Arthur V. Ratz

Привет ppolymorphe, который сказал вам, что "если у вас есть по крайней мере 2 круга, которые окружают все точки, есть еще один круг с меньшим радиусом, который тоже будет окружать все точки...". Меньший круг, охватывающий все точки, может существовать, а может и не существовать.

Patrice T

Это геометрия.

Arthur V. Ratz

А также позвольте мне рассказать вам, что именно делает мой код: он просто нацелен на итеративное нахождение этих координат и тех значений радиуса, с помощью которых мы можем нарисовать круг (не эллипс), окружающий все точки в наборе данных. Обычно это делается с помощью уравнения круга, чтобы проверить, принадлежит ли определенная точка определенной области круга с определенными координатами и радиусом. Если мы применим эти значения координат точки, координаты круга и радиуса к уравнению круга, которое имеет вид (x - Coord_x) ^ 2 + (y - Coord_y) ^ 2 <= R ^ 2, и условие истинно, тогда мы просто считайте, что точка (x; y) окружена кругом с координатами (координаты_x; координата_y) с радиусом, равным 3.

Разве это не ясно ??

Patrice T

Я не хотел сказать, что у вас есть точки вне круга.
Я хотел заметить, что круг не самый маленький.
На вашем рисунке переместите центр на {1.73, 2.53}, и вы увидите, что вокруг набора данных есть большой запас, если радиус равен 3, и что его можно уменьшить.

Кстати, спасибо за предоставленный набор данных.

Arthur V. Ratz

ppolymorphe, спасибо за ваш комментарий. Чтобы получить круг с наименьшим радиусом, просто уменьшите радиус precision_r до 0,01, и постепенно после выполнения кода Вы получите круг с меньшим радиусом, окружающий эти точки. Спасибо.

Patrice T

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

Arthur V. Ratz

Мне очень жаль, что вы на самом деле должны увеличить точность, уменьшив параметр precision_r, назначив ему 0,01. Это на самом деле даст больше результатов, включая круги с фактически наименьшим возможным радиусом.

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

Arthur V. Ratz

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

Kornfeld Eliyahu Peter

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

Рейтинг:
1

Rick Shaub

Вот довольно компактное консольное приложение C#, которое отвечает требованиям AFAIK.

Процесс:
1. Возьмите список точек и вычислите центр.
2. вычислите расстояние для каждой точки от центра и выберите самую дальнюю точку для радиуса.

using System;
using System.Collections.Generic;

namespace MinimumBoundingCircle
{
    class Program
    {
        struct PointF
        {            
            public float X;
            public float Y;
        }
        static void Main(string[] args)
        {
            Console.Out.WriteLine("Enter a comma delimited list of X and Y values:");
            string[] inValues = Console.In.ReadLine().Split(',');
            var vals = new List<PointF>();
            for(int i = 0;i< inValues.Length;i+=2)
            {
                PointF point = new PointF();
                point.X = float.Parse(inValues[i]);
                point.Y = float.Parse(inValues[i + 1]);
                vals.Add(point);
            }
            var cent = GetCenter(vals.ToArray());
            var radius = GetBoundingRadius(vals.ToArray(), cent);
            Console.Out.WriteLine("CenterX: " + cent.X);
            Console.Out.WriteLine("CenterY: " + cent.Y);
            Console.Out.WriteLine("Radius: " + radius);
            Console.Out.WriteLine("Press enter key to exit...");
            Console.In.ReadLine();
        }
        //Calculates the center point of a collection of points using 
        //Addapted formula from here: http://www.batesville.k12.in.us/Physics/APPhyNet/Dynamics/Center%20of%20Mass/2D_1.html
        static PointF GetCenter(PointF[] points)
        {
            float xSum = 0;
            float ySum = 0;
            foreach (PointF p in points)
            {
                xSum += p.X;
                ySum += p.Y;
            }
            return new PointF() { X = xSum / points.Length, Y = ySum / points.Length };
        }
        //Gets the bounding radius by checking for max distance from center for each point
        //Reference: http://math.info/Algebra/Distance_Cartesian_Plane/
        static float GetBoundingRadius(PointF[] points, PointF center)
        {
            float distance = 0.0f;
            foreach (PointF p in points)
            {
                float xDiffsSquared = 0;
                float yDiffsSquared = 0;
                var xDiff = center.X - p.X;
                var yDiff = center.Y - p.Y;
                xDiffsSquared = (xDiff * xDiff);
                yDiffsSquared = (yDiff * yDiff);
                float newDist = (float)Math.Sqrt(xDiffsSquared + yDiffsSquared);
                if (newDist > distance)
                {
                    distance = newDist;
                }

            }
            return distance;
        }
    }
}

Пример вывода программы:
Enter a comma delimited list of X and Y values:
2,3,1,2.3,7.2,5.8,10.5,9.6,-5,10,3.2,1.3
CenterX: 3.15
CenterY: 5.333333
Radius: 9.3915
Press any key to exit...

Patrice T

Похоже, вам нужно усовершенствовать свое решение.
Центр окружности не находится в Средней из всех точек. Добавление точек внутри круга не меняет его центра.
Для вашего набора данных наименьший центр окружности равен {2.73, 9.06}, а радиус-7.79

Graeme_Grant

Согласен, требуется больше работы.

Использовать это сводная таблица[^] чтобы войти и посмотреть, проходят ли ваши баллы и результаты.

Rick Shaub

Спасибо за обратную связь, ребята. Я недооценил сложность этой проблемы. Я оставлю это как пример неправильного подхода.

Graeme_Grant

Не волнуйтесь, моя первая попытка пострадала от подобной проблемы. Гораздо сложнее, чем кажется. Я тоже оставил его и опубликовал вторую версию.

Рейтинг:
0

Peter Leow

Я опоздал, потому что меня неправильно информировали, что

Цитата:
.. задача очень проста:

Тем не менее, я взглянул еще раз, и внезапно эти вещи начали преследовать меня: геометрия, линейная алгебра, наклон, y-перехват и все такое. Посмотрите, что единственный способ освободиться от кошмара - это принять этот "простой" вызов. В результате я пришел к следующему предположению и алгоритму:
1.  The smallest circle must include at least two of the points on its circumference.
2.  In order to encircle as many points as possible, these two points must be as far apart as possible.
3.  Seek out three pairs of furthest points in the set.
4.  For each pair, 
    4.1 Draw the bisector line where the center of circle lies
    4.2 Draw the line joining the pair of points
    4.3 Designate the intersect between these 2 lines as the center of circle and the half distance of the pair as radius
    4.4 Draw a cicle
    4.5 Gather all points that fall outside of the circle, call them outliers
    4.6 Check out which side of this line (in 4.2) the outliers lie
        4.6.1  IF they are on the different sides, then reject this pair as potential, ELSE
        4.6.2  MOVE the center of circle towards the side where the outliers lie and calculate new radius
    4.7 Repeat 4.4 to 4.6 until there is no more outliers, mark the pair as potential.
5.  The solution will be the one with the smallest radius!

Теперь, когда у меня есть план, какой инструмент я должен использовать для его реализации? Я хотел бы иметь инструмент, который позволяет мне визуализировать результат в графических точках, линиях и кругах с минимальным кодом. Понял! Р это тот самый! Вот вы, моя реализация в R:
################################################################
# Coding challenge: smallest circle to surround a set of points
#      Submitted by Peter Leow the circle haunter
################################################################

require(plotrix)

# The set of x, y points in contention!
# Assume min 3 points
# Uncomment to try out different test sets
x <- c(1.2,4.7,1.9,2.1,3.6,2.3,4.9,1.4,2.1,1.8,1.7,2.2);
y <- c(3.1,4.7,2.0,3.5,3.5,4.6,1.5,3.2,2.3,2.3,3.5,2.4);

# x <- c(1.2,4.7,1.9,4.1,3.6,3.3,4.9,1.4,2.8,1.8,1.7,2.2);
# y <- c(3.1,4.7,2.0,3.5,3.5,4.6,1.5,3.2,2.3,2.3,3.5,2.4);

# x <- c(1.2,4.7,1.9,2.1,3.6,2.3,4.9,1.4,2.1,1.8,4.7,2.2);
# y <- c(3.1,4.7,2.0,5.5,3.5,4.6,1.5,3.2,2.3,2.3,3.5,2.4);

# Turn x, y into a list of point vectors
all_points <- mapply( c , x , y , SIMPLIFY = FALSE )

# Number of furthest pairs of points
num_furthest_pairs <- 3

# Vector of colors
colors = c("red","green","blue")

# Meet them in a plot
plot(x, y, main="Seeing is Believing in R by Peter Leow", 
  xlab="X", ylab="Y",
  xlim=c(0, 10), ylim=c(0, 10))
axis(side=1, at=c(0:10))
axis(side=2, at=c(0:10))


# function to calculate Euclidean distance between 2 points
calEuclideanDistance <- function(point1, point2){
    
    return (sqrt((point1[1]-point2[1])^2 + (point1[2]-point2[2])^2))
    
}

# function to find pairs of furthest points
findPairsOfFurthestPoints <- function(all_points){
    
    furthest_pairs <- list()
    
    for (n in 1:num_furthest_pairs){
        
        furthest_distance <- 0
        
        for (i in 1:(length(all_points)-1)) {
        
            for (j in i+1:(length(all_points)-i)) {
                  
                b <- c(all_points[[i]], all_points[[j]])
                
                if (n > 1 & Position(function(x) identical(x, b), furthest_pairs, nomatch = 0) > 0) next
                                    
                distance <- calEuclideanDistance(all_points[[i]], all_points[[j]])

                if (distance > furthest_distance) {
                
                    furthest_distance <- distance
                    
                    furthest_pairs[[n]] <- c(all_points[[i]], all_points[[j]])
                    
                    furthest_pairs[[n]] 
                }
            
            }

        }
        
    }

    return (furthest_pairs) # return a list containing num_furthest_pairs of pairs of furthest points in descending order
}

# Find 3 pairs of further points
pairsOfFurthestPoints <- findPairsOfFurthestPoints(all_points)

cat("The",num_furthest_pairs,"furthest pairs (x1 y1 x2 y2):\n")
cat("Pair #1 (Red)  :",pairsOfFurthestPoints[[1]],"\n") # first furthest pair
cat("Pair #2 (Green):",pairsOfFurthestPoints[[2]],"\n") # second furthest pair
cat("Pair #3 (Blue) :",pairsOfFurthestPoints[[3]],"\n") # third furthest pair                         

# Check out the pairs visually!                                  
for (p in 1:num_furthest_pairs) {
    
    points(pairsOfFurthestPoints[[p]][1],pairsOfFurthestPoints[[p]][2],cex=2,pch=4,col=colors[p])
    
    points(pairsOfFurthestPoints[[p]][3],pairsOfFurthestPoints[[p]][4],cex=2,pch=4,col=colors[p])
    
    center <- c(pairsOfFurthestPoints[[p]][1] + pairsOfFurthestPoints[[p]][3], pairsOfFurthestPoints[[p]][2] + pairsOfFurthestPoints[[p]][4]) / 2

    radius <- calEuclideanDistance(c(pairsOfFurthestPoints[[p]][1], pairsOfFurthestPoints[[p]][2]), c(pairsOfFurthestPoints[[p]][3], pairsOfFurthestPoints[[p]][4])) / 2

    #points(center[1],center[2],cex=2,pch=18,col=colors[p])
    #draw.circle(center[1], center[2], radius,border=colors[p])
}

# function to find the line of two points
findLinearEquation <- function(point1, point2){

    # m = slope
    m <- (point2[2]-point1[2]) /(point2[1]-point1[1])
    
    # b = y - mx, the (y-intecept)
    b <- point1[2] - m * point1[1]
    
    return (c(m, b)) # slope, y-intercept
}                                     
                                     
# function to find the bisector line of two points
findBisectorEquation <- function(point1, point2){

    mid_point <- (point1 + point2) / 2
    
    slope <- (point2[2]-point1[2]) /(point2[1]-point1[1])
    
    # slope of the perpendicular bisector line
    # y = mx + b
    m <- -1 / slope
    
    # b= y - mx
    b <- mid_point[2] - m * mid_point[1]
    
    return (c(m, b)) # slope, y-intercept
}                                     
                                     
                                     
# function to find the smallest circle that crosses the pair of points
findSmallestCircle <- function(pair, all_points, pair_no){

    point1 <- pair[1:2]

    point2 <- pair[3:4]
  
    points <- list()
    
    n <- 0
    
    # exclude the pair from the rest of the points
    for (i in 1:length(all_points)) {
                
        if (!all(point1 == all_points[[i]]) & !all(point2 == all_points[[i]])) {
            
            n <- n + 1
            
            points[[n]] <- all_points[[i]]
                   
        } 
    }
      
    # (c(m, b)) # slope, y-intercept
    line = findLinearEquation(point1, point2)

    # Plot a line thru the pair of points
    abline(b=line[1], line[2], col=colors[pair_no])
    
    # slope, y-intercept
    bisector_line = findBisectorEquation(point1, point2)
    
    # Draw the bisector line to the pair of points
    abline(b=bisector_line[1], a=bisector_line[2], col=colors[pair_no])
    
    radius <- calEuclideanDistance(point1, point2) / 2
    
    center <- c(point1[1] + point2[1], point1[2] + point2[2]) / 2
    

    while (TRUE) {
    # Find all the points outside of the circle
    outliers <- list()
        
    q = 0

    for (i in 1:length(points)) {
                
        if (calEuclideanDistance(center, points[[i]]) > radius) {
            
            q <- q + 1
            
            outliers[[q]] = points[[i]]
            
            # cat("Outlier (x y):", outliers[[q]], "\n")
          
        } 
    }
        
    # if there is no outliers, then this point is one of the potential circle!
    if (q==0) {
        return (c(center, radius))
    }
    
    # Detemine which side of the line each outlier lies
    sides <- list()
    
    outlier_b <- list() # list of outlier y-intercepts
    
    for (i in 1:length(outliers)) {
        
        # find the y-intercep of the outlier line parallel to the line
        # b = y - mx
        outlier_b[[i]] <- outliers[[i]][2] - line[1] * outliers[[i]][1]
        
        # find the difference between the two y-intercepts
        sides[[i]] <- line[2] - outlier_b[[i]]
    }
    
    # If not all outliers on the same side, then reject this point
    if (!(all(sides > 0) | all(sides < 0))) {
        return (c(center, -1)) # assign -1 to radius to indicate rejection
    }
    
    move_x <- 0.1
        
    new_center_x <- 0
    
    if (all(sides > 0)) {

        new_center_x <- center[1] - move_x

    } else {
        
        new_center_x <- center[1] + move_x
  
    }
        
    new_center_y <- bisector_line[1] * new_center_x + bisector_line[2]
        
    new_center <- c(new_center_x, new_center_y)
        
    new_radius <- calEuclideanDistance(new_center, point1)
        
    draw.circle(new_center[1], new_center[1], new_radius,border=colors[pair_no])
        
    center <- new_center
    radius <- new_radius  
        
    #print(center)
    #print(radius)
        
    
  } # End of while
    
}   

for (i in 1:length(pairsOfFurthestPoints)){                                   
                                     
    smallestCircle <- findSmallestCircle(pairsOfFurthestPoints[[i]], all_points, i)  
    
    if (smallestCircle[3] != -1) {
        
        # a potential solution
        draw.circle(smallestCircle[1], smallestCircle[1], smallestCircle[3], border="black")
        
    }

    cat ("Result of Pair #", i, " (centerX, centreY, radius):", smallestCircle, "\n")
    
}

print("Note: The potential solutions are those pairs with positive radius and plotted in

Patrice T

Боюсь, ваше решение нуждается в некоторой доработке.
Для вашего первого набора данных я получаю cenrze {3.36,3.00} и radius 2.16

Peter Leow

Спасибо, что опробовали мой код. Ответ добавлен в мое решение.

Patrice T

Я считаю изменение move_x уточнением, поскольку оно приводит к лучшему решению.

Peter Leow

Добро пожаловать.

Graeme_Grant

Я согласен с ppolymorphe. Чтобы помочь вам, вот что я вижу:

--------------------------------------------------------
** Тест: 1 & gt; Питер Леоу-набор 1-12 локаций ....

Радиус: 2.158829 центр: (3.356944,3.009809)

(1.2, 3.1) находится на круге
(4.7, 4.7) находится на круге
(1.9, 2) находится внутри круга
(2.1, 3.5) находится внутри круга
(3.6, 3.5) находится внутри круга
(2.3, 4.6) находится внутри круга
(4.9, 1.5) находится на круге
(1.4, 3.2) находится внутри круга
(2.1, 2.3) находится внутри круга
(1.8, 2.3) находится внутри круга
(1.7, 3.5) находится внутри круга
(2.2, 2.4) находится внутри круга
--------------------------------------------------------
** Тест: 2 & gt; Питер Леоу-набор 2-12 локаций ....

Радиус: 2.158829 центр: (3.356944,3.009809)

(1.2, 3.1) находится на круге
(4.7, 4.7) находится на круге
(1.9, 2) находится внутри круга
(4.1, 3.5) находится внутри круга
(3.6, 3.5) находится внутри круга
(3.3, 4.6) находится внутри круга
(4.9, 1.5) находится на круге
(1.4, 3.2) находится внутри круга
(2.8, 2.3) находится внутри круга
(1.8, 2.3) находится внутри круга
(1.7, 3.5) находится внутри круга
(2.2, 2.4) находится внутри круга
--------------------------------------------------------
** Тест: 3 & gt; Питер Леоу-Набор 3-12 локаций ....

Радиус: 2.441311 центр: (3.5,3.5)

(1.2, 3.1) находится внутри круга
(4.7, 4.7) находится внутри круга
(1.9, 2) находится внутри круга
(2.1, 5.5) находится на окружности
(3.6, 3.5) находится внутри круга
(2.3, 4.6) находится внутри круга
(4.9, 1.5) находится на круге
(1.4, 3.2) находится внутри круга
(2.1, 2.3) находится внутри круга
(1.8, 2.3) находится внутри круга
(4.7, 3.5) находится внутри круга
(2.2, 2.4) находится внутри круга

Peter Leow

См. раздел добавленный ответ на мое решение.

Graeme_Grant

- да, понимаю. Я отвечал Тебе, когда ты отвечал пполиморфу. :)

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

Peter Leow

Да. Спасибо, что опробовали мой код.

Graeme_Grant

Хорошо смотрится с регулировкой. :)