Дуга задана тремя точками в трёхмерном пространстве, помогите определить лежит ли заданная точка на этой дуге.
Буду благодарен любой помощи

Здравствуйте, igas, Вы писали:

I>Дуга задана тремя точками в трёхмерном пространстве, помогите определить лежит ли заданная точка на этой дуге.
I>Буду благодарен любой помощи

1) строим плоскость, проходящую через эти точки
2) если заданная точка плоскости не принадлежит, то ответ отрицательный
3) вводим какую-нибудь декартову систему координат на плоскости, переводим координаты всех точек в нее, таким образом сводя задачу к двумерной
4) строим уравнение окружности, проходящей через три точки
5) если заданная точка окружности не принадлежит, то ответ отрицательный
6) вводим полярную систему координат с центром, совпадающим с центром окружности, переводим координаты крайних точек дуги и заданной точки в нее
7) если угловая координата заданной точки попадает в отрезок, заданный угловыми координатами крайних точек дуги, то ответ положительный, иначе отрицательный

Здравствуйте, LuciferSaratov, Вы писали:

I>>Дуга задана тремя точками в трёхмерном пространстве, помогите определить лежит ли заданная точка на этой дуге.

LS>1) строим плоскость, проходящую через эти точки
LS>2) если заданная точка плоскости не принадлежит, то ответ отрицательный
LS>3) вводим какую-нибудь декартову систему координат на плоскости, переводим координаты всех точек в нее, таким образом сводя задачу к двумерной
LS>4) строим уравнение окружности, проходящей через три точки
LS>5) если заданная точка окружности не принадлежит, то ответ отрицательный
LS>6) вводим полярную систему координат с центром, совпадающим с центром окружности, переводим координаты крайних точек дуги и заданной точки в нее
LS>7) если угловая координата заданной точки попадает в отрезок, заданный угловыми координатами крайних точек дуги, то ответ положительный, иначе отрицательный

Начиная с пункта 3 сложновато, не проще ли: строим центр окружности как точку пересечения этой плоскости с срединными перпендикулярами к двум парам исходных точек, сравниваем расстояние до этого центра от проверяемой точки и от одной из искомых. Если равны — то точка лежит и на сфере и на плоскости, то есть на нужной окружности, если не равны — не лежит.
Можно в символьном виде записать проверяемое равенство, там что-нибудь может сократиться, вычисления упростятся (можно будет явно координаты центра не искать).

Здравствуйте, cures, Вы писали:

C>Начиная с пункта 3 сложновато, не проще ли: строим центр окружности как точку пересечения этой плоскости с срединными перпендикулярами к двум парам исходных точек,

если вычисления делать с трехмерными координатами, то в общем-то можно просто рассчитать точку пересечения срединных перпендикуляров, она автоматически получится принадлежащей плоскости этой дуги.
однако искать точку пересечения двух прямых в трехмерном пространстве это та еще морока.
скорее всего автору топика это нужно для расчетов в программе, а там будут практически неизбежны неточности вычислений.
и вычислив эти срединные перпендикуляры может оказаться, что они не пересекаются вообще — из-за неточности операций с плавающей точкой.
это нужно будет как-то учитывать при расчетах.
в этом отношении перевод всего в координаты на плоскости даст более стабильный результат — срединные перпендикуляры в плоскости точно пересекутся.

> сравниваем расстояние до этого центра от проверяемой точки и от одной из искомых. Если равны — то точка лежит и на сфере и на плоскости, то есть на нужной окружности, если не равны — не лежит.
C>Можно в символьном виде записать проверяемое равенство, там что-нибудь может сократиться, вычисления упростятся (можно будет явно координаты центра не искать).

к такому решению нужно еще придумать какой-то прием, который позволит проверить принадлежность именно дуге, а не только окружности.
очевидный путь — это сравнение угловых координат точек, а для этого нужно вычислять центр.

Здравствуйте, LuciferSaratov, Вы писали:

LS>Здравствуйте, igas, Вы писали:

I>>Дуга задана тремя точками в трёхмерном пространстве, помогите определить лежит ли заданная точка на этой дуге.
I>>Буду благодарен любой помощи

LS>1) строим плоскость, проходящую через эти точки
LS>2) если заданная точка плоскости не принадлежит, то ответ отрицательный
LS>3) вводим какую-нибудь декартову систему координат на плоскости, переводим координаты всех точек в нее, таким образом сводя задачу к двумерной
LS>4) строим уравнение окружности, проходящей через три точки
LS>5) если заданная точка окружности не принадлежит, то ответ отрицательный
LS>6) вводим полярную систему координат с центром, совпадающим с центром окружности, переводим координаты крайних точек дуги и заданной точки в нее
LS>7) если угловая координата заданной точки попадает в отрезок, заданный угловыми координатами крайних точек дуги, то ответ положительный, иначе отрицательный

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

