����������: �������������� ���������.

�������� �������������� ����� ��������������.

������ ������������.

��� ������������ ���������� ����������� ��������, ������� ���� �����, ���� � ����� ����� ���� �������. ��� - '��������' ������������� ���������, � � ������ �������� ������������ ������ ��.

char BelongToPoly (point a, point b, point c, point p)

// ����������� �������������� ����� ������������

{

 float tmp1, tmp2;
 char f1, f2, f3; // ������

 /*
    ��� ����������� �������������� ����� 
   ������������ ������������ ��������� ��������:
   ��� ��������� ������� ������, ���������� 
   ������� ������������, �� ��� �������������.
    ����� �������, ���� ���� ����� � 
   ��������������� ���� ������� ������� ������������ 
   ����� � ������ ��������������, �� ����� �� 
   ����������� ������������.
����� �������� ���� �������� ��� ���� 3-� ������ !!!!!
 */

 // ��������� ������� AB
 // H������ � ��������� y(x) �� ���� ������
 // ���� ����� P � ����� C ����� � ������ ��������������, 
 // �� ������������
 // (y(p.x)-p.y)*(y(c.x)-c.y) ����� �������������
 // ��������� ������ ����� ���: 
 // y(x)=((x-a.x)*(b.y-a.y))/(b.x-a.x)+a.y

 tmp1=((p.x-a.x)*(b.y-a.y))/(b.x-a.x)+a.y-p.y;
 tmp2=((c.x-a.x)*(b.y-a.y))/(b.x-a.x)+a.y-c.y;
 if (tmp1*tmp2>=0) f1=1;

 // �� �� ����������� ��� ������� BC

 tmp1=((p.x-b.x)*(c.y-b.y))/(c.x-b.x)+b.y-p.y;
 tmp2=((a.x-b.x)*(c.y-b.y))/(c.x-b.x)+b.y-a.y;
 if (tmp1*tmp2>=0) f2=1;

 // ���������� ��� ������� CA

 tmp1=((p.x-c.x)*(a.y-c.y))/(a.x-c.x)+c.y-p.y;
 tmp2=((b.x-c.x)*(a.y-c.y))/(a.x-c.x)+c.y-b.y;
 if (tmp1*tmp2>=0) f3=1;
// ����� �����������
 if ((f1 == 1)&&(f2 == 1)&&(f3 == 1)) return (1); 
 // ����� �� �����������
 else return (0);                                

}

�������� �������������.

������ ����� ����� ��������, ���� ������ ��� �������� ���������������.

����� (x₁,y₁), (x₂,y₂), ... ,(x_n,y_n) - ���������� ����� �������� �� ���������.

����� ������, ��� ���������� ����� ������ � ������� ������ �������� � ����� ���� (�����) �������, � ������� �������� �� ������������ (� ��������� ������ �������� ���� ����� �������� ���������, �� ��� �������������� ��������)

����� � ����� ������� ���� ��� ������� �� ��������� ������������

��� Vn - �������� �.�. ��� n-��� ���� ��������, � Sign - ������� ������������ ���� ��������.

���� ��������, ��� � ���� ����� ��� n = ���������� ������, n+1 = 1 (� ����� ������ - � ��� �������).

��� �� ������ � �������������� ������ ?

����� ���� �������� � '������������' �� ��� �� ����� �� ���� �����. ���� ������� ��������, ������ ���������� ������� �� n-�� � (n+1)-�� ������ ���� �� ������� �������, ���� ���� Zn - '+', � ������ - ���� �����.

����� �������, ���� ����� ������, �� ����� ������ ����� ��������� - ��������� ����,
����� ������� - ����� ���� ���� ������������,
����� �� ������� �� n � n+1-o� ������� - Z_n=0.

���� �� ������� �������� ����� ������ (�������� �� ������� �������), �� ����� ��������� ������� ���������: ���� ����� ������ ���� '-' (��� ������� �������), �� ����� ����� ���, ����� ������.

������������ �������������.

� ������������ ��������������� ����� ��������� ������� �����, ������ �������� ����� �������� � ��� ���������� ������. �������� �������������� ������ ����� ����� � ��������� ���������� ����������� �� ��������� �� x.

���� ����� �� ������ ����� - ��� ������, �� �������� - �������. �������� ������������� ������ ���� � ����� �� ����� �� ����������� ����� �� ��������� - ����� ����� ���� �����.

�������� ������� ����������, �� ���� �������� ������ ������� ������. �� �������� ��������� ������, ����� ����� ����� �� ��������.

����� �� ��������, � ���������� � ���������.