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

Определить, по какую сторону плоскости точки - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
29.03.2014, 17:58     Определить, по какую сторону плоскости точки #1
Добрый вечер.

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

Даны 5 точек - A, B, C, X, Y. Несовпадающие точки A, B, C задают плоскость. Нужно определить, находятся ли точки X и Y по одну или по разные стороны от плоскости.

Вкурил тему с двумерным случаем, векторные и псевдоскалярные произведения, но как применить для трехмерного случая - не хватает фантазии

Подскажите, пожалуйста!
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.03.2014, 17:58     Определить, по какую сторону плоскости точки
Посмотрите здесь:

C++ Определить, какую фигуру образуют 4 точки
C++ Даны координаты точки на плоскости. Определить и вывести на экран номер квадранта, в который попадает точка
C++ Определить радиус и центр окружности минимального радиуса, проходящей хотя бы через три различные точки заданного множества точек на плоскости
Определить радиус и центр окружности минимального радиуса, проходящей хотя бы через три различные точки заданного множества точук на плоскости C++
C++ Две точки заданы своими координатами на плоскости.определить,какая из них находится ближе к началу координат
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
just_freelance
61 / 37 / 9
Регистрация: 15.03.2014
Сообщений: 315
29.03.2014, 18:01     Определить, по какую сторону плоскости точки #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Можно найти уравнение плоскости по 3 точкам. Затем подставить в него координаты точек. Если значения одного знака, то точки по 1 сторону и наоборот.
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
29.03.2014, 18:06  [ТС]     Определить, по какую сторону плоскости точки #3
Цитата Сообщение от just_freelance Посмотреть сообщение
Можно найти уравнение плоскости по 3 точкам
Ок, пусть получили уравнение вида Ax + By + Cz + D = 0
Цитата Сообщение от just_freelance Посмотреть сообщение
Затем подставить в него координаты точек.
Точек X и Y? они же в большинстве случаев не удовлетворяют этому уравнению (не лежат на плоскости)?
dimcoder
Полярный
 Аватар для dimcoder
449 / 422 / 66
Регистрация: 11.09.2011
Сообщений: 1,108
29.03.2014, 18:09     Определить, по какую сторону плоскости точки #4
Цитата Сообщение от Asker Посмотреть сообщение
Ax + By + Cz + D = 0
скорее
y = Ax + Bx + Cx + D
just_freelance
61 / 37 / 9
Регистрация: 15.03.2014
Сообщений: 315
29.03.2014, 18:12     Определить, по какую сторону плоскости точки #5
Цитата Сообщение от Asker Посмотреть сообщение
Ax + By + Cz + D
подставляем сюда координаты. Если число положительное, то точка над плоскостью, 0 — принадлежит, отрицательное — под плоскостью.
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
29.03.2014, 18:14  [ТС]     Определить, по какую сторону плоскости точки #6
Цитата Сообщение от dimcoder Посмотреть сообщение
y = Ax + Bx + Cx + D
Нет, это уравнение прямой.

Добавлено через 1 минуту
just_freelance,

Добавлено через 12 секунд
теперь понятно, сейчас попоробую
AndrSlav
44 / 44 / 6
Регистрация: 20.12.2013
Сообщений: 241
29.03.2014, 18:32     Определить, по какую сторону плоскости точки #7
Векторное произведение AB и AC задает вектор, перпендикулярный плоскости. Если скалярное произведение этого вектора на вектор AX (или BX или CX) больше нуля - точка с той стороны плоскости, куда показывает результат векторного произведения, иначе - с другой стороны.
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
29.03.2014, 19:07  [ТС]     Определить, по какую сторону плоскости точки #8
Да, всем спасибо, это работает
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
// точка - массив float[3] 
float plat_turn(float * a, float * b, float * c, float * x)
{
    float a21 = b[0] - a[0],
          a22 = b[1] - a[1],
          a23 = b[2] - b[2],
          a31 = c[0] - a[0],
          a32 = c[1] - a[1],
          a33 = c[2] - a[2];
    float A = (a22 * a33 - a23 * a32),
          B = (a23 * a31 - a21 * a33),
          C = (a21 * a32 - a22 * a31);
    float D = - a[0]*A - a[1]*B - a[2]*C;
    return A*x[0] + B*x[1] + C*x[2] + D;
}
 
 
int main()
{
    float a[3] = {0, 0, 1};
    float b[3] = {0, 1, 0};
    float c[3] = {1, 0, 0};
 
    float checkpoint1[3] = {0, 0, 0};
    float checkpoint2[3] = {3, 7, 5};
    float checkpoint3[3] = {-100500, -8, 0.07};
 
    cout << plat_turn(a, b, c, checkpoint1) << endl;
    cout << plat_turn(a, b, c, checkpoint2) << endl;
    cout << plat_turn(a, b, c, checkpoint3) << endl;
}
Байт
 Аватар для Байт
