双向交算法

‘壹’ 三角曲面相交特性

用三角曲面表示的两张简单曲面可能交于若干交线、若干交点与若干交面。下面将介绍两张简单曲面的交集的特性。

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');
}