雙向交演算法

『壹』 三角曲面相交特性

用三角曲面表示的兩張簡單曲面可能交於若干交線、若干交點與若干交面。下面將介紹兩張簡單曲面的交集的特性。

6.1.1.1 兩個空間三角形的關系與求交演算法及程序

6.1.1.1.1 空間三角形的關系

簡單曲面是若干三角形面片的集合，因此，簡單曲面的交由若干三角形面片對的交決定。兩個空間三角形面片的關系包括交於一點、交於一條線段、部分或全部重合、分離。圖6.1給出了兩個空間三角形可能存在的相交關系。

從圖6.1可以看出兩個三角形相交具有如下特徵:

(1)如果兩個三角形交於一點，那麼交點可能是一個或兩個三角形的頂點，或者兩個三角形只交於一條邊上。對於兩張曲面而言，這種交點可能是獨立的，也可能位於其他交線段上。如果交點位於其他交線上，則一定能在計算其他三角形對的交線時獲得。

(2)如果兩個三角形交於一條線段，那麼交線段的每個端點一定位於兩個三角形的某條邊上。在計算完所有三角形對的交線後，可以利用這個特點進行交線追蹤。

(3)如果兩個三角形完全或部分重合，那麼重合區域的邊界一定位於兩個三角形的邊界上。

6.1.1.1.2 空間三角形的求交演算法與程序

三角曲面求交運算最終歸結為空間三角形的求交運算，因此，三角形求交演算法的效率與正確性對曲面求交效率與結果影響顯著。下面介紹兩種求交演算法。

演算法一:先計算兩個三角形所在平面的交線，然後分別計算出該交線與兩個三角形邊的交點，再根據交點在交線上的位置直接確定交線段。如圖6.2所示，三角形Δ₁與Δ₂所在平面的交線為L，L與Δ₁的交點為a與b，L與Δ₂的交點為c與d。根據4個交點在L上的位置可以直接判斷出Δ₁與Δ₂的交線段為cb。

圖6.1 兩個空間三角形可能存在的相交關系

三維地質建模方法及程序實現

三維地質建模方法及程序實現

6.1.1.2 簡單曲面的相交特徵

兩張簡單曲面s₁與s₂之間可能交於一條或若干條交線，或者交於若干交點，也可能存在若幹部分重合。簡單曲面的交集具有如下特徵:

(1)s₁與s₂之間的每條交線由若干線段順序連接而成，每條線段同時位於s₁與s₂的一個三角形上。由於簡單曲面是由三角形組成的，曲面之間的交線實際上就是分別來自兩張曲面的三角形之間的交線段的集合，因此，每條交線段一定同時位於兩張曲面的一個三角形上。

(2)s₁與s₂之間每條交線是連續的，相當於一條封閉或不封閉的簡單弧。每條交線只存在兩種可能:交線是首尾相連的封閉環，或者交線的兩個端點分別位於s₁或s₂的某條邊界線上。根據這個特點，可以判斷一條交線上的所有交線段是否全部被搜索到。

(3)s₁與s₂之間可能存在若干獨立的交點，任意兩個獨立的交點之間的連線不位於其他交線上。當兩張簡單曲面之間出現獨立交點時，應在曲面重構後保證交點位於曲面網格的結點上，或者適當微調曲面，消除獨立交點。

(4)s₁與s₂之間可能存在若干獨立的重合面，每個重合面均有一個封閉的外邊界與若干個內邊界。重合面的邊界均位於s₁與s₂上三角形的邊上。在地質模型中，地層尖滅是經常遇到的地質現象，地層尖滅的位置就會出現地層界面部分重合。

『貳』 求兩個集合交集的演算法

我這里有一個很強的，是以前的作業，功能有很多！

有問題來找小斌
QQ：504449327

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

typedef struct NodeType
{
ElemType data;
struct NodeType *next;
} NodeType,*LinkType;

typedef struct
{
LinkType head,tail;
int size;
}OrderedList;

ElemType a[100]="magazine";
ElemType b[100]="paper";
OrderedList L1,L2,L3;

Status MakeNode(LinkType &p,ElemType e)/*函數功能，創建一個結點，用p指向它，並把e的值賦給date*/
{
p=(LinkType)malloc(sizeof(NodeType));
if(!p)
return FALSE;
p->data=e;
p->next=NULL;
return TRUE;
}

Status InitList(OrderedList &L) /*函數功能，建立空棧*/
{
if(MakeNode(L.head,' '))
{
L.tail=L.head;
L.size=0;
return TRUE;
}
else
{
L.head=NULL;
return FALSE;
}
}
Status LocateElem(OrderedList L, ElemType e, LinkType &p)
{
NodeType *pre;
if(L.head) /*棧建立成功*/
{
pre=L.head;
p=pre->next;
while(p && p->data<e) /*第二個結點中的data比e小，就讓p和pre指向下一個結點*/
{
pre=p;
p=p->next;
}
if(p && p->data==e)/*找到和e相等的date，p指向這個結點*/
{
return TRUE;
}
else /*如果找不到，p指向剛好比e小的結點*/
{
p=pre;
return FALSE;
}
}
else
return FALSE;
}

void InsertAfter(OrderedList L, LinkType q, LinkType s) /*在結點q之後插入s結點*/
{
if(L.head && q && s)
{
s->next=q->next;
q->next=s;
if(L.tail==q)
L.tail=s;
L.size++;
}
}
void CreateSet(OrderedList &T, char *s)/*將s中的元素按從小到大的順序插入到T控制的鏈表中*/
{
unsigned i;
LinkType p ,q;
if(InitList(T)) /*建立一個空棧*/
{
for(i=0;i<=strlen(s);i++)
{
if(s[i]>='a' && s[i]<='z' && !LocateElem(T,s[i],p))
{
if(MakeNode(q,s[i]))
{
InsertAfter(T,p,q);
}
}
}
}
}

