Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Построить треугольник

Автор: p0s0l 2.6.2005, 07:46

Вобщем, вопрос простейший smile

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

Автор: Domestic Cat 2.6.2005, 07:55

Теорема косинусов

c²=a² + b² - 2ab cos C

где С - угол, противолежащий стороне с.
Отсюда находишь косинусы всех трех углов.

Автор: poor_yorik 2.6.2005, 09:38

А по моему будет попроще с координатами.
Пусть треугольник со строонами a, b, c.
Возьмем первую вершину A с координатами (0, 0).
Вторая вершина пусть будет будет иметь координаты (b, 0).
А с третей стороной будет посложнее.
Во первых вычисли такие формулы.
p=(a+b+c)/2
S=sqrt(p*(p-a)*(p-b)*(p-c))
h=2*S/h
x=sqrt(a*a-h*h)

Ну тогда координаты третей будут (x,h).

Автор: p0s0l 2.6.2005, 10:39

Domestic Cat, poor_yorik, спасибо! Не ожидал, что так быстро среагируют smile

Попробовал оба варианта, через теорему косинусов расчет в принципе оказался не сложнее, если даже не проще...
А вариант poor_yorik чего-то не заработал, разбираться чего и как нет времени, но тут h делится на неопределенное само себя:
h=2*S/h, не знаю, что тут должно быть на самом деле smile

Автор: III.nfo 2.6.2005, 10:55

poor_yorik
Хорошее решение!
Только
p=(a+b+c)/2;
S=sqrt(p*(p-a)*(p-b)*(p-c));
h=2*S/a;
x=sqrt(c*c-h*h);
Если треугольник такой (по таким точкам и такими названиями сторон, извиняюсь за плохое качество):
/C\
c/ \b
A/__a__\B

A(0;0);
B(b;0);
C(x;x);
p0s0l
Этот вариант менее русурсоёмкий.
Кстати, взять бумажку и подправить код тоже можно.

Автор: p0s0l 2.6.2005, 21:38

Цитата(III @ 2.6.2005, 10:55)

Только
p=(a+b+c)/2;
S=sqrt(p*(p-a)*(p-b)*(p-c));
h=2*S/a;
x=sqrt(c*c-h*h);

Да, теперь работает

Цитата(III @ 2.6.2005, 10:55)

Этот вариант менее русурсоёмкий.

Этот как ? Если посчитать количество операций, то через теорему косинусов даже меньше выходит smile

, или как ресурсоёмкость измерять, в чем ?

Код


  cosB := (b*b - a*a - c*c) / (-2*a*c));
  sinB := Sqrt(1 - cosB*cosB);
  xx2 := cosB*a;
  yy2 := sinB*a;
// 1 операция корня, 1 деление, 8 умножений, 3 сложения

Код


  p := (a+b+c)/2;
  s := sqrt(p*(p-a)*(p-b)*(p-c));
  h := 2*s/a;
  x := sqrt(c*c-h*h);
// 2 операции корня, 1 деление, 7 умножений, 6 сложений

Цитата(III @ 2.6.2005, 10:55)

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

К сожалению, совершенно нет времени на разбирательства... smile

PS:

Цитата(III @ 2.6.2005, 10:55)

/C\
c/ \b
A/__a__\B

Используй теги кода, тогда бы выглядело так (пробелы не съелись бы):

Код


   /C\
 c/   \b
A/__a__\B

Автор: III.nfo 3.6.2005, 08:50

p0s0l
Насчёт code - спасибо.
Также, скорость выполнения - одинакова, сейчас проверил на .NET:

Код


int a = 3;
int b = 4;
int c = 5;
Console.ReadLine ();
Console.WriteLine (DateTime.Now + "." + DateTime.Now.Millisecond);
double cosb1 = (b*b - a*a - c*c) / (-2*a*c);
double sinb1 = System.Math.Sqrt (1 - cosb1*cosb1);
double xx2 = cosb1*a;
double yy2 = sinb1*a;
Console.WriteLine (DateTime.Now + "." + DateTime.Now.Millisecond);
Console.WriteLine (DateTime.Now + "." + DateTime.Now.Millisecond);
double p1 = (a+b+c)/2;
double s = System.Math.Sqrt (p1*(p1-a)*(p1-b)*(p1-c));
double h = 2*s/a;
double x = System.Math.Sqrt(c*c-h*h);
Console.WriteLine (DateTime.Now + "." + DateTime.Now.Millisecond);
Console.ReadLine ();

