Форум программистов, компьютерный форум CyberForum.ru

Многоугольник в пространстве - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.79
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
18.03.2013, 11:06     Многоугольник в пространстве #1
Добрый день!

Не могли бы вы мне помочь? У меня такая задача. Даны две точки A и B в трёхмерном пространстве, которые образуют вектор. А еще дан отрезок R. Как в трехмерном пространстве построить n-угольник, который лежит в плоскости, перпендикулярной вектору AB и который вписан в окружность радиусом R (например, на картинке построен шестиугольник)? Т.е. надо просто получить координаты (в массиве, например).


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

Заранее спасибо!
Изображения
 
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
HighPredator
 Аватар для HighPredator
5350 / 1733 / 320
Регистрация: 10.12.2010
Сообщений: 5,119
Записей в блоге: 3
18.03.2013, 11:23     Многоугольник в пространстве #2
Если нужен не правильный многоугольник, то пишете уравнение окружности и берете с него сколько надо точек.
Если нужен правильный, то для вычисления координат вершин можно использовать уравнения. Все они есть в той же википедии.
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
18.03.2013, 11:38  [ТС]     Многоугольник в пространстве #3
Мне нужен именно правильный многоугольник. В Википедии-то есть уравнения, но там только две координаты! В этом-то вся и проблема, что я не знаю, как третью припихнуть Ведь надо "нарисовать" многоугольник в плоскости, перпендикулярной вектору, а как получить эту плоскость?
IrineK
Заблокирован
18.03.2013, 12:09     Многоугольник в пространстве #4
Если есть вектор n = (A,B,C)
то любая плоскость вида Ax+By+Cz+D = 0 - перпендикулярна этому вектору.
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
18.03.2013, 12:19     Многоугольник в пространстве #5
Наверно проще построить новую систему координат, чтобы плоскость Ox'y' была перпендикулярна вектору AB. Тогда координаты вершин многоугольника легко написать, типа (1,0,0), (cos пи/3, sin пи/3, 0) и т. д. Потом умножить эти векторы на матрицу перехода и получить координаты точек в старой системе координат.
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
18.03.2013, 12:24  [ТС]     Многоугольник в пространстве #6
Построить в плоскости многоугольник - с этим проблем нет. Т.е. задача сводится к повороту относительно некоторого вектора, правильно я понимаю?
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.03.2013, 12:25     Многоугольник в пространстве #7
крути один конец отрезка вокруг вектора каждый раз на http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{360^0}{n} и ни каких гвоздёв.
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
18.03.2013, 12:27  [ТС]     Многоугольник в пространстве #8
Цитата Сообщение от taras atavin Посмотреть сообщение
крути один конец отрезка вокруг вектора каждый раз на и ни каких гвоздёв.
Хорошо, а откуда начальный вектор взять? т.е. который мы будем крутить?
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
18.03.2013, 12:29     Многоугольник в пространстве #9
Цитата Сообщение от Asker Посмотреть сообщение
Т.е. задача сводится к повороту относительно некоторого вектора, правильно я понимаю?
Я предложил другое решение. Но вы понимаете правильно. Только вам придется вычислить матрицу поворота вокруг вектора AB. Это непростая задача.

Добавлено через 1 минуту
Цитата Сообщение от Asker Посмотреть сообщение
Хорошо, а откуда начальный вектор взять? т.е. который мы будем крутить?
Взять любой вектор, который перпендикулярен AB (имеет с ним нулевое скалярное произведение) и домножить его на множитель так, чтобы его длина стала равной R.
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
18.03.2013, 12:34  [ТС]     Многоугольник в пространстве #10
Цитата Сообщение от palva Посмотреть сообщение
Взять любой вектор, который перпендикулярен AB (имеет с ним нулевое скалярное произведение) и домножить его на множитель так, чтобы его длина стала равной R.
А как это можно сделать?
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
18.03.2013, 12:38     Многоугольник в пространстве #11
Цитата Сообщение от Asker Посмотреть сообщение
А как это можно сделать?
А я разве не написал, как? Найти какое-нибудь решение уравнения
http://www.cyberforum.ru/cgi-bin/latex.cgi?AB_x x+AB_y y+AB_z z=0
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
18.03.2013, 12:38  [ТС]     Многоугольник в пространстве #12
Не так вопрос поставил тут почитал, понял, вопрос стоит так: допустим, я получил вектор, коллинеарный нужному (т.е. который будем вращать), мне, но он имеет длину, не равную R. Как домножить этот вектор и получить координаты коллинеарного вектора с длиной R?
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.03.2013, 12:40     Многоугольник в пространстве #13
колинеарный - это параллельный. на 1 с любым знаком. но тебе нужен копланарный.
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
18.03.2013, 12:41     Многоугольник в пространстве #14
Цитата Сообщение от Asker Посмотреть сообщение
Как домножить этот вектор и получить координаты коллинеарного вектора с длиной R?
Длина вектора равна корню квадратному из суммы квадратов его компонент. То есть все компоненты вектора нужно будет разделить на длину вектора и умножить на R
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
18.03.2013, 12:49  [ТС]     Многоугольник в пространстве #15
Последний вопрос: как повернуть один вектор вокруг другого вектора? Через матрицы?
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
18.03.2013, 13:00     Многоугольник в пространстве #16
Цитата Сообщение от Asker Посмотреть сообщение
Последний вопрос: как повернуть один вектор вокруг другого вектора?
Это к вам вопрос. Вы свели свою задачу к более сложной. Об этом я вам уже написал выше.
Если же отвечать на ваш вопрос... Нужно умножить вектор на матрицу поворота. Матрицу поворота вокруг любой из осей системы координат написать довольно просто. Ну вот и делайте последовательные повороты, чтобы перевести ось z в вектор AB (для этого понадобится два поворота вокруг осей системы координат) потом делайте поворот вокруг AB (оси z) на нужный вам угол, потом делайте два обратных поворота, чтобы вернуться к исходной системе координат. Произведение этих пяти матриц даст вам матрицу поворота.
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
18.03.2013, 13:04  [ТС]     Многоугольник в пространстве #17
Как это я усложнил?
Какой самый простой быстрый для компьютера будет вариант решения задачи?
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
18.03.2013, 14:27     Многоугольник в пространстве #18
Судя по игроделам, которым часто требуется решать задачи пространственных поворотов, эффективней всего использовать кватернионы. Но я слабо с этим знаком, мягко говоря.

