HOME ПРИМЕРЫ THANKS НОВИЧКАМ ДОКИ LINKS JavaScript Mail


 
В этот день много лет назад...
1 мая. В 1891 году (126 лет назад) - Первая маевка в Петербурге, организованная социал-демократической группой М.И. Бруснева.
 
 

Turbo Pascal Examples.
Проверка на принадлежность точки многоугольнику

Графика:
Построение графика функции
Прыгающий по экрану мячик.
Качание маятника.
Вложенные цветные круги.
Броуновское движение. Использование объектов.
Матрицы и массивы:
Сортировка элементов массива.
Удаление одинаковых элементов.
Простой пример на поворот матрицы.
Сортировка методом Шелла. +функции измерения временных интервалов.
Проверка выпуклости многоугольника.
Перемоножение матриц
Вычисление определителя матрицы. Рекурсия.
Нахождение обратной матрицы.
Задача об автостоянке.
Рекурсия. Подземелье сокровищ.
Численные методы:
Задачка на определение угла между стрелками часов.
Проверка на принадлежность точки многоугольнику.
Нахождение точки пересечения двух отрезков на плоскости.
Сортировка методом Шелла. +функции измерения временных интервалов.
Сортировка методом "пузырька". Пример на динамические структуры данных. Связанные списки.
Нахождение корня функции методом половинного деления.
Вычисление арккосинуса
Нахождение суммы цифр натурального числа.
Работа с фалами:
Рекурсивное сканирование директорий.
Работа со строками:
Работа со словами в предложении с разделителями.
Простейший синтаксический анализатор для распознавания и вычисления многчлена.
Синтаксический анализатор для распознавания и вычисления многчлена.
Работа со строками: смена кодировки, удаление тегов из HTML текста, обработка
Переименование файлов из кириллицы в латиницу.
Выдача контекстной подсказки.
Частотный словарь символов.
Подсчет повторяющихся символов в строке.
Ссылочные переменные:
Моделирование стека.
Пасьянс "Косынка".
Игры:
Пасьянс "Косынка".
Игра "Питон"
Игра "Анацефал". Пример использования объектов.
Игра "Минное поле"
Большие проекты:
Электронная картотека (без исходника)


 
Проверка на принадлежность точки многоугольнику
Формулировка задачи проста. Задан последовательный набор точек (хi,уi), i=1..n. Для заданной точки проверить, принадлежит ли она замкнутому многоугольнику, заданному этими точками, или нет.
Используется метод трассировки луча. Суть его в том, что если из заданной точки провести произвольный луч (не важно в каком направлении), то по числу пересечений этого луча со сторонами многоугольника можно однозначно сказать, лежит ли точка внутри или снаружи. А именно, если число пересечений четно (или 0) - то снаружи, нечетно - внутри. Причем, как оказывается, не важно в каком порядке следуют стороны. Для проверки пересечения луча со сторонами, используем процедуру из рассмотренной ранее задачи нахождение точки пересечения двух отрезков на плоскости, слегка ее видоизменив. А именно, если раньше нас интересовали только такие решения системы уравнений, когда параметр tb лежит в диапазоне [0.1] (что определяте отрезок), то теперь нас будут устраивать значения [0,бесконечность) (что определяет луч).

Несколько слов о программе. Исходные данные в виде восьми координат считываются из файла poligon.txt. В качестве примера можно использовать, например, такие значения:
1 1 2 1 2 2
3 2 3 1 4 0
4 5 1 5
Только убедитесь, что после последней пятерки в файле не присутствуют ни пробелы, ни концы строк, иначе будет прочитан лишнй ноль.

Точка а задается случайным образом.

Вместо сравнения d с нулем (if (d=0) ...) используется сравнение с малым числом Eps. Сделано это для того, чтобы не делить на очень малые числа. В вещественных представлениях числа 0 зачастую присутствуют что-нибудь вроде 1Е-12, и формального равенства с нулем нет, но фактически это самый что ни на есть 0.
Замечание из форума


