Подскажите где взять алгоритм определения принадлежности точки плоскоски заданной по 4-м точкам (в моем случае паралелограмм)?
Нужно знать точка внутри паралелограмма.
Хотелось бы что-нибудь попроще.
Спасибо за внимание к моему сообщению.
И БОЛЬШОЕ СПАСИБО за дельные ответы на мой вопрос.

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

__>Подскажите где взять алгоритм определения принадлежности точки плоскоски заданной по 4-м точкам (в моем случае паралелограмм)?
__>Нужно знать точка внутри паралелограмма.
__>Хотелось бы что-нибудь попроще.

Плоскость, вообще-то, задаётся 3 точками.
Тебе нужно проверить, точка на плоскости или точка на параллелограмме?

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

__>Подскажите где взять алгоритм определения принадлежности точки плоскоски заданной по 4-м точкам (в моем случае паралелограмм)?
__>Нужно знать точка внутри паралелограмма.
__>Хотелось бы что-нибудь попроще.
__>Спасибо за внимание к моему сообщению.
Вообще-то плоскость задается тремя точками Ладно, предположим, что действительно есть 4 точки, образующие невырожденный параллелограмм.

Тогда проверка делается за два этапа: а) определение принадлежности точки плоскости и б) определение попадания точки внутрь параллелограмма.

а) Строим уравнение плоскости в виде Ax+By+Cz+D=0 по любым трем из 4 точек. Подставляем координаты точки в уравнение. Если получается 0, точка принадлежит плоскости.

б) Простая проверка: точка принадлежит параллелограмму, если сумма площадей треугольников, которые образует точка со сторонами параллелограмма, равна площади параллелограмма. Раз уж у нас координаты, воспользуемся тем, что модуль векторного произведения — площадь параллелограмма, построенного на этих векторах, как на сторонах. Соответственно, если есть точки A, B, C, D и "тестовая" точка N, то проверяем

  __  __               __ __       __ __       __ __       __ __
|[AB, AC]| = 1/2 * ( |[NA,NB]| + |[NB,NC]| + |[NC,ND]| + |[ND,NA]| )

__>Подскажите где взять алгоритм определения принадлежности точки плоскоски заданной по 4-м точкам (в моем случае паралелограмм)?

Про то, что исходных точек 3, а 4 уже сказано выше. А вообще точки (x_i, y_i, z_i) (i = 1..4) лежат в одной плоскости, если и только если определитель

|  1   1   1   1  |
| x_1 x_2 x_3 x_4 |
| y_1 y_2 y_3 y_4 |
| z_1 z_2 z_3 z_4 |

равен нулю.

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

__>Подскажите где взять алгоритм определения принадлежности точки плоскоски заданной по 4-м точкам (в моем случае паралелограмм)?
__>Нужно знать точка внутри паралелограмма.
__>Хотелось бы что-нибудь попроще.
__>Спасибо за внимание к моему сообщению.
__>И БОЛЬШОЕ СПАСИБО за дельные ответы на мой вопрос.

Попробуем так:

Договоримся, что пар-м (ABCD) определяется двумя векторами (AB и AD) и точкой A. Пусть E -- данная точка. Проверка принадлежности E пар-му ABCD можно сделать так: a * AB + b * AD = AE. Есть несколько условий принадлежности: 0 <= a,b <= 1, и, собственно, существование решения этой системы. На халяву решение (коэф. a и b) можно поиметь так:

a * [ AB,AD] = [ AE,AD]
b * [ AD,AB] = [ AE,AB]

Если [ AB,AD], [ AE,AD] и [ AE,AB] лежат на одной прямой, то решение существует и счастье есть. Тогда a и b получить понятно как . А иначе точка не лежит в плоскости пар-ма.

Здравствуйте, Кодт, Вы писали:
К>Тебе нужно проверить, точка на плоскости или точка на параллелограмме?
Мне нужно определить попала ли точка в паралелограмм заданный по 4-м точкам.(включая грани илинет без разницы)
Спасибо.

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

__>Здравствуйте, Кодт, Вы писали:
К>>Тебе нужно проверить, точка на плоскости или точка на параллелограмме?
__>Мне нужно определить попала ли точка в паралелограмм заданный по 4-м точкам.(включая грани илинет без разницы)
Ааа... Эээ... Почему грани? Если это действительно параллелограмм, то ответов тебе достаточно дали. Может (раз там грани), речь идет про параллелепипед?

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

К>>Тебе нужно проверить, точка на плоскости или точка на параллелограмме?
__>Мне нужно определить попала ли точка в паралелограмм заданный по 4-м точкам.(включая грани илинет без разницы)

