Принадлежность точки фигуре.

[Winer]

Принадлежность точки фигуре.

Вот такой чисто алгоритмический вопрос, необходимо определить, находиться точка внутри объёмной фигуры, или снаружи. Объёмная фигура задаёться только координатами(например для куба для каждой его плоскости даються координаты 4-х вершин). Как это можно сделать.
Для двумерной фигуры всё очень просто, либо ищется количество пересечений линии, проведённой из исследуемой точки с гранями фигуры, либо используеться алгоритм построчного заполнения(сканирования) фигуры.

Заранее спасибо.

 

[Дионис]

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

 

[jer]

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

1. для фигуры необходимо задавать (при ее создании) одну точку принадлежащую фигуре;
2. при проверке определять по одну ли сторону находятся проверяемая точка и точка принадлежащая фигуре;
3. если для всех плоскостей проверяемая точка и точка точно принадлежащая фигуре находятся по одну сторону, то точка принадлежит фигуре.

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

 

[Дионис]

это тебе надо на какой-нить форум по графике сходить

А при чем тут графика? Геометрия!!!

 

[jer]

предмет (прикладная наука) называется "компьютерная графика"

 

[Sad Spirit]

Автор оригинала: Winer
Вот такой чисто алгоритмический вопрос, необходимо определить, находиться точка внутри объёмной фигуры, или снаружи. Объёмная фигура задаёться только координатами(например для куба для каждой его плоскости даються координаты 4-х вершин). Как это можно сделать.

Фигура выпуклая? Если да, то можно использовать аппарат опорных функций:

c(A,\psi) = \max_{a\in A}\langle a, \psi \rangle

где \psi --- n-мерный вектор
в случае выпуклого многогранника, заданного вершинами:

c(A, \psi) = \max_{i=1,\ldots , m}\langle a_i, \psi \rangle

точка a будет принадлежать множеству A, если

\langle a, \psi \rangle \leq c (A, \psi), \forall \psi \in S

где S --- окружность единичного радиуса.

 

[neko]

Фигура выпуклая? Если да, то можно использовать аппарат опорных функций:

а если нет, разбить ее на выпуклые и для каждой...

вообще то надо открыть учебник по аналитической геометрии/стереометрии а не на форум лезть