3D.ru

Кто знает английский переведите пожалуйста эту статью - http://blackpawn.com/texts/pointinpoly/default.html , очень интересно, но вот знания английского очень низкого уровня, помогите пожалуйста.

А наверно и нет смысла переводить статью, ведь там просто указаны формулы.

это статья про одного мальчика...

о определении наличия точки в треугольнике

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

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

Woolf писал(а):А чо там определять-то? Для любого выпуклого многоугольника точка будет находиться внутри, если при обходе граней по часовой стрелке, точка будет всегда справа для любого отрезка, образованного стороной многоугольника. Как определить лево-право мы уже недавно тут обсуждали. Все, что нужно, это в цикле пробежаться по сторонам.

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

Спасибо. Я думал все сложнее =)

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

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

Да и по сложности вычислений не понятно, что сложнее.

Ну так посчитайте.
2-й вариант:
6 Кроссов, три Дот, три сравнения, два and. Кросс - 6 умножений, три вычитания. Дот - Три умножения, два сложения.
Итого - 45 умножений, 24 сложения/вычитания, три сравнения, два and
3-й вариант (с барицентрическими кооржинатами):
5 Дот, 6 вычитаний, 8 умножений, одно деление, три сравнения, два and
Итого - 23 умножения, 16 сложений/вычитаний, одно деление, три сравнения, два and
___
Даже если считать, что у современных процессоров умножение/деление почти такое же по скорости как сложение/вычитание, все равно 3-й вариант должен быть значительно выгодней.