开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 多媒体 > 查看源码
N_PKT6-29PM.CPP
资源名称：vcavi.rar　[点击查看]
上传用户：shonly
上传日期：2022-06-05
资源大小：1939k
文件大小：120k
源码类别：

多媒体

开发平台：

Visual C++

N_PKT6-29PM.CPP：源码内容
  1. #include "stdafx.h"
  2. #include "sysdef.h"
  3. #include "math.h"
  4. #include "e_gvar.h"
  5. #include "e_uibas.h"
  6. #include "e_math3d.h"
  7. #include "e_curve.h"
  8. #include "e_surface.h"
  9. #include "e_nc.h"
  10. #include "e_datum.h"
  11. #include "e_system.h"
  13. #include "resource.h"
  14. #include "ToolPage.h"
  15. #include "MillParaPage.h"
  16. #include "ncpktpage.h"
  17. #include "ncplungepage.h"
  18. #include "ncpktproSheet.h"
  19. #include "Nc.h"
  20. //ZERO = 1.0E-5
  21. #define CCW   1    //
  22. #define CW    -1     //
  23. #define EP  10e-1
  24. #define EL  10e-1
  25. #define UPER   10e2
  26. #define LINEZ  10e-2
  27. #define LL  0  //line line bisector
  28. #define LC  1  //line circle bisector 
  29. #define CC  2  //circle circle bisector
  30. #define CCP 3  //concenter circle circle bisector
  31. #define LLP 4  //parallel line line bisector
  32. #define CIC 5  //circle in circle bisector //ellipse
  33. #define INFINITY  1  //
  34. #define LIMITED  0  //
  35. #define STEP  0.2//画平分线的步长
  36. #define SINGLE  0
  37. #define MULI    1
  38. #define VCOMMON 1
  39. #define CLOSED  2
  40. #define SINGLEPLF  0
  41. #define MULIPLF    1
  42. #define ISLAND     0
  43. #define LOOP       1
  44. #define ERRO      -100
  45. #define REFLEX    -1
  46. #define UNREFLEX   1
  47. ///////////////////////
  48. static int myflag=0;
  49. typedef struct bisector{
  50. double t1,t2,tmin,tmax;
  51. int infinite;//limitations/INFINITY/LIMITLINE
  52. int     bitype;//类型LC/CC/LL
  53. int     limit;
  54. double x1,x2,x3,x4,x5,x6,x7,x8;
  55. double y1,y2,y3,y4,y5,y6,y7,y8;
  56. double  a1,a2,a3,a4;
  57. int   m1,m2;
  58. }VBNS,*PVBNS;//表示单个角平分线
  59. typedef struct contournodesingle{
  60. int type;//直线或是弧
  61. PRIMITIVE element;//PRIMITIVE
  62. int reflex;//if 1,means the reflex node;
  63. int clockwise;//，段的方向 CCW OR CW
  64. }VCNS,*PVCNS;//?//单个轮廓线
  66. typedef struct contournodeinform{
  67. PVCNS cns;
  68. struct contournodeinform *ccw,*cw;
  69. }VCNI,*PVCNI;//一组轮廓线
  70. typedef struct besectorinform{
  71. PVBNS bns;//PVBNS
  72. PVCNS selfcns,othercns;//PVCNs
  73. int   flag;//使用过？0/1 
  74. }VBNI,*PVBNI;//单个角平分线，有对应轮廓线的信息
  76. typedef struct bisectorlinkinform {
  77. PVBNI bni;//PVBNI
  78. int clockwise;//角平分线的走向，0（顺）/1（逆）
  79. struct bisectorlinkinform *next,*last;//struct bisectorlinkinform
  80. }VBLI,*PVBLI;//一组角平分线
  82. typedef struct contournodebisectorlink{
  83. PVCNS cns;//PVCNI，节点
  84. PVBLI bli;//ccw direction;PVBLI
  85. int   flag;//是否是终节点？-1/1
  86. struct contournodebisectorlink *ccw,*cw;
  87. }VCNBL,*PVCNBL;//一个VORONOI 单元
  89. typedef struct profilelef{
  90. PVCNBL scnbl,ecnbl;//PVCNBL，一个含有节点和角平分线的voronoi 结构
  91. int    type;//单节点否？SINGLEPLF/MULIPLF
  92. struct profilelef *cw,*ccw;//f
  93. }VPLF,*PVPLF;//树叶
  94. typedef struct profilelink{
  95. PVPLF splf,eplf;//叶子的首末点   
  96. int   ptype;   //whether be a single reflex or a conected closed profile;
  97.    //if ptype= SINGLE and reflex=1,mean the reflexmax profile;
  98.    //if ptype= COMMON means the profile within an closed contour;
  99.                //if ptype= CLOSED means the closed contour include the isle 
  100.                //and the whole closed contour;   
  101.                    //in the other hand,we can only use one int for the useage of the label task,
  102.                    //for the safe reason I use two;
  103. }VPL,*PVPL;//一个轮廓环,树枝/也可是一棵树
  104. ///////////////////////above is the data used ,//ygm
  105. extern __declspec(dllimport) int DrawLine(double x0,double y0,double z0,
  106.  double x1,double y1,double z1,int color);
  107. //////////////////////////////////////////////////////////////////////////////ygm
  108. PVPLF  vmallocplf();//;叶
  109. PVCNBL vmalloccnbl();//;voronoi 节点
  110. PVBLI  vmallocbli();//;平分线连
  111. PVBNI  vmallocbni();//;角平分线
  112. PVCNI  vmalloccni();//;
  113. PVBNS  vmallocbns();//;
  114. PVCNS  vmalloccns();//;
  115. ////////////////...........................
  116. void   vdeletevlf(PVPL vpl);
  117. void   vdeleteplf(PVPLF plf);
  118. void   vdeletebli(PVBLI bli);
  119. //////////////////...............................................
  120. void  vdisplaybnstest(VBNS bi);
  121. void  vdisplayplv(VPL pl);
  122. void  vgainpointseg(PVCNS *c,PXYZ p);//;
  123. void  vdisplaysinglebi(VBNS bi,int color);//;tested
  124. void  vdisplayvoronoi(VCNI cnode);//;tested
  125. /////////////////..................
  126. void  vgainbisectorll(PVCNS l1, PVCNS l2, PVBNS *bi);//;tested unfinished
  127. void  vgainbisectorlc(PVCNS l1, PVCNS c2, PVBNS *bi);//;tested yet unfinished
  128. void  vgainbisectorcc(PVCNS c1, PVCNS c2, PVBNS *bi);//;tested yet unfinished
  129. void  vgainbisector(PVCNS c1, PVCNS c2, PVBNS *bi);
  130. /////////////////..................
  131. void  vgainintersectlll(PVCNS l1,PVCNS l2,PVCNS l3,int *i,double t[2]);//;tested
  132. void  vgainintersectllc(PVCNS l1,PVCNS l2,PVCNS c3,int *i,double t[2]);//;parallel untreated yet tested
  133. void  vgainintersectlcc(PVCNS l1,PVCNS c2,PVCNS c3,int *i,double t[2]);//;testing unfinished
  134. void  vgainintersectccc(PVCNS c1,PVCNS c2,PVCNS c3,int *i,double t[2]);//;testing unfinished
  135. void  vgainintersect(PVCNS c1,PVCNS c2,PVCNS c3,int *i,double t[2]);
  136. void  vgainintersectmvaluebns(PVBNS bns1,PVBNS bns2,double *t,int mblis,int * mvalue);
  137. void  vgainintersectmvaluecns(PVBNS bns,PVCNS c1,PVCNS c2,PVCNS c3,double t,int *mvalue); 
  138. ////////////////....................................................
  139. void vaddpointsegpre(PVCNBL cnbl);//cw 方向
  140. void vaddpointseglast(PVCNBL cnbl);
  141. void  vfindarcendpointo(PARC arc,PXYZ *pt,int *clockwise);
  142. PXYZ  vgetintersectpoint(VBNS bi,double t,int m);//;finished
  143. PXYZ  vgetintersectpointlc(VBNS bi,double t,int m);//;finished
  144. void  vgetvalue(double a,double b,double c,double t[2],int *i);//;tested
  145. void  vgetparaline(PLINE l,double *a,double *b,double *c);//;tested and it is o of the important function
  146. ///////////////......................................................
  147. void  vgetllimit(PVCNS cn,double *a,double *b,double *c,double *t);//parameter line;
  148. void  vgetcflimit(PVCNS cn,double *a,double *b,double *c,double *t);//paraeter line;
  149. void  vgetcslimit(PVCNS cn,double *a,double *b,double *c,double *t);//parameter line;
  150. /////////////.........................................................
  151. void vgainarrangedcnbl(PCURVE curve,PVCNBL *cnbl,int itype);
  152. void  vgainfistbisectorpoint(PVCNBL lcnbl,PVCNBL rcnbl);
  153. void  vgainsinglebisector(PVCNBL cnbl,PVBLI *bt);//;
  154. void  vchangepcurvetocnode(PCURVECMP curcmp,PVCNBL vnode);//
  155. int   vgetlm(PVCNS l);
  156. ///////////////........................................................
  157. int  vgetclockwisebli(PVBLI bli);
  158. double vmultipointvector(PXYZ v1,PXYZ v2);
  159. double vmultiplayvector(PXYZ v1,PXYZ v2);
  160. //////////////........................
  161. PXYZ  vgetplproject(double x,double y,PLINE line);
  162. int   vgetposition(double x,double y,PXYZ p0,PXYZ p1);
  163. int   vgetposition(double x,double y,double x0,double y0,double x1,double y1);//
  164. void  vtransintovcns(PCURVE pi);
  165. PVPL  vgaindoublelink(PCURVECMP cmp);
  166. /////////////..............................................................
  167. int  vgainintersectortl(PVCNBL lcnbl,PVCNS rcns,PVBNS bns,int startflag,int directionflag,PVBLI blif,double *t,int *m,PVBLI *bli);
  168. int  vgainintersectortr(PVCNBL rcnbl,PVCNS lcns,PVBNS bns,int startflag,int directionflag,PVBLI blif,double *t,int *m,PVBLI *bli);
  169. int  vcompareright(int m1,double t1,int m2,double t2);
  170. int  vcomparerights(int m1,double t1, int m2,double t2, int m3,double t3, int m4,double t4, int *mm1,double *tt1,int *mm2,double *tt2);
  171. void vmergesingleprofile(PVPL profile);
  172. int  vjudgeprofilesingle(PVPL profile);
  173. void vdivideprofiletwo(PVPL profile,PVPL pl,PVPL pr);
  174. void vgainsingleplfbli(PVPLF plf);
  175. void vmergetwoprofile(PVPL pl,PVPL pr,PVPL *profile);
  176. ////////////................................................................
  177. void  vchangepcurvetocnblloop(PCURVE curve,PVCNBL *cnbl);
  178. void vgainprofilebycurve(PCURVE curve,PVPL *vpl,int itype);
  179. void vjugedirection(PVCNBL cnbl,int *flag);
  180. double vgainangleofvector(PXYZ v);
  181. void  vmergecontour();
  182. void  vdividetheprofile(PVPL i_pr,PVPL o_prl,PVPL o_prr);
  183. PVPL  vgainvoronoi(PCOMPOSITE cmp,PCURVECMP island[],int num);
  184. //////ygm..///////////////////////////////////////////////////////////////////////
  185. extern __declspec(dllimport) void ReSaveProfileToolRCompPara(PPATH2D path);
  186. extern __declspec(dllimport) int g_pkt_RComp;
  187. extern void PreSetSpeedAndHeight(CSpeedPage *m_Page2);
  188. extern void ModifySpeedAndHeight(CSpeedPage *m_Page2);
  189. ///1999-6-7 ygr
  190. extern void SaveContourToParameter(NCPARA *m_para,char *name,PSELGRP hsel,PCURVECMP curvecmp);
  191. extern void SaveRefPoint2DToParameter(NCPARA *m_para,char *name,XY point);
  192. extern void SaveIntegerToParameter(NCPARA *m_para,char *name,int integer);
  193. void ncCreatPathTree(unsigned long handle,NCPARA para,char *name);
  194. ///1999-6-7 ygr
  195. void PreSetPktParameter(CNcPktSheet *spktSheet);
  196. void ModifyPktParameter(CNcPktSheet *spktSheet);
  197. extern PNCPARA MallocNcpara();
  198. extern void GiveOldParaToNewPara(PNCPARA m_oldpara,PNCPARA m_newpara);
  199. extern void SaveRefPoint3DToParameter(NCPARA *m_para,char *name,XYZ point);
  200. extern void SaveNCWCSToParameter(NCPARA *m_para,char *name,NCWCS wc);
  201. ///////////////////////////////////////////////////////////////////////ygm
  202. ////////////////////////////////////////////////////////////////////////////
  203. int AppNcProfile(int &step,int &flag){return 1;}
  204. void PreSetPktParameter(CNcPktSheet *spktSheet){}
  205. void ModifyPktParameter(CNcPktSheet *spktSheet){}
  206. void PreSetProParameter(CNcProSheet *sproSheet){}
  207. void ModifyProParameter(CNcProSheet *sproSheet){}
  208. //////////////////////////////////////////////
  209. ////////////////////////////////////////////////////////////////////////////
  210. int AppNcPkt(int &step,int &flag)//平面区域加工
  211. {
  212. static    XYZ       point;
  213. static    PCURVECMP pickcur=NULL;
  214. static    PCURVE     cur;
  215. static    PSELGRP   psel=NULL,sel=NULL;
  216. static    PCURVECMP islands=NULL,tisl=NULL;
  217. int ret,num;
  218. double pln_mat[4][4];
  219. PPATH2D path=NULL;
  220. PSELGRP seli=NULL;
  221. PCURVECMP isl=NULL,*islandin=NULL;
  222. CNcPktSheet pktSheet;
  223. static    PATH2D    temppath; //ygr 1999-6-7轨迹重算
  224. NCWCS     wc;
  225. CString sTemp; // gkq: 为了存储资源字符串
  226. ////////////test ygm
  227. PVPL vpl;
  228. VBNS a;
  229. PVCNS l1,l2,l3,c1,c2,c3;
  230. PLINE  line1,line2,line3;
  231. PARC arc1,arc2,arc3;
  232. PVCNBL cnbl;
  233. double t[2];
  234. int i;
  235. // ASSERT(0);
  236. a.x1=56;a.x2=6;a.x3=7;a.x4=2;a.x5=50;a.x6=5;a.x7=2;a.x8=5;
  237. a.y1=44;a.y2=0;a.y3=80;a.y4=2;a.y5=67;a.y6=5;a.y7=4;a.y8=0;
  238. a.m1=1;a.m2=1;a.tmin=1;a.t1=10;a.infinite=0;a.bitype=2;
  239. l1=vmalloccns();l1->clockwise=CCW;l1->type=CAXLINE;l1->reflex=0;
  240. l2=vmalloccns();l2->clockwise=CCW;l2->type=CAXLINE;l2->reflex=0;
  241. l3=vmalloccns();l3->clockwise=CCW;l3->type=CAXLINE;l3->reflex=0;
  242. c1=vmalloccns();c1->clockwise=CW;c1->type=CAXARC;c1->reflex=0;
  243. c2=vmalloccns();c2->clockwise=CW;c2->type=CAXARC;c2->reflex=0;
  244. c3=vmalloccns();c3->clockwise=CCW;c3->type=CAXARC;c3->reflex=0;
  245. //bi=vmallocbns();
  246. line1=l1->element.line=MallocLine();
  247. line1->p0.x=0;line1->p0.y=-1000;line1->p1.x=0;line1->p1.y=1000;
  248. line2=l2->element.line=MallocLine();
  249. line2->p0.x=0;line2->p0.y=0;line2->p1.x=100;line2->p1.y=0;
  250. line3=l3->element.line=MallocLine();
  251. line3->p0.x=100;line3->p0.y=0;line3->p1.x=0;line3->p1.y=100;
  252. arc1=c1->element.arc=MallocArc();
  253. arc1->pc.x=0;arc1->px.x=10;arc1->py.y=10;arc1->a=3.14*2;
  254. arc1->pc.y=-10;
  255. arc1->r=5;
  256. arc2=c2->element.arc=MallocArc();//cw
  257. arc2->pc.x=10;arc2->px.x=10;arc2->px.y=0;
  258. arc2->pc.y=0;arc2->py.x=0;arc2->py.y=10;
  259. arc2->r=10;
  260. arc3=c3->element.arc=MallocArc();
  261. arc3->pc.x=0;
  262. arc3->pc.y=0;
  263. arc3->r=100;
  264. XYZ o;
  265. XYZ v;
  266.     v.x=4;v.y=6;
  267. // PSTR3D o_p;
  268. int yyy = RGB(200,100,0);
  269. vgainintersect(c1,c2,l2,&i,t);
  270. // vdisplaybnstest(*bi);
  271. ///////////////////test
  272. switch(step)
  273. {
  274. case 0://填写参数表
  275. if(g_Mod6 != 1111)
  276. {
  277. AfxMessageBox(IDS_ILLIGIAL_MODE);
  278. uiEndCommand();
  279. return 0;
  280. }
  281. psel=NULL;
  282. islands=NULL;
  283. islandin=NULL;
  284. pickcur=NULL;isl=NULL;
  285. cla_bod=NULL;
  286. cla_isl=NULL;
  287. temppath.para.entity = NULL; //1999-6-9 ygr
  288. temppath.para.parameter = NULL;//1999-6-9 ygr
  289. path=NULL;
  291. uiPromptID(IDS_FILL_NCPARA);
  293. AssignValueToPktCutPara();
  294. uiRegisterPopMenu(IDR_CONTOUR_PICK_TOOLS,0);
  295. //uiPrompt("拾取轮廓:");
  296. uiPromptID(IDS_PICK_CONTOUR);
  297. //vdisplaysinglebi(bi);
  299. break;
  300. case 1://拾取轮廓
  301. ret=CaxGetCloseContour(&pickcur,&psel);
  302. point= PickBuffer[0].pick_pt;///what is the pickBuffer?
  303. if(ret!=PICK_OK)
  304. {
  305. uiEndCommand();
  306. return 1;
  307. }
  308. //// ygr 1999-6-7/// 轨迹重算
  309. //CaxGetNcPlaneMatrix(pln_mat);
  310. //SaveNcPlaneMatrixToParameter(&(temppath.para),"nc_plane_matrix",pln_mat);
  311. GetNCWcsFromSystemWCS(&wc);//get wc
  312. SaveNCWCSToParameter(&(temppath.para),"nc_working_coordinate",wc);
  313. SaveContourToParameter(&(temppath.para),"contour",psel,pickcur);
  314. SaveRefPoint3DToParameter(&(temppath.para),"referance_point",point);
  315. //// ygr 1999-6-7///轨迹重算
  316. for(sel = psel;sel->next != NULL;sel = sel->next)
  317. ;
  318. step = 2;
  319. //uiPrompt("拾取岛:");
  320. uiPromptID(IDS_PICK_ISLANDS);
  321. uiRegisterPopMenu(IDR_ISLAND_PICK_TOOLS,0);
  322. break;
  323. case 2://拾取岛屿
  324. ret = CaxGetIsland(&isl,&seli);
  325. if(ret==PICK_ESC)
  326. goto finish;
  327. else if(ret==PICK_FSH)
  328. goto cal;
  329. else
  330. {
  331. SaveContourToParameter(&(temppath.para),"islands",seli,isl);
  332. if(islands == NULL)
  333. tisl = islands = isl;
  334. else
  335. tisl = tisl->next = isl;
  336. sel->next = seli;
  337. for(sel = seli;sel->next != NULL;sel = sel->next)
  338. ;
  339. }
  340. break;
  341. }
  342. return 1;
  344. cal:
  345. uiRegisterPopMenu();
  347. SaveParameterToPocketPath(&temppath);
  348. if(g_AutoPath==1)
  349. {
  350. PNCPARA para;
  352. para = NULL;
  353. para = MallocNcpara();
  354. GiveOldParaToNewPara(&(temppath.para),para);
  355. g_NcparaList.AddTail(para);
  356. goto finish;
  357. }
  358. num=0;
  359. islandin=NULL;
  360. for(tisl=islands;tisl!=NULL;tisl=tisl->next)
  361. num++;
  362. num--;
  363. if(num>=0)
  364. {
  365. islandin=new PCURVECMP[num+1];
  366. if(islandin==NULL) uiNoMemoryError();
  367. for(int i=0;i<=num;i++)
  368. {
  369. islandin[i]=islands;
  370. islands=islands->next;
  371. }
  372. }
  373. ptx = new PT_SECT[2*MaxPktSegNumber];
  374. pty = new PT_SECT[2*MaxPktSegNumber];
  375. if(ptx==NULL||pty==NULL) uiNoMemoryError();
  376. //uiPrompt("生成加工轨迹,请稍等...");
  377. uiPromptID(IDS_WAITING);
  378. CaxGetNcPlaneMatrix(pln_mat);
  379. cur=pickcur->cmp->curve;
  380. vchangepcurvetocnblloop(pickcur->cmp->curve,&cnbl);
  381. vgainprofilebycurve(pickcur->cmp->curve,&vpl,CCW);
  382. vmergesingleprofile(vpl);
  383. vdisplayplv(*vpl);
  384. // vjugedirection(cnbl,&flag,1);
  385. //va:  t=vgainangleofvector(&v);
  386. //    goto va;
  387. // path=pktFlwPathCreat(pickcur,islandin,num,point,pln_mat);
  388. // path=NULL;
  389. if(path==NULL)
  390. {
  391. delete[] ptx;
  392. delete[] pty;
  393. FreePathPara(temppath.para);
  394. goto finish;
  395. }
  396. //SaveParameterToPocketPath(path);
  397. path->para=temppath.para; 
  398. cursor_off();
  399. InitialUndoBuffer();
  400. GetNCWcsFromSystemWCS(&(path->wc));
  401. CaxDrawPath2D(SavePath2D(path));
  402. //ncCreatPathTree(path->handle,path->para,"平面区域加工");
  403. sTemp.LoadString( IDS_PlanePocketCutStr );
  404. char str[100];
  405. strcpy(str, (LPCTSTR)sTemp);
  406. ncCreatPathTree(path->handle,path->para, str);
  408. uiSetModifiedFlag(TRUE);
  409. cursor_on();
  411. delete[] ptx;
  412. delete[] pty;
  413. if(islandin!=NULL)
  414. delete[] islandin;
  415. islands=NULL;
  416. islandin=NULL;
  417. pickcur=NULL;isl=NULL;
  418. cla_bod=NULL;
  419. cla_isl=NULL;
  420. path=NULL;
  422. finish:
  423. ptx=pty=NULL;
  424. InitialSelgrp(psel);
  425. uiEndCommand();
  426. return 1;
  427. }
  428. /////////...................................................................
  429. PVBNS vmallocbns()
  430. {
  431. PVBNS bi=NULL;
  433. bi = (PVBNS)malloc(sizeof(VBNS));
  434. if(NULL == bi)uiNoMemoryError();
  436. bi->a1=bi->a2=bi->a3=bi->a4=0.0;
  437. bi->x1=bi->x2=bi->x3=bi->x4=bi->x5=bi->x6=bi->x7=bi->x8=0;
  438. bi->y1=bi->y2=bi->y3=bi->y4=bi->y5=bi->y6=bi->y7=bi->y8=0;
  440. bi->m1=bi->m2=1;
  441. bi->tmin=bi->t1=bi->t2=0;
  442. bi->bitype=-1;
  443. bi->infinite = 1;
  444. bi->limit =0;
  445. return bi;
  446. }
  447. PVCNS vmalloccns()
  448. {
  449. PVCNS ci;
  451. ci = NULL;
  452. ci = (PVCNS)malloc(sizeof(VCNS));
  453. if(NULL==ci)uiNoMemoryError();
  454. ci->clockwise = CCW;
  455. ci->element.line=NULL;
  456. ci->reflex=0;
  457. ci->type=CAXLINE;
  458. return ci;
  459. }
  460. PVCNI vmalloccni()
  461. {
  462. PVCNI vi;
  464. vi = NULL;
  465. vi = (PVCNI)malloc(sizeof(VCNI));
  466. if(NULL == vi)uiNoMemoryError();
  467. vi->ccw=NULL;
  468. vi->cw=NULL;
  469. vi->cns=NULL;
  470. return vi;
  471. }
  472. PVBNI vmallocbni()
  473. {
  474. PVBNI bi;
  476. bi = NULL;
  477. bi = (PVBNI)malloc(sizeof(VBNI));
  478. if(NULL == bi)uiNoMemoryError();
  479. bi->bns=NULL;
  480. bi->selfcns=NULL;
  481. bi->othercns=NULL;
  482. bi->flag=0;
  483. return bi;
  484. }
  485. PVBLI  vmallocbli()//;平分线连
  486. {
  487. PVBLI bli=NULL;
  489. bli=new VBLI;
  490. ASSERT(bli);
  491. bli->last=NULL;
  492. bli->next=NULL;
  493. bli->clockwise=CCW;
  494. bli->bni=NULL;
  495. return bli;
  496. }
  497. PVCNBL vmalloccnbl()//;voronoi 节点
  498. {
  499. PVCNBL cnbl;
  500. cnbl=new VCNBL;
  501. cnbl->ccw=NULL;
  502. cnbl->cw=NULL;
  503. cnbl->flag = 0;
  505. cnbl->bli=NULL;
  506. cnbl->cns=NULL;
  507. return cnbl;
  508. }
  509. PVPL vmallocpl()
  510. {
  511. PVPL  pl=NULL;
  512. pl=new VPL;
  513. ASSERT(pl);
  514. pl->eplf=NULL;
  515. pl->ptype=SINGLE;
  516. pl->splf=NULL;
  517. return pl;
  518. }
  519. PVPLF vmallocplf()
  520. {
  521. PVPLF plf=NULL;
  522. plf =(PVPLF)malloc(sizeof(VPLF));
  523. if(NULL==plf)uiNoMemoryError();
  524. plf->ccw=NULL;
  525. plf->cw=NULL;
  526. plf->ecnbl=plf->scnbl=NULL;
  527. plf->type=SINGLEPLF;
  528. return plf;
  529. }
  530. ///
  531. void vdeletebli(PVBLI bli)
  532. {
  533. if(bli!=NULL)
  534. {
  535. if(bli->bni != NULL)
  536. delete bli->bni;
  537. else
  538. AfxMessageBox("you have attempt to deleter NULL bni");
  539. delete bli;
  540. bli = NULL;
  541. }
  542. else{
  543. AfxMessageBox("you have attempt to deleter NULL bli");
  544. }
  545. return ;
  546. }
  547. void vdeleteplf(PVPLF plf)
  548. {
  549. if(!plf)
  550. {
  551. if(plf->type==SINGLE)
  552. {
  553. vdeletebli(plf->scnbl->bli);
  554. delete plf->scnbl;
  555. delete plf;
  556. }
  557. else
  558. {
  559. vdeletebli(plf->scnbl->bli);
  560. delete plf->scnbl;
  561. vdeletebli(plf->ecnbl->bli);
  562. delete plf->ecnbl;
  563. delete plf;
  564. }
  565. }
  566. else
  567. {
  568. AfxMessageBox("you attempt to delete a null plf");
  569. }
  570. return;
  571. }
  572. void vdeletevendpointcnbl(PVCNBL cnbl)
  573. {
  574. ASSERT(cnbl);
  575. PVBLI bli;
  576. PVBLI blit;
  577. if(cnbl->flag==1)
  578. {
  579. bli = cnbl->bli;
  580. while(bli!=NULL){
  581. blit = bli->next;
  582. vdeletebli(bli);
  583. bli = blit;
  584. }
  585. delete cnbl->cns;
  586. delete cnbl;
  587. cnbl = NULL;
  588. }
  589. else 
  590. {
  591. AfxMessageBox("please check the data before you delete the cnbl");
  592. }
  593. return;
  594. }
  595. /////.................................................................
  596. void  vdisplaybnstest(VBNS bi)
  597. {
  598. PLINE line;
  599. double x1,x2,x3,x4,x5,x6,x7,x8,m1;
  600. double y1,y2,y3,y4,y5,y6,y7,y8,m2;
  601. double tmax,t1,t2;
  602. double tt,t0;
  603. double tm;
  604. XYZ p0,p1,p2,p3,p4;
  605. x1=bi.x1;x2=bi.x2;x3=bi.x3;x4=bi.x4;x5=bi.x5;x6=bi.x6;x7=bi.x7;x8=bi.x8;
  606. y1=bi.y1;y2=bi.y2;y3=bi.y3;y4=bi.y4;y5=bi.y5;y6=bi.y6;y7=bi.y7;y8=bi.y8;
  607. t1 = bi.t1;m1 = bi.m1;t0 = bi.tmin;
  608. t2 = bi.t2;m2 = bi.m2;tmax = bi.tmax;
  609. line = MallocLine();
  610. p1.x = p0.x = 0;
  611. p1.y = p0.y = 0;
  612. p1.z = p0.z = 0;
  613. int fff = 0;
  614. for(tm = -UPER;tm<UPER;tm+=STEP)
  615. {
  616. t0 = tm+STEP;
  617. tt = pow(x5+x6*(t0),2)-pow(x7+x8*(t0),2);
  618. if(tt>=0)
  619. {
  620. if(fff==0)
  621. {
  622. p0.x=x1-x2-x3*(t0)+x4*sqrt(tt);
  623. p0.y=y1-y2-y3*(t0)-y4*sqrt(tt);
  624. p1.x=x1-x2-x3*(t0)-x4*sqrt(tt);
  625. p1.y=y1-y2-y3*(t0)+y4*sqrt(tt);
  626. fff=1;
  627. continue;
  628. }
  629. p3.x=x1-x2-x3*(t0)+x4*sqrt(tt);
  630. p3.y=y1-y2-y3*(t0)-y4*sqrt(tt);
  631. p4.x=x1-x2-x3*(t0)-x4*sqrt(tt);
  632. p4.y=y1-y2-y3*(t0)+y4*sqrt(tt);
  633. }
  634. else continue;
  635. p3.z = 0.0;
  636. p4.z = 0.0;
  637. line->p0 = p0;
  638. line->p1 = p3;
  639. p0=p3;
  640. SaveLine(line);
  641. CaxDrawLine(line);
  642. line=NULL;
  643. line= MallocLine();
  644. ////
  645. line->p0 = p1;
  646. line->p1 = p4;
  647. p1 = p4;
  648. SaveLine(line);
  649. CaxDrawLine(line);
  650. line=NULL;
  651. line= MallocLine();
  652. }
  653. return;
  654. }
  655. void  vdisplaysinglebi(VBNS bi,int color)
  656. {
  657. PCURVECMP cur=NULL;
  658. PLINE line;
  659. double x1,x2,x3,x4,x5,x6,x7,x8,m1;
  660. double y1,y2,y3,y4,y5,y6,y7,y8,m2;
  661. double tmax,t1,t2,tmin;
  662. double tm,tstep;
  663. double detax,detay,detax0,detay0;
  664. XYZ p0,p1;
  665. x1=bi.x1;x2=bi.x2;x3=bi.x3;x4=bi.x4;x5=bi.x5;x6=bi.x6;x7=bi.x7;x8=bi.x8;
  666. y1=bi.y1;y2=bi.y2;y3=bi.y3;y4=bi.y4;y5=bi.y5;y6=bi.y6;y7=bi.y7;y8=bi.y8;
  667. t1 = bi.t1;m1 = bi.m1;tmin = bi.tmin;
  668. t2 = bi.t2;m2 = bi.m2;tmax = bi.tmax;
  669. line = MallocLine();
  670. switch (bi.bitype)
  671. {
  672. case LL:
  673.     p1.x = x1-x3*t2;
  674. p1.y = y1-y3*t2;
  675. p0.x = x1-x3*t1;
  676.         p0.y = y1-y3*t1;
  677. p0.z = 0.0;
  678. p1.z = 0.0;
  679. line->p0 = p0;
  680. line->p1 = p1;
  681. //CaxDrawLine(line);
  682. cur=SaveLine(line);
  683. cur->color = color;
  684. CaxDrawCurvecmp(cur);
  685. cur = NULL;
  686. //SaveLine(line);
  687. break;
  688. case CC:
  689. case LC://直线与圆弧求交
  690. if(m1 == m2)
  691. {
  692. tstep = m1*(t2-t1)/6;
  693. p0.x=x1-x2-x3*t1+m1*x4*sqrt(pow(x5+x6*t1,2)-pow(x7+x8*t1,2));
  694. p0.y=y1-y2-y3*t1-m1*y4*sqrt(pow(y5+y6*t1,2)-pow(y7+y8*t1,2));
  695. p0.z = 0.0;
  696. for(tm = t1*m1; t2*m2-tm>=ZERO;tm+=tstep)
  697. {
  698. p1.x=x1-x2-x3*(tm+tstep)*m1+m1*x4*sqrt(pow(x5+x6*(tm+tstep)*m1,2)-pow(x7+x8*(tm+tstep)*m1,2));
  699. p1.y=y1-y2-y3*(tm+tstep)*m1-m1*y4*sqrt(pow(y5+y6*(tm+tstep)*m1,2)-pow(y7+y8*(tm+tstep)*m1,2));
  700. p1.z = 0.0;
  701. line->p0 = p0;
  702. line->p1 = p1;
  703. p0 = p1;
  704. cur=SaveLine(line);
  705. cur->color = color;
  706. CaxDrawCurvecmp(cur);
  707. cur = NULL;
  708. //CaxDrawLine(line);
  709. line=NULL;
  710. line= MallocLine();
  711. }
  712. }
  713. else if(m1 != m2)
  714. {
  715. tstep = (t1-tmin)/3;
  716. detax0 = pow(x5+x6*tmin,2)-pow(x7+x8*tmin,2);
  717. if(detax0 <= ZERO)
  718. detax0 = 0;
  719. else detax0 = sqrt(detax0);
  720. detay0 = pow(y5+y6*tmin,2)-pow(y7+y8*tmin,2);
  721. if(detay0 <= ZERO)
  722. detay0 = 0;
  723. else detay0 = sqrt(detay0);
  724. p0.x=x1-x2-x3*tmin+x4*detax0;
  725. p0.y=y1-y2-y3*tmin-y4*detay0;
  726. for(tm = tmin;t1-tm>ZERO;tm+=tstep)
  727. {
  728. detax = pow(x5+x6*(tm+tstep),2)-pow(x7+x8*(tm+tstep),2);
  729. if(detax <= ZERO)
  730. detax = 0;
  731. else detax = sqrt(detax);
  732. detay = pow(x5+x6*(tm+tstep),2)-pow(x7+x8*(tm+tstep),2);
  733. if(detay <= ZERO)
  734. detay = 0;
  735. else detay = sqrt(detay);
  736. p1.x=x1-x2-x3*(tm+STEP)+m1*x4*detax;
  737. p1.y=y1-y2-y3*(tm+STEP)-m1*y4*detay;
  738. line->p0 = p0;
  739. line->p1 = p1;
  740. p0 = p1;
  741. //
  742. cur = SaveLine(line);
  743. cur->color = color;
  744. CaxDrawCurvecmp(cur);
  745. cur = NULL;
  746. //
  747. line=NULL;
  748. line= MallocLine();
  749. }
  750. tstep = (t2-tmin)/3;
  751. p0.x=x1-x2-x3*tmin+x4*detax0;
  752. p0.y=y1-y2-y3*tmin-y4*detay0;
  753. for(tm = tmin;t2-tm>ZERO;tm+=tstep)
  754. {
  755. detax = pow(x5+x6*(tm+tstep),2)-pow(x7+x8*(tm+tstep),2);
  756. if(detax <= ZERO)
  757. detax = 0;
  758. else detax = sqrt(detax);
  759. detay = pow(x5+x6*(tm+tstep),2)-pow(x7+x8*(tm+tstep),2);
  760. if(detay <= ZERO)
  761. detay = 0;
  762. else
  763. detay = sqrt(detay);
  764. p1.x=x1-x2-x3*(tm+tstep)+m2*x4*detax;
  765. p1.y=y1-y2-y3*(tm+tstep)-m2*y4*detay;
  766. line->p0 = p0;
  767. line->p1 = p1;
  768. p0 = p1;
  769. //
  770. cur = SaveLine(line);
  771. cur->color = color;
  772. CaxDrawCurvecmp(cur);
  773. cur = NULL;
  774. //
  775. line=NULL;
  776. line= MallocLine();
  777. }
  778. }
  779. break;
  780. default:
  781. ASSERT(0);
  782. break;
  783. }
  784. return;
  785. }
  786. void  vdisplayvoronoi(VCNBL cn)
  787. {
  788. PVBNS  bi=NULL;
  789. PVBLI  bil=NULL;
  790. PVCNBL tmnode=NULL;
  791. tmnode = &cn;
  792. int color=RGB(255,0,0);
  793. int colorstep = 20;
  794. do{
  795. color += colorstep;
  796. bil = tmnode->bli;
  797. do{
  798. bi = bil->bni->bns;
  799. vdisplaysinglebi(*bi,color);
  800. bil = bil->last;
  801. }while(bil);
  802. tmnode = tmnode->ccw;
  803. }while(tmnode!=&cn);
  804. return;
  805. }
  806. void vdisplayplv(VPL pl)
  807. {
  808. PVCNBL cnbls,cnble,cnbl;
  809. PVBLI  bli;
  810. PVBNS  bns;
  811. cnbl = cnbls = pl.splf->scnbl;
  812. cnble = pl.eplf->ecnbl;
  813. int colorstep = 20;
  814. while(cnbl!=NULL&&cnbl!=cnble)
  815. {
  816. bli = cnbl->bli;
  817. while(bli!=NULL)
  818. {
  819. if(bli->bni->flag==1);
  820. else{
  821. bns = bli->bni->bns;
  822. vdisplaysinglebi(*bns,RGB(200,0,200)+myflag*colorstep);
  823. //AfxMessageBox("2");
  824. bli->bni->flag =1;
  825. bli=bli->next;
  826. }
  827. }
  828. cnbl = cnbl->ccw;
  829. }
  830. if(cnbl==cnble)
  831. {
  832. bli = cnbl->bli;
  833. while(bli!=NULL)
  834. {
  835. if(bli->bni->flag==1);
  836. else{
  837. bns = bli->bni->bns;
  838. vdisplaysinglebi(*bns,RGB(200,0,200));
  839. bli->bni->flag =1;
  840. bli=bli->next;
  841. }
  842. }
  843. }
  844. cnbl = pl.splf->scnbl;
  845. do
  846. {
  847. bli = cnbl->bli;
  848. while(bli!=NULL)
  849. {
  850. bli->bni->flag =0;
  851. bli=bli->next;
  852. }
  853. cnbl = cnbl->ccw;
  854. }while(cnbl!=NULL&&cnbl!=cnble);
  855. if(cnbl!=NULL)
  856. {
  857. bli = cnbl->bli;
  858. while(bli!=NULL)
  859. {
  860. bli->bni->flag =0;
  861. bli=bli->next;
  862. }
  863. cnbl = cnbl->ccw;
  864. }
  865. }
  866. //////////........................................................
  867. //first we assume that the t1,t2 >=0;
  868. //if return 1 means the first is to the left of t2,m1t1 < m2t2
  869. // 2,vias
  870. //0 means m1t1==m2t2;
  871. int vcompareright(int m1,double t1,int m2,double t2)
  872. {
  873. double tm1,tm2;
  874. tm1 = m1*t1;
  875. tm2 = m2*t2;
  876. if(fabs(tm1-tm2)<=ZERO)
  877. return 0;
  878. else if(tm1-tm2>ZERO)
  879. return 2;
  880. else if(tm1-tm2<-ZERO)
  881. return 1;
  882. }
  883. //find the value of the line direction
  884. void vfindvectorinpositive(PVBNS bns,int m,double t,PXYZ *p)
  885. {//as for the CCP I assume that the p is head for alph adding direction
  886. ASSERT(bns);
  887. PXYZ pp = NULL;
  888. double x1,x0,y1,y0,deta,detax,detay;
  889. if(LLP == bns->bitype)
  890. {
  891. pp = new XYZ;
  892. if(m>0){
  893. pp->x =  bns->x2;
  894. pp->x = -bns->x1;
  895. }
  896. else{
  897. pp->x = -bns->x2;
  898. pp->y =  bns->x1;
  899. }
  900. *p = pp;
  901. }
  902. else if (CCP == bns->bitype)
  903. {
  904. pp = new XYZ;
  905. pp->x = cos(t*m + PI/2);
  906. pp->y = sin(t*m + PI/2);
  907. *p = pp;
  908. }
  909. else if (LL == bns->bitype)
  910. {
  911. pp = new XYZ;
  912. pp->x =  -bns->x3;
  913. pp->y =  -bns->y3;
  914. pp->z =   0;
  915. *p = pp;
  916. }
  917. else if (LC == bns->bitype || CC == bns->bitype)
  918. {
  919. deta = pow(bns->x5 + bns->x6*t,2) - pow(bns->x7 + bns->x8*t,2);
  920. if(deta<-ZERO)ASSERT(0);
  921. if(fabs(deta)<=ZERO){
  922. x0 = -bns->x3; x1 = 0;
  923. y0 = -bns->y3; y1 = 0;
  924. }
  925. else
  926. {
  927. detax = m*bns->x4/sqrt(deta);
  928. x0 = detax*(bns->x5*bns->x6 - bns->x7*bns->x8) - bns->x3;
  929. x1 =  detax*(bns->x6*bns->x6 - bns->x8*bns->x8);
  930. deta = pow(bns->y5 + bns->y6*t,2) - pow(bns->y7 + bns->y8*t,2);//can be deleted safely
  931. detay = -m*bns->y4/sqrt(deta);
  932. y0 = detay*(bns->y5*bns->y6 - bns->y7*bns->y8) - bns->y3;
  933. y1 = detay*(bns->y6*bns->y6 - bns->y8*bns->y8);//please pay attention
  934. }
  935. pp = new XYZ;
  936. pp->x = x0 + t*x1;
  937. pp->y = y0 + t*y1;
  938. pp->z = 0;
  939. *p = pp;
  940. }
  941. }
  942. //I do not know whether this function if ture
  943. //m is the m of bns
  944. int vfinddirection(PVBLI bli,PVBNS bns,double t,int m)
  945. {//t and m is the intersect point of between bli->bni->bns and bns
  946. ASSERT(bns);
  947. PXYZ  pa,pb;
  948. int mm;//mm is the m of bli->bni->bns; 
  949. double tm;
  950. double tt = t;
  951. vfindvectorinpositive(bns,m,tt,&pa);
  952. //
  953. vgainintersectmvaluebns(bli->bni->bns,bns,&tt,m,&mm);
  954. vfindvectorinpositive(bli->bni->bns,mm,tt,&pb);//we know that we must find all the information of bli
  955. tm = vmultiplayvector(pb,pa);
  956. //
  957. tm = tm*m*mm*bli->clockwise;//this if the critical judgement
  958. delete pa;
  959. delete pb;
  960. if(tm>=0)//==0 means parallel if so ,there will no intersect in funture caculation 
  961. {
  962. return CCW;//this mean the t*m >tfirst*mfirst is validative
  963. }
  964. else
  965. {
  966. return CW;//otherwise mean the t*m behand the tfirst*mfirst if validative
  967. }
  968. }
  969. //find the overlaps of m1t1-m2t2 and m3r3-m4t4;
  970. //if return 0,no overlaps;
  971. //if return 1,only one point overlaps;
  972. //if return 2,have segemented overlaps;
  973. int  vcomparerights(int m1,double t1, int m2,double t2, //input
  974. int m3,double t3, int m4,double t4, //input
  975. int *mm1,double *tt1,
  976. int *mm2,double *tt2)
  977. {//I think it will be ok.
  978. int m;
  979. double t;
  980. double tm1,tm2,tm3,tm4;
  981. tm1 = m1*t1; tm2 = m2*t2; tm3 = m3*t3;tm4 = m4*t4;
  982. if(tm1-tm2>ZERO)
  983. {
  984. m=m1; t=t1;
  985. m1=m2; t1=t2;
  986. m2=m; t2=t;
  987. }
  988. if(tm3-tm4>ZERO)
  989. {
  990. m=m3; t=t3;
  991. m3=m4; t3=t4;
  992. m4=m; t4=t;
  993. }
  994. //
  995. if((tm1 >m4*t4)||(tm3 > tm2))
  996. return 0;
  997. //
  998. if(fabs(tm1-tm2)<ZERO)
  999. {
  1000. if(tm1>=tm3&&tm1<=tm4)
  1001. {
  1002. *mm1=*mm2=m1;
  1003. *tt1=*tt2=t1;
  1004. return 1;
  1005. }    
  1006. else return 0;
  1007. }
  1008. if(fabs(tm3-tm4)<ZERO)
  1009. {
  1010. if(tm3>=tm1&&tm3<=tm2)
  1011. {
  1012. *mm1=*mm2=m3;
  1013. *tt1=*tt2=t3;
  1014. return 1;
  1015. }    
  1016. else return 0;
  1017. }
  1018. //
  1019. if(tm1 >= tm3 && tm1 <= tm4)
  1020. {
  1021. *tt1 = t1; *mm1 = m1;
  1022. if(m2*t2 >= m4*t4)
  1023. {
  1024. *tt2 = t4;*mm2= m4;
  1025. }
  1026. else if(m2*t2 < m4*t4)
  1027. {
  1028. *tt2 = t2;*mm2= m2;
  1029. }
  1030. return 2;
  1031. }
  1032. else if(tm1 < tm3)
  1033. {
  1034. *tt1=t3; *mm1=m3;
  1035. if(tm2 >= tm4)
  1036. {
  1037. *tt2 = t4;*mm2= m4;
  1038. }
  1039. else if(tm2 >= tm3)
  1040. {
  1041. *tt2 = t2;*mm2= m2;
  1042. }
  1043. return 2;
  1044. }
  1045. }
  1046. void  vgetparaline(PLINE l,double *a,double *b,double *c)
  1047. {
  1048. ASSERT(l);
  1049. double x0,y0,x1,y1;
  1050. double delt;
  1051. x0 = l->p0.x; y0 = l->p0.y;
  1052. x1 = l->p1.x; y1 = l->p1.y;
  1053. if(fabs(x1-x0)<ZERO)*b=0;else *b=x1-x0;
  1054. if(fabs(y1-y0)<ZERO)*a=0;else *a=y0-y1;
  1055. ASSERT(0!=*a||0!=*b);
  1056. delt = sqrt(pow(*a,2)+pow(*b,2));
  1057. *a = *a/delt;*b = *b/delt;
  1058. *c = ((y1-y0)*x0-y0*(x1-x0))/delt;
  1059. return;
  1060. }
  1061. PXYZ  vgetintersectpoint(VBNS bi,double t,int m)
  1062. {
  1063. PXYZ p=new XYZ;
  1064. if(bi.bitype==LL)
  1065. {
  1066. p->x = bi.x1-bi.x2-bi.x3*t;
  1067.         p->y = bi.y1-bi.y2-bi.y3*t;
  1068. p->z = 0.0;
  1069. }
  1070. else
  1071. {
  1072. p->x=bi.x1-bi.x2-bi.x3*t+m*bi.x4*sqrt(pow(bi.x5+bi.x6*t,2)-pow(bi.x7+bi.x8*t,2));
  1073. p->y=bi.y1-bi.y2-bi.y3*t-m*bi.y4*sqrt(pow(bi.y5+bi.y6*t,2)-pow(bi.y7+bi.y8*t,2));
  1074. p->z=0;
  1075. }
  1076. return p;
  1077. }
  1078. //find resultion of ax2+bx+c=0;
  1079. void  vgetvalue(double a,double b,double c,double t[2],int *i)
  1080. {
  1081. double deta;
  1082. if(fabs(a)<ZERO){
  1083. ASSERT(fabs(b)>ZERO);
  1084. if(fabs(b)<ZERO){
  1085. *i=0;
  1086. }
  1087. else{
  1088. t[0]=-c/b;
  1089. *i=1;
  1090. }
  1091. }
  1092. else if(fabs(b)<ZERO)
  1093. {
  1094. ASSERT(fabs(a)>ZERO);
  1095.         if(fabs(c)<ZERO){
  1096. *i=1;
  1097. t[0]=0;
  1098. }
  1099. else if(c<-ZERO){
  1100. *i=0;
  1101. }
  1102. else {
  1103. *i=2;
  1104. t[0]=sqrt(c);
  1105. t[1]=-sqrt(c);
  1106. }
  1107. }
  1108. else
  1109. {
  1110. deta=b*b-4*a*c;
  1111. if(deta<-ZERO){
  1112. *i=0;
  1113. t[0]=0;
  1114. }
  1115. else if(fabs(deta)<ZERO)
  1116. {
  1117. *i=1;
  1118. t[0]=-b/2/a;
  1119. }
  1120. else 
  1121. {
  1122. *i=2;
  1123. t[0]=(-b+sqrt(deta))/2/a;
  1124. t[1]=(-b-sqrt(deta))/2/a;
  1125. }
  1126. }
  1127. return;
  1128. }
  1129. //find the  validate areas;
  1130. void vgettminandtmaxvalue( double a,double b,double c,double t[4],int *i )
  1131. {//i=0 ,mean no area,1 mean 1area,2 mean,two area
  1132. double deta,o,p;
  1133. double tt[2];
  1134. if(fabs(a)<=ZERO)
  1135. {
  1136. if(fabs(b)<=ZERO){
  1137. if(c>=-ZERO){*i = 1;t[0] = 0;t[1] = UPER;}
  1138. else *i = 0;
  1139. }
  1140. else if( b<-ZERO )
  1141. {
  1142. if(fabs(-c/b)<=0) *i = 0;
  1143. else{
  1144. *i = 1;
  1145. t[0] = 0;t[1] = -c/b;
  1146. }
  1147. }
  1148. else
  1149. {
  1150. *i = 1;
  1151. t[1] = UPER;
  1152. if(-c/b>=0)
  1153. t[0] = -c/b;
  1154. else t[0] =0;
  1155. return;
  1156. }
  1157. }
  1158. else{
  1159. deta = b*b-4*a*c;
  1160. if(a>ZERO)
  1161. {
  1162. if(deta<=0){*i=1;t[0]=-UPER;t[1] = UPER;}
  1163. else{
  1164. o = (-b-sqrt(deta))/(2*a);p = (-b+sqrt(deta))/(2*a);
  1165. if(o>=0){*i = 2;t[0]=0;t[1] = o;t[2]=p,t[3] = UPER;}
  1166. else if(p>=0){*i=1;t[0] = p;t[1] =UPER;}
  1167. else if(p<0) {*i=1;t[0] = 0;t[1] =UPER;}
  1168. }
  1169. }
  1170. else if(a<-ZERO)
  1171. {
  1172. if(deta<=0){*i=0;}
  1173. else{
  1174. o = (-b-sqrt(deta))/(2*a);p = (-b+sqrt(deta))/(2*a);
  1175. if(o>=0){*i = 1;t[0]=o;t[1] = p;}
  1176. else if(o<0&&p>=0){*i=1;t[0] = 0;t[1] = p;}
  1177. else if(p<0) {*i=0;}
  1178. }
  1179. }
  1180. }
  1181. return;
  1182. }
  1183. //gain a b c&t ;
  1184. void  vgetllimit(PVCNS cn,double *a,double *b,double *c,double *t)
  1185. {
  1186. ASSERT(cn);
  1187. ASSERT(cn->type==0);
  1188. double x0,y0,x1,y1;
  1189. double delt;
  1190. XYZ p0,p1;
  1191. if(0==cn->clockwise){
  1192. p0 = cn->element.line->p0;
  1193. p1 = cn->element.line->p1;
  1194. }
  1195. else if(1==cn->clockwise){
  1196. p1 = cn->element.line->p0;
  1197. p0 = cn->element.line->p1;
  1198. }
  1199. x0 = p0.x;y0 = p0.y;
  1200. x1 = p1.x;y1 = p1.y;
  1201. if(fabs(x1-x0)<ZERO)*a=0;else *a=x1-x0;
  1202. if(fabs(y1-y0)<ZERO)*b=0;else *b=y1-y0;
  1203. ASSERT(0!=*a&&0!=*b);
  1204. delt = sqrt(pow(*a,2)+pow(*b,2));
  1205. *a = *a/delt;
  1206. *b = *b/delt;
  1207. *c = -((y1-y0)*y0+x0*(x1-x0))/delt;
  1208. *t = 0;
  1209. return;
  1210. }
  1211. void  vgetcflimit(PVCNS cn,double *a,double *b,double *c,double *t)
  1212. {
  1213. ASSERT(cn);
  1214. ASSERT(cn->element.arc);
  1215. PLINE line;
  1216. // XYZ pt,du,duu,dn;
  1217. // GeneratorArcAllValue(cn->element.arc,0.5,&pt,&du,&duu,&dn);
  1218. line->p0=cn->element.arc->pc;
  1219. line->p1=cn->element.arc->px;
  1220. vgetparaline(line,a,b,c);
  1221. *t = cn->element.arc->r;
  1222. return;
  1223. }
  1224. void  vgetcslimit(PVCNS cn,double *a,double *b,double *c,double *t)
  1225. {
  1226. ASSERT(cn);
  1227. ASSERT(cn->element.arc);
  1228. PLINE line;
  1229. line->p0=cn->element.arc->pc;
  1230. line->p1=cn->element.arc->px;
  1231. vgetparaline(line,a,b,c);
  1232. *t = cn->element.arc->r;
  1233. return;
  1234. }
  1235. //
  1236. void  vgainbisectorll(PVCNS l1, PVCNS l2, PVBNS *bi)//ok
  1237. {
  1238. ASSERT(l1);ASSERT(l2);ASSERT(CAXLINE==l1->type);ASSERT(CAXLINE==l2->type);
  1239. PVBNS  bt = NULL;
  1240. *bi = NULL;
  1241. XYZ p0,p1;
  1242. double a1,b1,c1;
  1243. double a2,b2,c2;
  1244. double deta;
  1245. int    m1,m2;
  1246. if(CCW == l1->clockwise)m1 = -1;
  1247. else m1 = 1;
  1248. if(CCW == l2->clockwise)m2 = -1;
  1249. else m2 = 1;
  1250. vgetparaline(l1->element.line,&a1,&b1,&c1);
  1251. vgetparaline(l2->element.line,&a2,&b2,&c2);
  1252. deta = a1*b2 - b1*a2;
  1253. if(fabs(deta)<=ZERO)//处理平行线
  1254. {//Anyway the same line have bisector too; 
  1255. ASSERT(0);//kill it afterwards
  1256. double tmtemp;
  1257. if(m1 == m2) return;
  1258. tmtemp = (c2-c1)/(m1-m2);
  1259. if(tmtemp<-ZERO) return;//we must be sure of the positive of integret
  1260. bt = vmallocbns();
  1261. bt->bitype = LLP;
  1262. bt->tmin = bt->tmax = tmtemp;
  1263. bt->x1 = a1;
  1264. bt->x2 = b1;
  1265. bt->x3 = c1 + m1*bt->tmin;//一般方程a**2+b**2 = 1;
  1266. bt->x4 = l1->element.line->p0.x + a1 * m1*tmtemp;
  1267. bt->y4 = l1->element.line->p0.y + b1 * m1*tmtemp;//find the first point
  1268. *bi = bt;
  1269. //以下对t1,t2赋值
  1270. return;
  1271. }//below 为平分线赋值
  1272. bt = vmallocbns();
  1273.     bt->x1 = (b1*c2-b2*c1)/deta;
  1274.     bt->x3 =-(b1*m2-b2*m1)/deta;
  1275.     bt->y1 = (a2*c1-a1*c2)/deta;
  1276.     bt->y3 =-(a2*m1-a1*m2)/deta;
  1277. bt->bitype = LL;
  1278. bt->infinite = INFINITY;
  1279. //以下对t1,t2赋值
  1280. bt->t1 = 0;
  1281. bt->t2 = UPER;
  1282. bt->m1=1;
  1283. bt->m2=1;
  1284. *bi = bt;
  1285. return ;
  1286. }
  1287. void  vgainbisectorlc(PVCNS l1, PVCNS cc2, PVBNS *bi)
  1288. {
  1289. ASSERT(l1);ASSERT(cc2);ASSERT(CAXARC==cc2->type);ASSERT(CAXLINE==l1->type);
  1290. double xc1,yc1,r1,a2,b2,c2;
  1291. double h,m1,m2;
  1292. double aa,bb,cc,tt[4];
  1293. int    iflag;
  1294. vgetparaline(l1->element.line,&a2,&b2,&c2);
  1295. if(CCW==cc2->clockwise)m1 = 1;
  1296. else m1 = -1;
  1297. if(CCW==l1->clockwise)m2 = -1;
  1298. else m2 = 1;
  1299. // GeneratorArcAllValue(c2->element.arc,1.0,&pt,&du,&duu,&dn);
  1300. xc1=cc2->element.arc->pc.x;
  1301. yc1=cc2->element.arc->pc.y;
  1302. r1 =cc2->element.arc->r;
  1304. h = a2*xc1 + b2*yc1 + c2; 
  1305. PVBNS bt = vmallocbns();
  1306.     //x1-x2-x3*t+x4*sqrt((x5+x6*t)**2-(x7+x8*t)**2);
  1307. bt->x1=xc1;   bt->x2=a2*h;  bt->x3=m2*a2;   bt->x4=b2;  bt->x5=r1;
  1308. bt->x6=m1;    bt->x7=h;     bt->x8=m2;
  1309. bt->y1=yc1;   bt->y2=b2*h;  bt->y3=m2*b2;   bt->y4=a2;  bt->y5=r1;
  1310. bt->y6=m1;    bt->y7=h;     bt->y8=m2;
  1312. bt->m1 = -1;
  1313. bt->m2 = 1;
  1314. //left out for later processing
  1315. /* aa = bt->x6*bt->x6 - bt->x8*bt->x8;
  1316. bb = 2*(bt->x5*bt->x6 - bt->x7*bt->x8);
  1317. cc = bt->x5*bt->x5 - bt->x7*bt->x7;
  1318. vgettminandtmaxvalue(aa,bb,cc,tt,&iflag);
  1319. if(iflag == 1)*/
  1320. //////////assign tmin;
  1321. aa = h*h-r1*r1;//t(2r1m1-2hm2)>=h**2-r1**2;
  1322. bb = 2*(r1*m1-h*m2);
  1323. if(fabs(bb)<=ZERO)
  1324. {
  1325. if(aa<=ZERO)bt->tmin = 0;
  1326. else ASSERT(0);
  1327. }
  1328. else if(bb<-ZERO)
  1329. {
  1330. if(aa/bb>ZERO){bt->tmin = 0;bt->tmax = aa/bb;}
  1331. else ASSERT(0);
  1332. }
  1333. else if(bb>ZERO)
  1334. {
  1335. if(aa<=ZERO)
  1336. bt->tmin = 0;
  1337. else {
  1338. bt->tmin = aa/bb ; 
  1339. }
  1340. }
  1341. //上面可以不要
  1342. bt->t1 = UPER;
  1343. bt->t2 = UPER;
  1344. bt->m1 = -1;
  1345. bt->m2 =  1;
  1346. bt->bitype = LC;
  1347. bt->infinite = INFINITY;
  1348. *bi = bt;
  1349. return;
  1350. }
  1351. void  vgainbisectorcc(PVCNS c1, PVCNS c2, PVBNS *bi)
  1352. {
  1353. ASSERT(c1);ASSERT(c2);ASSERT(CAXARC==c1->type);ASSERT(CAXARC==c2->type);
  1354. double xc1,yc1,r1,xc2,yc2,r2;
  1355. double h,m1,m2;
  1356. double deta,dx,dy,d;
  1358. xc1=c1->element.arc->pc.x;  xc2=c2->element.arc->pc.x;
  1359. yc1=c1->element.arc->pc.y;  yc2=c2->element.arc->pc.y;
  1360. r1 =c1->element.arc->r;     r2 =c2->element.arc->r;
  1361. if(CCW==c1->clockwise)m1 = 1;
  1362. else m1 = -1;
  1363. if(CCW==c2->clockwise)m2 = 1;
  1364. else m2 = -1;
  1365. // ASSERT(pow(xc1-xc2)+pow(yc1-yc2)>ZERO);
  1366. if(pow(xc1-xc2,2) + pow(yc1-yc2,2)<=ZERO)//同心处理
  1367. {
  1368. ASSERT(0);
  1369. double t;
  1370. if(m1 == m2)
  1371. {
  1372. t = -(r1+r2)/(m2+m1);
  1373. if(t<-ZERO)
  1374. {
  1375. *bi = NULL;
  1376. return;
  1377. }
  1378. }
  1379. else if(fabs(m1+m2)<=ZERO)
  1380. {
  1381. t = (r1-r2)/(m2-m1);
  1382. if(t<-ZERO){
  1383. *bi = NULL;
  1384. return;
  1385. }
  1386. }
  1387. PVBNS bt = vmallocbns();
  1388. bt->bitype = CCP;//标识同心
  1389. bt->x1 = (xc1 - xc2)/2;//圆心
  1390. bt->y1 = (yc1 - yc2)/2;//圆心
  1391. bt->x2 = m1*t + r1;//半径
  1392. bt->infinite = 1;
  1393. *bi = bt;
  1394. return;
  1395. }//below non同心处理
  1396. // if(m1*m2<0)
  1397. // {
  1398. // }//圆包含处理#
  1399. PVBNS bt = vmallocbns();
  1400. //
  1401. d=sqrt(pow(xc1-xc2,2)+pow(yc1-yc2,2));
  1402. dx=(xc2-xc1)/d;dy=(yc2-yc1)/d;
  1403. deta=(m2*r2-m1*r1)/d;
  1404. h=(r2*r2-r1*r1-d*d)/2/d;
  1405. //
  1406. bt->x1=xc1;  bt->x2=dx*h;  bt->x3=dx*deta;  bt->x4=dy;  bt->x5=r1;
  1407. bt->x6=m1;   bt->x7=h;     bt->x8=(r2*m2-r1*m1)/d;
  1408. bt->y1=yc1;  bt->y2=dy*h;  bt->y3=dy*deta;  bt->y4=dx;  bt->y5=r1;
  1409. bt->y6=m1;   bt->y7=h;     bt->y8=(r2*m2-r1*m1)/d;
  1411.     // bt->t0 = (d-r1*m1-r2*m2)/2;
  1412. //assign the tmin and the tmax;
  1413. deta = r1*m1-h*bt->y8;
  1414. if(fabs(deta)<ZERO)
  1415. {
  1416. bt->tmin = 0;
  1417. }
  1418. else if(deta<-ZERO)
  1419. {
  1420. bt->tmin=(r1*r1-bt->x8*bt->x8)/2/(bt->x5*bt->x6-bt->x7*bt->x8);
  1421. bt->limit=1;
  1422. }
  1423. else 
  1424. {
  1425. bt->tmin=(r1*r1-bt->x8*bt->x8)/2/(bt->x5*bt->x6-bt->x7*bt->x8);
  1426. bt->limit=0;
  1427. }
  1428. bt->tmin = 0;
  1429. bt->tmax = UPER;
  1430. //不要不要了，酸什么TMIN和TMAX了，去掉去掉
  1431. bt->bitype = CC;
  1432. bt->infinite = INFINITY;
  1433. bt->t1 = UPER;
  1434. bt->t2 = UPER;
  1435. bt->m1 = -1;
  1436. bt->m2 =  1;
  1437. *bi=bt;
  1438. return;
  1439. }
  1440. void  vgainbisector(PVCNS c1, PVCNS c2, PVBNS *bi)
  1441. {
  1442. PVBNS bt;
  1443. if(CAXLINE==c1->type)
  1444. {
  1445. if(CAXLINE==c2->type)
  1446. vgainbisectorll(c1,c2,&bt);
  1447. else if(CAXARC==c2->type)
  1448. vgainbisectorlc(c1,c2,&bt);
  1449. }
  1450. else if(CAXARC==c1->type)
  1451. {
  1452. if(CAXLINE==c2->type)
  1453. vgainbisectorlc(c2,c1,&bt);
  1454. else if(CAXARC==c2->type)
  1455. vgainbisectorcc(c1,c2,&bt);
  1456. }
  1457. *bi = bt;
  1458. }
  1459. //gain the the point of line line line intersect
  1460. //bisector l1&l2 intersect bisector l1&l3
  1461. //it have been ok but need text for further use
  1462. void vgainintersectlll(PVCNS l1,PVCNS l2,PVCNS l3,int *i,double t[2])
  1463. {
  1464. ASSERT(l1);ASSERT(l2);ASSERT(l3);
  1465. ASSERT(CAXLINE==l1->type);
  1466. ASSERT(CAXLINE==l2->type);ASSERT(CAXLINE==l3->type);
  1467. double a1,b1,c1,a2,b2,c2,a3,b3,c3;
  1468. double x0,y0;
  1469. double deta;
  1470. int m1,m2,m3;
  1471. vgetparaline(l1->element.line,&a1,&b1,&c1);
  1472. vgetparaline(l2->element.line,&a2,&b2,&c2);
  1473. vgetparaline(l3->element.line,&a3,&b3,&c3);
  1474. if(CCW == l1->clockwise)m1 = -1;
  1475. else m1 = 1;
  1476. if(CCW == l2->clockwise)m2 = -1;
  1477. else m2 = 1;
  1478. if(CCW == l3->clockwise)m3 = -1;
  1479. else m3 = 1;
  1480. deta = (m1*b1-m3*b3)*(a1*m1-a2*m2)-(b1*m1-b2*m2)*(a1*m1-a3*m3);
  1481. if(fabs(deta)<ZERO)//two line is parallel;//no it is two bisector parallel
  1482. {
  1483. ASSERT(0);    //if have only two line parallel,deta will not be zero 
  1484. *i=0;   //there are not intersect points
  1485. t[0] = UPER;
  1486. return;       //to be simple it is no intersector
  1487. }
  1488. x0 = (b1*m2-b2*m1)*(c1*m3-c3*m1) - (b1*m3-b3*m1)*(c1*m2-c2*m1);
  1489. y0 = (a1*m2-a2*m1)*(c1*m3-c3*m1) - (a1*m3-a3*m1)*(c1*m2-c2*m1);
  1490. x0 =  x0/deta;
  1491. y0 = -y0/deta;
  1492. t[0] = m1*(-a1*x0-b1*y0-c1);
  1493. *i = 1;
  1494.     return;
  1495. }
  1496. //i=0,1,or 2;
  1497. void vgainintersectllc(PVCNS l1,PVCNS l2,PVCNS c3,int *i,double t[2])
  1498. {
  1499. ASSERT(l1);ASSERT(l2);ASSERT(c3);
  1500. ASSERT(CAXLINE==l1->type);
  1501. ASSERT(CAXLINE==l2->type);ASSERT(CAXARC==c3->type);
  1502. //
  1503. double a1,b1,c1,a2,b2,c2,xc3,yc3,r3;
  1504. double a,b,c,deta,x0,x1,y0,y1;
  1505. int m1,m2,m3;
  1506. PVBNS bns = NULL;
  1507. double dtemp;
  1508. //double tt[2];//template uesed
  1510. vgetparaline(l1->element.line,&a1,&b1,&c1);
  1511. vgetparaline(l2->element.line,&a2,&b2,&c2);
  1512. xc3=c3->element.arc->pc.x;
  1513. yc3=c3->element.arc->pc.y;
  1514. r3=c3->element.arc->r;
  1515. if(CCW==l1->clockwise)m1 = -1;
  1516. else m1 = 1;
  1517. if(CCW==l2->clockwise)m2 = -1;
  1518. else m2 = 1;
  1519. if(CCW==c3->clockwise)m3 = 1;
  1520. else m3 = -1;
  1521. deta = a1*b2-b1*a2;
  1522. if(fabs(deta)<=ZERO)// two parallel  line left for later write
  1523. {
  1524. double ta;
  1525. if(m1 == m2)
  1526. {
  1527. *i = 0;
  1528. return;
  1529. }
  1530. //
  1531. ta = (c2-c1)/(m1-m2);
  1532. //t is minor than zero is unbearable so kick it out without mercy
  1533. if(ta<=-ZERO){
  1534. *i = 0;
  1535. return;
  1536. }
  1537. else
  1538. {
  1539. vgainbisectorlc(l1,c3,&bns);
  1540. dtemp = (bns->x5 + bns->x6*ta)*(bns->x5 + bns->x6*ta) -
  1541. (bns->x7 + bns->x8*ta)*(bns->x7 + bns->x8*ta);
  1542. delete bns; bns = NULL;
  1543. if(dtemp<-ZERO){
  1544. *i=0;
  1545. }
  1546. else{
  1547. *i = 1;
  1548. t[0] = t[1] = ta;
  1549. }
  1550. return;//if
  1551. }
  1552. //
  1553. /* tt = a1*xc3 + b1*yc3 + (c1+m1*ta);//tt is the distance between the center of circle and the line.
  1554. if(fabs(tt)-(r3+m3*ta)<=ZERO)
  1555. {
  1556. *i = 1;
  1557. t[0] = ta;
  1558. }
  1559. else if(fabs(tt)-(r3+m3*ta)>ZERO)
  1560. {
  1561. *i = 0;
  1562. }
  1563. //ASSERT(0);
  1564. AfxMessageBox("sorry but I find two duplicit lines");
  1565. return;   */
  1566. }
  1567. x0 = (b1*c2-b2*c1)/deta;
  1568. x1 = (m2*b1-b2*m1)/deta;
  1569. y0 =-(a1*c2-a2*c1)/deta;
  1570. y1 =-(a1*m2-a2*m1)/deta;
  1571.  
  1572. a=x1*x1+y1*y1-1;
  1573. b=2*(x1*(x0-xc3)+y1*(y0-yc3)-r3*m3);
  1574. c=(x0-xc3)*(x0-xc3)+(y0-yc3)*(y0-yc3)-r3*r3;
  1576. vgetvalue(a,b,c,t,i);
  1577. if(*i == 1 && t[0]<-ZERO)
  1578. {
  1579. *i = 0 ;
  1580. }
  1581. if(*i == 2)
  1582. {
  1583. if(t[0]<-ZERO&&t[1]<-ZERO){
  1584. *i = 0;
  1585. }
  1586. else if(t[0]>=-ZERO&&t[1]<-ZERO)
  1587. {
  1588. *i = 1;
  1589. }
  1590. else if (t[0]<-ZERO&&t[1]>=-ZERO)
  1591. {
  1592. *i = 1;
  1593. t[0] = t[1];
  1594. }
  1595. }
  1596. return ;
  1597. }
  1598. //i=0,1,or 2;
  1599. void  vgainintersectlcc(PVCNS l1,PVCNS cc2,PVCNS c3,int *i,double t[2])//
  1600. {
  1601. ASSERT(l1);ASSERT(cc2);ASSERT(c3);
  1602. ASSERT(CAXLINE==l1->type);
  1603. ASSERT(CAXARC==cc2->type);ASSERT(CAXARC==c3->type);
  1605. //
  1606. double a1,b1,c1,xc2,yc2,r2,xc3,yc3,r3;
  1607. double a2,b2,c2,m;
  1608. double a,b,c,deta,x0,x1,y0,y1;
  1609. int m1,m2,m3;
  1610. PVBNS bns= NULL;
  1611. double dtemp;
  1612. //double tt[2];//template uesed
  1614. vgetparaline(l1->element.line,&a1,&b1,&c1);
  1615. xc2 = cc2->element.arc->pc.x;
  1616. yc2 = cc2->element.arc->pc.y;
  1617. r2 = cc2->element.arc->r;
  1618. xc3 = c3->element.arc->pc.x;
  1619. yc3 = c3->element.arc->pc.y;
  1620. r3 = c3->element.arc->r;
  1621. if(CCW==l1->clockwise)m1 = -1;
  1622. else m1 = 1;
  1623. if(CCW==cc2->clockwise)m2 = 1;
  1624. else m2 = -1;
  1625. if(CCW==c3->clockwise)m3 = 1;
  1626. else m3 = -1;
  1627. m  = 2*(r3*m3-r2*m2);
  1628. a2 = 2*(xc3-xc2);
  1629. b2 = 2*(yc3-yc2);
  1630. c2 = xc2*xc2-xc3*xc3+yc2*yc2-yc3*yc3+r3*r3-r2*r2;
  1632. deta = a1*b2-b1*a2;
  1633. if(fabs(deta)<=ZERO)// two parallel  line left for later write
  1634. {//无解
  1635. *i = 0;
  1636. ASSERT(0);
  1637. return;
  1638. }
  1639. if(fabs(a2)<=ZERO && fabs(b2)<=ZERO)//the circle with the same center;
  1640. {
  1641. double ta;
  1642. if(m2 == m3)
  1643. {
  1644. *i = 0;
  1645. return;
  1646. }
  1647. //
  1648. ta = (r2-r3)/(m3-m2);
  1649. //t is minor than zero is unbearable so kick it out without mercy
  1650. if(ta<=-ZERO){
  1651. *i = 0;
  1652. return;
  1653. }
  1654. else 
  1655. {
  1656. vgainbisectorlc(l1,c3,&bns);
  1657. dtemp = (bns->x5 + bns->x6*ta)*(bns->x5 + bns->x6*ta) -
  1658. (bns->x7 + bns->x8*ta)*(bns->x7 + bns->x8*ta);
  1659. delete bns; bns = NULL;
  1660. if(dtemp<-ZERO){
  1661. *i=0;
  1662. }
  1663. else{
  1664. *i = 1;
  1665. t[0] = ta;
  1666. }
  1667. return;
  1668. }
  1669. }
  1670. x0 = (b1*c2-b2*c1)/deta;
  1671. x1 = (m*b1-b2*m1)/deta;
  1672. y0 =-(a1*c2-a2*c1)/deta;
  1673. y1 =-(a1*m-a2*m1)/deta;
  1674.  
  1675. a = x1*x1+y1*y1-1;
  1676. b = 2*(x1*(x0-xc3)+y1*(y0-yc3)-r3*m3);
  1677. c = (x0-xc3)*(x0-xc3)+(y0-yc3)*(y0-yc3)-r3*r3;
  1679. vgetvalue(a,b,c,t,i);
  1680. return ;
  1681. }
  1682. //i=0,1,or 2;//i!=2?
  1683. void vgainintersectccc(PVCNS c1,PVCNS c2,PVCNS c3,int *i,double t[2])
  1684. {
  1685. ASSERT(c1);ASSERT(c2);ASSERT(c3);
  1686. ASSERT(CAXARC==c1->type);
  1687. ASSERT(CAXARC==c2->type);ASSERT(CAXARC==c3->type);
  1688. //
  1689. double xc1,yc1,r1,xc2,yc2,r2,xc3,yc3,r3;
  1690. double a1,b1,cc1,mt1,mt2,a2,b2,cc2;
  1691. double a,b,c,deta,x0,x1,y0,y1;
  1692. int m1,m2,m3;
  1693. PVBNS bns=NULL;
  1694. double dtemp;
  1695. //double tt[2];//template uesed
  1697. xc1 = c1->element.arc->pc.x;
  1698. yc1 = c1->element.arc->pc.y;
  1699. r1 = c1->element.arc->r;
  1700. xc2 = c2->element.arc->pc.x;
  1701. yc2 = c2->element.arc->pc.y;
  1702. r2 = c2->element.arc->r;
  1703. xc3 = c3->element.arc->pc.x;
  1704. yc3 = c3->element.arc->pc.y;
  1705. r3 = c3->element.arc->r;
  1706. if(CCW==c1->clockwise)m1 = 1;
  1707. else m1 = -1;
  1708. if(CCW==c2->clockwise)m2 = 1;
  1709. else m2 = -1;
  1710. if(CCW==c3->clockwise)m3 = 1;
  1711. else m3 = -1;
  1712. mt1 = 2*(r1*m1-r2*m2);
  1713. a1  = 2*(xc1-xc2);
  1714. b1  = 2*(yc1-yc2);
  1715. cc1 = xc2*xc2-xc1*xc1+yc2*yc2-yc1*yc1+r1*r1-r2*r2;
  1717. mt2 = 2*(r1*m1-r3*m3);
  1718. a2  = 2*(xc1-xc3);
  1719. b2  = 2*(yc1-yc3);
  1720. cc2 = xc3*xc3-xc1*xc1+yc3*yc3-yc1*yc1+r1*r1-r3*r3;
  1721. if(fabs(a1)<=ZERO&&fabs(a2)<=ZERO&&fabs(b1)<=ZERO&&fabs(b2)<=ZERO)//三点同心
  1722. {
  1723. *i = 0;ASSERT(0);
  1724. return;
  1725. }
  1726. else if(fabs(a1)<=ZERO&&fabs(b1)<=ZERO)//两点同心
  1727. {
  1728. double ta;
  1729. if(m1 == m2)
  1730. {
  1731. *i = 0;
  1732. return;
  1733. }
  1734. ta = (r1-r2)/(m2-m1);
  1735. if(ta<=-ZERO){
  1736. *i = 0;
  1737. }
  1738. else 
  1739. {
  1740. vgainbisectorlc(c1,c3,&bns);
  1741. dtemp = (bns->x5 + bns->x6*ta)*(bns->x5 + bns->x6*ta) -
  1742. (bns->x7 + bns->x8*ta)*(bns->x7 + bns->x8*ta);
  1743. delete bns; bns = NULL;
  1744. if(dtemp<-ZERO){
  1745. *i=0;
  1746. }
  1747. else{
  1748. *i = 1;
  1749. t[0] = ta;
  1750. }
  1751. }
  1752. return;
  1753. }
  1754. else if(fabs(b2)<=ZERO&&fabs(a2<=ZERO))//两点同心
  1755. {
  1756. double ta;
  1757. if(m1 == m3)
  1758. {
  1759. *i = 0;
  1760. return;
  1761. }
  1762. //
  1763. ta = (r1-r3)/(m3-m1);
  1764. //t is minor than zero is unbearable so kick it out without mercy
  1765. if(ta<=-ZERO){
  1766. *i = 0;
  1767. }
  1768. else 
  1769. {
  1770. vgainbisectorlc(c2,c3,&bns);
  1771. dtemp = (bns->x5 + bns->x6*ta)*(bns->x5 + bns->x6*ta) -
  1772. (bns->x7 + bns->x8*ta)*(bns->x7 + bns->x8*ta);
  1773. delete bns; bns = NULL;
  1774. if(dtemp<-ZERO){
  1775. *i=0;
  1776. }
  1777. else{
  1778. *i = 1;
  1779. t[0] = ta;
  1780. }
  1781. }
  1782. return;
  1783. }
  1784. // above is the processing of the ccp 
  1785. //after the function we can make sure that the intersect point must be the validated one
  1786. //ok?
  1787. deta = a1*b2 - b1*a2;
  1788. if(fabs(deta)<ZERO)// two parallel  line left for later write
  1789. {  //三点一线,好象是三个圆并排在一条直线，不，这也有交点。
  1790. ASSERT(0);
  1791. *i=0;
  1792. return;
  1793. }
  1794. x0 = (b1*cc2-b2*cc1)/deta;
  1795. x1 = (mt2*b1-b2*mt1)/deta;
  1796. y0 =-(a1*cc2-a2*cc1)/deta;
  1797. y1 =-(a1*mt2-a2*mt1)/deta;
  1798.  
  1799. a = x1*x1+y1*y1-1;
  1800. b = 2*(x1*(x0-xc3)+y1*(y0-yc3)-r3*m3);
  1801. c = (x0-xc3)*(x0-xc3)+(y0-yc3)*(y0-yc3)-r3*r3;
  1803. vgetvalue(a,b,c,t,i);
  1804. return ;
  1805. }
  1806. void  vgainintersect(PVCNS c1,PVCNS c2,PVCNS c3,int *i,double t[2])
  1807. {
  1808. int t1,t2,t3 ;
  1809. t1=c1->type ;
  1810. t2=c2->type ;
  1811. t3=c3->type ;
  1812. if(CAXLINE==t1){
  1813. if(CAXLINE==t2){
  1814. if(CAXLINE==t3)
  1815. vgainintersectlll(c1,c2,c3,i,t);
  1816. else if(CAXARC==t3)
  1817. vgainintersectllc(c1,c2,c3,i,t);
  1818. }
  1819. else if(CAXARC==t2)
  1820. {
  1821. if(CAXLINE==t3)
  1822. vgainintersectllc(c1,c3,c2,i,t);
  1823. else if(CAXARC==t3)
  1824. vgainintersectlcc(c1,c2,c3,i,t);
  1825. }
  1826. }
  1827. else if(CAXARC==t1)
  1828. {
  1829. if(CAXLINE==t2){
  1830. if(CAXLINE==t3)
  1831. vgainintersectllc(c2,c3,c1,i,t);
  1832. else if(CAXARC==t3)
  1833. vgainintersectlcc(c2,c3,c1,i,t);
  1834. }
  1835. else if(CAXARC==t2)
  1836. {
  1837. if(CAXLINE==t3)
  1838. vgainintersectlcc(c3,c1,c2,i,t);
  1839. else if(CAXARC==t3)
  1840. vgainintersectccc(c1,c2,c3,i,t);
  1841. }
  1842. }
  1843. }
  1844. double vdis(double x1, double y1, double x2,double y2)
  1845. {
  1846. return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
  1847. }
  1848. //得到T对应的M值
  1849. void vgainintersectmvaluebns(PVBNS bns1,PVBNS bns2,double *t,int mblis,int * mvalue)
  1850. {//mblis is corrispondent to the bns2,and if bns1 =ccp or llp then t is useless
  1851. ASSERT(bns1);ASSERT(bns2);
  1852. double detaa,detab,dtemp,dt,tt;
  1853. double tfn,tsn;
  1854. double tfny,tsny,tfpy,tspy,tfp;
  1855. XYZ p;
  1856. tt = *t;
  1857. dt = tt * mblis ;
  1858. //
  1859. if(LL == bns1->bitype)
  1860. {
  1861. *mvalue = 1;
  1862. return;
  1863. }
  1864. ///////////gain tsn and tsny
  1865. if(bns2->bitype == LLP){
  1866. tsn  = bns2->x4 + bns2->x2 * dt;
  1867. tsny = bns2->y4 + (-1)*bns2->x1 * dt;
  1868. }
  1869. else if(bns2->bitype == CCP){//t represent the value of alph
  1870. tsn  = bns2->x1 + bns2->x2*cos(dt);
  1871. tsny = bns2->y1 + bns2->x2*sin(dt);
  1872. }
  1873. else if(bns2->bitype == LL){
  1874. tsn  = bns2->x1 - bns2->x3 * dt;//if is ll or lc or cc
  1875. tsny = bns2->y1 - bns2->y3 * dt;//mblis ==1 
  1876. }
  1877. else {
  1878. detab = pow(bns2->x5+bns2->x6*tt,2) - pow(bns2->x7+bns2->x8*tt,2);
  1879. if(fabs(detab)<= ZERO){
  1880. detab = 0;
  1881. }
  1882. else if(detab>ZERO){
  1883. detab = sqrt(detab);
  1884. }
  1885. else ASSERT(0);
  1886. tsn  = bns2->x1 -bns2->x2 - bns2->x3 * tt + mblis*bns2->x4*detab; 
  1887. tsny = bns2->y1 -bns2->y2 - bns2->y3 * tt - mblis*bns2->y4*detab;
  1888. }
  1889. ///////////////////
  1890. if(bns1->bitype == LLP){
  1891. if(fabs(bns1->x2)<=ZERO)
  1892. {
  1893. dtemp = (bns1->y4 - tsny )/bns2->x1;
  1894. }
  1895. else dtemp = (tsn - bns1->x4 )/bns2->x2;
  1896. if(dtemp<0){
  1897. *t = -dtemp;//for keep the same formation
  1898. *mvalue = -1;
  1899. }
  1900. else if(dtemp>=0)
  1901. {
  1902. *t = dtemp;
  1903. *mvalue = 1;
  1904. }
  1905. return;
  1906. }
  1907. else if(bns1->bitype == CCP){
  1908. p.x = tsn;
  1909. p.y = tsny;
  1910. dtemp = vgainangleofvector(&p);
  1911. *t = dtemp;//the fist alph value 
  1912. *mvalue = 1;
  1913. return;
  1914. }
  1915. ///////////////////
  1916. //////////////////////////above will 
  1917. if(LC == bns1->bitype || CC == bns1->bitype)
  1918. {
  1919. if(bns2->bitype == LLP||bns2->bitype == CCP)
  1920. tt = bns2->tmin;
  1921. else tt = *t;
  1922. detaa = pow(bns1->x5+bns1->x6*tt,2) - pow(bns1->x7+bns1->x8*tt,2);
  1923. if(detaa<-ZERO)ASSERT(0);
  1924. if(fabs(detaa) <=ZERO)
  1925. {
  1926. *mvalue = 1;
  1927. return ;
  1928. }
  1929. detaa = sqrt(detaa);
  1930. tfn  = bns1->x1 - bns1->x2 - bns1->x3*tt - bns1->x4*detaa;
  1931. tfny = bns1->y1 - bns1->y2 - bns1->y3*tt + bns1->y4*detaa;
  1932. tfn  = bns1->x1 - bns1->x2 - bns1->x3*tt + bns1->x4*detaa;
  1933. tfny = bns1->y1 - bns1->y2 - bns1->y3*tt - bns1->y4*detaa;
  1934. if(vdis(tsn,tsny,tfn,tfny)<=ZERO){
  1935. *mvalue = -1;
  1936. return;
  1937. }
  1938. else if(vdis(tsn,tsny,tfp,tfpy)<=ZERO){
  1939. *mvalue = 1;
  1940. return;
  1941. }
  1942. }
  1943. }
  1944. void  vgainintersectmvaluecns(PVBNS bns,PVCNS c1,PVCNS c2,PVCNS c3,double t,int *mvalue)
  1945. {
  1946. if(LL==bns->bitype)
  1947. {
  1948. *mvalue = 1;
  1949. return;
  1950. }
  1951. if(LLP==bns->bitype){}
  1952. if(LC == bns->bitype||CC == bns->bitype)
  1953. {
  1954. }
  1955. else if(CCP == bns->bitype){}
  1956. }
  1957. ////..............................................................................
  1958. int  vgainbisectorlimitedll(PVCNS l1, PVCNS l2, PVBNS *bi)
  1959. {
  1960. PVBNS bt;
  1961. double t,t1,t2,t3,t4,tt0,tt1;
  1962. double a1,a2,b1,b2,c1,c2;
  1963. vgainbisectorll(l1,l2,&bt);
  1964. if(bt==NULL)
  1965. {
  1966. *bi=bt;
  1967. return 0;
  1968. }
  1969. //以下对t1,t2赋值
  1970. vgetparaline(l1->element.line,&a1,&b1,&c1);
  1971. vgetparaline(l2->element.line,&a2,&b2,&c2);
  1972. t1 = (bt->x1 - l1->element.line->p0.x)/(a1 - bt->x3);
  1973. t2 = (bt->x1 - l1->element.line->p1.x)/(a1 - bt->x3);
  1974. t3 = (bt->x1 - l2->element.line->p0.x)/(a2 - bt->x3);
  1975. t4 = (bt->x1 - l2->element.line->p1.x)/(a2 - bt->x3);
  1976. if(t1>t2)
  1977. {
  1978. t=t1; 
  1979. t1=t2;
  1980. t2=t;
  1981. }
  1982. if(t3>t4)
  1983. {
  1984. t=t3;
  1985. t3=t4;
  1986. t4=t;
  1987. }
  1988. //
  1989. if(fabs(t4-t3)<ZERO&&t4<=t2&&t4>=t1)
  1990. {
  1991. tt0=tt1=t4;
  1992. }
  1993. else if(fabs(t1-t2)<ZERO&&t1<=t4&&t1>=t3){ tt0=tt1=t1; }
  1994. else if(t4<t1){ delete bt;*bi=NULL;return 0; }
  1995. else if(t2<t3){ delete bt;*bi=NULL;return 0; }
  1996. else if(t4>=t1 && t4<=t2)
  1997. {
  1998. if(t3<=t1)
  1999. {
  2000. tt0=t1;tt1=t4;
  2001. }
  2002. else
  2003. {
  2004. tt0=t3;tt1=t4;
  2005. }
  2006. }
  2007. else if(t4>t2)
  2008. {
  2009. tt1=t2;
  2010. if(t3<=t1)
  2011. {
  2012. tt0=t1;
  2013. }
  2014. else if(t3<=t2)
  2015. {
  2016. tt0=t3;
  2017. }
  2018. }
  2019. bt->t1=tt0;
  2020. bt->t2=tt1;
  2021. bt->m1=1;
  2022. bt->m2=1;
  2023. *bi = bt;
  2024. return 1;
  2025. }
  2026. //////........................................
  2027. int  vgainbisectorlimitedlc(PVCNS l1, PVCNS c2, PVBNS *bi)
  2028. {
  2029. PVCNS cns;
  2030. XYZ p;
  2031. double t1,t2,t3,t4,t[2],tt1,tt2,xxa,xxb,h;
  2032. int    m1,m2,m3,m4,i,mm1,mm2,clockwise;
  2033. ////...........................
  2034. PVBNS bia,bib;
  2035. vgainbisectorlc(l1,c2,&bia);
  2036. //////
  2037. p = l1->element.line->p0;
  2038. vgainpointseg(&cns,&p);
  2039. vgainintersectlcc(l1,c2,cns,&i,t);
  2040. //
  2041. if(i==2)AfxMessageBox("lcc find two solution");
  2042. if(i==0)
  2043. {
  2044. delete bia;
  2045. delete cns;
  2046. return 0;
  2047. }
  2048. h=bia->x4*sqrt(pow(bia->x5+bia->x6*t[0],2)-pow(bia->x7+bia->x8*t[0],2));
  2049. xxa = bia->x1 - bia->x2 - bia->x3*t[0] + h;
  2050. vgainbisectorlc(l1,cns,&bib);
  2051. xxb = bib->x1 - bib->x2 - bib->x3*t[0];//h==0 means deta=0;
  2052. if(fabs(xxa-xxb)<=ZERO*10)
  2053. m1=1;
  2054. else
  2055. m1=-1;
  2056. t1=t[0];
  2057. delete cns;
  2058. delete bib;
  2059. cns=NULL;bib=NULL;
  2060. //
  2061. p = l1->element.line->p1;
  2062. vgainpointseg(&cns,&p);
  2063. vgainintersectlcc(l1,c2,cns,&i,t);
  2064. //
  2065. if(i==2)AfxMessageBox("lcc find two solution");
  2066. if(i==0)
  2067. {
  2068. delete bia;
  2069. delete cns;
  2070. return 0;
  2071. }
  2072. h=bia->x4*sqrt(pow(bia->x5+bia->x6*t[0],2)-pow(bia->x7+bia->x8*t[0],2));
  2073. xxa = bia->x1-bia->x2-bia->x3*t[0]+h;
  2074. vgainbisectorlc(l1,cns,&bib);
  2075. xxb = bib->x1-bib->x2-bib->x3*t[0];//h==0 means deta=0;
  2076. if(fabs(xxa-xxb)<=ZERO*10)
  2077. m2=1;
  2078. else
  2079. m2=-1;
  2080. t2=t[0];
  2081. delete cns;
  2082. delete bib;
  2083. cns=NULL;bib=NULL;
  2084. //
  2085. if(m1==m2&&fabs(t1-t2)<ZERO)
  2086. {
  2087. delete bia;
  2088. return 0;
  2089. }
  2090. ///////////
  2091. p = c2->element.arc->px*(c2->element.arc->r/10)+c2->element.arc->pc;
  2092. vgainpointseg(&cns,&p);
  2093. vgainintersectlcc(l1,c2,cns,&i,t);
  2094. //
  2095. if(i==2)AfxMessageBox("lcc find two solution");
  2096. if(i==0)
  2097. {
  2098. delete bia;
  2099. delete cns;
  2100. return 0;
  2101. }
  2102. h=bia->x4*sqrt(pow(bia->x5+bia->x6*t[0],2)-pow(bia->x7+bia->x8*t[0],2));
  2103. xxa = bia->x1-bia->x2-bia->x3*t[0]+h;
  2104. vgainbisectorcc(c2,cns,&bib);
  2105. xxb = bib->x1-bib->x2-bib->x3*t[0];//h==0 means deta=0;
  2106. if(fabs(xxa-xxb)<=ZERO*10)
  2107. m3=1;
  2108. else
  2109. m3=-1;
  2110. t3=t[0];
  2111. delete cns;
  2112. delete bib;
  2113. cns=NULL;bib=NULL;
  2114. //
  2115. // vfindarcendpointo(c2->element.arc,&p,&clockwise);
  2116. vgainpointseg(&cns,&p);
  2117. vgainintersectlcc(l1,c2,cns,&i,t);
  2118. //
  2119. if(i==2)AfxMessageBox("lcc find two solution");
  2120. if(i==0)
  2121. {
  2122. delete bia;
  2123. delete cns;
  2124. return 0;
  2125. }
  2126. h=bia->x4*sqrt(pow(bia->x5+bia->x6*t[0],2)-pow(bia->x7+bia->x8*t[0],2));
  2127. xxa = bia->x1-bia->x2-bia->x3*t[0]+h;
  2128. vgainbisectorcc(c2,cns,&bib);
  2129. xxb = bib->x1-bib->x2-bib->x3*t[0];//h==0 means deta=0;
  2130. if(fabs(xxa-xxb)<=ZERO)
  2131. m4=1;
  2132. else
  2133. m4=-1;
  2134. t4=t[0];
  2135. delete cns;
  2136. delete bib;
  2137. cns=NULL;bib=NULL;
  2138. //
  2139. if(m3==m4&&fabs(t4-t3)<ZERO)
  2140. {
  2141. delete bia;
  2142. return 0;
  2143. }
  2144. //
  2145. if(!vcomparerights(m1,t1,m2,t2,m3,t3,m4,t4,&mm1,&tt1,&mm2,&tt2))
  2146. {
  2147. delete bia;
  2148. bia=NULL;
  2149. return 0;
  2150. }
  2151. bia->m1=mm1;bia->t1=tt1;
  2152. bia->m2=mm2;bia->t2=tt2;
  2153. bia->infinite=LIMITED;
  2154. return 1;
  2155. }
  2156. ////////.............................................
  2157. int  vgainbisectorlimitedcc(PVCNS c1, PVCNS c2, PVBNS *bi)
  2158. {
  2159. PVCNS cns;
  2160. XYZ p;
  2161. double t1,t2,t3,t4,t[2],tt1,tt2,xxa,xxb,h;
  2162. int    m1,m2,m3,m4,i,mm1,mm2;
  2163. ////...........................
  2164. PVBNS bia,bib;
  2165. vgainbisectorcc(c1,c2,&bia);
  2166. //
  2167. p = c1->element.arc->px*(c1->element.arc->r/10)+c1->element.arc->pc;
  2168. vgainpointseg(&cns,&p);
  2169. vgainintersectccc(c1,c2,cns,&i,t);
  2170. //
  2171. if(i==2)AfxMessageBox("lcc find two solution");
  2172. if(i==0)
  2173. {
  2174. delete bia;
  2175. delete cns;
  2176. return 0;
  2177. }
  2178. h=bia->x4*sqrt(pow(bia->x5+bia->x6*t[0],2)-pow(bia->x7+bia->x8*t[0],2));
  2179. xxa = bia->x1 - bia->x2 - bia->x3*t[0] + h;
  2180. vgainbisectorlc(c1,cns,&bib);
  2181. xxb = bib->x1 - bib->x2 - bib->x3*t[0];//h==0 means deta=0;
  2182. if(fabs(xxa-xxb)<=ZERO*10)
  2183. m1=1;
  2184. else
  2185. m1=-1;
  2186. t1=t[0];
  2187. delete cns;
  2188. delete bib;
  2189. cns=NULL;bib=NULL;
  2190. //
  2191. // vfindarcendpointo(c1->element.arc,&p,&clockwise);
  2192. vgainpointseg(&cns,&p);
  2193. vgainintersectccc(c1,c2,cns,&i,t);
  2194. //
  2195. if(i==2)AfxMessageBox("lcc find two solution");
  2196. if(i==0)
  2197. {
  2198. delete bia;
  2199. delete cns;
  2200. return 0;
  2201. }
  2202. h=bia->x4*sqrt(pow(bia->x5+bia->x6*t[0],2)-pow(bia->x7+bia->x8*t[0],2));
  2203. xxa = bia->x1 - bia->x2 - bia->x3*t[0] + h;
  2204. //
  2205. vgainbisectorlc(c1,cns,&bib);
  2206. xxb = bib->x1 - bib->x2 - bib->x3*t[0];//h==0 means deta=0;
  2207. if(fabs(xxa-xxb)<=ZERO*10)
  2208. m2=1;
  2209. else
  2210. m2=-1;
  2211. t2=t[0];
  2212. delete cns;
  2213. delete bib;
  2214. cns=NULL;bib=NULL;
  2215. if(m2==m1&&fabs(t1-t2)<ZERO)
  2216. {
  2217. delete bia;
  2218. return 0;
  2219. }
  2220. //
  2221. p = c2->element.arc->px*(c2->element.arc->r/10)+c2->element.arc->pc;
  2222. vgainpointseg(&cns,&p);
  2223. vgainintersectccc(c1,c2,cns,&i,t);
  2224. //
  2225. if(i==2)AfxMessageBox("lcc find two solution");
  2226. if(i==0)
  2227. {
  2228. delete bia;
  2229. delete cns;
  2230. return 0;
  2231. }
  2232. h=bia->x4*sqrt(pow(bia->x5+bia->x6*t[0],2)-pow(bia->x7+bia->x8*t[0],2));
  2233. xxa = bia->x1 - bia->x2 - bia->x3*t[0] + h;
  2234. vgainbisectorlc(c2,cns,&bib);
  2235. xxb = bib->x1 - bib->x2 - bib->x3*t[0];//h==0 means deta=0;
  2236. if(fabs(xxa-xxb)<=ZERO*10)
  2237. m3=1;
  2238. else
  2239. m3=-1;
  2240. t3=t[0];
  2241. delete cns;
  2242. delete bib;
  2243. cns=NULL;bib=NULL;
  2244. //
  2245. // vfindarcendpointo(c2->element.arc,&p,&clockwise);
  2246. vgainpointseg(&cns,&p);
  2247. vgainintersectccc(c1,c2,cns,&i,t);
  2248. //
  2249. if(i==2)AfxMessageBox("lcc find two solution");
  2250. if(i==0)
  2251. {
  2252. delete bia;
  2253. delete cns;
  2254. return 0;
  2255. }
  2256. h=bia->x4*sqrt(pow(bia->x5+bia->x6*t[0],2)-pow(bia->x7+bia->x8*t[0],2));
  2257. xxa = bia->x1 - bia->x2 - bia->x3*t[0] + h;
  2258. //
  2259. vgainbisectorlc(c2,cns,&bib);
  2260. xxb = bib->x1 - bib->x2 - bib->x3*t[0];//h==0 means deta=0;
  2261. if(fabs(xxa-xxb)<=ZERO*10)
  2262. m4=1;
  2263. else
  2264. m4=-1;
  2265. t4=t[0];
  2266. delete cns;
  2267. delete bib;
  2268. cns=NULL;bib=NULL;
  2269. //
  2270. if(m3==m4&&fabs(t4-t3)<ZERO)
  2271. {
  2272. delete bia;
  2273. return 0;
  2274. }
  2275. //
  2276. if(!vcomparerights(m1,t1,m2,t2,m3,t3,m4,t4,&mm1,&tt1,&mm2,&tt2))
  2277. {
  2278. delete bia;
  2279. bia=NULL;
  2280. return 0;
  2281. }
  2282. bia->m1=mm1;bia->t1=tt1;
  2283. bia->m2=mm2;bia->t2=tt2;
  2284. bia->infinite=LIMITED;
  2285. return 1;
  2286. }
  2287. int  vgainbisectorlimited(PVCNS c1, PVCNS c2, PVBNS *bi)
  2288. {
  2289. PVBNS bt;
  2290. if(CAXLINE==c1->type)
  2291. {
  2292. if(CAXLINE==c2->type)
  2293. vgainbisectorlimitedll(c1,c2,&bt);
  2294. else if(CAXARC==c2->type)
  2295. vgainbisectorlimitedlc(c1,c2,&bt);
  2296. }
  2297. else if(CAXARC==c1->type)
  2298. {
  2299. if(CAXLINE==c2->type)
  2300. vgainbisectorlimitedlc(c2,c1,&bt);
  2301. else if(CAXARC==c2->type)
  2302. vgainbisectorlimitedcc(c1,c2,&bt);
  2303. }
  2304. *bi=bt;
  2305. if(bt==NULL)
  2306. {
  2307. return 0;
  2308. }
  2309. else
  2310. {
  2311. return 1;
  2312. }
  2313. }
  2314. ////////........................................................
  2315. //////////////////////.............................................................
  2316. //make sure the cnbl  must be the double link
  2317. //进行环的转换
  2318. double vmultipointvector(PXYZ v1,PXYZ v2)
  2319. {
  2320. return v1->x*v2->x+v1->y*v2->y;
  2321. }
  2322. double vmultiplayvector(PXYZ v1,PXYZ v2)
  2323. {
  2324. return v1->x*v2->y-v1->y*v2->x;
  2325. }
  2326. double vgainangleofvector(PXYZ v)
  2327. {
  2328. if(fabs(v->x)<ZERO)
  2329. {
  2330. if(v->y>ZERO)
  2331. return PI/2;
  2332. else if(v->y<-ZERO)
  2333. return 1.5*PI;
  2334. else 
  2335. ASSERT(0);
  2336. }
  2337. else if(fabs(v->x)>ZERO)
  2338. {
  2339. if(v->x>ZERO)
  2340. {
  2341. if(v->y>ZERO)
  2342.     return atan(v->y/v->x);
  2343. else if(v->y<-ZERO)
  2344. return 2*PI+atan(v->y/v->x); 
  2345. else 
  2346. return 0;
  2347. }
  2348. else
  2349. {
  2350.    return PI+atan(v->y/v->x);
  2351. }
  2352. }
  2353. }
  2354. double vangleadd(double a1,double a2)
  2355. {
  2356. double t;
  2357. t=a1+a2;
  2358. if(t>=PI*2)
  2359. t=t-PI*2;
  2360. if(t<0.)
  2361. t=t+PI*2;
  2362. return t;
  2363. }
  2364. void vfindarcendpoint(PARC arc,PXYZ *pt)//?
  2365. {
  2366. ASSERT(arc);
  2367. XYZ px,py,pc;
  2368. PXYZ p=new XYZ;
  2369. double a,r,alph,blph;
  2370. int i;
  2371. a=arc->a;
  2372. r=arc->r;
  2373. pc=arc->pc;
  2374. px=arc->px-pc;
  2375. py=arc->py-pc;
  2376. alph=vgainangleofvector(&px);
  2377. blph=vgainangleofvector(&py);
  2378. if(fabs(vangleadd(alph,PI/2)-blph)<EP)
  2379. i=1;
  2380. else
  2381. i=-1;
  2382. alph=vangleadd(alph,i*a);
  2383. *pt=p;
  2384. p->x=pc.x+r*cos(alph);
  2385. p->y=pc.y+r*sin(alph);
  2386. p->z=0;
  2387. return;
  2388. }
  2389. void vfindarcendpointo(PARC arc,PXYZ *pt,int *clockwise)
  2390. {
  2391. ASSERT(arc);
  2392. XYZ px,py;
  2393. PXYZ p = new XYZ;
  2394. double alph,blph;
  2395. px = arc->px - arc->pc;
  2396. py = arc->py - arc->pc; 
  2397. alph = vgainangleofvector(&px);
  2398. blph = vgainangleofvector(&py);
  2399. double t = vangleadd(alph,PI/2);
  2400. if(fabs(t-blph)<=ZERO*10||(blph>t&&2*PI-blph+t<=ZERO*10)||(blph<t&&2*PI -t+blph<=ZERO*10))
  2401. {
  2402. *clockwise = 1;//CCW
  2403. }
  2404. else
  2405. {
  2406. t = vangleadd(alph,-PI/2);
  2407. if(fabs(t-blph)<=ZERO*10||(blph<t&&2*PI-t+blph<=ZERO*10)||
  2408. (blph>t&&2*PI-blph+t<=ZERO*10))
  2409. {
  2410. *clockwise = -1;//CW
  2411. }
  2412. else ASSERT(0);
  2413. }
  2414. alph = vangleadd(alph,*clockwise*arc->a);
  2415. *pt = p;
  2416. p->x = cos(alph);
  2417. p->y = sin(alph);
  2418. p->z = 0;
  2419. return;
  2420. }
  2421. int  vgetclockwisebli(PVBLI bli)
  2422. {
  2423. ASSERT(bli);
  2424. ASSERT(bli->bni);ASSERT(bli->bni->bns);
  2425. PVBNS bns;
  2426. bns = bli->bni->bns;
  2427. double tm1,tm2,t;
  2428. int m;
  2429. tm1 = bns->t1 * bns->m1;
  2430. tm2 = bns->t2 * bns->m2;
  2431. if(tm2 - tm1<-ZERO)
  2432. {
  2433. m = bns->m1;
  2434. t = bns->t1;
  2435. bns->m1 = bns->m2;
  2436. bns->t1 = bns->t2;
  2437. bns->t2 = t;
  2438. bns->m2 = m;
  2439. return CW;
  2440. }
  2441. else if(fabs(tm1-tm2)<ZERO)
  2442. {
  2443. //can be writed in the funture
  2444. }
  2445. return CCW;
  2446. }
  2447. //find t
  2448. /*
  2449. int vjudgepointinareal(PXYZ p,XYZ p0,XYZ p1)
  2450. {
  2451. XYZ v1,v2,v3;
  2452. double t,t1,t2;
  2453. v1=*p-p0;
  2454. v2=p1-p0;
  2455. v3=*p-p1;
  2456. t  = vmultipointvector(&v1,&v2);
  2457. t1 = vmultiplayvector(&v1,&v2);
  2458. t2 = vmultpointvector(&v3,&v1);
  2459. if(t1<-ZERO||t<-ZERO||t2>ZERO)
  2460. return 0;
  2461. if(t>ZERO&&t2<-ZERO&&t>ZERO)
  2462. return 1;
  2463. if(t>-ZERO&&t<ZERO)
  2464. {
  2465. return 2;//end in first point
  2466. }
  2467. if(t2>-ZERO&&t2<ZERO)
  2468. {
  2469. return 3;//end in end point
  2470. }
  2471. }
  2472. int vjudgepointinareaa(PXYZ p,XYZ pc,XYZ px, XYZ py,double r)
  2473. {
  2474. XYZ  v;
  2475. double t,tf,te;
  2476. v = arc->px-arc->pc;
  2477. tf = vgainangleofvector(v);
  2478. v = *p-arc->pc;
  2479. t = vgainangleofvector(v);
  2480. te = tf+arc->a;
  2481. if(te<PI*2)
  2482. {
  2483. if(fabs(tf-t)<ZERO)
  2484. return 2;
  2485. if(fabs(te-t)<ZERO)
  2486. return 3;
  2487. if(t<te&&t>tf)
  2488. return 1;
  2489. }
  2490. else
  2491. {
  2492. te=te-PI*2;
  2493. if(fabs(tf-t)<ZERO)
  2494. return 2;
  2495. if(fabs(te-t)<ZERO)
  2496. return 3;
  2497. if((t<te)||t>tf)
  2498. return 1;
  2499. }
  2500. }
  2501. int vjudgepointinarea(PXYZ p,PVCNS cns)
  2502. {
  2503. ASSERT(p);ASSERT(cns);
  2504. XYZ p1,p2;
  2505. int clocwise,type,juge;
  2506. type=cns->type;
  2507. clocwise=cns->clockwise;
  2508. if(CAXLINE==type)
  2509. {
  2510. if(clowise==CCW)
  2511. {
  2512. judge = vjudgepointinareal(p,cns->element.line->px,cns->element.line->py);
  2513. return judge;
  2514. }
  2515. else if(clocwise==CW)
  2516. {
  2517. judge = vjudgepointinareal(p,cns->element.line->py,cns->element.line->px);
  2518. return judge;
  2519. }
  2520. }
  2521. if(CAXARC==type)
  2522. {
  2523. if(clowise==CCW)
  2524. {
  2525. judge=vjudgepointinareaa(p,cns->element.arc);
  2526. }
  2527. else if(clowise==CW)
  2528. {
  2529. }
  2530. }
  2531. }
  2532. */
  2533. //the arc's own direction,from pfirst to pend.
  2534. double vfindnearestarcpoint(PARC arc,int *i,int *iclockwise)
  2535. {//only for perpendi
  2536. ASSERT(arc);
  2537. XYZ px,py,pc;
  2538. PXYZ p;
  2539. double a,b,c;
  2540. int clockwise;
  2541. pc = arc->pc;
  2542. px = arc->px - pc;
  2543. vfindarcendpointo(arc,&p,&clockwise);
  2544. *iclockwise = clockwise;
  2545. py.x = p->x;
  2546. py.y = p->y;
  2547. delete p;p= NULL;
  2548. //
  2549. a = vgainangleofvector(&px);
  2550. b = vgainangleofvector(&py);
  2551. if(clockwise == CCW)
  2552. {
  2553. c = b - a;
  2554. if(c<=-ZERO)
  2555. {
  2556. b = 2*PI + c; 
  2557. }
  2558. if(PI-a>=ZERO&&b-PI>= -ZERO)
  2559. {
  2560. *i = 1;
  2561. return PI;
  2562. }
  2563. else
  2564. {
  2565. *i=0;
  2566. return a;
  2567. }
  2568. }
  2569. else if(clockwise == CW)
  2570. {
  2571. c = a - b;
  2572. if(c<=-ZERO)
  2573. {
  2574. c = 2*PI + c; 
  2575. }
  2576. if(PI-b>=ZERO&&a-PI>= -ZERO)
  2577. {
  2578. *i = 1;
  2579. return PI;
  2580. }
  2581. else
  2582. {
  2583. *i = 0;
  2584. return a;
  2585. }
  2586. }
  2587. }
  2588. int vgainarcdirection(PARC arc)
  2589. {
  2590. ASSERT(arc);
  2591. XYZ px,py,pc;
  2592. PXYZ p=new XYZ;
  2593. double a,r,alph,blph;
  2594. a=arc->a;
  2595. r=arc->r;
  2596. pc=arc->pc;
  2597. px=arc->px-pc;
  2598. py=arc->py-pc;
  2599. alph=vgainangleofvector(&px);
  2600. blph=vgainangleofvector(&py);
  2601. if(fabs(vangleadd(alph,PI/2)-blph)<EP)
  2602. return CCW;
  2603. else
  2604. return CW;
  2605. }
  2606. int  vlineintarc(PLINE l1,PARC a1,PSTR3D *p)
  2607. {
  2608. PSTR3D o_p;
  2609. o_p=NULL;
  2610. int flag=ciInterLineArcAllActualOnPlane(l1, a1 , &o_p);
  2611. *p = o_p;
  2612. return flag;
  2613. }
  2614. //nead rewrited but it is sufficiant  if only line and without arc
  2615. void vjugedirection(PVCNBL cnbl,int *flag)
  2616. {//没有处理重复段，单段，自交段//I think it will be at fault.find it way out sir
  2617. ASSERT(cnbl);ASSERT(cnbl->cns);
  2618. PVCNBL cnblt = NULL,cnbl1=NULL,cnbl2=NULL;
  2619. double x,y,x0,y0,alph,tempt;
  2620. PXYZ   p;
  2621. int cnblflag,clockwiseflag,cnblflag0 = 0,clockwise;
  2622. if(cnbl->ccw == cnbl && CAXARC == cnbl->cns->type)//圆,弧
  2623. {
  2624. *flag = CCW;
  2625. return;
  2626. }
  2627. else if(cnbl->ccw == cnbl && CAXARC!=cnbl->cns->type)
  2628. {
  2629. AfxMessageBox("find spline,please");
  2630. *flag = ERRO;//erro = 0
  2631. return;
  2632. }
  2633. cnblt=cnbl1=cnbl2=cnbl;
  2634. if(CAXLINE == cnblt->cns->type)
  2635. {
  2636. x0 = cnblt->cns->element.line->p0.x;
  2637. y0 = cnblt->cns->element.line->p0.y;
  2638. }
  2639. else if(CAXARC == cnblt->cns->type)
  2640. {
  2641. alph = vfindnearestarcpoint(cnblt->cns->element.arc,&cnblflag,&clockwise);
  2642. if(cnblflag == 1)
  2643. {
  2644. x0 = cnblt->cns->element.arc->pc.x - cnblt->cns->element.arc->r;
  2645. y0 = cnblt->cns->element.arc->pc.y;
  2646. clockwiseflag = clockwise;
  2647. }
  2648. else if(cnblflag == 0)
  2649. {
  2650. x0 = cos(alph)*cnblt->cns->element.arc->r + cnblt->cns->element.arc->pc.x;
  2651. y0 = sin(alph)*cnblt->cns->element.arc->r + cnblt->cns->element.arc->pc.y;
  2652. }
  2653. }
  2654. else ASSERT(0);
  2655. do
  2656. {
  2657. cnblt = cnblt->ccw;
  2658. if(CAXLINE == cnblt->cns->type)
  2659. {
  2660. x = cnblt->cns->element.line->p0.x;
  2661. y = cnblt->cns->element.line->p0.y;
  2662. if(x-x0<-ZERO||(fabs(x-x0)<=ZERO&&y-y0>=ZERO))
  2663. {
  2664. x0 = x;
  2665. y0 = y;
  2666. cnbl1 = cnblt;
  2667. cnblflag0 = 0;
  2668. }
  2669. }
  2670. else if(CAXARC==cnblt->cns->type)
  2671. {
  2672. alph = vfindnearestarcpoint(cnblt->cns->element.arc,&cnblflag,&clockwise);
  2673. if(cnblflag == 1)
  2674. {
  2675. x = cnblt->cns->element.arc->pc.x - cnblt->cns->element.arc->r;
  2676. y = cnblt->cns->element.arc->pc.y;
  2677. if(x-x0<-ZERO||(fabs(x-x0)<=ZERO&&y-y0>=ZERO))
  2678. {
  2679. x0 = x;
  2680. y0 = y;
  2681. cnbl1 = cnblt;
  2682. clockwiseflag = clockwise;
  2683. cnblflag0 = 1;//this mark that the arc have contain the leftest point.
  2684. }
  2685. }
  2686. else if(cnblflag == 0)
  2687. {//this all be the first point of the segment
  2688. x = cos(alph)*cnblt->cns->element.arc->r + cnblt->cns->element.arc->pc.x;
  2689. y = sin(alph)*cnblt->cns->element.arc->r + cnblt->cns->element.arc->pc.y;
  2690. if(x-x0<-ZERO||(fabs(x-x0)<=ZERO&&y-y0>=ZERO))
  2691. {
  2692. x0 = x;
  2693. y0 = y;
  2694. cnbl1 = cnblt;
  2695. cnblflag0 = 0;
  2696. }
  2697. }
  2698. }
  2699. else ASSERT(0);
  2700. }while(cnblt!=cnbl);
  2701. XYZ p0,p1,p2;//以下代码应该可以简化
  2702. if(cnblflag0 == 1)//if we find the furtherest point in arc then
  2703. {
  2704. *flag = clockwiseflag;
  2705. return ;
  2706. }//below is the case that cnblflag0 = 0. 
  2707. if(CAXARC == cnbl1->cns->type)
  2708. {
  2709. p2 = cnbl1->cns->element.arc->px - cnbl1->cns->element.arc->pc;
  2710. vfindarcendpointo(cnbl1->cns->element.arc,&p,&clockwise);
  2711. delete p; p = NULL;
  2712. if(clockwise == CCW)
  2713. {
  2714. tempt=p2.x;
  2715. p2.x = -p2.y;
  2716. p2.y = tempt;
  2717. }
  2718. else if (clockwise == CW)
  2719. {
  2720. tempt=p2.x;
  2721. p2.x  =  p2.y;
  2722. p2.y  = -tempt;
  2723. }
  2724. }
  2725. else if(CAXLINE==cnbl1->cns->type)
  2726. {
  2727. p2 = cnbl1->cns->element.line->p1 - cnbl1->cns->element.line->p0;
  2728. }
  2729. //
  2730. if(CAXARC == cnbl1->cw->cns->type)
  2731. {
  2732. vfindarcendpointo(cnbl1->cns->element.arc,&p,&clockwise);
  2733. if(clockwise == CCW)
  2734. {
  2735. p1.x = -p->y*10;
  2736. p1.y = p->x*10;
  2737. }
  2738. else if(clockwise == CW)
  2739. {
  2740. p1.x =  p->y*10;
  2741. p1.y = -p->x*10;
  2742. }
  2743. delete p;p=NULL;
  2744. }
  2745. else if(CAXLINE == cnbl1->cw->cns->type)
  2746. {
  2747. p1 = cnbl1->cw->cns->element.line->p1 - cnbl1->cw->cns->element.line->p0;
  2748. }
  2749. if(vmultiplayvector(&p1,&p2)<-ZERO)
  2750. {
  2751. *flag = CW;
  2752. }
  2753. else
  2754. {
  2755. *flag = CCW;
  2756. }
  2757.     return;
  2758. }
  2759. void vreversecns(PVCNS cns,int cnstype)//finished
  2760. {//we make sure that the cn->reflex*cn->clockwise = CCW/1(环),CW/-1(岛)
  2761. //in the meantime we must make sure of the clockwise can use for bisector calculation
  2762. ASSERT(cns);
  2763. PVCNS cn;
  2764. PXYZ  p;
  2765. int clockwise;
  2766. cn = cns;
  2767. XYZ tp;
  2768. if(CAXARC == cn->type)
  2769. {
  2770. vfindarcendpointo(cn->element.arc,&p,&clockwise);
  2771. cn->element.arc->px.x = 10*p->x + cn->element.arc->pc.x;
  2772. cn->element.arc->px.y = 10*p->y + cn->element.arc->pc.y;
  2773. if(clockwise == CW)
  2774. {
  2775. cn->element.arc->py.x = -10*p->y + cn->element.arc->pc.x;
  2776. cn->element.arc->py.y =  10*p->x + cn->element.arc->pc.y;
  2777. cn->clockwise = cnstype * (-1);
  2778. cn->reflex = -1;
  2779. }
  2780. else
  2781. {
  2782. cn->element.arc->py.x =  10*p->y + cn->element.arc->pc.x;
  2783. cn->element.arc->py.y = -10*p->x + cn->element.arc->pc.y;
  2784. cn->clockwise = cnstype;
  2785. cn->reflex = 1;
  2786. }
  2787. delete p;
  2788. }
  2789. else if(CAXLINE == cn->type)
  2790. {
  2791. tp = cn->element.line->p0;
  2792. cn->element.line->p0 = cn->element.line->p1;
  2793. cn->element.line->p1 = tp;
  2794. cn->clockwise = cnstype;
  2795. }
  2796. }
  2797. void varrangecnbl(PVCNBL cnbl , int flag,int cnstype)
  2798. {
  2799. PVCNBL cn,tcnbl;
  2800. cn = cnbl;
  2801. PXYZ p;
  2802. int clockwise;
  2803. if(flag == CCW)
  2804. {
  2805. do{
  2806. if(cn->cns->type == CAXARC)
  2807. {
  2808. vfindarcendpointo(cn->cns->element.arc,&p,&clockwise);//only for the clockwise
  2809. cn->cns->clockwise = -cnstype * clockwise;
  2810. cn->cns->reflex = -clockwise;//
  2811. }
  2812. else
  2813. cn->cns->clockwise = cnstype;
  2814. }while(cn!=0&&cn!=cnbl);
  2815. }
  2816. else{
  2817. do{
  2818. tcnbl   = cn->ccw;
  2819. cn->ccw = cn->cw;
  2820. cn->cw  = tcnbl;
  2821. vreversecns(cn->cns,cnstype);
  2822. cn = cn->ccw;
  2823. }while(cn!=0&&cn!=cnbl);
  2824. }
  2825. }
  2826. //if cnbla and cnblb have reflex rlationship
  2827. //then below insert a reflex between them;
  2828. void vinsertpointseg(PVCNBL cnbla,PVCNBL cnblb)
  2829. {
  2830. ASSERT(cnbla);ASSERT(cnblb);
  2831.     XYZ px,py,pc;
  2832. PXYZ p;
  2833. PVCNBL cnbl;
  2834. PVCNS  c;
  2835. int clockwise;
  2836. cnbl=vmalloccnbl();
  2837. cnbl->cns=vmalloccns();
  2838. if(CAXLINE == cnblb->cns->type)
  2839. {
  2840. //if(cnblb->clockwise == CCW)
  2841. px = cnblb->cns->element.line->p0;
  2842. //else if (cnblb->clockwise == CW)
  2843. // px = cnblb->cns->element.line->p1;
  2844. }
  2845. else if(CAXARC==cnblb->cns->type)
  2846. {
  2847. //if(cnblb->clockwise == CCW)//all directions are in ccw met
  2848. px = cnblb->cns->element.arc->px*(cnblb->cns->element.arc->r/10);
  2849. // else if(cnblb->clockwise == CW)
  2850. // {
  2851. // vfindarcendpointo(arc,&p,&clockwise);
  2852. //}
  2853. }
  2854. vgainpointseg(&c,&px);
  2855. cnbl->cns  = c;
  2856. cnbl->cns->clockwise = cnbl->cns->clockwise;
  2857. cnbl->cw   =cnbla;
  2858. cnbl->ccw  =cnblb;
  2859. cnbla->ccw =cnbl;
  2860. cnblb->cw  =cnbl;
  2861. return;
  2862. }
  2863. //judge whether the cnsf and cnse are reflex relation
  2864. //return REFLEX OF UNREFLEX;
  2865. int vjudgeangle(PVCNS cnsf,PVCNS cnse)
  2866. {
  2867. ASSERT(cnsf);ASSERT(cnse);
  2868. double t;
  2869. XYZ p0,p1,p2;
  2870. PXYZ p = NULL;
  2871. int clockwise;
  2872. if(CAXLINE == cnsf->type)
  2873. {
  2874. p1 = cnsf->element.line->p1 - cnsf->element.line->p0;
  2875. if(CAXLINE == cnse->type)
  2876. {
  2877. p2 = cnse->element.line->p1 - cnse->element.line->p0;
  2878. }
  2879. else if(CAXARC == cnse->type)
  2880. {
  2881. vfindarcendpointo(cnse->element.arc,&p,&clockwise);
  2882. delete p;p=NULL;
  2883. p2 = cnse->element.arc->px - cnse->element.arc->pc;
  2884. t = p2.x;
  2885. if(clockwise == CCW)
  2886. {
  2887. p2.x = -p2.y;
  2888. p2.y = t;
  2889. }
  2890. else{
  2891. p2.x = p2.y;
  2892. p2.y = -t;
  2893. }
  2894. }
  2895. }
  2896. else if(CAXARC == cnsf->type)
  2897. {
  2898. vfindarcendpointo(cnsf->element.arc,&p,&clockwise);
  2899. p1.x = p->x*10;
  2900. p1.y = p->y*10;
  2901. delete p;p=NULL;
  2902. t = p1.x;
  2903. if(clockwise == CCW)
  2904. {
  2905. p1.x = -p1.y;
  2906. p1.y = t;
  2907. }
  2908. else if (clockwise == CW)
  2909. {
  2910. p1.x = p1.y;
  2911. p1.y = -t;
  2912. }
  2913. if(CAXLINE == cnse->type)
  2914. {
  2915. p2 = cnse->element.line->p1 - cnse->element.line->p0;
  2916. }
  2917. else if(CAXARC == cnse->type)
  2918. {
  2919. vfindarcendpointo(cnsf->element.arc,&p,&clockwise);
  2920. delete p; p=NULL;
  2921. p2 = cnse->element.arc->px - cnse->element.arc->pc;
  2922. t = p2.x;
  2923. if(clockwise == CCW)
  2924. {
  2925. p2.x = -p2.y;
  2926. p2.y = t;
  2927. }
  2928. else if(clockwise == CW)
  2929. {
  2930. p2.x = p2.y;
  2931. p2.y = -t;
  2932. }
  2933. }
  2934. }
  2935. t = vmultiplayvector(&p1,&p2);
  2936. //if I let the line's reflex =1 then two if can be compact to one
  2937. if(CAXARC == cnsf->type)
  2938. {
  2939. if(t*cnsf->clockwise*cnsf->reflex>=0)//=0 tangential 
  2940. return UNREFLEX;
  2941. else 
  2942. return REFLEX;
  2943. }
  2944. else if(CAXLINE == cnsf->type)
  2945. {
  2946. if(t*cnsf->clockwise>=0)//=0 tangential
  2947. {
  2948. return UNREFLEX;
  2949. }
  2950. else 
  2951. {
  2952. return REFLEX;
  2953. }
  2954. }
  2955. }
  2956. //request cnbl'loop have been arranged,or cnbl'loop'node'direction
  2957. void  vchangepcurvetocnblloop(PCURVE curve,PVCNBL *cnbl)
  2958. {
  2959. ASSERT(curve);
  2960. PVCNBL cnblt,cnblstf,cnblb;
  2961. PCURVE cur;
  2962. cur = curve;
  2963. do{
  2964. if(curve==cur)
  2965. {
  2966. cnblstf = cnblt = vmalloccnbl();
  2967. *cnbl=cnblstf;
  2968. cnblt->cns = vmalloccns();
  2969. cnblt->cns->type=cur->type;
  2970. cnblt->cns->element=cur->element;
  2971. cnblb=cnblt;
  2972. }
  2973. else
  2974. {
  2975. cnblt=vmalloccnbl();
  2976. cnblt->cns=vmalloccns();
  2977. cnblt->cns->type=cur->type;
  2978. cnblt->cns->element=cur->element;
  2979. cnblt->cw=cnblb;
  2980. cnblb->ccw=cnblt;
  2981. cnblb=cnblt;
  2982. }
  2983.     cur=cur->next;
  2984. }while(cur);
  2985. cnblb->ccw=cnblstf;
  2986. cnblstf->cw=cnblb;
  2987. return;
  2988. }
  2989. void vgainarrangedcnbl(PCURVE curve,PVCNBL *cnbl,int itype)
  2990. {
  2991. PVCNBL cnblt;
  2992. int flag;
  2993. vchangepcurvetocnblloop(curve,&cnblt);
  2994. vjugedirection(cnblt,&flag);
  2995. varrangecnbl(cnblt,flag,itype);
  2996. *cnbl=cnblt;
  2997. return;
  2998. }
  2999. void vpreprossesscnbl(PVCNBL cnbl,PVPL *vpl)
  3000. {
  3001. PVPL pl=NULL;
  3002. PVPLF plfa=NULL,plfb=NULL,plf=NULL,plfsta;
  3003. PVCNBL cnbla,cnblb,cnblsta,cnblf;
  3004. PVCNS  cns,cnsa,cnsb;
  3005. int flag = 1,label = 1,sum = 0;
  3006. int flagangle;
  3007. //
  3008. cnblb = cnbl;
  3009. cnbla = cnbl;
  3010. cnblsta=cnbla;
  3011. //
  3012. do{
  3013. cnsa = cnbla->cns;
  3014. cnblf = cnbla->cw;
  3015. cns = cnbla->cw->cns;
  3016. flagangle = vjudgeangle(cns,cnsa);
  3017. if(UNREFLEX == flagangle)
  3018. {
  3019. flag = 0;
  3020. }
  3021. else if(REFLEX==flagangle)
  3022. {
  3023. //insert an seg
  3024. vinsertpointseg(cnblf,cnbla);
  3025. if(cnblf==cnbl)
  3026. {
  3027. label=0;
  3028. }
  3029. else if(cnblf!=cnbl)
  3030. {
  3031. cnbla=cnblf;
  3032. }
  3033. }
  3034. }while(flag&&label);
  3035. //
  3036. if(!label)//whole loop
  3037. {
  3038. pl=vmallocpl();
  3039. plfa=vmallocplf();
  3040. if(cnbl->ccw==cnbl)
  3041. plfa->type=SINGLEPLF;
  3042. else
  3043. plfa->type=MULIPLF;
  3044. plfa->scnbl = cnbla;
  3045. plfa->ecnbl = cnbl;
  3046. pl->ptype=SINGLE;
  3047. pl->eplf=pl->splf=plfa;
  3048. *vpl = pl;
  3049. return;
  3050. }
  3051. else//not whole loop
  3052. {
  3053. if(cnbla->cw==cnbl)
  3054. {
  3055. pl=vmallocpl();
  3056. plfa=vmallocplf();
  3057. if(cnbl->cw==cnbla)
  3058. plfa->type=SINGLEPLF;
  3059. else
  3060. plfa->type=MULIPLF;
  3061. plfa->scnbl = cnbla->ccw;
  3062. plfa->ecnbl = cnbl;
  3063. plf = vmallocplf();
  3064. plf->type=SINGLEPLF;
  3065. plf->scnbl=plf->ecnbl=cnbla;
  3066. plf->ccw=plfa;
  3067. plf->cw=plfa;
  3068. plfa->ccw=plfa->cw=plf;
  3069. pl->eplf=plf;
  3070. pl->splf=plfa;
  3071. pl->ptype=MULI;
  3072. *vpl=pl;
  3073. return;
  3074. }
  3075. else{
  3076. plfa=vmallocplf();
  3077. plfa->scnbl=cnbla;
  3078. }
  3079. }
  3080. flag=0;
  3081. label=1;
  3082. cnblb=cnbl;
  3083. cnblsta=cnbla;
  3084. plfsta=plfa;
  3085. do{
  3086. cnsb=cnblb->cns;
  3087. cnblf=cnblb->ccw;
  3088. cns=cnblb->ccw->cns;
  3089. flagangle=vjudgeangle(cnsb,cns);
  3090. //
  3091. if(UNREFLEX==flagangle)
  3092. {
  3093. if(flag==0)
  3094. {
  3095. if(cnblb->ccw==cnbla)
  3096. {
  3097. pl=vmallocpl();
  3098. plfa=vmallocplf();
  3099. plfa->type=MULIPLF;
  3100. plfa->scnbl = cnbla->ccw;
  3101. plfa->ecnbl = cnblb;
  3102. //
  3103. plf = vmallocplf();
  3104. plf->type=SINGLEPLF;
  3105. plf->scnbl=plf->ecnbl=cnbla;
  3106. //
  3107. plf->ccw=plfa;
  3108. plf->cw=plfa;
  3109. plfa->ccw=plf;
  3110. plfa->cw=plf;
  3111. //
  3112. pl->eplf=plf;
  3113. pl->splf=plfa;
  3114. pl->ptype=MULI;
  3115. *vpl=pl;
  3116. return;
  3117. }
  3118. plfsta->ecnbl=cnblb;
  3119. if(cnblb==plfsta->scnbl)
  3120. plfsta->type=SINGLEPLF;
  3121. else
  3122. plfsta->type=MULIPLF;
  3123. //
  3124. cnbla = cnblb->ccw;
  3125. cnblb = cnbla;
  3126. flag = 1;
  3127. }
  3128. else{
  3129. if(cnblb->ccw==cnblsta)//end
  3130. {
  3131. plfb=vmallocplf();
  3132. plfb->scnbl=cnbla;
  3133. plfb->ecnbl=cnblb;
  3134. if(cnbla!=cnblb)
  3135. {
  3136. plfb->type=MULIPLF;
  3137. }
  3138. else
  3139. {
  3140. plfb->type=SINGLEPLF;
  3141. }
  3142. plfb->cw=plfa;
  3143. plfa->ccw=plfb;
  3144. //
  3145. plfsta->cw=plfb;
  3146. plfb->ccw=plfsta;
  3147. //
  3148. pl=vmallocpl();
  3149. pl->splf=plfsta;
  3150. pl->eplf=plfb;
  3151. if(plfb==plfsta)
  3152. {
  3153. pl->ptype=SINGLE;
  3154. }
  3155. else
  3156. {
  3157. pl->ptype=MULI;
  3158. }
  3159. //
  3160. label=0;
  3161. *vpl=pl;
  3162. }
  3163. else
  3164. {
  3165. //
  3166. plfb=vmallocplf();
  3167. plfb->scnbl=cnbla;
  3168. plfb->ecnbl=cnblb;
  3169. if(plfb->ecnbl==plfb->scnbl)
  3170. plfb->type=SINGLE;
  3171. else
  3172. plfb->type=MULIPLF;
  3173. //
  3174. plfa->ccw =plfb;
  3175. plfb->cw =plfa;
  3176. plfa=plfb;
  3177. //
  3178. cnbla=cnblb->ccw;
  3179. cnblb=cnbla;
  3180. }
  3181. }
  3182. }
  3183. ///
  3184. else if(REFLEX==flagangle)
  3185. {
  3186. vinsertpointseg(cnblb,cnblf);
  3187. cnblb=cnblf;
  3188. }
  3189. }while(label);
  3191. }
  3192. void vgainprofilebycurve(PCURVE curve,PVPL *vpl,int itype)
  3193. {
  3194. PVCNBL cnbl;
  3195. PVPL  vplt;
  3196. vgainarrangedcnbl(curve,&cnbl,itype);
  3197. vpreprossesscnbl(cnbl,&vplt);
  3198. *vpl=vplt;
  3199. return;
  3200. }
  3201. ////////////.................................................................
  3202. void vgainpointseg(PVCNS *c,PXYZ p)
  3203. {
  3204. ASSERT(p);
  3205. PVCNS cn;
  3206. cn = vmalloccns(); 
  3207. *c = cn;
  3208. cn->element.arc = new ARC;
  3209. cn->type = CAXARC;
  3210. cn->element.arc->r = 0;
  3211. cn->element.arc->a = 2*PI;
  3212. cn->element.arc->pc.x = p->x;
  3213. cn->element.arc->pc.y = p->y;
  3214. cn->element.arc->pc.z = p->z;
  3215.   return;
  3216. }
  3217. void vaddpointsegcnbl(PVCNS *c,PXYZ p,PVCNBL *cnbl)
  3218. {
  3219. ASSERT(p);
  3220. PVCNBL tcnbl=NULL;
  3221. //
  3222. PVCNS cn=new VCNS;
  3223. *c=cn;
  3224.     cn->clockwise=CCW;
  3225. cn->element.arc=new ARC;
  3226. cn->reflex=0;
  3227. cn->type=CAXARC;
  3228. cn->element.arc->r=0;
  3229. cn->element.arc->pc.x=p->x;
  3230. cn->element.arc->pc.y=p->y;
  3231. cn->element.arc->pc.z=p->z;
  3232. //
  3233. tcnbl=new VCNBL;
  3234. tcnbl->bli=new VBLI;
  3235. tcnbl->cns=cn;
  3236. tcnbl->bli->bni=new VBNI;
  3237.   return;
  3238. }
  3239. void vaddpointsegpre(PVCNBL cnbl)//cw 方向
  3240. {
  3241. ASSERT(cnbl);
  3242. ASSERT(cnbl->cns);
  3243. ASSERT(1!=cnbl->flag);
  3245. XYZ px,py;
  3246. PXYZ p;
  3247. int clockwise;
  3248. PVCNS cns = NULL;
  3249. PVCNBL tcnbl = NULL,cnblt;
  3250. tcnbl = vmalloccnbl();
  3251. //
  3252. if(CAXLINE == cnbl->cns->type)
  3253. {
  3254. px = cnbl->cns->element.line->p0;
  3255. py = cnbl->cns->element.line->p1;
  3256. }
  3257. else if(CAXARC == cnbl->cns->type)
  3258. {
  3259. ASSERT(cnbl->cns->element.arc->r!=0);//perhaps if there are problem in reflex assert
  3260. px = cnbl->cns->element.arc->px * (cnbl->cns->element.arc->r/10);
  3261. vfindarcendpointo(cnbl->cns->element.arc,&p,&clockwise);
  3262. py.x = p->x*cnbl->cns->element.arc->r + cnbl->cns->element.arc->pc.x;
  3263. py.y = p->y*cnbl->cns->element.arc->r + cnbl->cns->element.arc->pc.y;
  3264. delete p;p=NULL;
  3265. }
  3266. else 
  3267. ASSERT(0);//not belong to line or arc
  3268. if(cnbl->cns->type == CAXLINE)cnbl->cns->reflex = 1;
  3269. if(CCW == cnbl->cns->clockwise*cnbl->cns->reflex)
  3270. {
  3271. vgainpointseg(&cns,&px);
  3272. }
  3273. else if(CW == cnbl->cns->clockwise*cnbl->cns->reflex)
  3274. {
  3275. vgainpointseg(&cns,&py);
  3276. }
  3277. cnblt = cnbl->cw;
  3278. tcnbl->cns = cns;
  3279. tcnbl->ccw = cnbl;
  3280. cnbl->cw = tcnbl;
  3281. tcnbl->cw = cnblt;
  3282. tcnbl->flag = 1;
  3283. return;
  3284. }
  3285. void vaddpointseglast(PVCNBL cnbl)
  3286. {
  3287. ASSERT(cnbl);ASSERT(cnbl->cns);ASSERT(1!=cnbl->flag);
  3288. XYZ px,py;
  3289. PXYZ p;
  3290. int clockwise;
  3291. PVCNS cns = NULL;
  3292. PVCNBL tcnbl = NULL,cnblt;
  3293. tcnbl = vmalloccnbl();
  3294. //
  3295. if(CAXLINE == cnbl->cns->type)
  3296. {
  3297. px=cnbl->cns->element.line->p0;
  3298. py=cnbl->cns->element.line->p1;
  3299. }
  3300. else if(CAXARC==cnbl->cns->type)
  3301. {
  3302. ASSERT(cnbl->cns->element.arc->r!=0);
  3303. px = cnbl->cns->element.arc->px * (cnbl->cns->element.arc->r/10);
  3304. vfindarcendpointo(cnbl->cns->element.arc,&p,&clockwise);
  3305. py.x = p->x*cnbl->cns->element.arc->r + cnbl->cns->element.arc->pc.x;
  3306. py.y = p->y*cnbl->cns->element.arc->r + cnbl->cns->element.arc->pc.y;
  3307. delete p;p=NULL;
  3308. }
  3309. else 
  3310. ASSERT(0);
  3311. if(cnbl->cns->reflex == CAXLINE)cnbl->cns->reflex = 1;
  3312. if(CCW == cnbl->cns->clockwise*cnbl->cns->reflex)
  3313. {
  3314. vgainpointseg(&cns,&py);
  3315. }
  3316. else if(CW==cnbl->cns->clockwise*cnbl->cns->reflex)
  3317. {
  3318. vgainpointseg(&cns,&px);
  3319. }
  3320. cnblt = cnbl->ccw;
  3321. tcnbl->cns = cns;
  3322. tcnbl->cw = cnbl;
  3323. cnbl->ccw = tcnbl;
  3324. tcnbl->ccw = cnblt;
  3325. tcnbl->flag = 1;
  3326. return;
  3327. }
  3328. //NOTES:I am sure that there are no zerolenght line,duplicity line or arc;
  3329. //在两边都加上平分线
  3330. void vgainsinglebisector(PVCNBL cnbl,PVBLI *obli)
  3331. {
  3332. ASSERT(cnbl);
  3333. PVBLI blis=NULL,blie=NULL,blit = NULL;//blis mean start bli,blie mean end bli
  3334. PVBNI bni=NULL,bnit=NULL;
  3335. PVCNS cns=NULL,cnst=NULL,cnse = NULL;
  3336. PVBNS bns=NULL;
  3337. XYZ  px,py;
  3338. PXYZ p;
  3339. int clockwise;
  3340. //
  3341. cns = cnbl->cns;
  3342. //
  3343. if(CAXLINE == cns->type)
  3344. {
  3345. px = cns->element.line->p0;
  3346. //
  3347. vgainpointseg(&cnst,&px); ASSERT(cnst);
  3348. vgainbisectorlc(cns,cnst,&bns); ASSERT(bns);
  3349. bns->t1 = 0;
  3350. blis = vmallocbli();
  3351. blis->bni = vmallocbni();
  3352. blis->bni->selfcns = cnbl->cns;
  3353. blis->bni->bns = bns;
  3354. //
  3355. bns = NULL;cnst = NULL;
  3356. px = cns->element.line->p1;
  3357. vgainpointseg(&cnst,&px); ASSERT(cnst);
  3358. vgainbisectorlc(cns,cnst,&bns); ASSERT(bns);
  3359. bns->t1 = 0;
  3360. blie = vmallocbli();
  3361. blie->bni = vmallocbni();
  3362. blie->bni->selfcns = cnbl->cns;
  3363. blie->bni->bns = bns;
  3364. //
  3365. bns=NULL;cnst=NULL;
  3366. if(CCW == cns->clockwise)
  3367. {
  3368. *obli = blie;
  3369. blie->clockwise = CCW;
  3370. blis->clockwise = CW;
  3371. blie->next = blis;
  3372. blis->last = blie;
  3373. }
  3374. else if(CW == cns->clockwise)
  3375. {
  3376. *obli = blis;
  3377. blis->clockwise = CCW;
  3378. blie->clockwise = CW;
  3379. blis->next = blie;
  3380. blie->last = blis;
  3381. }
  3382. }
  3383. else if(CAXARC == cns->type)
  3384. {
  3385. if(fabs(cns->element.arc->r)>ZERO)
  3386. {
  3387. px = (cns->element.arc->px - cns->element.arc->pc)*(cns->element.arc->r/10)
  3388.  + cns->element.arc->pc ;
  3389. vfindarcendpointo(cns->element.arc,&p,&clockwise);
  3390. py.x = p->x * cns->element.arc->r + cns->element.arc->pc.x;
  3391. py.y = p->y * cns->element.arc->r + cns->element.arc->pc.y;
  3392. delete p;p=NULL;
  3393. //
  3394. vgainpointseg(&cnst,&px);ASSERT(cnst);
  3395. vgainbisectorcc(cnst,cns,&bns);ASSERT(bns);
  3396. bns->t1 = 0;
  3397. blis = vmallocbli();
  3398. blis->bni = vmallocbni();
  3399. blis->bni->selfcns = cnbl->cns;
  3400. blis->bni->bns = bns;
  3401. bns = NULL;cnst = NULL;
  3402. //
  3403. vgainpointseg(&cnse,&py);ASSERT(cnse);
  3404. vgainbisectorcc(cnse,cns,&bns);ASSERT(bns);
  3405. bns->t1 = 0;
  3406. //
  3407. blie=vmallocbli();
  3408. blie->bni=vmallocbni();
  3409. blie->bni->selfcns = cnbl->cns;//I think this number will be deleted
  3410. blie->bni->bns = bns;
  3411. bns = NULL;cnst = NULL;
  3412. //
  3413. if(cns->clockwise == CW){
  3414. blie->bni->bns->t2 = cns->element.arc->r;
  3415. blis->bni->bns->t2 = cns->element.arc->r;
  3416. }
  3417. if(CCW == cns->clockwise*cns->reflex)
  3418. {
  3419. *obli = blie;
  3420. blie->clockwise = CCW;
  3421. blis->clockwise = CW;
  3422. blie->next = blis;
  3423. blis->last = blie;
  3424. }
  3425. else if(CW == cns->clockwise*cns->reflex)
  3426. {
  3427. *obli = blis;
  3428. blis->clockwise = CCW;
  3429. blie->clockwise = CW;
  3430. blis->next = blie;
  3431. blie->last = blis;
  3432. }
  3433. }
  3434. }
  3435. return;
  3436. }
  3437. ///////////////////////////////////////
  3438. ///////////////////////////////////////
  3439. //得到单树枝，即只有一个树叶的树枝，对其树叶进行赋bisector
  3440. //没有任何角平分线信息，头尾也没有新加节点
  3441. //function
  3442. //加上头尾节点，加上角平分线连，加上角平分线对应关系
  3443. /////////////////////////////
  3444. void vgainsingleplfbli(PVPLF plf)
  3445. {
  3446. ASSERT(plf);
  3447. PVBLI  bli = NULL,tbli = NULL;
  3448. PVCNBL tcnbl = NULL;
  3449. PVCNBL cnbls = NULL,cnble = NULL;
  3450. //是单节点树叶 it's impossible to have zero segment
  3451. if(SINGLEPLF == plf->type)
  3452. { 
  3453. vgainsinglebisector(plf->scnbl,&bli);//得到节点的bisector连
  3454. plf->scnbl->bli=bli;
  3455. vaddpointsegpre(plf->scnbl);//在前加上点节点note 没有bli的信息
  3456. vaddpointseglast(plf->ecnbl);//在后加上点节
  3457. //
  3458. cnbls = plf->scnbl->cw;
  3459. cnble = plf->ecnbl->ccw;
  3460. //
  3461. tbli = bli;
  3462. while(tbli->next)
  3463. {
  3464. tbli=tbli->next;
  3465. }
  3466. //
  3467. cnbls->bli=vmallocbli();
  3468. cnbls->bli->bni = vmallocbni();
  3469. cnble->bli = vmallocbli();
  3470. cnble->bli->bni = vmallocbni();
  3471. //
  3472. cnbls->bli->bni->bns  = tbli->bni->bns;
  3473. cnbls->bli->clockwise =-tbli->clockwise;//?
  3474. cnble->bli->bni->bns  = bli->bni->bns;
  3475. cnble->bli->clockwise = -bli->clockwise;//?
  3476. //
  3477. cnbls->bli->bni->othercns = cnbls->ccw->cns;
  3478. cnble->bli->bni->othercns = cnble->cw->cns;
  3479. plf->ecnbl->bli->bni->othercns = cnble->cns;
  3480. plf->ecnbl->bli->next->bni->othercns = cnbls->cns;
  3481. //
  3482. plf->scnbl=cnbls;
  3483. plf->ecnbl=cnble;
  3484. //
  3485. return;
  3486. }//多节点 have the oppotunity to be an point segment
  3487. plf->type = MULIPLF;
  3488. //
  3489. tcnbl = plf->scnbl;
  3490. vaddpointsegpre(tcnbl);
  3491. tcnbl->cw->bli = vmallocbli();
  3492. tcnbl->cw->bli->bni = vmallocbni();
  3493. //
  3494. do
  3495. {
  3496. if(tcnbl->cns->type==CAXARC&&fabs(tcnbl->cns->element.arc->r)<=ZERO)//是点
  3497. {
  3498. tcnbl->bli = vmallocbli();
  3499. tcnbl->bli->bni = vmallocbni(); 
  3500. tcnbl->bli->next = vmallocbli();
  3501. tcnbl->bli->next->bni = vmallocbni();
  3502. tcnbl->bli->next->last = tcnbl->bli;
  3503. //
  3504. tcnbl->bli->next->bni->othercns = tcnbl->cw->cns;
  3505. tcnbl->cw->bli->bni->othercns = tcnbl->cns;
  3506. //
  3507. tcnbl->bli->next->bni->bns = tcnbl->cw->bli->bni->bns;
  3508. tcnbl->bli->next->clockwise = -tcnbl->cw->bli->clockwise;
  3509. tcnbl = tcnbl->ccw;
  3510. }
  3511. else
  3512. {
  3513. vgainsinglebisector(tcnbl,&bli);
  3514. ASSERT(bli);
  3515. tcnbl->bli = bli;
  3516. //
  3517. tcnbl->cw->bli->bni->othercns = tcnbl->cns;
  3518. tcnbl->bli->next->bni->othercns = tcnbl->cw->cns;
  3519. //
  3520. tcnbl->cw->bli->bni->bns = bli->next->bni->bns;
  3521. tcnbl->cw->bli->clockwise = -bli->next->clockwise;
  3522. tcnbl = tcnbl->ccw;
  3523. }
  3524. tcnbl->bli=bli;
  3525. bli=NULL;
  3526. }while(tcnbl != plf->ecnbl);
  3527. //
  3528. vgainsinglebisector(tcnbl,&bli);
  3529. ASSERT(bli);
  3530. tcnbl->bli = bli;
  3531. //
  3532. tcnbl->cw->bli->bni->bns = bli->next->bni->bns;
  3533. tcnbl->cw->bli->clockwise = -bli->next->clockwise;
  3534. //
  3535. tcnbl->cw->bli->bni->othercns = tcnbl->cns;
  3536. tcnbl->bli->next->bni->othercns = tcnbl->cw->cns;
  3537. //给最后的一个节点进行赋值
  3538. vaddpointseglast(tcnbl);
  3539. tcnbl = tcnbl->ccw;
  3540. tcnbl->bli = vmallocbli();
  3541. tcnbl->bli->bni = vmallocbni();
  3542. //
  3543. tcnbl->bli->bni->bns = tcnbl->cw->bli->bni->bns;
  3544. tcnbl->bli->clockwise = -tcnbl->cw->bli->clockwise;
  3545. tcnbl->bli->bni->othercns = tcnbl->cw->cns;
  3546. //
  3547. tcnbl->cw->bli->bni->othercns = tcnbl->cns;
  3548. //
  3549. plf->scnbl=plf->scnbl->cw;
  3550. plf->ecnbl=plf->ecnbl->ccw;
  3551. //
  3552. return;
  3553. }
  3554. //把一个树枝分成两个近似相等的树枝
  3555. //ok
  3556. void vdivideprofiletwo(PVPL vpl,PVPL *pl,PVPL *pr)
  3557. {
  3558. ASSERT(vpl);ASSERT(vpl->ptype!=SINGLE);
  3559. ASSERT(vpl->splf);
  3560. PVPL kpl=NULL;
  3561. int sum=1;
  3562. PVPLF plf=NULL;
  3563. plf = vpl->splf;
  3564. while(plf != vpl->eplf)
  3565. {
  3566. sum++;
  3567. plf=plf->ccw;
  3568. }
  3569. plf = vpl->splf;
  3570. if(sum==2)
  3571. {
  3572. kpl=new VPL;ASSERT(kpl);
  3573. kpl->eplf = kpl->splf = vpl->eplf;
  3574. kpl->ptype=SINGLE;
  3575. *pl=kpl;
  3576. kpl=NULL;
  3577. kpl=new VPL;ASSERT(kpl);
  3578. kpl->eplf = kpl->splf = vpl->splf;
  3579. kpl->ptype=SINGLE;
  3580. *pr=kpl;
  3581. kpl=NULL;
  3582. }
  3583. else if(sum==3)
  3584. {
  3585. kpl = new VPL;ASSERT(kpl);
  3586. kpl->splf = vpl->eplf->cw;
  3587. kpl->eplf = vpl->eplf;
  3588. kpl->ptype = MULIPLF;
  3589. *pl = kpl;
  3590. kpl = NULL;
  3591. kpl = new VPL;ASSERT(kpl);
  3592. kpl->eplf = kpl->splf = vpl->splf;
  3593. kpl->ptype = SINGLE;
  3594. *pr = kpl;
  3595. kpl = NULL;
  3596. }
  3597. else if(sum>3)
  3598. {
  3599. sum = sum/2;
  3600. for(int i=1;i<sum;i++)
  3601. plf = plf->ccw;
  3602. kpl = new VPL;ASSERT(kpl);
  3603. kpl->splf = plf->ccw;
  3604. kpl->eplf = vpl->eplf;
  3605. kpl->ptype = MULIPLF;
  3606. *pl = kpl;
  3607. kpl = NULL;
  3608. kpl = new VPL; ASSERT(kpl);
  3609. kpl->splf = vpl->splf;
  3610. kpl->eplf = plf;
  3611. kpl->ptype = MULIPLF;
  3612. *pr=kpl;
  3613. kpl=NULL;
  3614. }
  3615. delete vpl;   //?
  3616. vpl=NULL;
  3617. return;
  3618. }
  3619. ///////////////////////////////////////////////////////////////////////////
  3620. ///merge
  3621. ///////////////////////////////////////////////////////////////////////////
  3622. //find whether the t is in the limitation of bns 
  3623. //rcnbl=vfindcnblr(blir->bni->othercns,rcnbl)
  3624. //找到blil的另一部分cns对应的cnbl节点
  3625. PVCNBL vfindcnblr(PVCNS cns,PVCNBL rcnbl)
  3626. {
  3627. PVCNBL cnbl;
  3628. cnbl = rcnbl;
  3629. while(cnbl->cns != cns)
  3630. cnbl = cnbl->cw;
  3631. return cnbl;
  3632. }
  3633. //找到blil的另一部分cns对应的cnbl节点
  3634. PVCNBL vfindcnbll(PVCNS cns,PVCNBL lcnbl)
  3635. {
  3636. PVCNBL cnbl;
  3637. cnbl=lcnbl;
  3638. while(cnbl->cns != cns)
  3639. cnbl=cnbl->ccw;
  3640. return cnbl;
  3641. }
  3642. ////.............................................
  3643. //判断t,m 是否在bns中 
  3644. //return 0,mean t is not in bns
  3645. //return 1,mean only in the end point of bns
  3646. //return 2,mean in the middle of bns
  3647. int vjudgetheinbns(PVBNS bns,double t,int m)
  3648. {
  3649. ASSERT(bns);//ASSERT(bns->t1<=bns->t2);
  3650. double tm1,tm2,tm;
  3651. double tt;
  3652. //
  3653. tm = t * m;
  3654. tm1 = bns->t1 * bns->m1;
  3655. tm2 = bns->t2 * bns->m2;
  3656. if((t - bns->tmin)<-ZERO)// t不能小于tmin>=0
  3657. {
  3658. return 0;
  3659. }
  3660. else if(fabs(t-bns->tmin)<ZERO)
  3661. {
  3662. return 1;
  3663. }
  3664. //arrange ,are the bns arrange before?
  3665. //if be arranged bellow can be deleted safely
  3666. if(fabs(tm1-tm2)<=ZERO){ASSERT(0);return 0;}//点角平分线处理
  3667. else if(tm1-tm2>ZERO)
  3668. {
  3669. tt=tm1;
  3670. tm1=tm2;
  3671. tm2=tt;
  3672. }
  3673. //
  3674. /* if(INFINITY == bns->infinite) //下面是两个未arrange的算法
  3675. {
  3676. if(bns->t1 == UPER&&bns->t2 == UPER)
  3677. return 2;
  3678. else if(bns->t1 != UPER)
  3679. {
  3680. if(fabs(tm1-tm)<=ZERO)
  3681. return 1;
  3682. else if(tm-tm1>ZERO)
  3683. return 2;
  3684. else return 0;
  3685. }
  3686. else// bns->t2!=UPPER 
  3687. {
  3688. if(fabs(tm2-tm)<=ZERO)
  3689. return 1;
  3690. else if(tm2-tm>ZERO)
  3691. return 2;
  3692. else return 0;
  3693. }
  3694. }
  3695. else//neither bns->t1 nor bns->t2 ==uper  
  3696. */ {
  3697. if(fabs(tm - tm1)<=ZERO||fabs(tm-tm2)<=ZERO)return 1;
  3698. else if(tm-tm1>ZERO&&tm-tm2<-ZERO)
  3699. return 2;
  3700. else return 0;
  3701. }
  3702. }
  3703. //
  3704. PVBLI vfindimlimitedbli(PVBLI bli,int flag)
  3705. {
  3706. PVBLI blit=NULL;
  3707. int m;
  3708. if(flag ==2)//meet with right
  3709. {
  3710.     blit = bli;
  3711. while(blit->next)
  3712. {
  3713. blit = blit->next;
  3714. }
  3715. }
  3716. else if(flag == 1)//meet with left
  3717. {
  3718. blit = bli;
  3719. while(blit->last)
  3720. {
  3721. blit = blit->last;
  3722. }
  3723. }
  3724. while(blit)
  3725. {
  3726. if((blit->clockwise==CCW && flag == 1)||(blit->clockwise==CW && flag==2))
  3727. {
  3728. if(blit->bni->bns->t2 == UPER)
  3729. break;
  3730. }
  3731. else if((blit->clockwise==CW && flag==1)||(blit->clockwise==CCW && flag==2))
  3732. {
  3733. if(blit->bni->bns->t1 ==UPER)
  3734. break;
  3735. }
  3736. if(flag == 2)
  3737. blit = blit->last;
  3738. else if(flag == 1)
  3739. blit = blit->next;
  3740. }
  3741. if(blit)
  3742. return blit;
  3743. else
  3744. ASSERT(0);
  3745. return NULL;
  3746. }
  3747. //for unexpected dealing with
  3748. //make sure that pbl>=0,rcnblin!=NULL,and so on and the blistart is the first bli needed
  3749. void vregendercnblunexpectedl(PVCNBL *lcnblin,PVCNBL rcnbl,PVBLI blistart,PVBLI bliend,
  3750. PVBLI pbufl[],int pbl,PVBLI *bliout)
  3751. {
  3752. PVCNBL lcnbl = *lcnblin;
  3753. PVBLI  blia  = NULL;
  3754. int i;
  3755. if(lcnbl->flag == 1)
  3756. {
  3757. if(pbl == 0)
  3758. {
  3759. pbufl[0]->clockwise = -pbufl[0]->clockwise;
  3760. lcnbl->bli = pbufl[0];
  3761. pbufl[0]->next = blistart;
  3762. if(blistart)
  3763. {
  3764. blistart->last = pbufl[0];
  3765. }
  3766. else{
  3767. ASSERT(0);
  3768. }
  3769. return ;
  3770. }
  3771. for( i = pbl; i>=0; i--)
  3772. {
  3773. pbufl[i]->clockwise *=-1;
  3774. if(i==pbl)
  3775. {
  3776. lcnbl->bli = pbufl[i];
  3777. }
  3778. else if (i==0)
  3779. {
  3780. pbufl[i]->last = pbufl[i+1];
  3781. pbufl[i+1]->next = pbufl[i];
  3782. //
  3783. pbufl[i]->next = blistart;
  3784. if(blistart != NULL)
  3785. {
  3786. blistart->last = pbufl[i];
  3787. }
  3788. }
  3789. else
  3790. {
  3791. pbufl[i]->last = pbufl[i+1];
  3792. pbufl[i+1]->next = pbufl[i];
  3793. }
  3794. }
  3795. return;
  3796. }
  3797. else
  3798. {
  3799. //above is the finding of the first/(last in sequential meaning) bli
  3800. blia = vfindimlimitedbli(blistart,1);
  3801. if(pbl == 0)
  3802. {
  3803. pbufl[0]->next = blistart;
  3804. pbufl[0]->clockwise *=-1;//it is so important that it safe to never touch it
  3805. if(blistart){
  3806. blistart->last = pbufl[0];
  3807. }
  3808. else ASSERT(0);
  3809. if(blia)
  3810. {
  3811. pbufl[0]->last = blia;
  3812. blia->next = pbufl[0];
  3813. }
  3814. else
  3815. {
  3816. lcnbl->bli = pbufl[0];
  3817. }
  3818. }
  3819. else{//为伊消得人憔悴
  3820. for(i=0;i<=pbl;i++)
  3821. {
  3822. pbufl[i]->clockwise *=-1;
  3823. if(i == 0)
  3824. {
  3825. pbufl[i] ->next = blistart;
  3826. if(blistart){
  3827. blistart->last = pbufl[i];
  3828. }
  3829. else ASSERT(0);
  3830. }
  3831. else if(i == pbl)
  3832. {
  3833. pbufl[i]->next = pbufl[i-1];//与前面取得联系
  3834. pbufl[i-1]->last = pbufl[i];
  3835. if(blia)
  3836. {
  3837. pbufl[i]->last = blia;
  3838. blia->next = pbufl[i];
  3839. }
  3840. else
  3841. {
  3842. lcnbl->bli = pbufl[i];
  3843. }
  3844. }
  3845. else 
  3846. {
  3847. pbufl[i]->next = pbufl[i-1];
  3848. pbufl[i-1]->last = pbufl[i];
  3849. }
  3850. }
  3851. }
  3852. }
  3853. return ;
  3854. }
  3855. //for the unexpected dealing with the merge processing 
  3856. void vregendercnblunexpectedr(PVCNBL *rcnblin,PVCNBL lcnbl,PVBLI blistart,PVBLI bliend,
  3857. PVBLI pbufr[],int pbr,PVBLI *bliout)
  3858. {
  3859. PVCNBL rcnbl = *rcnblin;
  3860. PVBLI  blia  = NULL;
  3861. int i ;
  3862. if(rcnbl->flag == 1)
  3863. {
  3864. if(pbr == 0)
  3865. {
  3866. if(blistart == NULL)
  3867. {
  3868. rcnbl->bli = pbufr[0];
  3869. ASSERT(0);
  3870. }
  3871. else
  3872. {
  3873. pbufr[0]->last = blistart;
  3874. blistart->next = pbufr[0];
  3875. }
  3876. }
  3877. for(i = 0;i<= pbr;i++)
  3878. {
  3879. if(i == 0)
  3880. {
  3881. if(blistart == NULL)
  3882. {
  3883. rcnbl->bli = pbufr[i];
  3884. ASSERT(0);
  3885. }
  3886. else
  3887. {
  3888. pbufr[i]->last = blistart;
  3889. blistart->next = pbufr[i];
  3890. }
  3891. }
  3892. else if (i == pbr)
  3893. {
  3894. pbufr[i]->last = pbufr[i-1];//
  3895. pbufr[i-1]->next = pbufr[i];//
  3896. }
  3897. else 
  3898. {
  3899. pbufr[i]->last = pbufr[i-1];
  3900. pbufr[i-1]->next = pbufr[i];
  3901. }
  3902. }//return;
  3903. }
  3904. else
  3905. {
  3906. //above is the finding of the first/(last in sequential meaning) bli
  3907. blia = vfindimlimitedbli(blistart,2);
  3908. if(pbr == 0)
  3909. {
  3910. if(blistart == NULL)
  3911. {
  3912. rcnbl->bli = pbufr[0];
  3913. if(!blia){
  3914. pbufr[0]->next = blistart->next; 
  3915. ASSERT(0);
  3916. blistart->next->last = pbufr[0];
  3917. }//it never happens,if so it must be rewrited
  3918. ASSERT(0);
  3919. return;
  3920. }
  3921. else
  3922. {
  3923. pbufr[0]->last = blistart;//have been fixed 6-15p.m. 
  3924. blistart->next = pbufr[0];
  3925. pbufr[0]->next = blia;
  3926. blia->last = pbufr[0];
  3927. }
  3928. }
  3929. else{
  3930. for( i = 0; i<=pbr; i++)
  3931. {
  3932. if(i == 0)
  3933. {
  3934. if(blistart == NULL)
  3935. {
  3936. rcnbl->bli = pbufr[i];
  3937. ASSERT(0);//it never happens(?)6-15PM
  3938. }
  3939. else
  3940. {
  3941. blistart->next = pbufr[i];
  3942. pbufr[i]->last = blistart;
  3943. }
  3944. }
  3945. else if(i == pbr)
  3946. {
  3947. pbufr[i]->last = pbufr[i-1];
  3948. pbufr[i-1]->next = pbufr[i];//
  3949. if(blia)
  3950. {
  3951. pbufr[i]->next = blia;
  3952. blia->last = pbufr[i];
  3953. }
  3954. }
  3955. else 
  3956. {
  3957. pbufr[i]->last = pbufr[i-1];
  3958. pbufr[i-1]->next = pbufr[i];
  3959. }
  3960. }
  3961. }
  3962. }
  3963. return ;
  3964. }
  3965. //找到最近的一个交点，t/大小,blit/所处角平分线连的位子,lrflag/交于那边;
  3966. //bns input tfirst,mfirst,and out put tend and mend,
  3967. //startflag input the start place of 
  3968. //bisector,blil,blir out put... ,irflag out put....
  3969. //blil input the first lcnbl bli ,the blir input the first rcnbl
  3970. //blil and blif output the bli have been update according to the startflag
  3971. //lrflag out put the first intersect bli of cnbls.
  3972. //lrflag = 1 intersect first with lcnbl blil be regenerated
  3973. //lrflag = 2 rcnbl be regenerated
  3974. //lrflag = 0 all blir and blil be regenerated;
  3975. //lrflag = -1 no firstpoint been found;  
  3976. void vfindfirstpoint(PVCNBL rcnbl,PVCNBL lcnbl,PVBNS bns,int startflag,int directionflag,//input//startflag useless
  3977.  PVBLI *blil,PVBLI *blir,int *lrflag)//output
  3978.  // bli
  3979. {
  3980. ASSERT(rcnbl);ASSERT(lcnbl);
  3981. ASSERT(rcnbl->bli);ASSERT(lcnbl->bli);
  3982. //all are template useing parameters
  3983. double tl,tr,tfirst;
  3984. int    ml,mr,flagl,flagr;
  3985. int    mfirst;
  3986. double tmfirst,tml,tmr;
  3987. //
  3988. PVBLI blitl,blitr;
  3989. //
  3990. tfirst = bns->t1;
  3991. //I think this is the wrong statement
  3992. mfirst  = bns->m1;//bns have been the bisector of the validate bisector of lcnbl and rcnbl
  3993. tmfirst = tfirst * mfirst; 
  3994. //
  3995. if(rcnbl->flag==0 && lcnbl->flag==0)
  3996. {
  3997. //this function are writed
  3998. flagl = vgainintersectortl(lcnbl,rcnbl->cns,bns,startflag,directionflag,*blil,&tl,&ml,&blitl);//函数体中得保证有解（唯一）
  3999. flagr = vgainintersectortr(rcnbl,lcnbl->cns,bns,startflag,directionflag,*blir,&tr,&mr,&blitr);//函数体中得保证有解
  4000. if(0==flagl&&0==flagr)
  4001. {
  4002. *lrflag = -1;
  4003. return ;
  4004. }
  4005. else if (0==flagl&&flagr)
  4006. {
  4007. *blir = blitr;
  4008. bns->t2 = tr;
  4009. bns->m2 = mr;
  4010. *lrflag = 2;
  4011. return ;
  4012. }
  4013. else if (flagl && 0==flagr)
  4014. {
  4015. *blil = blitl;
  4016. bns->t2 = tl;
  4017. bns->m2 = ml;
  4018. *lrflag = 1;
  4019. return ;
  4020. }
  4021. tml = tl*ml; tmr = tr*mr;
  4022. if(fabs(tmfirst-tml)<ZERO||fabs(tmfirst-tmr)<ZERO)
  4023. {
  4024. ASSERT(0);//
  4025. }
  4026. else if(tmfirst-tml>ZERO && tmfirst-tmr>ZERO)
  4027. {
  4028. if(fabs(tmr-tml)<=ZERO)
  4029. {
  4030. bns->t2 = tl;
  4031. bns->m2 = ml;
  4032. *blil = blitl;
  4033. *blir = blitr;
  4034. *lrflag = 0;
  4035. }
  4036. else if(tmr-tml>ZERO)
  4037. {
  4038. bns->t2 = tr;
  4039. bns->m2 = mr;
  4040. *blir = blitr;
  4041. *lrflag = 2;
  4042. }
  4043. else
  4044. {
  4045. bns->t2 = tl;
  4046. bns->m2 = ml;
  4047. *blil = blitl;
  4048. *lrflag = 1;
  4049. }
  4050. }
  4051. else if(tmfirst-tml<-ZERO && tmfirst-tmr<-ZERO)
  4052. {
  4053. if(fabs(tmr-tml)<=ZERO)
  4054. {
  4055. bns->t2 = tl;
  4056. bns->m2 = ml;
  4057. *blil = blitl;
  4058. *blir = blitr;
  4059. *lrflag = 0;
  4060. }
  4061. else if(tmr-tml>ZERO)
  4062. {
  4063. bns->t2 = tl;
  4064. bns->m2 = ml;
  4065. *blil = blitl;
  4066. *lrflag = 1;
  4067. }
  4068. else
  4069. {
  4070. bns->t2 = tr;
  4071. bns->m2 = mr;
  4072. *blir = blitr;
  4073. *lrflag = 2;
  4074. }
  4075. }
  4076. else if((tmfirst-tml)*(tmfirst-tmr)<-ZERO)
  4077. {
  4078. if((tmfirst>=0 && tml>=0 )||( tmfirst<0 && tml<0 ))
  4079. {
  4080. bns->t2 = tl;
  4081. bns->m2 = ml;
  4082. *blil = blitl;
  4083. *lrflag = 1;
  4084. }
  4085. else if((tmfirst>=0 && tmr>=0 )||( tmfirst<0 && tmr<0 ))
  4086. {
  4087. bns->t2 = tr;
  4088. bns->m2 = mr;
  4089. *blir = blitr;
  4090. *lrflag =2;
  4091. }
  4092. else
  4093. ASSERT(0);//tfirst 在两者之间
  4094. }
  4095. }
  4096. else if(lcnbl->flag==1 && rcnbl->flag==0)
  4097. {
  4098. //如果flag==0应该有解
  4099. flagl = vgainintersectortr(rcnbl,lcnbl->cns,bns,startflag,directionflag,*blir,&tr,&mr,&blitr);//函数体中得保证有解
  4100. if(flagl == 0)
  4101. {
  4102. //AfxMessageBox("bisector meet with nothing ");
  4103. *lrflag = -1;
  4104. return;
  4105. }
  4106. tmr = tr*mr;
  4107. if(fabs(tmfirst-tmr)<ZERO)
  4108. ASSERT(0);
  4109. bns->t2 = tr;
  4110. bns->m2 = mr;
  4111. *blir = blitr;
  4112. *lrflag = 2;
  4113. }
  4114. else if(lcnbl->flag==0 && rcnbl->flag==1)
  4115. {//why I put the blil into blir
  4116. flagr = vgainintersectortl(lcnbl,rcnbl->cns,bns,startflag,directionflag,*blil,&tl,&ml,&blitl);//函数体中得保证有解
  4117. if(flagr == 0)
  4118. {
  4119. //AfxMessageBox("bisector meet with nothing");
  4120. *lrflag = -1;
  4121. return ;
  4122. }
  4123. tml = tl*ml;
  4124. if(fabs(tmfirst-tml)<ZERO)
  4125. ASSERT(0);
  4126. bns->t2 = tl;
  4127. bns->m2 = ml;
  4128. *blil = blitl;
  4129. *lrflag = 1;
  4130. }
  4131. else 
  4132. {
  4133. ASSERT(0);
  4134. }
  4135. }
  4136. //删除lcnbl中的角平分线，加入栈中的角平分线
  4137. //lcnbl is the main process-needed objector,blistart&bliend is the limitation of voronoi 
  4138. //diagram .pbufl[]and it mark pbl is the collection of all the bisector information need
  4139. //be inputed into lcnbl voronoi diagram;
  4140. //and we are sure that all bisectors have limitations.
  4141. void vregendercnbll(PVCNBL *lcnblin,PVCNBL rcnbl,PVBLI blistart,PVBLI bliend,
  4142. PVBLI pbufl[],int pbl,PVBLI *bliout)
  4143. {
  4144. if(pbl <= -1)//if no bli appears
  4145. {
  4146. if(blistart->bni->flag)
  4147. blistart->bni->flag = 0;
  4148. return ;
  4149. }
  4150. //
  4151. ASSERT(*lcnblin);ASSERT(blistart);ASSERT(bliend);ASSERT(rcnbl);
  4152. PVBLI  bli,blit,blia,blis,blie;
  4153. double tm,tm1,tm2;
  4154. double  t1,t2;
  4155. int  mvalue;
  4156. int i,flag1 = 0;
  4157. PVCNBL  lcnbl = *lcnblin ;
  4158. //gain blis;
  4159. if(pbufl[0]->clockwise == CW)
  4160. {
  4161. vgainintersectmvaluebns(blistart->bni->bns,
  4162. pbufl[0]->bni->bns,pbufl[0]->bni->bns->t2,&mvalue);
  4163. t1 = pbufl[0]->bni->bns->t2;
  4164. }
  4165. else
  4166. {
  4167. vgainintersectmvaluebns(blistart->bni->bns,
  4168. pbufl[0]->bni->bns,pbufl[0]->bni->bns->t1,&mvalue);
  4169. t1 = pbufl[0]->bni->bns->t1;
  4170. }
  4171. tm = t1 * mvalue;
  4172. tm1 = blistart->bni->bns->t1 * blistart->bni->bns->m1;
  4173. tm2 = blistart->bni->bns->t2 * blistart->bni->bns->m2;
  4174. //merge terminited,means the lcnbl and rcnbl meet in the place of t=0
  4175. //删去bisector
  4176. if(rcnbl->flag == 1 && lcnbl->flag == 1 && pbufl[pbl]->bni->bns->t2!=0)
  4177. {//make all bli out of in the buf  
  4178. if(pbl == 0)
  4179. {
  4180. pbufl[0]->clockwise *=-1;//I add it 6-15
  4181. lcnbl->bli = pbufl[0];
  4182. pbufl[0]->next = blistart;
  4183. if(blistart)
  4184. blistart->last = pbufl[0];
  4185. else ASSERT(0);
  4186. return;
  4187. }
  4188. for(i = pbl;i>=0;i--)
  4189. {
  4190. pbufl[i]->clockwise *=-1;//I add it 6-15 it cause me a lot of time
  4191. if(i == pbl)
  4192. {
  4193. lcnbl->bli = pbufl[i];
  4194. }
  4195. else if(i == 0)
  4196. {
  4197. pbufl[i]->last = pbufl[i+1];
  4198. pbufl[i+1]->next = pbufl[i];
  4199. pbufl[i]->next = blistart;
  4200. if(blistart)
  4201. blistart->last = pbufl[i];
  4202. else ASSERT(0);
  4203. }
  4204. else
  4205. {
  4206. pbufl[i]->last = pbufl[i+1];
  4207. pbufl[i+1]->next = pbufl[i];
  4208. }
  4209. }
  4210. return ;
  4211. }
  4212. //
  4213. if(rcnbl->flag == 1&&lcnbl->flag == 1 && pbufl[pbl]->bni->bns->t2!=0)
  4214. {
  4215. ASSERT(0);
  4216. }
  4217. if((CCW == blistart->clockwise && fabs(tm-tm2)<=ZERO) ||
  4218. (CW == blistart->clockwise && fabs(tm-tm1)<=ZERO))
  4219. {
  4220. blis = blistart;
  4221. }
  4222. else if((CCW == blistart->clockwise && fabs(tm-tm1)<=ZERO) ||
  4223. (CW == blistart->clockwise && fabs(tm-tm2)<=ZERO))
  4224. {
  4225. blis = blistart->last;
  4226. }
  4227. else if(tm-tm1>ZERO&&tm-tm2<-ZERO||(tm-tm2>ZERO&&tm-tm1<-ZERO))
  4228. {
  4229. blis = blistart->last;
  4230. if(blistart->clockwise == CCW)//modify the original
  4231. {
  4232. blistart->bni->bns->t1 = t1;
  4233. blistart->bni->bns->m1 = mvalue;
  4234. }
  4235. else
  4236. {
  4237. blistart->bni->bns->t2 = t1;
  4238. blistart->bni->bns->m2 = mvalue;
  4239. }
  4240. }
  4241. else ASSERT(0);
  4242. //when the bisector have meet nothing but it isn't wrong so have to be delt with
  4243. if(blistart->bni->flag)
  4244. {
  4245. if(blistart == blis)
  4246. {
  4247. blia = blistart->next;
  4248. }
  4249. else
  4250. {
  4251. blia = blistart;
  4252. }
  4253. vregendercnblunexpectedl(lcnblin,rcnbl,blia,bliend,pbufl,pbl,bliout);
  4254. /////
  4255. blistart->bni->flag = 0;
  4256. return;
  4257. }
  4258. //gain blie
  4259. if(pbufl[pbl]->clockwise ==CW)
  4260. {
  4261. t2 = pbufl[pbl]->bni->bns->t1;
  4262. vgainintersectmvaluebns(bliend->bni->bns,
  4263. pbufl[pbl]->bni->bns,pbufl[pbl]->bni->bns->t1,&mvalue);
  4264. }
  4265. else
  4266. {
  4267. t2 = pbufl[pbl]->bni->bns->t2;
  4268. vgainintersectmvaluebns(bliend->bni->bns,
  4269. pbufl[pbl]->bni->bns,pbufl[pbl]->bni->bns->t2,&mvalue);
  4270. }
  4271. tm = t2 * mvalue;
  4272. tm1 = bliend->bni->bns->t1 * bliend->bni->bns->m1;
  4273. tm2 = bliend->bni->bns->t2 * bliend->bni->bns->m2;
  4274. if((CCW == bliend->clockwise && fabs(tm-tm1) <= ZERO) ||
  4275. (CW == bliend->clockwise && fabs(tm-tm2) <= ZERO))
  4276. {
  4277. blie = bliend;
  4278. flag1 = 1;
  4279. }
  4280. else if((CCW == bliend->clockwise && fabs(tm-tm2)<=ZERO) ||
  4281. (CW == bliend->clockwise && fabs(tm-tm1)<=ZERO))
  4282. {
  4283. blie = bliend->next;
  4284. }
  4285. else if(tm-tm1>ZERO && tm-tm2<-ZERO || (tm-tm2>ZERO && tm-tm1<-ZERO))
  4286. {
  4287. blie = bliend->next;
  4288. if(bliend->clockwise == CCW)
  4289. {
  4290. bliend->bni->bns->t2 = t2;
  4291. bliend->bni->bns->m2 = mvalue;
  4292. }
  4293. else
  4294. {
  4295. bliend->bni->bns->t1 = t2;
  4296. bliend->bni->bns->m1 = mvalue;
  4297. }
  4298. }
  4299. else ASSERT(0);
  4300. //添上bisector from blifirst to bliend
  4301. bli = NULL;
  4302. for(i=0;i<=pbl;i++)
  4303. {
  4304. bli = pbufl[i];
  4305. bli->clockwise = -bli->clockwise;
  4306. //assign clockwise
  4307. //assign link info  ??
  4308. if(pbl == 0)//if there is only one besector in the voronoi diagram
  4309. {
  4310. if(blistart == blis)
  4311. {
  4312. if(blistart->next != NULL)
  4313. {
  4314. bli->next = blistart->next;
  4315. blistart->next->last = bli;
  4316. }
  4317. //
  4318. if(bliend == blie)
  4319. {
  4320. ASSERT(0);//the have the duplicited objector
  4321. }
  4322. else
  4323. {
  4324. bli->last = bliend;
  4325. bliend->next = bli;
  4326. }
  4327. }
  4328. else
  4329. {
  4330. bli->next = blistart;
  4331. blistart->last = bli;
  4332. if(bliend != blie)
  4333. {
  4334. bli->last = bliend;
  4335. bliend->next = bli;
  4336. }
  4337. else if(bliend == blie)
  4338. {
  4339. if(bliend->last !=NULL)
  4340. {
  4341. bli->last = bliend->last;
  4342. bliend->last->next = bli;
  4343. }
  4344. else{
  4345. lcnbl->bli = bli;
  4346. }
  4347. }
  4348. }
  4349. }
  4350. else //at least have two besector;
  4351. {
  4352. if(i==0)//Assign the first 
  4353. {
  4354. if(blistart == blis)
  4355. {
  4356. if(blistart->next != NULL)
  4357. {
  4358. bli->next = blistart->next;
  4359. blistart->next->last = bli;
  4360. }
  4361. }
  4362. else
  4363. {
  4364. bli->next = blistart;
  4365. blistart->last = bli;
  4366. }
  4367. blia = bli;
  4368. bli = NULL;
  4369. }
  4370. //assing the last;
  4371. else if(i==pbl)
  4372. {
  4373. //
  4374. if(bliend != blie)
  4375. {
  4376. bli->last = bliend;
  4377. bliend->next = bli;
  4378. }
  4379. else if(bliend == blie)
  4380. {
  4381. if(bliend->last !=NULL)
  4382. {
  4383. bli->last = bliend->last;
  4384. bliend->last->next = bli;
  4385. }
  4386. else{
  4387. lcnbl->bli = bli;
  4388. }
  4389. }
  4390. //
  4391. bli->next = blia;
  4392. blia->last = bli;
  4393. }
  4394. else//assign the middle objector
  4395. {
  4396. bli->next = blia;
  4397. blia->last = bli;
  4398. blia = bli;
  4399. }
  4400. }
  4401. bli = NULL;
  4402. }
  4403. //before delete the rebundant bisector we must find the next lcnbl first;
  4404. lcnbl = vfindcnbll(bliend->bni->othercns,lcnbl);//
  4405. //
  4406. bli = lcnbl->bli;
  4407. while(bli!=NULL)
  4408. {
  4409. if(bli->bni->bns == bliend->bni->bns)
  4410. break;
  4411. bli = bli->next;
  4412. }
  4413. ASSERT(bli);
  4414. *lcnblin = lcnbl;
  4415. *bliout = bli;
  4416. //delete rebundant bisector;information of bnses is left untouched
  4417. blit = blis;
  4418. if(blis == blie&&blis!=NULL)
  4419. {
  4420. delete blis;
  4421. return;
  4422. }
  4423. else if(blis == bliend || blie == blistart ) 
  4424. {
  4425. return;
  4426. }
  4427. else
  4428. {
  4429. while(blit != blie && blit!=NULL){
  4430. blia = blit->last;
  4431. vdeletebli(blit);//? I do not know whether I can delete all node including bns
  4432. blit = blia;
  4433. }
  4434. if(blit!=NULL)
  4435. {
  4436. if(flag1)
  4437. blit->bni->flag = 1;
  4438. else{
  4439. vdeletebli(blit);
  4440. }
  4441. }
  4442. return;
  4443. }
  4444. //
  4445. }//ok
  4446. //删除rcnbl中的角平分线，加入栈中的角平分线
  4447. void vregendercnblr(PVCNBL *rcnblin,PVCNBL lcnbl,PVBLI blistart,PVBLI bliend,
  4448. PVBLI pbufr[],int pbr,PVBLI *bliout)
  4449. {
  4450. if(pbr <= -1) return ;
  4451. ASSERT(*rcnblin);ASSERT(blistart);ASSERT(bliend);ASSERT(lcnbl);
  4452. PVBLI   bli,blit,blia,blis,blie;
  4453. double  tm,tm1,tm2;
  4454. double  t1,t2;
  4455. int     mvalue;
  4456. int     i;
  4457. PVCNBL   rcnbl = *rcnblin;
  4458. //删去bisector
  4459. //gain blis first;
  4460. if(pbufr[0]->clockwise == CW)
  4461. {
  4462. t1 = pbufr[0]->bni->bns->t2;
  4463. vgainintersectmvaluebns(blistart->bni->bns,
  4464. pbufr[0]->bni->bns,pbufr[0]->bni->bns->t2,&mvalue);
  4465. }
  4466. else
  4467. {
  4468. t1 = pbufr[0]->bni->bns->t1;
  4469. vgainintersectmvaluebns(blistart->bni->bns,
  4470. pbufr[0]->bni->bns,pbufr[0]->bni->bns->t1,&mvalue);
  4471. }
  4472. tm  = t1 * mvalue;
  4473. tm1 = blistart->bni->bns->t1 * blistart->bni->bns->m1;
  4474. tm2 = blistart->bni->bns->t2 * blistart->bni->bns->m2;
  4475. if(rcnbl->flag == 1&&lcnbl->flag ==1)
  4476. {
  4477. if(pbr == 0)
  4478. {
  4479. if(blistart)
  4480. {
  4481. blistart->next = pbufr[0];
  4482. pbufr[0]->last = blistart;
  4483. }
  4484. else 
  4485. {
  4486. rcnbl->bli = pbufr[0];
  4487. ASSERT(0);
  4488. }
  4489. return;
  4490. }
  4491. for(i=0;i<=pbr;i++)
  4492. {
  4493. if(i == 0)
  4494. {
  4495. if(blistart)
  4496. {
  4497. blistart->next = pbufr[i];
  4498. pbufr[i]->last = blistart;
  4499. }
  4500. else ASSERT(0);
  4501. }
  4502. else
  4503. {
  4504. pbufr[i]->last = pbufr[i-1];
  4505. pbufr[i-1]->next = pbufr[i];
  4506. }
  4507. }
  4508. return ;
  4509. }
  4510. if((CCW == blistart->clockwise && fabs(tm2-tm)<=ZERO) ||
  4511. (CW == blistart->clockwise && fabs(tm1-tm)<=ZERO))
  4512. {
  4513. blis = blistart->next;
  4514. }
  4515. else if((CCW == blistart->clockwise && fabs(tm1-tm)<=ZERO) ||
  4516. (CW == blistart->clockwise && fabs(tm2-tm)<=ZERO))
  4517. {
  4518. blis = blistart;
  4519. }
  4520. else if(tm-tm1>ZERO&&tm-tm2<-ZERO||(tm-tm2>ZERO&&tm-tm1<-ZERO))
  4521. {
  4522. blis = blistart->next;
  4523. if(blistart->clockwise == CCW)
  4524. {
  4525. blistart->bni->bns->t2 = t1;
  4526. blistart->bni->bns->m2 = mvalue;
  4527. }
  4528. else
  4529. {
  4530. blistart->bni->bns->t1 = t1;
  4531. blistart->bni->bns->m1 = mvalue;
  4532. }
  4533. }
  4534. else ASSERT(0);
  4535. if(blistart->bni->flag)
  4536. {
  4537. if(blistart == blis)
  4538. {
  4539. blia = blistart->last;
  4540. }
  4541. else
  4542. {
  4543. blia = blistart;
  4544. }
  4545. vregendercnblunexpectedr(rcnblin,lcnbl,blia,bliend,pbufr,pbr,bliout);
  4546. /////
  4547. blistart->bni->flag = 0;
  4548. return;
  4549. }
  4550. //gain blie
  4551. if(pbufr[pbr]->clockwise == CW)
  4552. {
  4553. t2 = pbufr[pbr]->bni->bns->t1;
  4554. vgainintersectmvaluebns(bliend->bni->bns,
  4555. pbufr[pbr]->bni->bns,pbufr[pbr]->bni->bns->t1,&mvalue);
  4556. }
  4557. else
  4558. {
  4559. t2 = pbufr[pbr]->bni->bns->t2;
  4560. vgainintersectmvaluebns(bliend->bni->bns,
  4561. pbufr[pbr]->bni->bns,pbufr[pbr]->bni->bns->t2,&mvalue);
  4562. }
  4563. tm = t2 * mvalue;
  4564. tm1 = bliend->bni->bns->t1 * bliend->bni->bns->m1;
  4565. tm2 = bliend->bni->bns->t2 * bliend->bni->bns->m2;
  4566. if((CCW == bliend->clockwise && fabs(tm-tm2)<=ZERO) ||
  4567. (CW == bliend->clockwise && fabs(tm-tm1)<=ZERO))
  4568. {
  4569. blie = bliend;
  4570. }
  4571. else if((CCW == bliend->clockwise && fabs(tm-tm1)<=ZERO) ||
  4572. (CW == bliend->clockwise && fabs(tm-tm2)<=ZERO))
  4573. {
  4574. blie = bliend->last;
  4575. }
  4576. else if(tm-tm1>ZERO&&tm-tm2<-ZERO||(tm-tm2>ZERO&&tm-tm1<-ZERO))
  4577. {
  4578. blie = bliend->last;
  4579. if(bliend->clockwise == CCW)
  4580. {
  4581. bliend->bni->bns->t1 = t2;
  4582. bliend->bni->bns->m1 = mvalue;
  4583. }
  4584. else
  4585. {
  4586. bliend->bni->bns->t2 = t2;
  4587. bliend->bni->bns->m2 = mvalue;
  4588. }
  4589. }
  4590. else ASSERT(0);
  4591. //below is the dealing with the special case.
  4592. //添上bisector from blifirst to bliend
  4593. bli = NULL;
  4594. for(i=0;i<=pbr;i++)
  4595. {
  4596. bli = pbufr[i];
  4597. //assign clockwise
  4598. //assign link info  ??
  4599. if(pbr == 0)//if there is only one besector in the voronoi diagram
  4600. {
  4601. if(blistart == blis)
  4602. {
  4603. if(blistart->last == NULL)
  4604. {
  4605. rcnbl->bli = bli;//bli->last=NULL;bli->next=NULL;
  4606. }
  4607. else
  4608. {
  4609. bli->last = blistart->last;
  4610. blistart->last->next = bli;
  4611. }
  4612. //
  4613. if(bliend == blie)
  4614. {
  4615. ASSERT(0);//the have the duplicited objector
  4616. }
  4617. else
  4618. {
  4619. bli->next = bliend;
  4620. bliend->last = bli;
  4621. }
  4622. }
  4623. else
  4624. {
  4625. bli->last = blistart;
  4626. blistart->next = bli;
  4627. if(bliend != blie)
  4628. {
  4629. bli->next = bliend;
  4630. bliend->last = bli;
  4631. }
  4632. else if(bliend == blie)
  4633. {
  4634. if(bliend->next !=NULL)
  4635. {
  4636. bli->next = bliend->next;
  4637. bliend->next->last = bli;
  4638. }
  4639. }
  4640. }
  4641. }
  4642. else //at least have two besector;
  4643. {
  4644. if(i == 0)//Assign the first 
  4645. {
  4646. if(blistart == blis)
  4647. {
  4648. if(blistart->last == NULL)
  4649. {
  4650. rcnbl->bli = bli;//bli->last=NULL;bli->next=NULL;
  4651. }
  4652. else
  4653. {
  4654. bli->last = blistart->last;
  4655. blistart->last->next = bli;
  4656. }
  4657. }
  4658. else
  4659. {
  4660. bli->last = blistart;
  4661. blistart->next = bli;
  4662. }
  4663. blia = bli;
  4664. bli = NULL;
  4665. }
  4666. //assing the last;
  4667. else if(i == pbr)
  4668. {
  4669. //
  4670. if(bliend != blie)
  4671. {
  4672. bli->next = bliend;
  4673. bliend->last = bli;
  4674. }
  4675. else if(bliend == blie)
  4676. {
  4677. if(bliend->next !=NULL)
  4678. {
  4679. bli->next = bliend->next;
  4680. bliend->next->last = bli;
  4681. }
  4682. }
  4683. //
  4684. bli->last = blia;
  4685. blia->next = bli;
  4686. }
  4687. else//assign the middle objector
  4688. {
  4689. bli->last = blia;
  4690. blia->next = bli;
  4691. blia = bli;
  4692. }
  4693. }
  4694. bli = NULL;
  4695. }
  4696. //before deleter the rebundant bisector we must assignt the rcnble and bliout first;
  4697. rcnbl = vfindcnblr(bliend->bni->othercns,rcnbl);//
  4698. //
  4699. bli = rcnbl->bli;
  4700. while(bli != NULL)
  4701. {
  4702. if(bli->bni->bns == bliend->bni->bns)
  4703. break;
  4704. bli = bli->next;
  4705. }
  4706. ASSERT(bli);
  4707. *rcnblin = rcnbl;
  4708. *bliout = bli;
  4709. //delete rebundant bisector;information of bnses is left untouched
  4710. blit = blis;
  4711. if(blis == blie&&blis!=NULL)
  4712. {
  4713. delete blis;
  4714. return;
  4715. }
  4716. else if( blis == bliend ) 
  4717. {
  4718. return;
  4719. }
  4720. else
  4721. {
  4722. while(blit!=blie && blit!=NULL){
  4723. blia = blit->next;
  4724. vdeletebli(blit);//? I do not know whether I can delete all node including bns
  4725. blit = blia;
  4726. }
  4727. if(blit!=NULL)
  4728. vdeletebli(blit);
  4729. return;
  4730. }
  4731. //
  4732. }//ok?
  4733. //find intersection t;and the label of bli;
  4734. // blif is the first bli of lcnbl (**not rcnbl**)
  4735. // bli output the first bli of lcnbl regenerted.
  4736. // bns input the the bisector of lcnbl and rcns,because(???)
  4737. // the bisector must be gennerated in the first processing
  4738. //求得角平分线与左边沃诺图区的交点
  4739. //是否需要传入bns?//如果没有交点，返回0；否则返回1
  4740. int vgainintersectortl(PVCNBL lcnbl,PVCNS rcns,PVBNS bns,int startflag,int directionflag,PVBLI blif,double *t,int *m,PVBLI *bli)
  4741. {
  4742. //如果与一条边有两个"有效"交点，只取一个最近点。
  4743. ASSERT(rcns);ASSERT(lcnbl);
  4744. ASSERT(lcnbl->flag!=1);
  4745. ASSERT( blif );
  4746. //
  4747. PVCNS cns;
  4748. PVBLI blig;
  4749. int i,flag1,flag2;
  4750. double tg[2];
  4751. int   mm[2],mvalue;
  4752. int tmlabel = 0;
  4753. //
  4754. double tmfirst = bns->t1 * bns->m1;//how about the validation of m1?
  4755. //                                 //is m1 belong to bns?looking into it afterwards
  4756. blig = blif;
  4757. cns  = blig->bni->othercns;
  4758. /*
  4759. vgainintersect(lcnbl->cns,rcns,cns,&i,tg);
  4760. if(i == 2)//有可能与同一条角平分线有两个交点???
  4761. {
  4762. return 1;
  4763. }
  4764. */
  4765. blig = blig->last;
  4766. int flag = 1;
  4767. while0( blig && flag)
  4768. {
  4769. cns = blig->bni->othercns;
  4770. vgainintersect(lcnbl->cns,rcns,cns,&i,tg);//????
  4771. if(i == 1)
  4772. {
  4773. if(tg[0] - bns->tmin<-ZERO)
  4774. {
  4775. blig = blig->last;
  4776. continue;
  4777. }
  4778. }
  4779. else if(i==2)
  4780. {
  4781. if(tg[0]-bns->tmin < -ZERO && tg[1] - bns->tmin < -ZERO)
  4782. {
  4783. blig = blig->last;
  4784. continue;
  4785. }
  4786. else if(tg[0] - bns->tmin < -ZERO)
  4787. {
  4788. i = 1;
  4789. tg[0] = tg[1];
  4790. }
  4791. else if(tg[1] - bns->tmin < -ZERO)
  4792. {
  4793. i = 1;
  4794. }
  4795. }
  4796. if(i == 0){
  4797. blig = blig->last;
  4798. continue;
  4799. }
  4800. else if(i == 1)
  4801. {
  4802. vgainintersectmvaluebns(bns,blig->bni->bns,tg[0],1,&mvalue);
  4803. mm[0] = mvalue;
  4804. //
  4805. vgainintersectmvaluebns(blig->bni->bns,bns,tg[0],&mvalue);
  4806. flag1 = vjudgetheinbns(blig->bni->bns,tg[0],mvalue);
  4807. if(flag1 == 0)
  4808. {
  4809. blig = blig->last;
  4810. continue;
  4811. }
  4812. else if(flag1 != 0)
  4813. {
  4814. if((tg[0]*mm[0] - tmfirst)*directionflag>=0)
  4815. {//this statement can confirm t*m is in validative position against tmfirst;
  4816. *bli = blig;
  4817. *t = tg[0];
  4818. *m = mm[0];
  4819. flag = 0;
  4820. }
  4821. else 
  4822. {
  4823. blig = blig->last;
  4824. continue;
  4825. }
  4826. }
  4827. }
  4828. else if(i==2)
  4829. {
  4830. vgainintersectmvaluebns(bns,blig->bni->bns,tg[0],&mvalue);
  4831. mm[0] = mvalue;
  4832. vgainintersectmvaluebns(bns,blig->bni->bns,tg[1],&mvalue);
  4833. mm[1] = mvalue;
  4834. //
  4835. vgainintersectmvaluebns(blig->bni->bns,bns,tg[0],&mvalue);
  4836. flag1 = vjudgetheinbns(blig->bni->bns,tg[0],mvalue);
  4837. //
  4838. vgainintersectmvaluebns(blig->bni->bns,bns,tg[1],&mvalue);
  4839. flag2 = vjudgetheinbns(blig->bni->bns,tg[1],mvalue);
  4840. if(0 == flag1 ) 
  4841. {
  4842. if(0 == flag2)
  4843. {
  4844. blig = blig->last;
  4845. continue;
  4846. }
  4847. else if(0 != flag2)
  4848. {
  4849. if((tg[1]*mm[1] - tmfirst)*directionflag>=0)
  4850. {
  4851. *bli = blig;
  4852. *t = tg[1];
  4853. *m = mm[1];
  4854. flag = 0;
  4855. }
  4856. else
  4857. {
  4858. blig = blig->last;
  4859. continue;
  4860. }
  4861. }
  4862. }
  4863. else if(flag1 != 0 )
  4864. {
  4865. if(0 == flag2)
  4866. {
  4867. if((tg[0]*mm[0] - tmfirst)*directionflag>=0){
  4868. *bli = blig;
  4869. *t = tg[0];
  4870. *m = mm[0];
  4871. flag = 0;
  4872. }
  4873. else {
  4874. blig =blig->last;
  4875. continue;
  4876. }
  4877. }
  4878. else if(0 != flag2)
  4879. {
  4880. double tg1,tg2;
  4881. tg1 = tg[0]*mm[0];
  4882. tg2 = tg[1]*mm[1];
  4883. if((tg1-tmfirst)*directionflag>=0)
  4884. {
  4885. if((tg2-tmfirst)*directionflag>=0)
  4886. {
  4887. if((tg1-tg2)*directionflag>=0)
  4888. {
  4889. tg[0] = tg[1];
  4890.         mm[0] = mm[1];
  4891. }
  4892. /*else
  4893. {tg[0]=tg[0];mm[0]=mm[0];//so it can be left out
  4894. }*/
  4895. }
  4896. /*else 
  4897. {
  4898. }*/
  4899. }
  4900. else 
  4901. {
  4902. if((tg2-tmfirst)*directionflag>=0)
  4903. {
  4904. tg[0] = tg[1];
  4905.         mm[0] = mm[1];
  4906. }
  4907. else 
  4908. {
  4909. blig = blig->last;
  4910. continue;
  4911. }
  4912. }
  4913. *bli = blig;
  4914. *t = tg[0];
  4915. *m = mm[0];
  4916. flag = 0;
  4917. }
  4918. //flag = 0;
  4919. }
  4920. }
  4921. blig = blig->last;
  4922. }
  4923. if(flag == 1){
  4924. //AfxMessageBox("you have counter no intersector,so you have to return and leave the processing to the uper functions");
  4925. return 0;
  4926. }//
  4927. return 1;
  4928. }
  4929. //求得角平分线与右边沃诺图区的交点
  4930. int vgainintersectortr(PVCNBL rcnbl,PVCNS lcns,PVBNS bns,int startflag,int directionflag,PVBLI blif,double *t,int *m,PVBLI *bli)
  4931. {
  4932. //如果与一条边有两个交点，只取一个最近点。
  4933. ASSERT(lcns);ASSERT(rcnbl);
  4934. ASSERT(rcnbl->flag!=1);
  4935. ASSERT(blif);
  4936. //
  4937. PVCNS cns;
  4938. PVBLI blig;
  4939. int i,flag1,flag2;
  4940. double tg[2],tmfirst,dtemp;
  4941. int   mm[2],mvalue;
  4942. //
  4943. *bli=NULL;
  4944. tmfirst = bns->m1*bns->t1;
  4945. //
  4946. blig = blif;
  4947. //
  4948. blig = blif->next;
  4949. int flag = 1;
  4950. while( blig && flag)
  4951. {
  4952. cns = blig->bni->othercns;
  4953. vgainintersect(rcnbl->cns,lcns,cns,&i,tg);//
  4954. if(i == 0){
  4955. blig = blig->next;
  4956. continue;
  4957. }
  4958. else if(i == 1)
  4959. {
  4960. dtemp = tg[0];
  4961. flag1 = vjudgetheinbns(blig->bni->bns,dtemp,1);
  4962. flag2 = vjudgetheinbns(blig->bni->bns,dtemp,-1);
  4963. if(flag1 == 0&&flag2 == 0)
  4964. {
  4965. blig = blig->next;
  4966. continue;
  4967. }
  4968. if(flag1&&flag2)
  4969. {
  4970. mvalue = -1;
  4971. vgainintersectmvaluebns(bns,blig->bni->bns,&dtemp,1,&mvalue);
  4972. mm[0] = mvalue;
  4973. vgainintersectmvaluebns(blig->bni->bns,bns,&dtemp,&mvalue);
  4974. flag1 = vjudgetheinbns(blig->bni->bns,dtemp,mvalue);
  4975. }
  4976. else{
  4977. if(flag1)mvalue = 1;
  4978. if(flag2)mvalue = -1;
  4979. }
  4980. dtemp = tg[0];
  4981. vgainintersectmvaluebns(bns,blig->bni->bns,&dtemp,1,&mvalue);
  4982. mm[0] = mvalue;
  4983. vgainintersectmvaluebns(blig->bni->bns,bns,&dtemp,&mvalue);
  4984. flag1 = vjudgetheinbns(blig->bni->bns,dtemp,mvalue);
  4985. }
  4986. else if(i==2)
  4987. {
  4988. }
  4989. blig=blig->next;//this if the only diffirence between vgainbisectortr
  4990.                 //and vgainbisectortl;
  4991. }
  4992. if(flag == 1){
  4993. //AfxMessageBox("you have counter no intersector,so you have to return and leave the processing to the uper functions");
  4994. return 0;
  4995. }//
  4996. return 1;
  4997. }
  4998. //.....................................................................
  4999. void vmergetwoprofile(PVPL pl,PVPL pr,PVPL *vpl)
  5000. {
  5001. ASSERT(pl);ASSERT(pr);ASSERT(pl->eplf);ASSERT(pl->splf);
  5002. ASSERT(pr->splf);ASSERT(pr->eplf);
  5003. //template used 
  5004. PVCNBL  lcnbl,rcnbl,tlcnbl,trcnbl,cnbl=NULL;
  5005. PVBLI   bli;
  5006. PVBNS   bns = NULL;
  5007. int     clockwiseflag = 1;
  5008. int     directionflag = 0;
  5009. //initial
  5010. int     mfirst = 1;
  5011. int     mblis  = 1;//mblis = ?
  5012. double  tfirst = 0;
  5013. int     startflag = 0;//=0,from l and r,=1 start from l,=2  start from r only
  5014. //
  5015. PVBLI   blir,blil;
  5016. PVBLI   blistr,blistl;
  5017. //flag tab
  5018. double  mtemp;
  5019. int     lrflag;
  5020. //stack
  5021. PVBLI pbufl[40],pbufr[40];//栈
  5022. int   pbl = -1, pbr = -1;
  5023. //
  5024. tlcnbl = pl->splf->scnbl;
  5025. trcnbl = pr->eplf->ecnbl;
  5026. //
  5027. lcnbl = tlcnbl->ccw; //leave the point segment out
  5028. rcnbl = trcnbl->cw;  //leave the point segment out
  5029. lcnbl->cw = rcnbl;
  5030. rcnbl->ccw = lcnbl;
  5031. //vdeletevendpointcnbl(tlcnbl);
  5032. //vdeletevendpointcnbl(trcnbl); //flag=1 mean the pointsegment for ending
  5033. //initial
  5034. blil = lcnbl->bli;
  5035. while(blil->next!=NULL)
  5036. {
  5037. blil = blil->next;
  5038. }
  5039. blir = rcnbl->bli;
  5040. blistl = blil;
  5041. blistr = blir;
  5042. //
  5043. int iflag=1;
  5044. while(iflag)
  5045. {
  5046. if(!(1==rcnbl->flag && 1==lcnbl->flag))// if not all met the end of cnbl node.
  5047. {
  5048. bns = NULL;
  5049. vgainbisector(lcnbl->cns,rcnbl->cns,&bns);//关键的函数,可以是无穷函数
  5050. //放入角平分线作为参数传入bns不能释放
  5051. if(bns == NULL)     //只有终止时才会有空或,交点到无穷远
  5052. {
  5053. return ; //应该得到一条无限的角平分线,并结束缝合
  5054. }//it is impossible
  5055. else
  5056. {
  5057. bns->t1 = tfirst;//I think/wonder the statement can be delete safely 
  5058. if( pbl == -1  )//如果两边都空或左空
  5059. {
  5060. vgainintersectmvaluebns(bns,blistl->bni->bns,&tfirst,mblis,&mfirst);
  5061. bns->m1 = mfirst;
  5062. bns->t1 = tfirst;
  5063. directionflag = vfinddirection(blil,bns,tfirst,mfirst);
  5064. }
  5065. else if(pbr == -1 )//右空
  5066. {
  5067. vgainintersectmvaluebns(bns,blistr->bni->bns,&tfirst,mblis,&mfirst);
  5068. bns->m1 = mfirst;
  5069. bns->t1 = tfirst;
  5070. directionflag = vfinddirection(blir,bns,tfirst,mfirst);
  5071. }
  5072. }
  5073. //give the vfindfirstpoint a direction
  5074. ASSERT(directionflag);
  5075. //
  5076. //找到最近的一个交点，t/大小,blit/所处角平分线连的位子,lrflag/交于那边;
  5077. vfindfirstpoint(rcnbl,lcnbl,bns,startflag,directionflag,//VIF(very impotant function)
  5078. &blil,&blir ,&lrflag );//i=0 none intersect,i=1 left,i=2,right;
  5079. //对tfirst进行赋值运算//可行
  5080. if(lrflag == -1)//there aren't any intersect point meet the needs
  5081. {//应有特殊处理//modified in 6-17
  5082. bli = vmallocbli();
  5083. bli->bni = vmallocbni();
  5084. bli->bni->bns = bns;
  5085. if(directionflag == CCW)
  5086. {
  5087. bli->bni->bns->m2 = 1;
  5088. clockwiseflag = 1;
  5089. }
  5090. else if(directionflag == CW)
  5091. {
  5092. bli->bni->bns->m2 = -1;
  5093. clockwiseflag = -1;
  5094. }
  5095. //
  5096. pbl++;
  5097. pbufl[pbl] = bli;
  5098. bli->bni->selfcns = lcnbl->cns;
  5099. bli->bni->othercns = rcnbl->cns;
  5100. bli->clockwise = clockwiseflag;
  5101. bli = NULL;
  5102. //
  5103. bli = vmallocbli();
  5104. bli->bni = vmallocbni();
  5105. bli->bni->bns = bns;
  5106. pbr++;
  5107. pbufr[pbr] = bli;
  5108. bli->bni->selfcns = rcnbl->cns;
  5109. bli->bni->othercns = lcnbl->cns;
  5110. bli->clockwise = clockwiseflag;
  5111. bli = NULL;
  5112. //
  5113. *vpl = pl;
  5114. pl->ptype = VCOMMON;
  5115. blistr->bni->flag = 1;
  5116. blistl->bni->flag = 1;//bni->flag have left for the special processing
  5117. vregendercnblr(&rcnbl,lcnbl,blistr,blir,pbufr,pbr,&bli);//
  5118. vregendercnbll(&lcnbl,rcnbl,blistl,blil,pbufl,pbl,&bli);//
  5119. pl->splf->scnbl = pr->splf->scnbl; 
  5120. pl->eplf->ecnbl = pl->eplf->ecnbl;
  5121. return;
  5122. }
  5123. //
  5124. tfirst = bns->t2;
  5125. //在此之前，bns还没有被排列，即bli中的clockwise没有被更新
  5126. bli = vmallocbli();
  5127. bli->bni =vmallocbni();
  5128. bli->bni->bns = bns;
  5129. clockwiseflag = vgetclockwisebli(bli);
  5130. //
  5131. //
  5132. pbl++;
  5133. pbufl[pbl] = bli;
  5134. bli->bni->selfcns = lcnbl->cns;
  5135. bli->bni->othercns = rcnbl->cns;
  5136. bli->clockwise = clockwiseflag;
  5137. bli = NULL;
  5138. //
  5139. bli = vmallocbli();
  5140. bli->bni = vmallocbni();
  5141. bli->bni->bns = bns;
  5142. pbr++;
  5143. pbufr[pbr] = bli;
  5144. bli->bni->selfcns = rcnbl->cns;
  5145. bli->bni->othercns = lcnbl->cns;
  5146. bli->clockwise = clockwiseflag;
  5147. bli = NULL;
  5148. //bns = NULL;//in this time the bns can't be put zero
  5149. //压栈
  5150. //
  5151. if(lrflag == 1)//先与左边相交
  5152. {
  5153. //删除lcnbl中的角平分线，加入栈中的角平分线
  5154. vregendercnbll(&lcnbl,rcnbl,blistl,blil,pbufl,pbl,&bli);//?
  5155. pbl=-1;//清空栈
  5156. //找到blil的另一部分cns对应的cnbl节点
  5157. startflag = 1;
  5158. //
  5159. blil = blistl = bli;
  5160. mblis = bli->bni->bns->m2;
  5161. bli = NULL;
  5162. }   
  5163. else if(lrflag == 2) //intersect with right
  5164. {
  5165. vregendercnblr(&rcnbl,lcnbl,blistr,blir,pbufr,pbr,&bli);//?
  5166. pbr = -1;//清空栈
  5167. //清空并更新
  5168. startflag = 2;
  5169. //
  5170. blir = blistr = bli;
  5171. mblis = bli->bni->bns->m1;
  5172. }
  5173. else if(lrflag == 0)//intersect with two all simultaniously
  5174. {
  5175. cnbl = rcnbl;
  5176. vregendercnblr(&rcnbl,lcnbl,blistr,blir,pbufr,pbr,&bli);//
  5177. blir = blistr = bli;
  5178. bli  = NULL;
  5179. //
  5180. vregendercnbll(&lcnbl,cnbl,blistl,blil,pbufl,pbl,&bli);//
  5181. blil = blistl = bli;
  5182. mblis = bli->bni->bns->m2;
  5183. bli = NULL;
  5184. //
  5185. pbr=-1;pbl=-1;//清空栈
  5186. //请空并更新
  5187. startflag = 0;
  5188. }
  5189. }
  5190. //
  5191. else if(1==rcnbl->flag&&1==lcnbl->flag)//both left and right  end
  5192. {
  5193. *vpl = pl;
  5194. pl->ptype = VCOMMON;
  5195. if(tfirst<=ZERO)//this is the end of the whole merge processing.
  5196. {
  5197. tlcnbl = lcnbl->cw;
  5198. trcnbl = rcnbl->ccw;
  5199. tlcnbl->ccw = trcnbl;
  5200. trcnbl->cw  = tlcnbl;
  5201. vdeletevendpointcnbl(lcnbl);
  5202. vdeletevendpointcnbl(rcnbl);
  5203. pl->splf->scnbl = trcnbl;
  5204. pl->eplf->ecnbl = tlcnbl;
  5205. }
  5206. else
  5207. {
  5208. vregendercnblr(&rcnbl,lcnbl,blistr,blir,pbufr,pbr,&bli);//
  5209. vregendercnbll(&lcnbl,rcnbl,blistl,blil,pbufl,pbl,&bli);//
  5210. pbr=-1;pbl=-1;//清空栈
  5211. pl->splf->scnbl = pr->splf->scnbl; 
  5212. pl->eplf->ecnbl = pl->eplf->ecnbl;
  5213. }
  5214. return;
  5215. }
  5216.     }
  5217. }
  5218. //计算卧诺图
  5219. void  vmergesingleprofile(PVPL profile)
  5220. {
  5221. ASSERT(profile);
  5222. PVPL pl,pr,midprofile;
  5223. PVBNS bns;
  5224. PVCNBL cnbl;
  5225. PVBLI bli;
  5226. int i = 0;
  5228. if(SINGLE == profile->ptype)//判断是否是叶子/单树枝ok
  5229. {
  5230. vgainsingleplfbli(profile->eplf);//给叶子赋值//ok perhaps
  5231. if(0)
  5232. {
  5233. cnbl = profile->eplf->scnbl;
  5234. do{
  5235. bli = cnbl->bli;
  5236. do{
  5237. vdisplaysinglebi(*bli->bni->bns,RGB(0,0,255));
  5238. AfxMessageBox("show the result");
  5239. bli = bli->next;
  5240. }while(bli);
  5241. cnbl = cnbl->ccw;
  5242. }while(cnbl!=profile->eplf->ecnbl);
  5243. }
  5244. return;
  5245. }
  5246. vdivideprofiletwo(profile,&pl,&pr);//均分树枝；//ok
  5247. vmergesingleprofile(pl);
  5248. if(i)
  5249. {
  5250. vdisplayplv(*pl);
  5251. AfxMessageBox("show the result");
  5252. }
  5253. vmergesingleprofile(pr);
  5254. if(i)
  5255. {
  5256. vdisplayplv(*pr);
  5257. AfxMessageBox("show the result");
  5258. }
  5259. vmergetwoprofile(pl,pr,&midprofile);//缝合枝枝叶叶waiting
  5260. myflag++;
  5261. if(i)
  5262. {
  5263. vdisplayplv(*midprofile);
  5264. AfxMessageBox("show the result");
  5265. }
  5266. profile->eplf  = midprofile->eplf ;
  5267. profile->splf  = midprofile->splf ;
  5268. profile->ptype = midprofile->ptype;
  5269. }
  5270. /*the end*/