ReSQL.ru
     
powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Принцип работы функции ????
12 сообщений из 12, страница 1 из 1
Принцип работы функции ????
    #32792784
Andrew07
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Andrew07
Гость
Имеется программа, проверяющая принадлежит ли многоугольнику точка. Никак не могу понять алгоритм работы функции PointInSidebar (она возвращает true есили точка принадлежит и false если не принадлежит многоугольнику). Буду очень признателен, если кто-нибудь поподробнее объяснит.
Заранее спасибо.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
Type
  TPoint =
    Record
      X, Y: Integer;
    End;

Function PointInSidebar(Const SideBar: Array Of TPoint;
         p: TPoint; Count: Integer): Boolean;
  Var
    x1,y1,x2,y2: Double;
    x0, y0, sum, divisor: Double;
    i: integer;
  Begin
    sum :=  0 ;
    y0 := p.y;
    x0 := p.x;
    For i :=  0  to Pred(count- 1 ) do
      Begin
        x1:=sidebar[i].x;
        y1:=sidebar[i].y;
        x2:=sidebar[i+ 1 ].x;
        y2:=sidebar[i+ 1 ].y;

        divisor:=y1*x2-x1*y2-y0*x2+y0*x1+x0*y2-x0*y1;
        divisor := divisor +  1 .0E- 10 ;

        Sum := sum + (
        -arctan( (-x2*x1+x1*x0+y0*y1-x2*x0+x2*x2-y2*y0+y2*y2-y1*y2 )/divisor)+
        arctan( (-x1*x1+x2*x1+x1*x0+y0*y1+y1*y2-x2*x0-y1*y1-y2*y0 )/divisor)
        );
      End;

    x1:=sidebar[count- 1 ].x;
    y1:=sidebar[count- 1 ].y;
    x2:=sidebar[ 0 ].x;
    y2:=sidebar[ 0 ].y;

    divisor:=y1*x2-x1*y2-y0*x2+y0*x1+x0*y2-x0*y1;
    divisor := divisor +  1 .0E- 10 ;
    Sum := sum + (
    -arctan((-x2*x1+x1*x0+y0*y1-x2*x0+x2*x2-y2*y0+y2*y2-y1*y2)/divisor)+
    arctan((-x1*x1+x2*x1+x1*x0+y0*y1+y1*y2-x2*x0-y1*y1-y2*y0)/divisor)
    );

    pointinsidebar := not (abs(Sum) <  0 . 0001 )
  End;

Const
  arr: Array[ 0  ..  3 ] Of TPoint =
    (*
    ( {First}
      (X: 3 ;Y: 3 ),
      (X: 7 ;Y: 10 ),
      (X: 12 ;Y: 6 ),
      (X: 9 ;Y: 7 )
    );
    *)
    (*
    (
      (X: 12 ;Y: 8 ),
      (X: 17 ;Y: 14 ),
      (X: 17 ;Y: 11 ),
      (X: 21 ;Y: 7 )
    );
    *)
    (
      (X: 1 ;Y: 2 ),
      (X: 1 ;Y: 4 ),
      (X: 3 ;Y: 4 ),
      (X: 3 ;Y: 2 )
    );

Const
  (* {First}
  Check1: TPoint = (X: 4 ; Y: 8 );
  Check2: TPoint = (X: 7 ; Y: 8 );
  Check3: TPoint = (X: 7 ; Y: 5 );
  Check4: TPoint = (X: 9 ; Y: 5 );
  *)

  (* {Second}
  Check1: TPoint = (X: 13 ; Y: 12 );
  Check2: TPoint = (X: 16 ; Y: 10 );
  Check3: TPoint = (X: 18 ; Y: 11 );
  Check4: TPoint = (X: 19 ; Y: 8 );
  *)
  Check1: TPoint = (X: 1 ; Y: 3 );

Var
  b: Boolean;
Begin
  b := PointInSidebar(arr, Check1,  4 );
  {
  b := PointInSidebar(arr, Check2,  4 );
  b := PointInSidebar(arr, Check3,  4 );
  b := PointInSidebar(arr, Check4,  4 );
  }
End.
...
Рейтинг: 0 / 0
20.11.2004, 22:42
| Ответить | Цитировать | Написать  
Принцип работы функции ????
    #32792785
Andrew07
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Andrew07
Гость
Забыл пояснить: Arr - массив исходных точек, Check1 - какая - либо другая точка.
...
Рейтинг: 0 / 0
20.11.2004, 22:45
| Ответить | Цитировать | Написать  
Принцип работы функции ????
    #32792868
Фотография Lelikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lelikk
Участник
Функция считает углы отклонения.
Вариант для поставленной задачи далеко не оптимальный, так как arctan -- функция медленная. Уж лучше считать через площади треугольников -- и проще и быстрее
________________________________________________________
Глюк - это высокоорганизованная система не поддающихся определению частиц
...
Рейтинг: 0 / 0
21.11.2004, 11:38
| Ответить | Цитировать | Написать  
Принцип работы функции ????
    #32800537
Andrew07
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Andrew07
Гость
Что значит эта строка:

Код: plaintext
1.
pointinsidebar := not (abs(Sum) <  0 . 0001 )

Пока понять не могу.
...
Рейтинг: 0 / 0
25.11.2004, 21:18
| Ответить | Цитировать | Написать  
Принцип работы функции ????
    #32800559
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
Andrew07Что значит эта строка:
Код: plaintext
1.
pointinsidebar := not (abs(Sum) <  0 . 0001 )

