Библиотека myBasicGeometry

	Теория
Теоретические выкладки по этой теме можно найти на странице Прикладная геометрия

Назначение библиотеки

Выполнение простейших функций прикладной вычислительной геометрии.

Функции (описание)

rfwGetLine

Получить уравнение прямой по двум её различным точками

rfwLinesCrossing

Получить пересечение двух прямых. Возвращает тип пересечения: -1 - пусто, 0 - прямые совпадают, 1 - точка (результат в 3-м параметре).

rfwSectionsCrossing

Получить пересечение двух отрезков. Возвращает тип пересечения: -1 - пусто, 0 - отрезок (результат в 4-м параметре), 1 - точка (результат в 3-м параметре).

rfwLineAndPolygonSectionCrossing

Выяснить пересекается ли отрезок и внутренность секции многоугольника (см. теорию).

Файлы библиотеки

myBasicGeometry.h

<source lang="cpp">

1. ifndef myBasicGeometryH
2. define myBasicGeometryH

//--------------------------------------------------------------------------- typedef double rfwFloat; typedef int rfwInt;

typedef struct{

 rfwFloat x,y;

} rfwPoint;

typedef struct{

 rfwFloat a,b,c;

} rfwLine;

typedef struct{

 rfwFloat xa,ya,xb,yb;

} rfwSection;

rfwFloat max(rfwFloat a,rfwFloat b); rfwFloat min(rfwFloat a,rfwFloat b);

rfwLine rfwGetLine(rfwPoint p1, rfwPoint p2); rfwInt rfwLinesCrossing(rfwLine L1,rfwLine L2,rfwPoint &P); rfwInt rfwSectionsCrossing(rfwSection S1,rfwSection S2,rfwPoint &P,rfwSection &S); rfwInt rfwLineAndPolygonSectionCrossing(rfwInt x1, rfwInt y1, rfwInt x2, rfwInt y2, rfwInt xp, rfwInt yp, rfwInt xc, rfwInt yc, rfwInt xn, rfwInt yn);

1. endif

</source>

myBasicGeometry.cpp

<source lang="cpp">

1. pragma hdrstop
2. include "myBasicGeometry.h"

//---------------------------------------------------------------------------

1. pragma package(smart_init)

rfwFloat max(rfwFloat a,rfwFloat b) {

 if( a>b ){
   return a;
 }else{
   return b;
 };

};

rfwFloat min(rfwFloat a,rfwFloat b) {

 if( a<b ){
   return a;
 }else{
   return b;
 };

};

rfwLine rfwGetLine(rfwPoint p1, rfwPoint p2) {

 rfwLine l;
 l.a=p2.y-p1.y;
 l.b=p1.x-p2.y;
 l.c=-l.a*p1.x-l.b*p1.y;
 return l;

};

rfwInt rfwLinesCrossing(rfwLine L1,rfwLine L2,rfwPoint &P) {

 rfwFloat d=L1.a*L2.b-L1.b*L2.a;
 rfwFloat d1=L2.c*L1.b-L2.b*L1.c;
 rfwFloat d2=L1.c*L2.a-L2.c*L1.a;
 if(d==0){
   if(d1==0 && d2==0){
     return 0; //Same line
   }else{
     return -1; //Empty
   };
 }else{
   P.x=d1/d;
   P.y=d2/d;
   return 1; //Point
 };

};