14004 / 8835 / 1234
Регистрация: 24.12.2010
Сообщений: 16,014
29.03.2014, 19:33     Определить, по какую сторону плоскости точки #9
Цитата Сообщение от Asker Посмотреть сообщение
это работает
Да, но зачем? Левой ногой правое ухо чесать - полезно для развития гибкости ног.
Хочу пояснить мысль уважаемого just_freelance. Пусть есть плоскость, уравнение коей Ax+By+Cz+D=0
Эта плоскость разбивает пространство на 3 множества.
0) Точки, принадлежащие множеству. Подстановка их координат в выражение Ax+By+Cz+D дает 0
1) Точки. лежащие с одной стороны плоскости. Подстановка их координат в это выражение дает число больше нуля.
-1) Точки. лежащие с другой стороны плоскости. Подстановка их координат в это выражение дает число меньше нуля.
Это все понятно из "обще-топологических" соображений (да не пугает вас это слово!) Просто возьмите мысленно точку в одной из половин пространства и немного подвигайте ее. Ясно, что знак выражения Ax+By+... изменится только при пересечении плоскости.
IrineK
Заблокирован
29.03.2014, 20:43     Определить, по какую сторону плоскости точки #10
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
using std::cin;
using std::cout;
 
typedef struct _TPoint
{   double x,y,z;
}   TPoint;
 
typedef struct _TVector
{   double x,y,z;
}   TVector;
 
TPoint *CreatePoint ()
{   TPoint *point = new TPoint;
    point->x = point->y = point->z = 0.;
    return point;
}
 
void DeletePoint (TPoint *point)
{   delete point;
}
 
void SetPointDialogue (TPoint *point, char *name)
{   cout << name << ":\n";
    cout <<"\tx = "; cin >> point->x;
    cout <<"\ty = "; cin >> point->y;
    cout <<"\tz = "; cin >> point->z;
    cin.sync();
}
 
void SetPoint (TPoint *point, double x, double y, double z)
{   point->x = x;
    point->y = y;
    point->z = z;
}
 
TVector *CreateVector (TPoint *a, TPoint *b)
{   TVector *vector = new TVector;
    vector->x = b->x - a->x;
    vector->y = b->y - a->y;
    vector->z = b->z - a->z;
    return vector;
}
 
void DeleteVector (TVector *vector)
{   delete vector;
}
 
//векторное произведение
void CrossProduct (TVector *res, TVector *a, TVector *b)
{   res->x = a->y*b->z - a->z*b->y;
    res->y =  - a->x*b->z + a->z*b->x;
    res->z = a->x*b->y - a->y*b->x;
}
 
//скалярное произведение
double DotProduct (TVector *a, TVector *b)
{   return a->x*b->x + a->y*b->y + a->z*b->z;
}
 
//смешанное произведение
double TripleProduct (TVector *a, TVector *b, TVector *c)
{   TVector res;
    CrossProduct (&res, b, c);
    return DotProduct (a, &res);
}
 
int main()
{   setlocale (LC_CTYPE, "Russian");
    
    TPoint *A, *B, *C, *X, *Y;
    A = CreatePoint();
    SetPoint(A, 1,0,0);
    B = CreatePoint();
    SetPoint(B, 0,1,0);
    C = CreatePoint();
    SetPoint(C, 0,0,1);
 
    X = CreatePoint();
    SetPointDialogue (X, "X");
    Y = CreatePoint();
    SetPointDialogue (Y, "Y");
 
    TVector *AB, *AC, *AX, *AY;
    AB = CreateVector (A, B);
    AC = CreateVector (A, C);
    AX = CreateVector (A, X);
    AY = CreateVector (A, Y);
 
    if (TripleProduct (AX, AB, AC) * TripleProduct (AY, AB, AC) > 0)
        cout << "Точки лежат по одну сторону от плоскости";
    else if (TripleProduct (AX, AB, AC) * TripleProduct (AY, AB, AC) < 0)
        cout << "Точки лежат по разные стороны от плоскости";
    else 
        cout << "По крайней мере одна из точек лежит в плоскости";
 
    DeletePoint (A); DeletePoint (B); DeletePoint (C); DeletePoint (X); DeletePoint (Y);
    DeleteVector (AB); DeleteVector (AC); DeleteVector (AX); DeleteVector (AY);
 
    cin.get();
    return 0;
}
Добавлено через 50 секунд
Собственно, решение задачи - это строка 90-95.
Все остальное - необходимый довесок.
Байт
 Аватар для Байт