abs(Sum) < 0.0001 - логическое выражение, имеющее результат true или false.
not (abs(Sum) < 0.0001) - имеет результат false если выражение внутри скобок имеет результат true, и наоборот.
Потом все это присваивается логической переменной pointinsidebar.

короче: pointinsidebar равно false, если Sum равно или близко к нулю.
...
Рейтинг: 0 / 0
25.11.2004, 22:41
| Ответить | Цитировать | Написать  
Принцип работы функции ????
    #32801977
Andrew07
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Andrew07
Гость
Спасибо, S.G..

Lelikk
Уж лучше считать через площади треугольников -- и проще и быстрее


Врятли, это лучший вариант. Так как будут образовываться большие погрешности при вычисления площади фигур и результат вычисления будет неверен.
...
Рейтинг: 0 / 0
26.11.2004, 17:09
| Ответить | Цитировать | Написать  
Принцип работы функции ????
    #32802133
Фотография Lelikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lelikk
Участник
Только не надо говорить о малой погрешности тригонометрических функций -- одна просто ОГРОМНА и превосходит погрешность вычисления квадратных корней. К тому же метод вычисления через площади работает серьезно быстрее (проверял) и используется достаточно часто
________________________________________________________
Глюк - это высокоорганизованная система не поддающихся определению частиц
...
Рейтинг: 0 / 0
26.11.2004, 18:33
| Ответить | Цитировать | Написать  
Принцип работы функции ????
    #32808921
Tellur
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Tellur
Участник
Вот более логичное решение и без арктангентсов.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
function LineDef(const a,b,p :TPoint):Double;
begin
  Result:=(p.Y-a.Y)*(b.X-a.X)-(p.X-a.X)*(b.Y-a.Y);
end;

function Solve(const s: array of TPoint; p: TPoint; Count: Integer):Boolean;
var
  i,next,prev  :Integer;
begin
  prev:=count- 1 ;
  for i:= 0  to count- 1  do
    begin
      if i<count- 1  then next:=i+ 1  else next:= 0 ;
      if LineDef(s[i],s[next],p)*LineDef(s[i],s[next],s[prev])< 0  then
        begin
          Result:=False;
          Exit;
        end;
      prev:=i;
    end;
  Result:=True;
end;
Следует добавить, что все вышесказанное справедливо только для выпуклх многоугольников.
...
Рейтинг: 0 / 0
02.12.2004, 10:22
| Ответить | Цитировать | Написать  
Принцип работы функции ????
    #32813455
Andrew07
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Andrew07
Гость
TellurВот более логичное решение и без арктангентсов.
Следует добавить, что все вышесказанное справедливо только для выпуклх многоугольников.

Для выпуклых алгоритм составить легко, а вот для невыпуклых...
Я все-таки сделал через площадь. Но там все равно появляется погрешность (если решать через arctan, то ее нет) равная 0.0000001. Я ее просто вычитаю и все ОК.
...
Рейтинг: 0 / 0
05.12.2004, 16:51
| Ответить | Цитировать | Написать  
Принцип работы функции ????
    #32813489
DocAl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DocAl
Участник
Чёрт, хотел бы я при обработки измерений "просто вычитать погрешность"...

Не обращайте внимания, это так, поток сознания)
...
Рейтинг: 0 / 0
05.12.2004, 18:19
| Ответить | Цитировать | Написать  
Принцип работы функции ????
    #32813748
Фотография Хрен
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Хрен
Участник
Хмм.. Если мне не изменяет склероз, существут типовое решение для общего случая (не только для выпуклых).

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

Если число таких пересечений будет нечетное, то точка внутри фигуры, если четное (включая случай = 0) то вне фигуры.
...
Рейтинг: 0 / 0
06.12.2004, 09:43
| Ответить | Цитировать | Написать  
Принцип работы функции ????
    #32816466
Tellur
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Tellur
Участник
Тогда так
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
 function  LineDef( const  a,b,p :TPoint):Double;
 begin 
  Result:=(p.Y-a.Y)*(b.X-a.X)-(p.X-a.X)*(b.Y-a.Y);
 end ;

 function  IsCross( const  a1,a2,b1,b2 :TPoint):Boolean;
 begin 
  Result:=(LineDef(a1,a2,b1)*LineDef(a1,a2,b2)< 0 ) and (LineDef(b1,b2,a1)*LineDef(b1,b2,a2)< 0 );
 end ;

 function  Solve2( const  s:  array   of  TPoint; p: TPoint; Count: Integer):Boolean;
 var 
  i,prev  :Integer;
  cnt     :Integer;
  p0      :TPoint;
 begin 
  p0:=s[ 0 ];
   for  i:= 1   to  count- 1   do 
     begin 
       if  s[i].X>p0.X  then  p0.X:=s[i].X;
       if  s[i].Y>p0.Y  then  p0.Y:=s[i].Y;
     end ;
  p0.X:=p0.X+ 10 ;
  p0.Y:=p0.Y+ 10 ;

  cnt:= 0 ;
  prev:=count- 1 ;
   for  i:= 0   to  count- 1   do 
     begin 
       if  (IsCross(s[prev],s[i],p0,p))  then  inc(cnt);
      prev:=i;
     end ;
  Result:=(cnt  and   1 )<> 0 ;
 end ;
...
Рейтинг: 0 / 0
07.12.2004, 13:41
| Ответить | Цитировать | Написать  
12 сообщений из 12, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Принцип работы функции ????
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]