Здравствуйте, LuciferSaratov, Вы писали:

LS>если вычисления делать с трехмерными координатами, то в общем-то можно просто рассчитать точку пересечения срединных перпендикуляров, она автоматически получится принадлежащей плоскости этой дуги.
LS>однако искать точку пересечения двух прямых в трехмерном пространстве это та еще морока.

Зачем прямых? Срединные перпендикуляры в трёхмерном пространстве — это плоскости, плюс исходная плоскость, получается линейная система из трёх уравнений.

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

Про это ничего не сказано, если исходные координаты целочисленные, то всё считается в целых числах (возможно, длинных), а если исходные в плавучке, то можно считать расстояние от целевой точки до окружности и определяться с критериями допуска.

LS>и вычислив эти срединные перпендикуляры может оказаться, что они не пересекаются вообще — из-за неточности операций с плавающей точкой.
LS>это нужно будет как-то учитывать при расчетах.

Если плоскости не пересекутся, то они параллельны, тогда исходные 3 точки не определяют окружность, и задача некорректна. Но тогда и Вашим методом уравнение не построится
Погрешности надо учитывать, конечно.

LS>в этом отношении перевод всего в координаты на плоскости даст более стабильный результат — срединные перпендикуляры в плоскости точно пересекутся.

Тоже не факт Из-за погрешностей от замены координат, если исходная дуга — почти прямая, то прямые могут либо вообще не пересечься, либо пересечься в произвольной точке, очень далёкой от центра окружности. Как с этим бороться — непонятно, нужно чёткое ТЗ.

C>> сравниваем расстояние до этого центра от проверяемой точки и от одной из искомых. Если равны — то точка лежит и на сфере и на плоскости, то есть на нужной окружности, если не равны — не лежит.

LS>к такому решению нужно еще придумать какой-то прием, который позволит проверить принадлежность именно дуге, а не только окружности.
LS>очевидный путь — это сравнение угловых координат точек, а для этого нужно вычислять центр.

Про дугу не заметил, да. Но там не сказано, что дуга должна быть между точками, да и что значит между — ещё надо определять, ТС этого не сделал, и, наверное, пока об этом не думал. Можно попробовать через сонаправленность векторных произведений, если действительно нужно.

Здравствуйте, cures, Вы писали:

LS>>однако искать точку пересечения двух прямых в трехмерном пространстве это та еще морока.

C>Зачем прямых? Срединные перпендикуляры в трёхмерном пространстве — это плоскости, плюс исходная плоскость, получается линейная система из трёх уравнений.

да, верно. считал срединные перпендикуляры по привычке прямыми : )

C>Тоже не факт Из-за погрешностей от замены координат, если исходная дуга — почти прямая, то прямые могут либо вообще не пересечься, либо пересечься в произвольной точке, очень далёкой от центра окружности. Как с этим бороться — непонятно, нужно чёткое ТЗ.

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

C>Про дугу не заметил, да. Но там не сказано, что дуга должна быть между точками, да и что значит между — ещё надо определять, ТС этого не сделал, и, наверное, пока об этом не думал.

похоже на недостаточно формализованную практически нужную фичу в чем-то вроде графического редактора.

C>Можно попробовать через сонаправленность векторных произведений, если действительно нужно.

я тоже об этом думал, но сходу для меня неочевидно, получится ли так.

Здравствуйте, LuciferSaratov, Вы писали:

LS>Здравствуйте, cures, Вы писали:

C>>Про дугу не заметил, да. Но там не сказано, что дуга должна быть между точками, да и что значит между — ещё надо определять, ТС этого не сделал, и, наверное, пока об этом не думал.

LS>похоже на недостаточно формализованную практически нужную фичу в чем-то вроде графического редактора.

Дуга окружности задана тремя точками, соответственно одна из них начало дуги, одна из них — точка через которую дуга проходит и ещё одна — конец дуги. Да и это нужно определить.

Здравствуйте, igas, Вы писали:

I>Дуга окружности задана тремя точками, соответственно одна из них начало дуги, одна из них — точка через которую дуга проходит и ещё одна — конец дуги. Да и это нужно определить.

Известно ли, которая из них — начало, которая — конец, и которая — промежуточная? Никакие две из этих точек не совпадают? В чём изначально заданы координаты? Какие допуски?
Зачем скорость вычисления? Предполагается, что будет мало дуг, и для каждой много проверяемых точек? Или много и дуг, и точек? Может ли дуга быть больше развёрнутого угла?

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