2.2.1下面開(kāi)始程序的設(shè)計(jì)：

由于本部分需要判斷空間多邊形的拓?fù)潢P(guān)系，現(xiàn)在約定凸多邊形的邊界和內(nèi)部，凸多邊形用頂點(diǎn)坐標(biāo)的逆時(shí)針?lè)较蛐蛄写_定。凸多邊形P Q的頂點(diǎn)序列為p1 p2 ..pn和q1 q2 …qn。為了簡(jiǎn)單，假設(shè)P邊界上不包含Q的頂點(diǎn)，Q的邊界上不包含P的頂點(diǎn)。這使得P和Q或者完全分離，或者重疊而交出一個(gè)新的凸多邊形。(這是我對(duì)本部分的初步設(shè)計(jì)。)

程序部分：

struct point

{

double x,y;

bool operator !=(point& p){return ((x!=p.x)||(y!=p.y));}

};

定義點(diǎn)的存儲(chǔ)結(jié)構(gòu)同時(shí)根據(jù)需要重載了operator !=。

然后是主類實(shí)現(xiàn)拓?fù)潢P(guān)系判斷。此外還有兩個(gè)輔助類dotline.h，LineIntersect.h分別實(shí)現(xiàn)點(diǎn)線判斷，兩線段相交求交點(diǎn)，為主類提供相應(yīng)的輔助功能。

Yolk.h(主類)

class ConvexPolyIntersection

{

private:

point R;

void output(double ,double);

void advance();頂點(diǎn)前進(jìn)程序部分

point *p,*q;

int il,jl,i,j,onlyonce;

dot inst1;

Intersect inst2;

public:

ConvexPolyIntersection(int itmp,int jtmp);求交集函數(shù)部分。

int intersection(int tab);

void printRelate();

~ConvexPolyIntersection(){delete p;delete q;inst1.~dot();inst2.~Intersect();}

};

為了有次序地求出交點(diǎn)，可以在兩個(gè)多邊形上交替的前進(jìn)，原則是在哪個(gè)多邊形的邊上可能有交點(diǎn)就等待，在另一個(gè)多邊形的邊上前進(jìn)。如果兩個(gè)凸多邊形相交，本程序可以精確的輸出交得的新凸多邊形的坐標(biāo)。并且已經(jīng)具備了一定的拓?fù)潢P(guān)系判斷能力，可是由于程序在設(shè)計(jì)之前添加了很多苛刻限制，使得程序不能很好的判斷EQ和相切關(guān)系。但是基本的分明蛋黃RCC5程序已經(jīng)完成。

難點(diǎn)問(wèn)題解決

主要難點(diǎn)是判斷多邊形頂點(diǎn)前進(jìn)的方法，規(guī)定P0＝P1 Q0＝Q1，接下來(lái)在哪個(gè)多邊形上前進(jìn)，需要區(qū)分8種情況，其中前四種和后四種是P和Q的地位對(duì)調(diào)。如圖

情形

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

Pi在Qi-1Qi

左

左

右

右

右

左

右

左

Qi在Pi-1Pi

左

左

右

左

左

左

右

右

安排在那個(gè)多邊形前進(jìn)

Q

P

Q

P

P

Q

P

Q

這樣完成了理論部分。

本來(lái)我認(rèn)為完成上面的程序就已經(jīng)大功告成，可是我發(fā)現(xiàn)他不遵守RCC標(biāo)準(zhǔn)，即沒(méi)有求三原謂詞P，C和I,雖然程序在改進(jìn)后可以完全實(shí)現(xiàn)RCC5拓?fù)渑袛喙δ?#xff0c;但是已經(jīng)無(wú)法直接求取三原謂詞P，C和I了。因?yàn)槌绦蛑嘘P(guān)于三原謂詞P，C和I的理解發(fā)生了偏差，程序中是按照相交為P考慮的，即求出交集p=true。而當(dāng)C=true時(shí)P并不為真，他僅僅關(guān)注邊和點(diǎn)，而理論中應(yīng)該是關(guān)注邊所圍成的面積。P是C的一部分。所以將對(duì)程序進(jìn)行改寫(xiě)。

由于下面將繼續(xù)使用點(diǎn)線判斷類，所以對(duì)此類的實(shí)現(xiàn)進(jìn)行詳細(xì)介紹：

