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

[Tonny_Bennet]

Здравствуйте.

Пишу программу, частью алгоритма которой является проверка на принадлежность заданной точки на плоскости заданному восьмиугольнику. На время отладки аппроксимировал восьмиугольник кругом заданного радиуса. Теперь решил перейти к восьмиугольнику. (сейчас я задаю его при помощи координат вершин; если есть какой-нибудь другой метод скажите пожалуйста). Нашёл на просторах Интернета интересную идею: построить с пробной точкой и соседними вершинами восьмиугольника треугольники. Просуммировать их площадь. Если сумма площадей равна площади восьмиугольника - точка внутри, иначе - снаружи. Просто и не затратно, подумал я. Закодил.

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

И вот если ставить точное равенство то картина получается не полная... некоторые фрагменты отсутствуют. Если поставить меньше или равно - по-моему появляются и лишние элементы рисунка :(

В общем я думаю это из-за несовершенства алгоритма проверки принадлежности точки.

[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, это не оно?!
Кушниренко Лебедев Проект Выпуклая оболочка (http://www.google.ru/search?q=%D0%9A%D1%83%D1%88%D0%BD%D0%B8%D1%80%D0%B5%D0%BD%D0%BA%D0%BE+%D0%9B%D0%B5%D0%B1%D0%B5%D0%B4 %D0%B5%D0%B2+%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82+%D0%92%D1%8B%D0%BF%D1%83%D0%BA%D0%BB%D0%B0%D1%8F+% D0%BE%D0%B1%D0%BE%D0%BB%D0%BE%D1%87%D0%BA%D0%B0). Там эта задача:

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

Если вкратце, то определение, принадлежит ли точка полигону, заданному координатами своих вершин, сводится к перебору рёбер полигона (отрезков, соединяющих его вершины) и определения, будет ли «освещено» очередное ребро полигона, если поместить в координаты точки источник света:
Прежде всего, заметим, что понятие освещенности было определено неформально и при этом использовалось расположение точки относительно всего многоугольника. Желательно было бы, чтобы освещенность или неосвещенность ребра определялась только по точке и ребру. Это можно сделать для ориентированных ребер (ориентированного многоугольника) следующим образом: рассмотрим ориентированное ребро AB, новую точку T и ориентированную площадь треугольника ABT:
http://img843.imageshack.us/img843/4651/62602926.png
http://img199.imageshack.us/img199/6920/27157692.png
(ориентированная площадь треугольника считается как половина площади параллелограмма, натянутого на векторы TA и TB).

Легко видеть:
http://img28.imageshack.us/img28/6681/83008457.png
что если многоугольник ориентирован «против часовой стрелки», то ребро AB освещено из T тогда и только тогда, когда:
http://img17.imageshack.us/img17/5473/70656117.png

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

[ferget]

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

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