const eps = 0.000001;
     maxNodes = 50;

type point = object
  x,y:real;
  procedure setPoint(xp,yp:real);
  end;

  poligonType = array[1..maxNodes] of point;

procedure point.setPoint(xp,yp:real);
  begin
  x:=xp;
  y:=yp;
  end;

var a,ax,c:point;

function readPoligon(var p:poligonType):integer;
var buf:text;
   n:integer;
   x1,y1:real;
  begin
  assign(buf, 'poligon.txt');
  reset(buf);
  n:=0;
  {$I-}
  while not eof(buf) and (n<=maxNodes) and (IOResult=0) do
    begin
    inc(n);
    read(buf, p[n].x);
    if (IOResult = 0) then
      read(buf, p[n].y);
    end;
  if (IOResult <> 0) then dec(n);
  {$I+}
  if (not eof(buf)) then
    writeln(' The maximum number of nodes has been reached. Using maxN=',maxNodes);
  readPoligon := n;
  end;

const
  ONE_INTERSECTION_POINT =  1;
  CHUNKS_ARE_PARALLEL    =  0;
  NO_INTERSCTION         = -1;
  A1_BORDER_INTERSECTION =  2;

function checkIntersection(a1,a2,b1,b2:Point):shortint;
{
returns
  1 if there is one intersection point "c"
  0 if chunks ar on parallel lines
-1 if there are no intersection points
  2 if a1 lies on [b1,b2]
}

var d,da,db,ta,tb: real;
{

}


  begin
  d :=(a1.x-a2.x)*(b2.y-b1.y) - (a1.y-a2.y)*(b2.x-b1.x);
  da:=(a1.x-b1.x)*(b2.y-b1.y) - (a1.y-b1.y)*(b2.x-b1.x);
  db:=(a1.x-a2.x)*(a1.y-b1.y) - (a1.y-a2.y)*(a1.x-b1.x);
  {writeln('d=',d:12:4,'da=',da:12:4,'db=',db:12:4);}

  if (abs(d)<eps) then
    checkIntersection := CHUNKS_ARE_PARALLEL
  else
    begin
    ta:=da/d;
    tb:=db/d;
    if (abs(ta)<eps) and ((0<=tb) and (tb<=1))
      then checkIntersection := A1_BORDER_INTERSECTION
    else
    if (0<=ta) {and (ta<=1)} { luch a -----> }
      and (0<=tb) and (tb<=1)
        then
          begin
          c.setPoint(a1.x+ta*(a2.x-a1.x),a1.y+ta*(a2.y-a1.y));
          checkIntersection := ONE_INTERSECTION_POINT
          end
        else checkIntersection := NO_INTERSCTION;
    end;
  end;

var i,n:integer;
    plg:poligonType;
    xr,yr:real;

function pointInsidePoligon(a:Point;plg:poligonType):integer;
{ 0 - outside
  1 - inside
  2 - on border
}

var i,k,i1,i2,r:integer;
    ax:Point;
  begin
  ax.setPoint(a.x+5,a.y);
  k:=0;
  for i:=1 to n do
    begin
    i1:=i; i2:=i+1; if (i=n) then i2:=1;
    r:=checkIntersection(a,ax,plg[i1],plg[i2]);
    if (r=2) then
      begin
      pointInsidePoligon := 2; exit;
      end;
    if (r=1) then
      k:=1-k;
    end;
  pointInsidePoligon := k;
  end;

begin
n:=readPoligon(plg);
xr:=4; yr:=1;
for i:=1 to 20 do
  begin
  a.setPoint(xr,yr);
  write(i:3,'. Point A(',a.x:8:4,',',a.y:8:4,') ');
  case pointInsidePoligon(a,plg) of
    1: writeln('is inside');
    0: writeln('is outside');
    2: writeln('on border');
    end;
  xr:=random(60); xr:=(xr)/10;
  yr:=random(50); yr:=(yr)/10;
  end;
end.


 

 

 

 

 

 

 


HOME