LINUX.ORG.RU
Форум — Talks  

Алгоритм пересечения отрезка с выпуклым многоугольником. Не понимаю


0

1

http://www.intuit.ru/department/graphics/graphalg/class/free/5/3.html

http://www.intuit.ru/department/graphics/graphalg/class/free/5/05_07.gif

«В каждом из этих вариантов для нахождения пересечения отрезка с окном необходимо уметь определять принадлежность точки выпуклому многоугольнику. Из рис. 5.7 видно, что если для любой точки g, принадлежащей многоугольнику (или его границе), и произвольной точки ребра f построить вектор m=g-f, то выполняется условие m.n>=0, поскольку угол между векторами не может превышать 90°. Таким образом, если данное условие выполняется для всех ребер многоугольника, то точка является внутренней.»

Я начертил многоугольник, поставил произвольную точку внутри него, вторую - на ребре. Кроме этих четырех координат, ничего нет. Как построить вектора g и f, которые можно друг из друга вычесть? Или каждую точку нужно рассматривать как радиус-вектор? Я попробовал так, но угол a получился острым. Скорее всего, подразумевалось что-то другое:(

http://tinypic.com/view.php?pic=2cz7t02&s=7

★★★★

Угол между построенным вектором и нормалью и должен получатся острым. Если он тупой, значит точка находится на другой стороне от ребра относительно многоугольника.
А вектор g-f можно просто вычислить математически, вычитанием координат f из координат g. Ну и либо геометрически, отложив вектор, обратный ветору f(начальная точка меняется местами с конечной точкой) от конца ветора g.

Tark ★★
()

По рисунку на tinypic. Что за угол «a» я не понимаю. Угол в условии вычисляется между вектором g-f(у вас вроде опечатка и написано f-g) и нормалью к ребру квадрата на котором лежит точка f. И он не может быть больше 90 градусов, если точка находится по нужную сторону этого ребра.

Tark ★★
()
Ответ на: комментарий от Tark

Понятно, про нормаль-то и забыл

wingear ★★★★
() автор топика
Ответ на: комментарий от Tark

т.е., все сводится к тому, что точка не должна лежать на прямых, параллельных граням многоугольника?

wingear ★★★★
() автор топика
Ответ на: комментарий от wingear

>т.е., все сводится к тому, что точка не должна лежать на прямых, параллельных граням многоугольника?
Нет, представьте, что грань многоугольника это линия OX(линия по которой отмечается ось X координат), а нормаль - OY. Угол между нормалью и вектором до произвольной точки будет меньше 90 градусов пока они по одну сторону OX.
Грубо говоря вы можете встать на ровном полу и привязать к ноге веревку. Вы будете обозначать нормаль, а веревка - вектор до нужной точки. Между вами и веревкой угол больше 90 градусов может быть только если веревка будет под полом, а не внутри комнаты.
А точка в любом случае будет лежать на прямых параллельных граням многоугольника, так как этому условию соответствуют любые точки на плоскости.

Tark ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Talks