Библиотека 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>