Автор: p0s0l 3.6.2005, 12:24

Цитата(III @ 3.6.2005, 08:50)

Также, скорость выполнения - одинакова, сейчас проверил на .NET:

И какая она ? 0 мс ? smile

Тут же такие микроскопические вычисления, что DateTime не должен их отловить...
Или же .NET на столько медленный, что эти вычисления занимают милисекунды ? (в этом сомневаюсь, хотя с .Net не работал...)
Надо бы сделать большой цикл повторяющихся вычислений...

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

Автор: III.nfo 3.6.2005, 17:47

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

Автор: poor_yorik 3.6.2005, 17:58

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

Автор: p0s0l 4.6.2005, 13:33

Цитата(III @ 3.6.2005, 17:47)

Как ошибочный, если работает smile

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

Цитата(poor_yorik @ 3.6.2005, 17:58)

Отнюдь не так... В обоих способах, можно принять, что координаты вершины А = (0, 0), координаты вершины B = (a, 0). Координаты третьей вершины вычисляются по формулам... В общем, сравни:

Код

  cosB := (b*b - a*a - c*c) / (-2*a*c);
  sinB := Sqrt(1 - cosB*cosB);

  xx[1] := 0;
  yy[1] := 0;
  xx[2] := a;
  yy[2] := 0;
  xx[3] := cosB*c;
  yy[3] := sinB*c;

Код


  p := (a+b+c)/2;
  s := sqrt(p*(p-a)*(p-b)*(p-c));
  h := 2*s/a;

  xx[1] := 0;
  yy[1] := 0;
  xx[2] := a;
  yy[2] := 0;
  xx[3] := sqrt(c*c-h*h);
  yy[3] := h;

Как видишь, даже строк кода-то больше smile

во втором способе, не говоря уже о коренных вычислениях...

Только еще обнаружился 1 баг во втором способе при тестировании... Дело в том, что все координаты (x и y) треугольника всех трех вершин данным способом получаются положительными... Хотя бывают ситуации, когда знак xx[3] должен быть отрицательным... Пример - на рисунке... Для тестирования я генерил случайным образом координаты трех вершин треугольника, вычислял длины сторон, и по ним обоими способами строил новые треугольники. Через теорему косинусов всегда треугольник получался на ура, а вторым способом - иногда даже очень сильно отличался (в одной координате).
Т.е. надо еще дорабатывать второй способ для таких ситуаций, чтобы получался отрицательный знак X (возможно даже что-то простейшее)...

Автор: poor_yorik 5.6.2005, 11:24

p0s0l, таки да на одну строчку у меня код больше, но зато и без тригонометрии.
А насчет отрицательных координат, я так понял когда тупоугольный треуголник.
Так если посмотришь, треугольник то все равно будет правильный, просто в нем стороны c и b местами поменялись.

Автор: p0s0l 5.6.2005, 14:25

Цитата(poor_yorik @ 5.6.2005, 11:24)

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

Честно говоря, смотря на вычисления обоих способов, я ни в одном не увидел ни операций синусов, ни косинусов и др тригонометрических операций... Обычные умножения, сложения и т.д.... Или ты про что ?

Цитата(poor_yorik @ 5.6.2005, 11:24)

А насчет отрицательных координат, я так понял когда тупоугольный треуголник.
Так если посмотришь, треугольник то все равно будет правильный, просто в нем стороны c и b местами поменялись.

