2.2.1下面开始程序的设计：
由于本部分需要判断空间多边形的拓扑关系，现在约定凸多边形的边界和内部，凸多边形用顶点坐标的逆时针方向序列确定。凸多边形P Q 的顶点序列为 p1 p2 ..pn 和q1 q2 …qn 。为了简单，假设P边界上不包含Q的顶点，Q的边界上不包含P的顶点。这使得P 和Q或者完全分离，或者重叠而交出一个新的凸多边形。（这是我对本部分的初步设计。）
程序部分：
struct point
{
double x,y;
bool operator !=(point& p){return ((x!=p.x)||(y!=p.y));}
};
定义点的存储结构同时根据需要重载了operator !=。
然后是主类实现拓扑关系判断。此外还有两个辅助类dotline.h ，LineIntersect.h分别实现点线判断，两线段相交求交点，为主类提供相应的辅助功能。
Yolk.h（主类）
class ConvexPolyIntersection
{
private:
point R;
void output(double ,double);
void advance();顶点前进程序部分
point *p,*q;
int il,jl,i,j,onlyonce;
dot inst1;
Intersect inst2;
public:
ConvexPolyIntersection(int itmp,int jtmp);求交集函数部分。
int intersection(int tab);
void printRelate();
~ConvexPolyIntersection(){delete p;delete q;inst1.~dot();inst2.~Intersect();}
};
为了有次序地求出交点，可以在两个多边形上交替的前进，原则是在哪个多边形的边上可能有交点就等待，在另一个多边形的边上前进。如果两个凸多边形相交，本程序可以精确的输出交得的新凸多边形的坐标。并且已经具备了一定的拓扑关系判断能力，可是由于程序在设计之前添加了很多苛刻限制，使得程序不能很好的判断EQ 和相切关系。但是基本的分明蛋黄RCC5 程序已经完成。
难点问题解决
主要难点是判断多边形顶点前进的方法，规定P0＝P1 Q0＝Q1 ，接下来在哪个多边形上前进，需要区分8种情况，其中前四种和后四种是P 和Q的地位对调。如图
情形
（1）
（2）
（3）
（4）
（5）
（6）
（7）
（8）
Pi在Qi-1Qi
左
左
右
右
右
左
右
左
Qi在Pi-1Pi
左
左
右
左
左
左
右
右
安排在那个多边形前进
Q
P
Q
P
P
Q
P
Q
这样完成了理论部分。
本来我认为完成上面的程序就已经大功告成，可是我发现他不遵守RCC标准，即没有求三原谓词P， C和I,虽然程序在改进后可以完全实现RCC5拓扑判断功能，但是已经无法直接求取三原谓词P， C和I了。因为程序中关于三原谓词P ，C 和I的理解发生了偏差，程序中是按照相交为P考虑的，即求出交集p=true。而当C=true 时 P并不为真，他仅仅关注边和点，而理论中应该是关注边所围成的面积。P是C的一部分。所以将对程序进行改写。
由于下面将继续使用点线判断类，所以对此类的实现进行详细介绍：
dotline.h（注意这里直线是有方向性的）
怎么判断坐标为（xp，yp）的点P是在直线的哪一侧呢?设直线是由其上两点（x1,y1）(x2,y2)确定的，直线方向是由（x1，y1）到（x2，y2）的方向。这时若直线方程记为Ax+By+C=0
则有：
A=y2-y1; B=x1-x2; C=x2*y1-x1*y2;
这时可以计算D：
D=A*xp+B*yp+C
若D<0，则点（xp，yp）在直线的左侧；若D>0，则点在直线的右侧；D＝0点在直线上。
接下来将实现真正的RCC5程序。在原有程序的实践基础上，求三原谓词P ，C 和I 关系实际上就是求凸多边形的边界顶点与另一个凸多边形的位置关系。
即：
P（x,y）只要有凸多边形x或y 的一个顶点在凸多边形 y 或x 内，说明x，y 有相交部分（即，面积有重合部分），P=true 否则 P=false。
C (x,y) 凸多边形y 的所有顶点都在凸多边形x 中或上， c=true，否则 c=false。
I (x,y)与C (x,y)同理。
这样就减少了设计的复杂性，同时相切问题也会得到解决，即主要注意“点线”关系，就可以很好的判断各种关系。
难点问题解决：
这样程序的焦点就都集中在一个功能齐全的点与线段关系判断类上。此类首先能判断点与线段所在直线的位置关系（点在直线左侧；点在直线右侧 ；点在直线上），当点在直线上时，进一步判断点与线段的关系，在线段上（在线段端点上 或 不在），在线段外。
本程序将继承 dotline.h
实现Superdotline.h
#include”dotline.h”/*头文件*/
class SuperDot: public dot
{
public:
SuperDot(){}
SuperDot(double xp1,double yp1,double x11,double y11,double x22,double y22):dot(xp1, yp1,x11,y11,x22,y22){}
~SuperDot(){}
int judgeDeeply();/*此函数返回点线关系结果*/
};
/*
点线关系 ：
1 在线段左侧 －－ 点在凸多边形 内部 是点在直线的公共左侧
0 在线段右侧
2 点在线段外
3 点与线段端点重合
4 点在线段上
*/
其中 输出结果为 3 4 时，是为RCC8 程序准备的。此程序由于是对dotline.h的扩展，所以函数数量较少。
完成点线关系判断后，实现RCC5判断
实现yolk1.h （在yolk.h 的基础上对其进行标准RCC5 重写 求三原谓词P ，C和I）
本程序继承了yolk.h的优点，使用指针存储点结构（对顶点数没有限制）。
class yolk :public SuperDot
{
proteced:
point *p,*q;
int il,jl,i,j;
bool P,C,I;
void relateRcc();/* 求P C I*/
yolk(){}
public:
yolk(int itmp,int jtmp);
~yolk(){delete p;delete q;}
void printRelate();
};
算法设计：
此类的焦点集中在relateRcc()函数上。他对矢量数据进行两次扫描判断三原谓词P，C和I。以“点 、凸多边形”拓扑关系为基础。如当其中一个凸多边形的端点在另一个的内部时，可以判断 P=true.
以这样的原理实现分明区域蛋黄模型RCC5。
难点问题解决：
在设计过程中遇到了一些临界条件的判断，如当有多个顶点重合时，怎么判断是否相交（p=true）和一些相切情况。程序中利用标识位很好的解决了上述问题。
另一个难点就是多少次扫描最合理，当然一次扫描是程序设计所追求的最理想的，但是在编码过程中我发现求P是影响扫描次数的关键，在现有的程序结构基础上，两次扫描可以接受。
实现效果：
当以文件形式输入矢量坐标后，输出结果为RCC5关系的相应表示。
本文地址：http://com.8s8s.com/it/it37148.htm