|
Вопрос # 374/ вопрос решён / |
|
Здравствуйте ув. эксперты. Существует замкнутый полигон из N количества линий, соотвественно все вершины данны. Как опередить попадает ли данная точка в полигон или нет? (без использования регионов)
 |
Вопрос задал: SMaks (статус: 1-ый класс)
Вопрос отправлен: 4 марта 2007, 00:23
Состояние вопроса: решён, ответов: 2.
|
Ответ #1. Отвечает эксперт: Матвеев Игорь Владимирович
Здравствуйте, SMaks!
Существует несколько алгоритмов решения данной задачи, созданных для различных начальных услуовий. Например, если известно, что многоугольник будет выпуклый, можно найти границы прямоугольника, описанного вогруг многоугольника, затем брать отдельно каждую грать многоугольника, продливать отрезок до пересечения с описанным многоугольником, а затем проверять не находится ли точка внутри образованного прямоугольного треугольника.
Этот метод работает достаточно быстро, но годится только для выпуклых многоугольников.
Я подготовил для Вас демонстрационную программу, использующую другой алгоритм:
1. Случайным образом выбирается точка A
2. Проверяется число пересечений отрезка, образованного точками A и исследуемой точки со всеми гранями многоугольника
3. Если число пересечений = 0 => переход к пункту 1
4. Если число пересечений четное - точка вне многоугольника, если нечетное - внутри.
(прикреплённый файл)
И еще замечания: Данный метод работает для любых многоугольников, но могут быть проблемы с перекрещеными многоугольниками. В таких случайх алгоритм выдает результат, будто при образовании многоугольника используется операция xor, т.е. если на площадь многоугольника еще раз накладывается площадь многоугольника - эта область не считается многоугольником.
Если это положение для Вас критично, Вы можете делать проверку несколько раз, а затем делать вывод.
К ответу прикреплён файл. Загрузить » (срок хранения: 60 дней с момента отправки ответа)
 |
Ответ отправил: Матвеев Игорь Владимирович (статус: Студент)
Время отправки: 4 марта 2007, 06:58
Оценка за ответ: 5
Комментарий к оценке: Огромное спасибо, особенно за пример! Обратите внимание - можно увести точку за канву, нужно при перетаскивании ограничивать область курсора.
|
Ответ #2. Отвечает эксперт: Роман
Здравствуйте, SMaks!Привожу вам функцию которая определяет находится ли точка внутри многоугольника или нет.TestPolygon : array of TPoint - многоугольник;P : TPoint - точка положение которой нужно определить.Работает с любыми замкнутыми многоугольниками.
Приложение: Переключить в обычный режим- function PtInRgn(TestPolygon : array of TPoint; const P : TPoint): boolean;
- var
- ToTheLeftofPoint, ToTheRightofPoint : byte;
- np : integer;
- OpenPolygon : boolean;
- XIntersection : real;
- begin
- ToTheLeftofPoint := 0;
- ToTheRightofPoint := 0;
- OpenPolygon := False;
-
- {Prufen ob das Polygon geschlossen ist}
- {tests if the polygon is closed}
-
- if not ((TestPolygon[0].X = TestPolygon[High(TestPolygon)].X) and
- (TestPolygon[0].Y = TestPolygon[High(TestPolygon)].Y)) then
- OpenPolygon := True;
-
- {Tests fur jedes Paar der Punkte, um zu sehen wenn die Seite zwischen
- ihnen, die horizontale Linie schneidet, die TestPoint durchlauft}
- {tests for each couple of points to see if the side between them
- crosses the horizontal line going through TestPoint}
-
- for np := 1 to High(TestPolygon) do
- if ((TestPolygon[np - 1].Y <= P.Y) and
- (TestPolygon[np].Y > P.Y)) or
- ((TestPolygon[np - 1].Y > P.Y) and
- (TestPolygon[np].Y <= P.Y))
- {Wenn es so ist} {if it does}
- then
- begin
- {berechnet die x Koordinate des Schnitts}
- {computes the x coordinate of the intersection}
-
- XIntersection := TestPolygon[np - 1].X +
- ((TestPolygon[np].X - TestPolygon[np - 1].X) /
- (TestPolygon[np].Y - TestPolygon[np - 1].Y)) * (P.Y - TestPolygon[np - 1].Y);
-
- {Zahler entsprechend verringern}
- {increments appropriate counter}
- if XIntersection < P.X then Inc(ToTheLeftofPoint);
- if XIntersection > P.X then Inc(ToTheRightofPoint);
- end;
-
- {Falls das Polygon offen ist, die letzte Seite testen}
- {if the polygon is open, test for the last side}
-
- if OpenPolygon then
- begin
- np := High(TestPolygon); {Thanks to William Boyd - 03/06/2001}
- if ((TestPolygon[np].Y <= P.Y) and
- (TestPolygon[0].Y > P.Y)) or
- ((TestPolygon[np].Y > P.Y) and
- (TestPolygon[0].Y <= P.Y)) then
- begin
- XIntersection := TestPolygon[np].X +
- ((TestPolygon[0].X - TestPolygon[np].X) /
- (TestPolygon[0].Y - TestPolygon[np].Y)) * (P.Y - TestPolygon[np].Y);
-
- if XIntersection < P.X then Inc(ToTheLeftofPoint);
- if XIntersection > P.X then Inc(ToTheRightofPoint);
- end;
- end;
-
- if (ToTheLeftofPoint mod 2 = 1) and (ToTheRightofPoint mod 2 = 1) then Result := True
- else
- Result := False;
- end;
 |
Ответ отправил: Роман (статус: 5-ый класс)
Время отправки: 4 марта 2007, 12:07
Оценка за ответ: 5
Комментарий к оценке: То что нужно, Спасибо!
|
Мини-форум вопроса
Всего сообщений: 1; последнее сообщение — 5 марта 2007, 10:49; участников в обсуждении: 1.
|
|
Матвеев Игорь Владимирович (статус: Студент), 5 марта 2007, 10:49 [#1]:
>Огромное спасибо, особенно за пример!
>Обратите внимание - можно увести точку за канву, нужно при перетаскивании ограничивать область курсора.
----
Это только пример. Я и не собирался учитывать в нем все. Обратите внимание, там выбирается вектор для проверки только с левой вертикальной грани, что потенциально неправильно и может привести к зацикливанию, если в треугольник, образованный исследуемой точкой и концами левого края поля не будет попадать отрезок(ки) многоугольника.
Нужно исправить, чтобы вибиралось со всех сторон.
|
31 января 2011, 19:26: Статус вопроса изменён на решённый (изменил модератор Ерёмин А.А.): Автоматическая обработка (2 и более ответов с оценкой 5)
Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.
|
