Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

Спасибо за реализацию, она действительно быстрая. Но не все линии отрисовывает в нужную сторону... Необходимо добавить проверку для случая X-линии if(y1 "<" y0) grad=-grad; и аналогично для Y-линии if(x1 "<" x0) grad=-grad; P.S. На...
Отличные уроки(учу GL по ним), только в renderScene нужно добавить очистку буфера цвета и буфера глубины. При изменении размеров треугольники размножаются)
как исправить это , сделал все по инструкции
Timer1 - выдает ошибку. Использовал IdleTimer1, работает! unit Unit1; {$mode objfpc}{$H+} interface uses Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls, ExtCtrls, OpenGLContext, GL, GLU; type { TForm1 } TForm1 =...
в коде присутствуют ошибки! // Считываем координаты procedure TForm1.getCoords(Sender: TObject); var j1:longint; begin n:= StrToInt(Edit2.Text); //число точек s1:=Edit1.Text; s2:=''; i := 1; j:=1; k:=0...

Счетчики и рейтинг

Яндекс.Метрика Рейтинг@Mail.ru

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


Рис. 1. Каждый луч, исходящий из точки а, пересекает границу нечетное число раз, а каждый луч, исходящий из точки b, имеет четное число пересечений с границей полигона

Построение алгоритма на основе этой идеи базируется на двух особенностях. Во-первых, для решения задачи подходит любой луч, начинающийся в анализируемой точке а (рис. 1). Поэтому для простоты выберем правый горизонтальный луч ra, начинающийся в точке а и направленный вправо параллельно положительной полуоси х.

Во-вторых, порядок расположения ребер, пересекаемых лучом ra безразличен, имеет значение лишь парность (четное или нечетное количество) их общего числа. Следовательно, вместо моделирования движения вдоль луча ra для алгоритма достаточно определить все пересечения ребер в любом порядке, определяя четность по мере продвижения. Простейшим решением будет обход границы полигона с переключением бита четности при каждом обнаружении ребра, пересекаемого лучом ra.

Относительно горизонтального луча ra, направленного вправо, будем различать три типа ребер полигона: касательное ребро, содержащее точку а; пересекающее ребро, не содержащее точку а; безразличное ребро, которое совсем не имеет пересечения с лучом га. Например, на рис. 2 ребро с является пересекающим ребром, ребро d — касательным, а ребро е — безразличным.


Рис. 2: Ребро с является пересекающим ребром, ребро d — касательное, ребро е — безразличное

Функция pointlnPolygon решает задачу о принадлежности для точки а и полигона р. В процессе работы алгоритма обходится граница полигона и переключается переменная parity для каждого обнаруженного факта пересечения ребра лучом. Возвращается значение INSIDE типа перечисления, если окончательное значение переменной parity равно 1 (означающее нечетное число), или возвращает OUTSIDE, если это конечное значение равно О (означающее четность). Если обнаруживается касательное ребро, то алгоритм немедленно возвращает значение типа перечисления BOUNDARY (граница).

enum { INSIDE, OUTSIDE, BOUNDARY };         // положение точки
//     ВНУТРИ, ВНЕ,     НА ГРАНИЦЕ
enum { TOUCHING, CROSSING, INESSENTIAL };   // положение ребра
//     КАСАТЕЛbНОЕ, ПЕРЕСЕКАЮЩЕЕ, НЕСУЩЕСТВЕННОЕ
 
int pointInPolygon(Point &a, Polygon &p)
{
  int parity = 0;
  for (int i = 0;  i < p.size(); i++, p.advance (CLOCKWISE)) { 
    Edge e = p.edge();
    switch (edgeType(a, e)) {
      case TOUCHING:
        return BOUNDARY;
      case CROSSING:
        parity = 1 - parity;
    }
  }
  return (parity ? INSIDE : OUTSIDE);
}

Функция PointInPolygon( Точка a, Многоугольник p)
1. Четность = 0;
2. Цикл по всем ребрам многоугольника (Начало)
3. Берем ребро e
4. Анализируем положение точки относительно ребра с помощью функции edgeType(Точка a, Ребро e)
5. Если положение точки КАСАТЕЛЬНОЕ, то ТОЧКА НА РЕБРЕ (конец работы)
6. Если положение точки ПЕРЕСЕКАЮЩЕЕ, то меняем четность.
7. Конец цикла (2).
8. Анализ четности, возвращение результата работы алгоритма, если нечетно то внутри, если четно снаружи.