Status Print(LinkType p)/*輸出一個鏈表*/
{
if(p)
{
printf("%c",p->data);
return TRUE;
}
else
return FALSE;
}

void ListTraverse(LinkType p, Status (*visit)( LinkType ))
{
printf("%c",'\t');
while(p)
{
visit(p); //這句看不懂
p=p->next;
}
printf("%c",'\n');

}

void Append(OrderedList &L,LinkType s)
{
if(L.head && s)
{
if(L.tail!=L.head)
L.tail->next=s;
else
L.head->next=s;
L.tail=s;
L.size++;
}
}

void Union(OrderedList &T,OrderedList S1,OrderedList S2)
{
LinkType p1,p2,p;
if(InitList(T))
{
p1=S1.head->next;
p2=S2.head->next;
while( p1 && p2)
{
if(p1->data<=p2->data)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
if(p1->data==p2->data)
p2=p2->next;
p1=p1->next;
}
else
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p2->data;
p->next=NULL;
Append(T,p);
p2=p2->next;
}
}
while(p1)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
p1=p1->next;
}
while(p2)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p2->data;
p->next=NULL;
Append(T,p);
p2=p2->next;
}
}
}

void Intersection(OrderedList &T,OrderedList S1,OrderedList S2)
{
LinkType p1,p2,p;
if(!InitList(T))
T.head=NULL;
else
{
p1=S1.head->next;
p2=S2.head->next;
while( p1 && p2)
{
if(p1->data<p2->data)
p1=p1->next;
else if(p1->data>p2->data)
p2=p2->next;
else
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
p2=p2->next;
p1=p1->next;
}
}
}
}

void Difference(OrderedList &T,OrderedList S1,OrderedList S2)
{
LinkType p1,p2,p;
if(!InitList(T))
T.head=NULL;
else
{
p1=S1.head->next;
p2=S2.head->next;
while( p1 && p2)
{
if(p1->data<p2->data)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
p1=p1->next;
}
else if(p1->data>p2->data)
p2=p2->next;
else
{
p1=p1->next;
p2=p2->next;
}
}
while(p1)
{
p=(LinkType)malloc(sizeof(NodeType));
p->data=p1->data;
p->next=NULL;
Append(T,p);
p1=p1->next;
}

}
}

void ReadCommand(char &cmd)
{
printf("\n ------------------------------------------------------------------------\n");
printf("\n\t\t\t\t操 作 提 示");
printf("\n ------------------------------------------------------------------------\n");
printf("\tMakeSet1------1\t\t\t\tMakeSet2--------2\n\tUnion---------u\t\t\t\tIntersection----i\n\tDifference----d\t\t\t\tQuit------------q\n\tDisplay-------y");
do{
printf("\n\n\t請選擇操作：");
cmd=getch();
printf("\n--------------------------------------------------------------------------\n");
}while(cmd!='1' && cmd!='2' && cmd!='u' && cmd!='i' && cmd!='d' && cmd!='q' && cmd!='y');
}
void Interpret(char &cmd)
{
system("cls");
switch(cmd)
{
case '1':
printf("\n\t請輸入字元串：");
gets(a);
printf("\t原始字元串:");
printf("\t%s\n",a);
CreateSet(L1, a);
printf("\t構建的集合:");
ListTraverse(L1.head->next,Print);
break;
case '2':
printf("\n\t請輸入字元串：");
gets(b);
printf("\t原始字元串:");
printf("\t%s\n",b);
CreateSet(L2, b);
printf("\t構建的集合:");
ListTraverse(L2.head->next,Print);
break;
case 'u':
CreateSet(L1, a);
CreateSet(L2, b);
Union(L3,L1,L2);
printf("\n\t集合1:");
ListTraverse(L1.head->next,Print);
printf("\t集合2:");
ListTraverse(L2.head->next,Print);
printf("\t並集:");
ListTraverse(L3.head->next,Print);
break;
case 'i':
CreateSet(L1, a);
CreateSet(L2, b);
Intersection(L3,L1,L2);
printf("\n\t集合1:");
ListTraverse(L1.head->next,Print);
printf("\t集合2:");
ListTraverse(L2.head->next,Print);
printf("\t交集:");
ListTraverse(L3.head->next,Print);
break;
case 'd':
CreateSet(L1, a);
CreateSet(L2, b);
Difference(L3,L1,L2);
printf("\n\t集合1:");
ListTraverse(L1.head->next,Print);
printf("\t集合2:");
ListTraverse(L2.head->next,Print);
printf("\t差集:");
ListTraverse(L3.head->next,Print);
break;
case 'y':
printf("\n\t原始字元串:\n");
printf("\t\t%s\n\t\t%s\n",a,b);
CreateSet(L1, a);
CreateSet(L2, b);
printf("\t由字元串構建的集合:\n");
printf("\t");
ListTraverse(L1.head->next,Print);
printf("\t");
ListTraverse(L2.head->next,Print);
Union(L3,L1,L2);
printf("\t並集:");
ListTraverse(L3.head->next,Print);

Intersection(L3,L1,L2);
printf("\t交集:");
ListTraverse(L3.head->next,Print);

Difference(L3,L1,L2);
printf("\t差集:");
ListTraverse(L3.head->next,Print);
break;
}
}
void main()
{
char cmd;
do
{
ReadCommand(cmd);
Interpret(cmd);
}while(cmd!='q');
}