Точка и треугольник. (В ПРОСтРАНСТВЕ)

← →
Agent[007] (2003-11-02 12:53) [0]

У меня есть некая точка (x0, y0, z0) и треугольник(а соответственно и плоскость)(x1,y1,z1; x2,y2,z2; x3,y3,z3)
Расстояние от точки до плоскости измеряется так:
A=(y2-y1)(z3-z1)-(y3-y1)(z2-z1) B=(x3-x1)(z2-z1)-(x2-x1)(z3-z1) C=(x2-x1)(y3-y1)-(x3-x1)(y2-y1) D=-(A+B+C) расстояние = abs(A*x0 + B*y0 + C*z0 + D) / sqrt(A*A + B*B + C*C)Но это для плоскости(бесконечной)...

Вот вопрос:

Как определить лежит ли проэкция точки на это плоскость в этом треугольнике?

PS: Если кто знает способ проверки пересечения ШАРА с ТРЕУГОЛЬНИКОМ, то скажите, пожалуйста...

PPS: Если не трудно, скажите, что такое НОРМАЛЬ и почему вектор задается всего-лишь тремя координатами, а не шестью (начало, направление)...

← →
Думкин (2003-11-02 13:41) [1]

1.Насчет координат проекции точки на плоскость.Было недавно в Играх или Медиа. Недалеко от начала.

2. После нахождения координат этой точки - надо подумать.

Или можно так:
1. Через прямые образующие треугольник провести плоскости перпендекулярные плоскости треугольника.
2. Подставить координаты точки в правую часть этих уравнений. Получится 3 числа. Знаки этих чисел определят положение точки. Но какие знаки и как - тут вопрос тоньше.
Если положительный знак, то точка лежит в одном полупространстве с вектором нормали к плоскости, который фигурирует в записи уравнения.
Ax+By+Cz+D (A,B,C). Но так как уравнение задается с точностью до знака, то тут и тонкость.
Тебе надо определить - лежат ли точка и третья вершина в одной полуплоскости - исходя из сказанного. И так для всех трех вершин.

3. Принадлежит ли точка шару или нет - это просто. Теперь если есть пара вершин, т. что одна внутри а другая снаружи - то ....

4. Тут путаница. Есть разные вектора - это если по старому, старому и упрощенно.
Одни - это плавающие - они определяют направление и длину(ну типа).
Другие - это когда ты его привяжешь к точке - тут 6 величин.
Нормаль - вектоор который перпендикулярен люому к чему он нормаль. Или иначе скалярка = 0.

P.S. Почитай чего-нить по аналитической геометрии. Александрова например.

← →
nikkie (2003-11-02 14:19) [2]

>3. Принадлежит ли точка шару или нет - это просто. Теперь если есть пара вершин, т. что одна внутри а другая снаружи - то ....
ну это точно не так. например, могут все три точки лежать снаружи, но треугольник будет пересекаться со сферой.

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

← →
DiamondShark (2003-11-02 16:21) [3]

>>и почему вектор задается всего-лишь тремя координатами, а не шестью (начало, направление)...

По определению.

← →
Думкин (2003-11-02 17:13) [4]

> [2] nikkie © (02.11.03 14:19)
> >3. Принадлежит ли точка шару или нет - это просто. Теперь
> если есть пара вершин, т. что одна внутри а другая снаружи
> - то ....
> ну это точно не так. например, могут все три точки лежать
> снаружи, но треугольник будет пересекаться со сферой.

Нет. То что у меня - так. Просто это не охватило все случаи. Поэтому не надо так категорично - точно не так.

← →
Думкин (2003-11-02 17:33) [5]

> [1] Думкин © (02.11.03 13:41)
> Тебе надо определить - лежат ли точка и третья вершина в
> одной полуплоскости - исходя из сказанного

Извиняюсь - описка - я имел в виду полупространство.

← →
uw (2003-11-02 22:09) [6]

>Agent[007] © (02.11.03 12:53)

Уравнения перпендикуляра к плоскости, проходящего через точку (x0, y0, z0), выглядят примерно так:

(x – x0)/A = (y – y0)/B =(z-z0)/C.

Пересечение этой прямой и плоскости решается в лоб, получается точка (Ox, Oy, Oz). Она, естественно, лежит в одной плоскости с вершинами тр. DEF. Теперь нужно понять, лежит ли точка O по одну сторону с вершиной F относительно стороны DE. Решаем пересечение прямых DE и OF, получаем точку (Kx, Ky, Kz). Если выполняется условие Fx < Ox < Kx или Kx < Ox < Fx, то точки O и F лежат по одну сторону от стороны DE, и точка O может быть внутри треугольника. Теперь делаем то же самое с двумя другими сторонами и соответствующими вершинами. Если точка О лежит по одну сторону со всеми вершинами относительно соответствующих сторон, то наша точка внутри треугольника.

Все уравнения линейные, поэтому все решается.

