[решено] Принадлежность точки к восьмиугольнику

Iska · Отправлено: **07:18, 25-09-2011** | #4

Цитата ferget:

а чем вам не нравится метод трассировки луча?

ferget, это не оно?!

Кушниренко Лебедев Проект Выпуклая оболочка. Там эта задача:

* решается чисто алгоритмически;
* входит как составная часть в более крупный алгоритм;
* решается в целом для замкнутого полигона.

Если вкратце, то определение, принадлежит ли точка полигону, заданному координатами своих вершин, сводится к перебору рёбер полигона (отрезков, соединяющих его вершины) и определения, будет ли «освещено» очередное ребро полигона, если поместить в координаты точки источник света:

Цитата:

Прежде всего, заметим, что понятие освещенности было определено неформально и при этом использовалось расположение точки относительно всего многоугольника. Желательно было бы, чтобы освещенность или неосвещенность ребра определялась только по точке и ребру. Это можно сделать для ориентированных ребер (ориентированного многоугольника) следующим образом: рассмотрим ориентированное ребро AB, новую точку T и ориентированную площадь треугольника ABT:

(ориентированная площадь треугольника считается как половина площади параллелограмма, натянутого на векторы TA и TB).

Легко видеть:

что если многоугольник ориентирован «против часовой стрелки», то ребро AB освещено из T тогда и только тогда, когда:

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