14004 / 8835 / 1234
Регистрация: 24.12.2010
Сообщений: 16,014
29.03.2014, 21:25     Определить, по какую сторону плоскости точки #11
Уважаемая IrineK, ни секунды не сомневаясь в ваших способностях и опыту, как программиста, даже не стал смотреть код вашей программы, он, без сомнения - блестящь! Но заметив в коде функцию CrossProduct, осмелился все-таки сделать маленькое замечание. Все значительно проще! Математическое обоснование было представлено уважаемым just_freelance уже в посте #2. Я в своем посте #9 просто попытался это разъяснить. Это же самая элементарная (в мое время - 1-й курс любого техвуза, а ноне и в школе это проходят) аналитическая геометрия! И не надо здесь никаких векторных произведений! Всего лишь чуток здравого смысла. Ведь непрерывная функция (а Ax+By+Cz+D именно такова) не может сменить знака, не перейдя через ноль.
Кстати, ценность вышеизложенных соображений еще и в том, что они работают в пространствах любой размерности, с любыми гиперплоскостями. А как вы там свой CrossProduct будете использовать?
С уважением.
IrineK
Заблокирован
29.03.2014, 21:45     Определить, по какую сторону плоскости точки #12
В решении со смешанными векторами есть некоторое преимущество, если мы перейдем к практическим задачам, где координаты задаются интами, а размерность равна 3. Если нужно перелопатить много точек, это - быстрое и точное решение.

Что касается больших размерностей, уравнение плоскости изменится:
f = Ax+By+Cz+Du + E (4-мерное пространство)
http://www.cyberforum.ru/cgi-bin/latex.cgi?f = {A}_{0} +\sum_{1}^{n}{A}_{i}\cdot {X}_{i}
и это нужно будет учесть в коде.
Т.е. решение Ax+By+Cz+D не является универсальным и требует допиливания. Построение плоскости через N точек в N-мерном пространстве - это не так тривиально.

Но и смешанные вектора можно допилить )
Байт
 Аватар для Байт
14004 / 8835 / 1234
Регистрация: 24.12.2010
Сообщений: 16,014
29.03.2014, 22:41     Определить, по какую сторону плоскости точки #13
Цитата Сообщение от IrineK Посмотреть сообщение
Построение плоскости через N точек в N-мерном пространстве - это не так тривиально.
Ну, принципиальных сложностей не вижу. Просто нормаль считается определителем N-го порядка. Вместо i, j, k - I1... IN. И миноры считать N-1 -го порядка. Конечно, простым умножением тут не обойтись. Придется циклы циклить или рекурсию рекурсировать. А уж нормаль есть - все далее как по маслу.
Впрочем, трудоемкость похожая. Только при моем подходе не нужно скалярные произведения считать. И получить удовольствие от использования хорошо известного математического факта.
IrineK
Заблокирован
29.03.2014, 22:49     Определить, по какую сторону плоскости точки #14
Цитата Сообщение от Байт Посмотреть сообщение
трудоемкость похожая
Один в один.

Цитата Сообщение от Байт Посмотреть сообщение
не нужно скалярные произведения считать
Умножение вектора коэффициентов на вектор координат - не похоже ли на скалярное произведение?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.03.2014, 22:55     Определить, по какую сторону плоскости точки
Еще ссылки по теме:

C++ Ввести координаты точки на плоскости, и определить, попала ли эта точка в заштрихованную область
C++ Даны четыре точки на плоскости, определить какое расстояние меньше
По заданным целочисленным координатам на плоскости определить какую геометрическую фигуру они образуют C++

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

Или воспользуйтесь поиском по форуму:
Байт
 Аватар для Байт
14004 / 8835 / 1234
Регистрация: 24.12.2010
Сообщений: 16,014
29.03.2014, 22:55     Определить, по какую сторону плоскости точки #15
Цитата Сообщение от IrineK Посмотреть сообщение
Умножение вектора коэффициентов на вектор координат - не похоже ли на скалярное произведение?
Сдаюсь. Уговорили.
Yandex
Объявления
29.03.2014, 22:55     Определить, по какую сторону плоскости точки
Ответ Создать тему
Опции темы

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