Часто/Обыцно/Иногда для определения находится ли точка внутри или вне плоского многоугольника используется трассировка лучей – смотрят сколько раз произвольный луч выпущенный на свободу из этой самой точки пересекает границу многоугольника. Если это число чётное – точка внутри. Нечётное – вне.
Но есть меленькая хитрость: если на пути луча встречается вершина – сушествует опасность что она будет посчитана два раза: по одному пересечению для каждой из двух сторон смежных в ней…
Лечится легко: –
При проверке пересечения считается что для каждой стороны только одна вершина ей принадлежит (а-ля "начало") а второй находится в полном распоряжении смежной стороны. (на рис. точка А принадлежит стороне AB, точка B – чтороне BC, точка C – чтороне CD и т. д.)
Но мы ведь люди трёхмерные, поэтому давайте перейдём в пространство!
Итак, дан некий трёхмерный многоугольник. Ясно, что при трассировке луча опять возникает проблема множественного учёта пересечения с рёбрами и вершинами – почти так же как и в уже рассмотренном случае…
Внимание вопрос(Ы):
* Сушествует ли тут "лечение" аналогичное 2D-варианту? (точнее:
"в каких случаях оно сушествует?")
** Если да, то сколько сушествует различных вариантов распределения принадлежности рёбер/вершин граням?
** Если нет, то, естественно,
почему?