[Естественный язык]Задача по геометрии

[Бинари]

Дано множество точек, заданных своими координатами (оси направлены так: (0,0) - левый верхний угол, ось x - вправо, ось y - вниз, все координаты положительны).

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

Мне нужен алгоритм на ЕСТЕСТВЕННОМ языке: "обычную" геометрию понимаю плохо и ненавижу ещё со школы.

Заранее спасибо.

[Utkin]

Уравнение окружности знаем? Берем одну из точек за центр, остальные подставляем в уравнение. Это в общих чертах... Конкретно я бы подумал как выбрать точку в центре скопления остальных точек, чтобы повысить шансы на успех.

[Serge_Bliznykov]

Мне нужен алгоритм на ЕСТЕСТВЕННОМ языке: "обычную" геометрию понимаю плохо и ненавижу ещё со школы.

что вы называете "естественным" языком? Расстояние между точками, треугольник, три перпендикуляра к сторонам треугольника, проведённые через их середины, точка пересения, описанная вокруг треугольника окружность - это всё обычная геометрия или "естественный" язык?

И непонятно, как Вы собираетесь решать задачу на геометрию БЕЗ геометрии?!..

[evg_m]

1. берем любые три точки (a,b,c)
вычисляем центр и радиус (x,r) окружности проходящей через три точки.
ищем уравнение окружности подставляем координаты, решаем систему уравнений
2. если есть берем четвертую точку (d). иначе заканчиваем работу.
нужна формула расстояния между двумя точками на плоскости.
определяем ее расстояние до центра окружности (п1)
3. если расстояние <= радиуса(r) то точка внутри окружности (или НА окружности) и берем новую точку и переходим к п2.

4. в противном случаем выбираем новую окружность из тех что проходят через нашу точку (d) и две точки из трех (a,b,с). Таких окружностей возможно три. А четвертая оставшаяся точка должна лежать внутри этой окружности.
т.е. проверяем (с) внутри (a,b, d); (b) внутри (a,c, d); (a) внутри (b,c, d)
теперь п3 выполняется, поэтому берем новую точку и повторяем п2.

[Serge_Bliznykov]

в помощь решающему:

1) ОТСЮДА

Type TPoint = Record {Тип точка}
      X, Y : Extended;
     End;
 
{Поиск центра описанной окружности. Если точки лежат на одной прямой, функция возвращает false, иначе true}
Function FindOuterRadius(A, B, C : TPoint; Var Rr : TPoint): Boolean;
Var M : Array[1..2,1..3] Of Extended;
    D, Dx, Dy : Extended;
Begin
 M[1, 1] := 2 * (A.X - B.X);
 M[1, 2] := 2 * (A.Y - B.Y);
 M[1, 3] := Sqr(A.X) +Sqr(A.Y) - (Sqr(B.X) + Sqr(B.Y));
 
 M[2, 1] := 2 * (B.X - C.X);
 M[2, 2] := 2 * (B.Y - C.Y);
 M[2, 3] := Sqr(B.X) +Sqr(B.Y) - (Sqr(C.X) + Sqr(C.Y));
 
 D := M[1, 1] * M[2, 2] - M[2, 1] * M[1, 2];
 Dx := M[1, 3] * M[2, 2] - M[2, 3] * M[1, 2];
 Dy := M[1, 1] * M[2, 3] - M[2, 1] * M[1, 3];
 
 If D <> 0 Then
  Begin
   Rr.X := Dx/D;
   Rr.Y := Dy/D;
   FindOuterRadius := True;
  End Else
  Begin
   Rr.X := 0;
   Rr.Y := 0;
   FindOuterRadius := False;
  End;
End;

2) вариант "с эвристикой" я бы брал точку, находящуюся ближе всего к центру координат,
находил для неё МАКСИМАЛЬНО УДАЛЁННУЮ.
а потом для этой пары перебирал все оставшиеся точки,
для каждой полученной тройки находя центр и радиус описанной окружности,
проверял - сколько точек попадает внутрь круга.
Максимум, имхо, и даст нужный ответ.

3) для небольших количествах точек (меньше 100) можно тупо перебирать ВСЕ возможные сочетания.
Пример перебора на Паскаль смотрите тут:
Задача "Треугольник" Нахождения минимального периметра.

[Utkin]

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

[Serge_Bliznykov]

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

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

ну, не надо ничего "достраивать"!

Коллега, для любого треугольника заведомо существует описанная вокруг него окружность.

Код, который я привёл выше как раз и возвращает ЦЕНТР данной окружности. (радиус окружности можно найти, взяв расстояние от центра до любой вершины треугольника - до любой - потому что все три вершины треугольника лежат на описанной окружности).

[Utkin]

ну, не надо ничего "достраивать"!

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

[Serge_Bliznykov]

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

Это Вы, как птица, просто заблуждаетесь! :-D




если интересно, то это нарисовано таким кодом:

procedure TForm1.Button2Click(Sender: TObject);
const
  Triangle: array[1..4] of TPoint = ((X: 150; Y: 100), (X: 200; Y:100),
    (X: 280; Y: 200), (X:  150; Y: 100));
var
  cR : TPoint;
  R  : extended;
begin
  if FindOuterRadius(Triangle[1], Triangle[2], Triangle[3], cR) then begin
    R := sqrt(sqr(cR.x - Triangle[1].x) + sqr(cR.y - Triangle[1].y) );
    Canvas.Ellipse(round(cR.x - R), round(cR.y - R), round(cR.x + R), round(cR.y + R));
  end;
  Canvas.MoveTo(Triangle[1].x, Triangle[1].y);
  Canvas.LineTo(Triangle[2].x, Triangle[2].y);
  Canvas.LineTo(Triangle[3].x, Triangle[3].y);
  Canvas.LineTo(Triangle[1].x, Triangle[1].y);
end;

[Бинари]

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