← →
Думкин (2003-11-03 05:22) [7]

1. По поводу принадлежности проекции - все сказано. Только самое простое вижу в описанных мной полупространствах.

2. По поводу треугольника и шара. Есть функция расстояния до центра шара.
Ищем ее максимум и минимум в треугольнике. Если точка максимума вне, а минимума внутри - то ответ ясен, иначе тоже. Точки экстремумма есть - ибо треугольник компактное множество, а функция непрерывна.

← →
nikkie (2003-11-03 13:03) [8]

>Думкин
1. по-моему, самый простой способ проверки того, что точка O лежит внутри треугольника ABC - через вычисление скалярных произведений [OA x OB], [OB x OC], [OC x OA] - они должны быть одинаково направлены, т.е. попарные скалярные произведения должны быть больше 0.

2. понятное дело, надо искать максимум и минимум - вопрос в алгоритме. максимум достигается в какой-то вершине, а минимум - либо в основании проекции, если она лежит внутри треугольника, либо на границе. с границей получается такая же ситуация - либо основание проекции на сторону, либо вершина. получается то, что я описал в [2].

← →
uw (2003-11-03 14:25) [9]

>nikkie © (03.11.03 13:03) [8]

Да, это хорошее решение.

← →
ИдиотЪ (2003-11-03 14:29) [10]

самый простой способ проверки того, что точка O лежит внутри треугольника ABC - вычисление так называемых треугольных координат. Если точка лежит внутри, то все координаты в пределах от 0 до 1.

← →
Думкин (2003-11-03 15:05) [11]

> nikkie © (03.11.03 13:03) [8]
> >Думкин
> 1. по-моему, самый простой способ проверки того, что точка
> O лежит внутри треугольника ABC - через вычисление скалярных
> произведений [OA x OB], [OB x OC], [OC x OA] - они должны
> быть одинаково направлены, т.е. попарные скалярные произведения
> должны быть больше 0.

Но при этом ты ищешь проекцию - я ее не ищу.

← →
ShaggyDoc (2003-11-03 15:18) [12]

http://algolist.manual.ru/maths/geom/belong/

← →
Думкин (2003-11-03 16:21) [13]

> [8] nikkie © (03.11.03 13:03)

А если так, то можно и так:
[PA x PB], [PB x PC], [PC x PA] и составляем скалярные произведения этих векторов с вектором нормали к треугольнику. Если все 3 числа одного знака - то внутри.
То есть есть 3 метода. А вот какой из них будет производительней?

> [10] ИдиотЪ © (03.11.03 14:29)
Нужна не точка а проекция.

> [12] ShaggyDoc (03.11.03 15:18)
Речь об ином.

← →
uw (2003-11-03 16:29) [14]

>Думкин © (03.11.03 15:05) [11]
>Но при этом ты ищешь проекцию - я ее не ищу.

А что ты вообще ищешь? Растолкуй суть твоих пунктов:

>1. Через прямые образующие треугольник провести плоскости перпендекулярные плоскости треугольника.
>2. Подставить координаты точки в правую часть этих уравнений. Получится 3 числа. Знаки этих чисел определят положение точки. Но какие знаки и как - тут вопрос тоньше.

Т.е. мы имеем три уравнения трех плоскостей. Дальше, что куда подставляем? x0 - в правую часть первого уравнения, y0 - в правую часть второго уравнения и т.д.? Что это означает?

← →
ИдиотЪ (2003-11-03 16:35) [15]

← →
uw (2003-11-03 16:41) [16]

← →
Думкин (2003-11-03 17:17) [17]

> [14] uw © (03.11.03 16:29)
Это означает:
1. А что тут непонятно?
2. У нас три урния вида Ax+By+Cz+D=0. Кажде такое делит пространство на три части - 2 полупространства и саму плоскость. Принадлежность точек разным полупространствам определяется разными знаками выражений Ax0+By0+Cz0+D - остальная идея прозрачна. Или нет?

> [16] uw © (03.11.03 16:41)
Оно так, но мне кажется, что в первом случае - вычислений меньше - хотя не проверял. Вполне возможно в третьем еще меньше - надо посмотреть.

> [15] ИдиотЪ © (03.11.03 16:35)
Это вряд ли будет проще.
Да можно - способ описан и в
> [1] Думкин © (02.11.03 13:41)> 1.Насчет координат проекции точки на плоскость.Было недавно в Играх или Медиа. Недалеко от начала.
и в > [6] uw © (02.11.03 22:09) - что одно и тоже.

← →
uw (2003-11-03 17:44) [18]

← →
Думкин (2003-11-04 05:39) [19]

> [18] uw © (03.11.03 17:44)

А что здесь автоматически пишется? Просто это не представляет вопроса - один детерминант и все. А при поиске проекции - без них(детов) тоже никуда.

Точка и треугольник. (В ПРОСтРАНСТВЕ) Найти похожие ветки