Обращение к функции edgeType(a,e) классифицирует положение ребра е относительно горизонтального луча ra, направленного вправо, возвращая значения TOUCHING, CROSSING или INESSENTIAL (касательное, пересекающее или безразличное) типа перечисления. Определение функции edgeType несколько хитроумное, поскольку функция pointInPolygon должна правильно обрабатывать особые ситуации, возникающие при прохождении луча га точно через вершины.

Рассмотрим рис. 3.
В случае (а) бит четности должен быть переключен — луч пересекает границу только однажды, хотя при этом на самом деле пересекает два ребра.

В случаях (б) и (в) четность не изменяется. Это может быть достигнуто путем некоторого уточнения схемы классификации ребер:
Ребро е — касательное ребро, если оно содержит точку а.
Ребро е — пересекающее ребро, если
(1) ребро е не горизонтальное и
(2) луч ra пересекает ребро е в некоторой точке, отличающейся от его нижней конечной точки.
Ребро е — безразличное, если оно не касательное и не пересекающее.


Рис. 3: Специальные случаи: (а) и (г) — переменная parity переключается однажды; (6) и (д) - parity не изменяется, (в) и (е) — parity переключается дважды и ситуация остается без изменения

Обращаясь к рис. 3, мы можем видеть, что в случае (а) переменная parity должна переключиться однажды, в случае (б) parity не изменяется, в случае (в) parity переключается дважды и ситуация остается без изменения.

Заметим, что горизонтальное ребро, не включающее точку а, считается безразличным и оно игнорируется функцией pointInPolygon. Поэтому случаи (г), (д) и (е) обрабатываются точно так же, как соответствующие случаи (а), (б) и (в).

Итак, функция edgeType классифицирует ребро е как TOUCHING, CROSSING или INESSENTIAL (пересекающее, касательное или безразличное) относительно точки а:

int edgeType (Point &a, Edge &e)
{
  Point v = e.org;
  Point w = e.dest;
  switch (a.classify(e)) {
    case LEFT:
      return ((v.y<a.y)&&(a.y<=w.y)) ? CROSSING : INESSENTIAL; 
    case RIGHT:
      return ((w.y<a.y)&&(a.y<=v.y)) ? CROSSING : INESSENTIAL; 
    case BETWEEN:
    case ORIGIN:
    case DESTINATION:
      return TOUCHING;
    default:
      return INESSENTIAL;
  }
}

Функция edgeType ( Точка a, Ребро e)
1. Получим концы ребра е, как точки v и w;
2. Вызовем функцию анализа расположения точки classify(точка a, ребро e)
3. Если точка а слева от ребра e: ребро ПЕРЕСЕКАЕТСЯ, если (v.y < a.y) && (a.y <= w.y), в противном случае БЕЗРАЗЛИЧНО.
4. Если точка а справа от ребра e: ребро ПЕРЕСЕКАЕТСЯ, если (w.y < a.y) && (a.y <= v.y), в противном случае БЕЗРАЗЛИЧНО.
5. Если точка совпадает с v,w или лежит на отрезке, то ребро КАСАТЕЛЬНОЕ
6. Во всех остальных случаях БЕЗРАЗЛИЧНО

Обратите внимание, как функция edgeType обнаруживает пересекающие ребра. Если точка а лежит слева от ребра е, то ребро является пересекающим, только если вершина начала ребра v(=e.org) лежит ниже луча ra, а вершина конца w(=e.dest) расположена на луче или лежит выше его. Тогда ребро не может быть горизонтальным и луч га должен пересекать ребро в некоторой точке, отличающейся от его нижнего конца. Если точка а находится справа от ребра е, то роли конечных точек v и w взаимно меняются.

В худшем случае (когда точка а не принадлежит границе полигона) время выполнения программы pointInPolygon пропорционально размеру полигона.

Демонстрационные примеры по теме