VPF::Нахождение координат центра и радиуса

Тутанхамец

Дата 25.4.2006, 07:54 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 612
Регистрация: 10.10.2005
Где: в пирамидЕ!

Репутация: нет
Всего: 6

Здравствуйте, уважаемые.

Вот нашел алгоритм. Но он иногда дает деление на ноль.
Если х2=х1 или х2=х2, то есть если ДВЕ точки лежат на одной прямой по х.
И что? Тогда задача не имеет решения? Фигня какая-то...
Не подскажете, как интерпретировать эту ситуацию?

Код


{================================================} 
{     This program is taken from the book,       } 
{ "PASCAL programs in science and engineering"   } 
{    by Jules H. Gilder & J. Scott Barrus        } 
{   Published by, HAYDEN ISBN 0-8104-6265-6      } 
{================================================} 
{ Title:  Circle Finder                          } 
{ Program Summary: Program will find the center  } 
{ and radius of a circle that is formed by three } 
{ points not in a straight line.                 } 
{================================================} 
 
Program Circle_Finder; 
 uses Crt; 
var 
   cont     : Char; 
    X1,X2,X3,     Y1,Y2,Y3,      Part1,    Part2,    Part3,    Part4,    X,Y,    Radius   : Real; 
 
Procedure Title; 
   begin 
        Clrscr; 
        Writeln('Circle Finder');        Writeln; 
        Writeln('This program will find the center and'); 
        Writeln('radius of a circle that is determined'); 
        Writeln('by any three points in a plane that '); 
        Writeln('does not form a straight line.'); 
        Writeln; 
        Writeln('Note: For all entries that require'); 
        Writeln('      data entries (x,y); separate '); 
        Writeln('      all data with a space.'); 
        Writeln; 
   end;  { Title } 
 
Procedure Input; 
  begin 
     Write('Enter first point  (X,Y):   '); 
     Readln(X1,Y1); 
     Write('Enter second point (X,Y):   '); 
     Readln(X2,Y2); 
     Write('Enter third point  (X,Y):   '); 
     Readln(X3,Y3); 
     Writeln;Writeln;Writeln; 
  end; 
 
Procedure Find; 
   begin 
     Part1 := ((X2-X1) * (X2+X1) + (Y2-Y1) * (Y2 + Y1)) / (2.0 * (X2-X1)); 
     Part2 := ((X3-X1) * (X3+X1) + (Y3-Y1) * (Y3 + Y1)) / (2.0 * (X3-X1)); 
     Part3 := (Y2 - Y1) / (X2 - X1); 
     Part4 := (Y3 - Y1) / (X3 - X1); 
{*}   If (Part3=Part4) 
{*}    then begin 
{*}           writeln('three points in a straight line!!! Plz, enter another three points!!!'); 
{*}           exit; 
{*}           end; 
     Y := (Part2 - Part1) / (Part4 - Part3); 
     X := Part2 - Part4 * Y; 
     Radius := SQRT (SQR (X3 - X) + SQR (Y3 - Y)); 
   end; 
 
Procedure Print1; 
   begin 
      Writeln('The circle defined by the following'); 
      Writeln('three points:'); 
      Writeln; 
      Writeln(' X1 = ',X1:7:4,' Y1 = ',Y1:7:4); 
      Writeln(' X2 = ',X2:7:4,' Y2 = ',Y2:7:4); 
      Writeln(' X3 = ',X3:7:4,' Y3 = ',Y3:7:4); 
      Writeln; 
      Writeln('has a radius = ',Radius:4:4); 
      Writeln; Radius:=0; 
      Writeln('at a center located at:'); 
      Writeln; 
      Writeln(' X = ',X:4:4,'    Y = ',Y:4:4); x:=0; y:=0; 
   end; { Print1 } 
 
begin  { Main } 
  Repeat 
        Title; 
        Input; 
        Find; 
        Print1; 
          Writeln;Writeln; 
          Write('Do you have another 3 points? (Y/N)'); 
          Readln(cont); 
   Until cont in ['n','N']; 
end.

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

Мой блог / Мои фотки / Моё Skolkobudet.ru

Тутанхамец

