Просмотр исходного текста страницы Библиотека myBasicGeometry

{{InfoBlock|Теоретические выкладки по этой теме можно найти на странице [[Прикладная геометрия]]|&nbsp; &nbsp; &nbsp; &nbsp; Теория}}

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

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

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

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

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

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

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

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

=== myBasicGeometry.h ===

<source lang="cpp">

#ifndef myBasicGeometryH
#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);

#endif

</source>

=== myBasicGeometry.cpp ===

<source lang="cpp">

#pragma hdrstop
#include "myBasicGeometry.h"
//---------------------------------------------------------------------------
#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>