 |
|
| Tonny_Bennet |
25-09-2011 00:39 1759564 |
Принадлежность точки к восьмиугольнику
Здравствуйте.
Пишу программу, частью алгоритма которой является проверка на принадлежность заданной точки на плоскости заданному восьмиугольнику. На время отладки аппроксимировал восьмиугольник кругом заданного радиуса. Теперь решил перейти к восьмиугольнику. (сейчас я задаю его при помощи координат вершин; если есть какой-нибудь другой метод скажите пожалуйста). Нашёл на просторах Интернета интересную идею: построить с пробной точкой и соседними вершинами восьмиугольника треугольники. Просуммировать их площадь. Если сумма площадей равна площади восьмиугольника - точка внутри, иначе - снаружи. Просто и не затратно, подумал я. Закодил.
На выходе должна получаться некоторая картинка, напечатанная в одном издании т.е. есть с чем сравнить правильность работы всей проги.
И вот если ставить точное равенство то картина получается не полная... некоторые фрагменты отсутствуют. Если поставить меньше или равно - по-моему появляются и лишние элементы рисунка :(
В общем я думаю это из-за несовершенства алгоритма проверки принадлежности точки.
|
а чем вам не нравится метод трассировки луча?
|
| Tonny_Bennet |
25-09-2011 01:18 1759576 |
Цитата:
Цитата ferget
а чем вам не нравится метод трассировки луча? »
|
тем что он слишком уж громоздкий.
проблему решил встроенными средствами 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;
}
|
Цитата:
Цитата ferget
а чем вам не нравится метод трассировки луча?
|
ferget, это не оно?!
читать дальше »
Кушниренко Лебедев Проект Выпуклая оболочка. Там эта задача:
* решается чисто алгоритмически;
* входит как составная часть в более крупный алгоритм;
* решается в целом для замкнутого полигона.
Если вкратце, то определение, принадлежит ли точка полигону, заданному координатами своих вершин, сводится к перебору рёбер полигона (отрезков, соединяющих его вершины) и определения, будет ли «освещено» очередное ребро полигона, если поместить в координаты точки источник света:
Цитата:
Прежде всего, заметим, что понятие освещенности было определено неформально и при этом использовалось расположение точки относительно всего многоугольника. Желательно было бы, чтобы освещенность или неосвещенность ребра определялась только по точке и ребру. Это можно сделать для ориентированных ребер (ориентированного многоугольника) следующим образом: рассмотрим ориентированное ребро AB, новую точку T и ориентированную площадь треугольника ABT:
(ориентированная площадь треугольника считается как половина площади параллелограмма, натянутого на векторы TA и TB).
Легко видеть:
что если многоугольник ориентирован «против часовой стрелки», то ребро AB освещено из T тогда и только тогда, когда:
Заметим также, что при таком формальном определении понятия освещенности никакое ребро многоугольника не освещено ни из одной точки внутри или на границе многоугольника.
|
|
это 3D вариант
а в 2D
Цитата:
Предположим, что нам необходимо определить принадлежность точки а полигону р. Для этого из некоторой удаленной точки проведем прямую линию в точку а. На этом пути может встретиться нуль или несколько пересечений границы полигона: при первом пересечении мы входим внутрь полигона, при втором — выходим из него, при третьем пересечении снова входим внутрь и так до тех пор, пока не достигнем точки а. Таким образом каждое нечетное пересечение означает попадание внутрь полигона р, а каждое четное — выход из него. Если мы попадаем в точку а с нечетным числом пересечений границы полигона, то точка а лежит внутри полигона, а если получается четное число пересечений, то точка находится вне полигона р.
|
|
Время: 00:49.
© OSzone.net 2001-