Дата 25.4.2006, 08:53 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 612
Регистрация: 10.10.2005
Где: в пирамидЕ!

Репутация: нет
Всего: 6

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

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

Мой блог / Мои фотки / Моё Skolkobudet.ru

Akina

Дата 25.4.2006, 09:16 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

А ты попробуй решить систему аналитически:

Код


(x-x1)^2 + (y-y1)^2 = R^2
(x-x2)^2 + (y-y2)^2 = R^2
(x-x3)^2 + (y-y3)^2 = R^2

3 уравнения, 3 неизвестных... а потом просто подставляй.

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

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

MBo

Дата 25.4.2006, 09:23 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 5
Всего: 18

Код


function CalcCircle(X0, Y0, X1, Y1, X2, Y2: Integer; var CX, CY, R: Integer):Boolean;
var
  S2, X10, X20, Y10, Y20, L1, L2: Integer;
begin
  X10 := X1 - X0;
  X20 := X2 - X0;
  Y10 := Y1 - Y0;
  Y20 := Y2 - Y0;
  S := 2 * (X10 * Y20 - X20 * Y10);
  Result := S <> 0;
  if Result then begin
    L1 := X10 * X10 + Y10 * Y10;
    L2 := X20 * X20 + Y20 * Y20;
    CX := X0 + (Y20 * L1 - Y10 * L2) div S;
    CY := Y0 + (X10 * L2 - X20 * L1) div S;
    R := Round(Sqrt(Sqr(CX - X0) + Sqr(CY - Y0)));
  end;
end;

Тутанхамец

Дата 25.4.2006, 15:11 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 612
Регистрация: 10.10.2005
Где: в пирамидЕ!

Репутация: нет
Всего: 6

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

МВО, а в твоем варианте S ведь тоже может быть равно нулю. И тогда будет тот же крэш, что и у в моем.

Или нет?

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

Мой блог / Мои фотки / Моё Skolkobudet.ru

MBo

Дата 25.4.2006, 15:20 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 5
Всего: 18

> в твоем варианте S ведь тоже может быть равно нулю. И тогда будет тот же крэш, что и у в моем.
Нет. Если три точки лежат на прямой, то это ловится:

Result := S <> 0;
if Result then begin...

Тутанхамец

Дата 25.4.2006, 15:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 612
Регистрация: 10.10.2005
Где: в пирамидЕ!

Репутация: нет
Всего: 6

Три точки, лежащие на прямой - ловятся и в моем.

Код


If (Part3=Part4) 
{*}    then begin 
{*}           writeln('three points in a straight line!!! Plz, enter another three points!!!'); 
{*}           exit; 
{*}           end;

А если две? Если, скажем, это равносторонний треугольник, нижняя грань которого паралелльная оси х? И

У тебя ведь может быть X10 * Y20 = X20 * Y10? И тогда S=0;

Или нет?

Добавлено @ 15:52
Не знаю, получится ли изобразить... ИМХО, твой способ, как и мой, сломается на прямоугольном треугольнике, нижний катет которого параллелен ОХ, а правый катет параллелен ОУ.

          о   х1, у1
        оо
     о   о
  о      о
оооооо
               х2, у2
х0, у0

х10=х1-х0=х20=х2-х0

у10=у1-у0=у20=у2-у0

X10 * Y20 = X20 * Y10

и тогда S=0

Да, ты это ловишь и не производишь деления, но как посчитать центр и радиус окружность в этом случае?

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

Мой блог / Мои фотки / Моё Skolkobudet.ru

MBo

Дата 25.4.2006, 15:58 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 5
Всего: 18

Не пойму, с чего ты взял, что алгоритм на чем-то "сломается"?

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

Тутанхамец

Дата 25.4.2006, 16:34 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 612
Регистрация: 10.10.2005
Где: в пирамидЕ!

Репутация: нет
Всего: 6

Да, площадь, конечно не нулевая...

Что-то меня в этом алгоритме все равно смущает, но это часто бывает, когда берусь за математику. Ладно, задача работает в большинстве случаев и на данный момент мне этого достаточно.

Спасибо smile

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

Мой блог / Мои фотки / Моё Skolkobudet.ru

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »