python判断点在直线的哪⼀侧_判断点在直线的哪⼀侧 由于本部分需要判断空间多边形的拓扑关系，现在约定凸多边形的边界和内部，凸多边形⽤顶点坐标的逆时针⽅向序列确定。凸多边形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点在直线上。
白介素6接下来将实现真正的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.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议