Это как ? Исходные длины сторон: 89, 95 и 9. Через теорему косинусов эти стороны и получаются. Через твой способ получаются: 89, 83 и 9... Тут нигде ни с чем не менялось, одна сторона получилась короче, чем нужно... По координатам (если посмотришь приаттаченный рисунок) ясно и понятно, что причина неправильного расчета твоего способа в том, что x-координата третьей вершины (которую вычисляем) имеет другой знак, нежели необходимый (вместо -5,694 имеем +5,694)... Может и пример не совсем удачный, на глаз можно подумать, что две стороны просто поменялись, но приглядись к цифрам...

Автор: p0s0l 5.6.2005, 14:34

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

Автор: SoWa 6.6.2005, 19:01

Я вспомнил Геометрию 7-8 класса. Там сказано так:
-Строим отрезок длинной одной из сторон.
-Проведем окружности радиусами двух других сторон с центрами в концах отрезка.
-Соединим точку пересечения окружностей с концами отрезка(точку будем искать из уравнений окружностей)

Вот и треугольник.

Автор: p0s0l 7.6.2005, 23:19

Цитата(SoWa @ 6.6.2005, 19:01)

Попробовал ради интереса решить и так. Вобщем, после решения уравнений окружностей формулы получаются абсолютно те же, что и в теореме косинусов smile

Автор: poor_yorik 9.6.2005, 15:16

p0s0l, прошу прощения. Решил исправить свою ошибку.
Что поделать, если я такой дурак.
Вот чтобы решение было правильное нужно изменить эту строчку.
x=sqrt(sqr(max(a,c))-sqr(h))

Автор: p0s0l 9.6.2005, 21:06

Вот, теперь работает smile

Но мне все равно через т. косинусов нравится больше smile

Спасибо за участие!

Автор: BOB4uK 22.5.2008, 17:00

Конечно тема старая, но может ее авторы отслеживают (надеюсь на это)!
У меня вопрос!
Как построить многоугольник спомощью треугольников?
Извесны только стороны и диагонали (многоугольник состоит из треугольников).
Я начал писать и зашел в тупик...
первый треугольник построил беспроблем а вотт как быть дальше? вроди пишу но както мне не нравится...

Автор: SoWa 22.5.2008, 17:18

Уф, археологи, блин smile

Если известны диагонали и вершины. Если вершины для полного счастья пронумерованы, то элементарно.
Допустим имеем.
Вершина 1.
Вершина 2.
Вершина 3.
Вершины 1 и 3- диагональ.
Строим треугольник по очевидным данным из трех вершин.

Сложнее если диагональ Вершина 1 - Вершина 5 например.
Но решается так же. На бумажке посиди, порисуй.

Автор: BOB4uK 22.5.2008, 17:35

Вот пример:
Стороны:
АБ 300
БС 500
СД 300
ДА 500
БД 583 - диагональ

Это прямоугольник, но прога этого не знает!

строим первый треугольник как выше описывалось, а вот второй?
Я вот запутался со сторонами треугольников! Че да как? В геометрии не селен!
Нужна помощь!

Автор: SoWa 22.5.2008, 17:52

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

Автор: xDragon 29.5.2008, 11:59

Вопрос: а можно ли вместо корня, для синусов, использовать какуюнито аналогичную формулу, как и для косинусов?

Автор: SoWa 29.5.2008, 14:32

?
Формулу в студию. Не совсем понимаю, о чем ты.
Если о теоремах- то вспомни геометрию. Есть еще теорема синусов.

Автор: maxdiver 29.5.2008, 23:54

Наверно имеется в виду формула для косинуса через скалярное произведение.

Автор: BOB4uK 4.6.2008, 16:59

Задачу решил через пересечение двух окружностей... зная что даны изначально две точки с координатами (0;0) и (0;длина одно стороны)...

Но вот тут подумал и пришел к выводу что можно еще по другому сделать:
учитывая что известны первые две точки находим третью как описано выше...
затем зная две другие точки нужно сделать тоже самое, приравнять одну точку к (0;0) вторую к (0;длина стороны) находим точку и нужно ее перевести в обратную систему координат... Вот только я не могу собраться с мыслями...
Прошу помощи! Или я что то не так понимаю?