dotline.h(注意這里直線是有方向性的)

怎么判斷坐標(biāo)為(xp，yp)的點(diǎn)P是在直線的哪一側(cè)呢?設(shè)直線是由其上兩點(diǎn)(x1,y1)(x2,y2)確定的，直線方向是由(x1，y1)到(x2，y2)的方向。這時(shí)若直線方程記為Ax+By+C=0

則有：

A=y2-y1; B=x1-x2; C=x2*y1-x1*y2;

這時(shí)可以計(jì)算D：

D=A*xp+B*yp+C

若D<0，則點(diǎn)(xp，yp)在直線的左側(cè)；若D>0，則點(diǎn)在直線的右側(cè)；D＝0點(diǎn)在直線上。

接下來(lái)將實(shí)現(xiàn)真正的RCC5程序。在原有程序的實(shí)踐基礎(chǔ)上，求三原謂詞P，C和I關(guān)系實(shí)際上就是求凸多邊形的邊界頂點(diǎn)與另一個(gè)凸多邊形的位置關(guān)系。

即：

P(x,y)只要有凸多邊形x或y的一個(gè)頂點(diǎn)在凸多邊形y或x內(nèi)，說(shuō)明x，y有相交部分(即，面積有重合部分)，P=true否則P=false。

C (x,y)凸多邊形y的所有頂點(diǎn)都在凸多邊形x中或上，c=true，否則c=false。

I (x,y)與C (x,y)同理。

這樣就減少了設(shè)計(jì)的復(fù)雜性，同時(shí)相切問(wèn)題也會(huì)得到解決，即主要注意“點(diǎn)線”關(guān)系，就可以很好的判斷各種關(guān)系。

難點(diǎn)問(wèn)題解決：

這樣程序的焦點(diǎn)就都集中在一個(gè)功能齊全的點(diǎn)與線段關(guān)系判斷類上。此類首先能判斷點(diǎn)與線段所在直線的位置關(guān)系(點(diǎn)在直線左側(cè)；點(diǎn)在直線右側(cè) ；點(diǎn)在直線上)，當(dāng)點(diǎn)在直線上時(shí)，進(jìn)一步判斷點(diǎn)與線段的關(guān)系，在線段上(在線段端點(diǎn)上 或 不在)，在線段外。

本程序?qū)⒗^承 dotline.h

實(shí)現(xiàn)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();/*此函數(shù)返回點(diǎn)線關(guān)系結(jié)果*/

};

/*

點(diǎn)線關(guān)系：

1在線段左側(cè) －－ 點(diǎn)在凸多邊形 內(nèi)部 是點(diǎn)在直線的公共左側(cè)

0在線段右側(cè)

2點(diǎn)在線段外

3點(diǎn)與線段端點(diǎn)重合

4點(diǎn)在線段上

*/

其中 輸出結(jié)果為3 4時(shí)，是為RCC8程序準(zhǔn)備的。此程序由于是對(duì)dotline.h的擴(kuò)展，所以函數(shù)數(shù)量較少。

完成點(diǎn)線關(guān)系判斷后，實(shí)現(xiàn)RCC5判斷

實(shí)現(xiàn)yolk1.h(在yolk.h的基礎(chǔ)上對(duì)其進(jìn)行標(biāo)準(zhǔn)RCC5重寫(xiě) 求三原謂詞P，C和I)

本程序繼承了yolk.h的優(yōu)點(diǎn)，使用指針存儲(chǔ)點(diǎn)結(jié)構(gòu)(對(duì)頂點(diǎn)數(shù)沒(méi)有限制)。

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();

};

算法設(shè)計(jì)：

此類的焦點(diǎn)集中在relateRcc()函數(shù)上。他對(duì)矢量數(shù)據(jù)進(jìn)行兩次掃描判斷三原謂詞P，C和I。以“點(diǎn) 、凸多邊形”拓?fù)潢P(guān)系為基礎(chǔ)。如當(dāng)其中一個(gè)凸多邊形的端點(diǎn)在另一個(gè)的內(nèi)部時(shí)，可以判斷P=true.

總結(jié)

以上是生活随笔為你收集整理的python判断点在直线的哪一侧_判断点在直线的哪一侧的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。