Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/35: Рейтинг темы: голосов - 35, средняя оценка - 4.83
iama
1329 / 980 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
1

Косое произведение векторов

24.03.2011, 18:05. Просмотров 6960. Ответов 12

Элементарная задача - найти площать треугольника, заданного координатами его точек на плоскости. В решении нужна максимальная точность и быстродействие - формула Герона не катит. Почитал про про косое произведение векторов, алгоритм понял так
  1. Сместить координаты так, чтобы первая лежала в (0; 0)
  2. Вычислить площадь паралеллограмма, натянутого на векторы, по формуле |x1*y2 - x2*y1|
  3. Вывести половину площади паралеллограмма
Это, конечно, всё прекрасно, но я заметил, что эта формула возращает ноль, когда 2 точка лежит на оси Х, а 3 - на оси Y. Я неправильно использую формулу? Какая класическая реализация этой задачи? Так и надо через if проверять упомянутый вариант, и просчитывать его отдельно, или тут что-то другое?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.03.2011, 18:05
Ответы с готовыми решениями:

Сложение векторов
Здравствуйте Есть точки имеющие координаты, цвет и прозрачность (ARGB) + у...

Кластеризация бинарных векторов
Здравствуйте! Я тут недавно и пока что не знаю, как лучше задавать вопросы,но...

Векторное умножение векторов
Как умножить два N-мерных вектора? Примечание: необходимо найти координаты ,...

Перебов бинарных векторов веса от 1 до w
Нужен алгоритм, который позволит перебрать все вектора длинной n и веса 1 - w. ...

Найти пару (2 и более) векторов СКО = 0
Есть массив double data Содержит значения -100..100 Нужно найти сумму...

12
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,292
24.03.2011, 19:51 2
2 точка лежит на оси Х => y1 = 0
3 - на оси Y => x2 = 0
Одно из слагаемых равно нулю. А другое-то не равно.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <fstream>
 
using namespace std;
 
ifstream cin("input.txt");
ofstream cout("output.txt");
 
struct point //точка или вектор
{
    double x, y;
    point(double xx = 0, double yy = 0) : x(xx), y(yy) {}
    point operator - (point &a)
    {
        return point(x-a.x, y-a.y);
    }
 
};
 
double wp(point &a, point &b) // wedge product
{
    return a.x*b.y - a.y*b.x;
}
 
double area(point &a, point &b, point &c)
{
    return abs(wp(b-a,c-a))/2;
}
 
int main()
{
    point a, b, c;
    cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
    cout << area(a,b,c);
}
Цитата Сообщение от iama Посмотреть сообщение
В решении нужна максимальная точность и быстродействие - формула Герона не катит.
Если речь об олимпиадной задаче, формула герона скорее всего прокатит как миленькая (если только не требуется действительно очень большая точность, а это нечасто бывает). Но с косым произведением все равно круче.

Добавлено через 11 минут
Где действительно не обойтись без косого произведения - так это определение взаимного расположения векторов (справа/слева).
1
snake32
1675 / 1125 / 199
Регистрация: 26.02.2009
Сообщений: 4,179
Записей в блоге: 5
24.03.2011, 19:52 3
Косое произведение векторов??

я знаю только два вида произведения векторов:
скалярное и векторное.

Ваша задача решается через векторное. Только оно определено в 3д пространстве и только.
Поэтому все ваши вершины должны иметь 3 кмпонента x,y,z

здесть есть формулы(Delphi)
Простая работа с OpenGL на Delphi. Вычисление нормали.

сначала нужно вычесть из двух вершин третью
результат перемножить
после векторного произведения нужно найти его длину и разделить на 2
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,292
24.03.2011, 19:57 4
Цитата Сообщение от snake32 Посмотреть сообщение
Косое произведение векторов??
я знаю только два вида произведения векторов:
А погуглить?
1
iama
1329 / 980 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
24.03.2011, 20:01  [ТС] 5
Хохол, хорошо, возьмем такой пример - (0; 0), (1; 0), (0; 1). 1*0 - 0*1 = 0. А площадь-то - 0,5. Кстати, ваш пример не компилирует, на 26 строке ругает неправильную инициализацию point. Сам я реализовывал так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <stdlib.h>
 
using namespace std;
 
long double t(long double a, long double b)
{
  if (a < 0.00001) return b; else return a;
}
 