Параллелограмм, кстати говоря, задаётся 3 точками — вне зависимости, два измерения или три.
Параллелепипед — 4 точками.

Ха! Я придумал дешёвое решение!
Выберем систему координат (анизотропную и косоугольную), в которой параллелограмм/параллелепипед превращается в единичный квадрат/куб, причём начало координат — это его угол/вершина.
Построим преобразование из исходной системы в новую.
Преобразуем координаты интересующей нас точки и убедимся, лежат ли они все на интервале (0;1) — если без сторон/граней, или отрезке [0;1] — если со сторонами/гранями.
Всё.

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

или точка на параллелограмме?
__>Мне нужно определить попала ли точка в паралелограмм заданный по 4-м точкам.(включая грани илинет без разницы)

У меня таки ощущение, что на самом деле нужен inside test (или hit-test), то есть, находится ли точка внутри многоугольника на плоскости или снаружи. Оно?

К>Построим преобразование из исходной системы в новую.
К>Преобразуем координаты интересующей нас точки и убедимся, лежат ли они все на интервале (0;1) — если без сторон/граней, или отрезке [0;1] — если со сторонами/гранями.
К>Всё.

Осталось добавить, что матрица преобразования из новой системы в старую устроена так: по столбцам записаны коорданаты векторов-ребер палаллелепипеда (считаем, что начала коордиант уже совмещены). Соответственно, для того, чтобы решить задачу, нужно лишь обратить эту матрицу 3x3.

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

MS>У меня таки ощущение, что на самом деле нужен inside test (или hit-test), то есть, находится ли точка внутри многоугольника на плоскости или снаружи. Оно?

Оно!!! Сейчас сделано на регионах. Но это временный выход из положения и очень хотелось бы сделать ф-ю определения попадания
точки в паралелограмм свою. Свои мысли быи , но одна голова хорошо, а больше вообще ништяк.
Сейчас выглядит так:
Region = CreatePolygonRgn(pt,4,WINDING);// создаем область
}
if (PtInRegion(Region, tX, tY)){
if (Region!=NULL){
DeleteRgn(Region);
Region = NULL;
}
return true;
}
else {
if (Region!=NULL){
DeleteRgn(Region);
Region = NULL;
}
return false;
}
где pt — это массив их 4-x точек задающих область.
Но где-то вычитал , что регионы работают только на главных окнах, а это не есть хорошо.
Спасибо.

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

C>Ладно, предположим, что действительно есть 4 точки, образующие невырожденный параллелограмм.

C>Тогда проверка делается за два этапа: а) определение принадлежности точки плоскости и б) определение попадания точки внутрь параллелограмма.

C>а) Строим уравнение плоскости в виде Ax+By+Cz+D=0 по любым трем из 4 точек. Подставляем координаты точки в уравнение. Если получается 0, точка принадлежит плоскости.

C>б) Простая проверка: точка принадлежит параллелограмму, если сумма площадей треугольников, которые образует точка со сторонами параллелограмма, равна площади параллелограмма. Раз уж у нас координаты, воспользуемся тем, что модуль векторного произведения — площадь параллелограмма, построенного на этих векторах, как на сторонах. Соответственно, если есть точки A, B, C, D и "тестовая" точка N, то проверяем
C>

C>  __  __               __ __       __ __       __ __       __ __
C>|[AB, AC]| = 1/2 * ( |[NA,NB]| + |[NB,NC]| + |[NC,ND]| + |[ND,NA]| )
C>

По-моему первый этап не нужен.Если уж пощади равны то точно внутри.Из неравенства тетраэдера(не путать с треугольником).Площадь грани не превосходит сумму трех остальных

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

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

MS>>У меня таки ощущение, что на самом деле нужен inside test (или hit-test), то есть, находится ли точка внутри многоугольника на плоскости или снаружи. Оно?

__>Оно!!! Сейчас сделано на регионах. Но это временный выход из положения и очень хотелось бы сделать ф-ю определения попадания

Эрик Хайнес поможет.
Подробное описание разных стратегий: http://www.acm.org/tog/editors/erich/ptinpoly/
Исходники: http://www.acm.org/tog/GraphicsGems/gemsiv/ptpoly_haines/
Я бы посоветовал взять самый простейший CrossingsMultiplyTest:
http://www.acm.org/pubs/tog/GraphicsGems/gemsiv/ptpoly_haines/ptinpoly.c (в самом конце).
Тем более, что для четурехугольников он будет самым быстрым.

P.S. Учимся четче формулировать задачу...

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

__>Подскажите где взять алгоритм определения принадлежности точки плоскоски заданной по 4-м точкам (в моем случае паралелограмм)?
может кому будет полезноздесь