rfwInt rfwSectionsCrossing(rfwSection S1,rfwSection S2,rfwPoint &P,rfwSection &S) {

 rfwFloat u,v;
 rfwLine L1,L2;
 L1.a=S1.xa-S1.xb; L1.b=S2.xa-S2.xb; L1.c=S1.xa-S2.xa;
 L2.a=S1.ya-S1.yb; L2.b=S2.ya-S2.yb; L2.c=S1.ya-S2.ya;
 rfwFloat d=L1.a*L2.b-L1.b*L2.a;
 rfwFloat d1=L2.b*L1.c-L2.c*L1.b;
 rfwFloat d2=L1.c*L2.a-L2.c*L1.a;
 //printf("d=%d\nd1=%d\nd2=%d\n",d,d1,d2);
 if(d==0){
   if(d1==0 && d2==0){
     //Same line
     rfwFloat length1=(S1.xb-S1.xa)*(S1.xb-S1.xa)+(S1.yb-S1.ya)*(S1.yb-S1.ya);
     rfwFloat u2a=((S2.xa-S1.xa)*(S1.xb-S1.xa)+(S2.ya-S1.ya)*(S1.yb-S1.ya))/length1;
     rfwFloat u2b=((S2.xb-S1.xa)*(S1.xb-S1.xa)+(S2.yb-S1.ya)*(S1.yb-S1.ya))/length1;
     rfwFloat max_u=max(u2a,u2b);
     rfwFloat min_u=min(u2a,u2b);
     if(max_u<0 || min_u>1){
       return -1; //Empty
     }else{
       u2a=max(0,min_u);
       u2b=min(1,max_u);
       S.xa=S1.xa+u2a*(S1.xb-S1.xa);
       S.ya=S1.ya+u2a*(S1.yb-S1.ya);
       S.xb=S1.xa+u2b*(S1.xb-S1.xa);
       S.yb=S1.ya+u2b*(S1.yb-S1.ya);
       return 0; //Section S1+u*(S2-S1), where u2a<=u<=u2b
     };
   }else{
     return -1; //Empty
   };
 }else{
   u=d1/d;
   v=d2/d;
   if(u>=0 && u<=1 && v>=0 && v<=1){
     P.x=S1.xa+u*(S1.xb-S1.xa);
     P.y=S1.ya+u*(S1.yb-S1.ya);
     return 1; //Point
   }else{
     return -1; //Empty
   };
 };

};

rfwInt rfwLineAndPolygonSectionCrossing(rfwInt x1, rfwInt y1, rfwInt x2, rfwInt y2, rfwInt xp, rfwInt yp, rfwInt xc, rfwInt yc, rfwInt xn, rfwInt yn){

 if(x1==x2 && y1==y2){ return 0; };
 rfwSection s0,s1,sr;
 rfwPoint pr;
 s0.xa=x1; s0.ya=y1;
 s0.xb=x2; s0.yb=y2;
 s1.xa=xp; s1.ya=yp;
 s1.xb=xc; s1.yb=yc;
 rfwInt res=rfwSectionsCrossing(s0,s1,pr,sr);
 if(res==-1){ return 0; };
 if(res==0){
   //Intersection is section "sr"
   if( ( (sr.xa-xc)*(xc-xp)+(sr.ya-yc)*(yc-yp)>0)
    && (-(sr.xa-xc)*(yn-yc)+(sr.ya-yc)*(xn-xc)>0) ){ return 1; };
   if( ( (sr.xb-xc)*(xc-xp)+(sr.yb-yc)*(yc-yp)>0)
    && (-(sr.xb-xc)*(yn-yc)+(sr.yb-yc)*(xn-xc)>0) ){ return 1; };
   return 0;
 };
 if(res==1){
   //Intersection is point "pr"
   if(pr.x==xp && pr.y==yp){ return 0; }; //PR=P
   if(pr.x==xc && pr.y==yc){ //PR=C
     if( -(xn-xc)*(yc-yp)+(yn-yc)*(xc-xp)>0 ){ //Angle PCN<=180 deg
       if( (-(x1-xc)*(yc-yp)+(y1-yc)*(xc-xp)>0)
        && (-(x1-xc)*(yn-yc)+(y1-yc)*(xn-xc)>0) ){ return 1; };
       if( (-(x2-xc)*(yc-yp)+(y2-yc)*(xc-xp)>0)
        && (-(x2-xc)*(yn-yc)+(y2-yc)*(xn-xc)>0) ){ return 1; };
       return 0;
     }else{ //Angle PCN>180 deg
       if( (-(x1-xc)*(yc-yp)+(y1-yc)*(xc-xp)>0)
        || (-(x1-xc)*(yn-yc)+(y1-yc)*(xn-xc)>0) ){ return 1; };
       if( (-(x2-xc)*(yc-yp)+(y2-yc)*(xc-xp)>0)
        || (-(x2-xc)*(yn-yc)+(y2-yc)*(xn-xc)>0) ){ return 1; };
       return 0;
     };
   }else{ //PR belongs to interval (P,C)
     if( -(x1-xc)*(yc-yp)+(y1-yc)*(xc-xp)>0 ){ return 1; };
     if( -(x2-xc)*(yc-yp)+(y2-yc)*(xc-xp)>0 ){ return 1; };
     return 0;
   };
 };

};

</source>