int main()
{
  long double x1, y1, x2, y2, x3, y3;
 
  cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
 
  x2 -= x1; x3 -= x1; y2 -= y1; y3 -= y1;
 
  if (((x2 == 0) & (y3 == 0)) | ((x3 == 0) & y2 == 0))
    cout << t(abs(x2), abs(x3)) * t(abs(y2), abs(y3)) / 2.0;
  else
    cout << abs(x2*y3 - x3*y2) / 2.0 << endl;
 
  return 0;
}
но совсем мне этот вариант не нравится, кривой он. Хотя тут прокатило

Добавлено через 1 минуту
snake32, http://ru.wikipedia.org/wiki/Псевдоскалярное_произведение
1
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,292
24.03.2011, 20:05 6
Ну вы неправильно считаете по своей же формуле.
(0; 0), (1; 0), (0; 1)
x1 = 1, y1 = 0
x2 = 0, y2 = 1
x1*y2 - x2*y1 = 1*1 - 0*0
1
iama
1329 / 980 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
24.03.2011, 20:07  [ТС] 7
Хохол, со мной бывает, извиняйте
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,292
24.03.2011, 20:07 8
Цитата Сообщение от iama Посмотреть сообщение
на 26 строке ругает неправльную инициализацию point
Странно, всю жизнь так пишу. Какой компилятор?
0
iama
1329 / 980 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
24.03.2011, 20:12  [ТС] 9
Хохол, GNU C++, под Code::Blocks
Лог
||=== test, Debug ===|
\CodeBlocks\test\test\main.cpp||In function 'double area(point&, point&, point&)':|
\CodeBlocks\test\test\main.cpp|26|error: invalid initialization of non-const reference of type 'point&' from a temporary of type 'point'|
\CodeBlocks\test\test\main.cpp|19|error: in passing argument 1 of 'double wp(point&, point&)'|
\CodeBlocks\test\test\main.cpp|26|error: 'abs' was not declared in this scope|
||=== Build finished: 3 errors, 0 warnings ===|
0
Mr.X
Эксперт С++
3184 / 1711 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
24.03.2011, 22:29 10
Цитата Сообщение от iama Посмотреть сообщение
на 26 строке ругает неправильную инициализацию point.
Не знаю как у вас, а мой компилятор пишет предупреждение, что abs там для целых чисел, и совершенно справедливо, так как перегруженные функции abs по Стандарту находятся в заголовоке cmath.
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,292
24.03.2011, 22:44 11
В VS 2010 все пучком - ни единого варнинга ^_^
Ну и работает правильно соответственно.
0
taras atavin
4206 / 1773 / 211
Регистрация: 24.11.2009
Сообщений: 27,565
29.03.2011, 08:08 12
Цитата Сообщение от iama Посмотреть сообщение
Элементарная задача - найти площать треугольника, заданного координатами его точек на плоскости. В решении нужна максимальная точность и быстродействие - формула Герона не катит. Почитал про про косое произведение векторов, алгоритм понял так
  1. Сместить координаты так, чтобы первая лежала в (0; 0)
  2. Вычислить площадь паралеллограмма, натянутого на векторы, по формуле |x1*y2 - x2*y1|
  3. Вывести половину площади паралеллограмма
Это, конечно, всё прекрасно, но я заметил, что эта формула возращает ноль, когда 2 точка лежит на оси Х, а 3 - на оси Y. Я неправильно использую формулу? Какая класическая реализация этой задачи? Так и надо через if проверять упомянутый вариант, и просчитывать его отдельно, или тут что-то другое?
Произведение векторов есть скалярное, векторное и смешанное, но ни как не косое.
0
iama
1329 / 980 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
29.03.2011, 08:26  [ТС] 13
taras atavin,
Цитата Сообщение от snake32 Посмотреть сообщение
я знаю только два вида произведения векторов:
скалярное и векторное.
0
29.03.2011, 08:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.03.2011, 08:26

Скалярное произведение векторов(косинус), разность векторов
Кто понимает, объясните, пожалуйста, как вы понимаете, почему две формулы -...

Определить функцию работы с векторами: Сложение векторов, разность, умножение на скаляр,скалярное произведение векторов,вычисление длины вектора
с помощью фукнций map/ map-into / reduce определить функцию работы с векторами:...

Произведение векторов
Вот написал функцию которая должа умножать вектора(находить нормаль): ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru