[ferget]

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

[Tonny_Bennet]

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

тем что он слишком уж громоздкий.

проблему решил встроенными средствами C#. Построил область. Нашёл метод определяющий принадлежит ли точка области.

Код:

            PointF[] _oct_vertex = new PointF[8];
            _oct_vertex[0] = new PointF(1,0);
            _oct_vertex[1] = new PointF(2.5f, 0);
            _oct_vertex[2] = new PointF(3.5f, 1);
            _oct_vertex[3] = new PointF(3.5f, 2.5f);
            _oct_vertex[4] = new PointF(2.5f, 3.5f);
            _oct_vertex[5] = new PointF(1, 3.5f);
            _oct_vertex[6] = new PointF(0, 2.5f);
            _oct_vertex[7] = new PointF(0, 1);

            
            byte[] _type_vertex = new byte[8];

            _type_vertex[0] = (byte)PathPointType.Start;

            for (int i=1; i<=_type_vertex.Length -1; i++)
            {
                _type_vertex[i] = (byte)PathPointType.Line;
            }

            Region octagon = new Region(new GraphicsPath(_oct_vertex, _type_vertex));


            if (octagon.IsVisible(pt))
            {
                return true;
            }
            else
            {
                return false;
            }

[Iska]

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

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

читать дальше »

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

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

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

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

[ferget]

это 3D вариант
а в 2D

Предположим, что нам необходимо определить принадлежность точки а полигону р. Для этого из некоторой удаленной точки проведем прямую линию в точку а. На этом пути может встретиться нуль или несколько пересечений границы полигона: при первом пересечении мы входим внутрь полигона, при втором — выходим из него, при третьем пересечении снова входим внутрь и так до тех пор, пока не достигнем точки а. Таким образом каждое нечетное пересечение означает попадание внутрь полигона р, а каждое четное — выход из него. Если мы попадаем в точку а с нечетным числом пересечений границы полигона, то точка а лежит внутри полигона, а если получается четное число пересечений, то точка находится вне полигона р.