Добавлено через 53 минуты
Цитата Сообщение от Asker Посмотреть сообщение
Как это я усложнил?
Вот смотрите: в 5 я предложил способ решения задачи. В 6 вы предложили другой способ при помощи поворотов и спросили правильно ли вы понимаете. в 9 я ответил, что предлагал другое, но ваш способ тоже подойдет, хотя он будет сложнее.
IrineK
Заблокирован
18.03.2013, 16:42     Многоугольник в пространстве #19
На основании того, что написано в Википедии, получается такое:
Миниатюры
Многоугольник в пространстве  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.03.2013, 09:43     Многоугольник в пространстве
Еще ссылки по теме:

C++ Соединить рёбра в многоугольник
Построить многоугольник по координатам C++
Многоугольник. Переопределение оператора += C++

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

Или воспользуйтесь поиском по форуму:
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
19.03.2013, 09:43  [ТС]     Многоугольник в пространстве #20
Кто-нибудь знает, в какой программе можно построить несколько 3D точек, чтобы посмотреть чисто визуально, правильно программа работает или нет?

Добавлено через 53 минуты
При помощи Excel построил точки, на правду похоже, поэтому задача решена выложил сюда, может быть, она кому-нибудь пригодится
Чтобы это сделать, пришлось вспомнить, что такое правильный многоугольник, его уравнения, нормированные векторы, матрица поворота и как умножать матрицы.
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <math.h>
using namespace std;
#define pi  3.141592653589793238462643383279502884197169399375 
const int n = 10;
const int r = 15;
 
struct Point3d // Структура точки в трёхмерном пространстве
{long double x, y, z;};
 
long double qw(long double k) {return k*k;} // возведение в квадрат
 
int main()
{
Point3d A, B, a[n]; // Массив из всех вершин n-угольника
long double R = 15, // радиус описанной около многоугольника окружности
            AB,     // Это длина вектора AB
            p, q, r,// Это координаты нормированного радиус-вектора
            t;      // Это для промежуточных вычислений (оптимизация извлечения кв. корня)
 
A.x = 5;  // AB - любой 
A.y = 3;  // радиус-вектор
A.z = -4; // от балды
B.x = 7;  //  
B.y = 2;  // 
B.z = -6; // 
 
AB = sqrt(qw(B.x-A.x)+qw(B.y-A.y)+qw(B.z-A.z)); //находим длину вектора AB
 // делаем нормированный вектор n(p, q, r):
p = (B.x-A.x)/AB;
q = (B.y-A.y)/AB;
r = (B.z-A.z)/AB;
// промежуточные вычисления :
t = sqrt(p*p+q*q);
// формируем обратную матрицу:
long double M[3][2] = 
    {r*p/t,  -q/t, 
     r*q/t,   p/t, 
      -t,      0};
long double T[2]; // временная матрица
// По идее, там должно быть 3 элемента: x, y и Z. Но z у нас изначально равен 0,
// поэтому я его убрал
 
for (int i=0; i<n; i++) // 
{
T[0]=R*cos(2*pi*i/n); // строим в плоскости по формуле из Википедии
T[1]=R*sin(2*pi*i/n); //
 
a[i].x = T[0]*M[0][0] + T[1]*M[0][1] + A.x; // поворачиваем, используя
a[i].y = T[0]*M[1][0] + T[1]*M[1][1] + A.y; // умножение матриц
a[i].z = T[0]*M[2][0] + T[1]*M[2][1] + A.z; //
 
cout << "Point " << i+1 << " : (" << a[i].x << "; " << a[i].y << "; " << a[i].z << ");\n";
}
 
system("pause");
return 0;
}
Мучался несколько дней, а кода - меньше листа

Огромное спасибо IrineK и palva за помощь!
Yandex
Объявления
19.03.2013, 09:43     Многоугольник в пространстве
Ответ Создать тему
Опции темы

Текущее время: 04:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru