Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Принцип работы функции ???? / 12 сообщений из 12, страница 1 из 1
20.11.2004, 22:42
    #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:45
    #32792785
Andrew07
Andrew07
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Принцип работы функции ????
Забыл пояснить: Arr - массив исходных точек, Check1 - какая - либо другая точка.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.11.2004, 11:38
    #32792868
Lelikk
Lelikk
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Принцип работы функции ????
Функция считает углы отклонения.
Вариант для поставленной задачи далеко не оптимальный, так как arctan -- функция медленная. Уж лучше считать через площади треугольников -- и проще и быстрее
________________________________________________________
Глюк - это высокоорганизованная система не поддающихся определению частиц
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2004, 21:18
    #32800537
Andrew07
Andrew07
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Принцип работы функции ????
Что значит эта строка:

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

Пока понять не могу.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2004, 22:41
    #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
| Ответить | Цитировать | Написать  
26.11.2004, 17:09
    #32801977
Andrew07
Andrew07
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Принцип работы функции ????
Спасибо, S.G..

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


Врятли, это лучший вариант. Так как будут образовываться большие погрешности при вычисления площади фигур и результат вычисления будет неверен.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.11.2004, 18:33
    #32802133
Lelikk
Lelikk
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Принцип работы функции ????
Только не надо говорить о малой погрешности тригонометрических функций -- одна просто ОГРОМНА и превосходит погрешность вычисления квадратных корней. К тому же метод вычисления через площади работает серьезно быстрее (проверял) и используется достаточно часто
________________________________________________________
Глюк - это высокоорганизованная система не поддающихся определению частиц
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.12.2004, 10:22
    #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
| Ответить | Цитировать | Написать  
05.12.2004, 16:51
    #32813455
Andrew07
Andrew07
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Принцип работы функции ????
TellurВот более логичное решение и без арктангентсов.
Следует добавить, что все вышесказанное справедливо только для выпуклх многоугольников.

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

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

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

Если число таких пересечений будет нечетное, то точка внутри фигуры, если четное (включая случай = 0) то вне фигуры.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.12.2004, 13:41
    #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
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Принцип работы функции ???? / 12 сообщений из 12, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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