计算几何C#源码文档格式.docx
《计算几何C#源码文档格式.docx》由会员分享，可在线阅读，更多相关《计算几何C#源码文档格式.docx（40页珍藏版）》请在冰点文库上搜索。
10
判断多边形顶点的排列方向，方法二
射线法判断点是否在多边形内
判断点是否在凸多边形内
11
寻找点集的graham算法
12
10.寻找点集凸包的卷包裹法
13
11.判断线段是否在多边形内
14
12.求简单多边形的重心
15
13.求凸多边形的重心
17
14.求肯定在给定多边形内的一个点
15.求从多边形外一点出发到该多边形的切线
18
16.判断多边形的核是否存在
19
㈣
圆的基本运算
.点是否在圆内
20
.求不共线的三点所确定的圆
21
㈤
矩形的基本运算
1.已知矩形三点坐标，求第4点坐标
22
㈥
常用算法的描述
㈦
补充
1．两圆关系：
24
2．判断圆是否在矩形内：
3．点到平面的距离：
25
4．点是否在直线同侧：
5．镜面反射线：
6．矩形包含：
26
7．两圆交点：
27
8．两圆公共面积：
28
圆和直线关系：
29
10.
内切圆：
30
11.
求切点：
31
12.
线段的左右旋：
13．公式：
32
*/
/*
需要包含的头文件
*/
#include
<
cmath
>
常用的常量定义
const
double
INF
=
1E200
EP
1E-10
int
MAXV
300
PI
3.14159265
基本几何结构
struct
POINT
{
x;
y;
POINT（double
a=0,
b=0）
x=a;
y=b;
}
//constructor
};
LINESEG
s;
e;
LINESEG（POINT
a,
b）
s=a;
e=b;
LINESEG（）
LINE
//
直线的解析方程
a*x+b*y+c=0
为统一表示，约定
a
0
a;
b;
c;
LINE（double
d1=1,
d2=-1,
d3=0）
{a=d1;
b=d2;
c=d3;
/**********************
*
**********************/
dist（POINT
p1,POINT
p2）
返回两点之间欧氏距离
return（
sqrt（
（p1.x-p2.x）*（p1.x-p2.x）+（p1.y-p2.y）*（p1.y-p2.y）
）
）;
bool
equal_point（POINT
判断两个点是否重合
return
（
（abs（p1.x-p2.x）<
EP）&
&
（abs（p1.y-p2.y）<
EP）
/******************************************************************************
r=multiply（sp,ep,op）,得到（sp-op）和（ep-op）的叉积
r>
0：
ep在矢量opsp的逆时针方向；
r=0：
opspep三点共线；
r<
ep在矢量opsp的顺时针方向
*******************************************************************************/
multiply（POINT
sp,POINT
ep,POINT
op）
return（（sp.x-op.x）*（ep.y-op.y）-（ep.x-op.x）*（sp.y-op.y））;
r=dotmultiply（p1,p2,op）,得到矢量（p1-op）和（p2-op）的点积，如果两个矢量都非零矢量
两矢量夹角为钝角；
两矢量夹角为直角；
两矢量夹角为锐角
dotmultiply（POINT
p2,POINT
p0）
（（p1.x-p0.x）*（p2.x-p0.x）+（p1.y-p0.y）*（p2.y-p0.y））;
判断点p是否在线段l上
条件：
（p在线段l所在的直线上）
（点p在以线段l为对角线的矩形内）
online（LINESEG
l,POINT
p）
（multiply（l.e,p,l.s）==0）
（p.x-l.s.x）*（p.x-l.e.x）<
=0
）&
（p.y-l.s.y）*（p.y-l.e.y）<
返回点p以点o为圆心逆时针旋转alpha（单位：
弧度）后所在的位置
rotate（POINT
o,double
alpha,POINT
tp;
p.x-=o.x;
p.y-=o.y;
tp.x=p.x*cos（alpha）-p.y*sin（alpha）+o.x;
tp.y=p.y*cos（alpha）+p.x*sin（alpha）+o.y;
返回顶角在o点，起始边为os，终止边为oe的夹角（单位：
弧度）
角度小于pi，返回正值
角度大于pi，返回负值
可以用于求线段之间的夹角
原理：
r
dotmultiply（s,e,o）
/
（dist（o,s）*dist（o,e））
r'
multiply（s,e,o）
angle
0;
-1
-PI
-1<
arccos（r）
-arccos（r）
angle（POINT
o,POINT
s,POINT
e）
cosfi,fi,norm;
dsx
s.x
-
o.x;
dsy
s.y
o.y;
dex
e.x
dey
e.y
cosfi=dsx*dex+dsy*dey;
norm=（dsx*dsx+dsy*dsy）*（dex*dex+dey*dey）;
cosfi
/=
norm
if
（cosfi
1.0
-1.0
-3.1415926;
fi=acos（cosfi）;
（dsx*dey-dsy*dex>
0）
fi;
说明矢量os
在矢量
oe的顺时针方向
-fi;
/*****************************\
\*****************************/
判断点与线段的关系,用途很广泛
本函数是根据下面的公式写的，P是点C到线段AB所在直线的垂足
AC
dot
AB
---------
||AB||^2
（Cx-Ax）（Bx-Ax）
+
（Cy-Ay）（By-Ay）
-------------------------------
L^2
has
the
following
meaning:
r=0
P
A
r=1
B
is
on
backward
extension
of
forward
0<
interior
to
relation（POINT
p,LINESEG
l）
tl;
tl.s=l.s;
tl.e=p;
dotmultiply（tl.e,l.e,l.s）/（dist（l.s,l.e）*dist（l.s,l.e））;
求点C到线段AB所在直线的垂足
perpendicular（POINT
r=relation（p,l）;
tp.x=l.s.x+r*（l.e.x-l.s.x）;
tp.y=l.s.y+r*（l.e.y-l.s.y）;
求点p到线段l的最短距离,并返回线段上距该点最近的点np
注意：
np是线段l上到点p最近的点，不一定是垂足
ptolinesegdist（POINT
np）
if（r<
np=l.s;
dist（p,l.s）;
if（r>
1）
np=l.e;
dist（p,l.e）;
np=perpendicular（p,l）;
dist（p,np）;
求点p到线段l所在直线的距离,请注意本函数与上个函数的区别
ptoldist（POINT
abs（multiply（p,l.e,l.s））/dist（l.s,l.e）;
计算点到折线集的最近距离,并返回最近点.
调用的是ptolineseg（）函数
ptopointset（int
vcount,POINT
pointset[],POINT
p,POINT
q）
i;
cd=double（INF）,td;
l;
tq,cq;
for（i=0;
i<
vcount-1;
i++）
l.s=pointset[i];
l.e=pointset[i+1];
td=ptolinesegdist（p,l,tq）;
if（td<
cd）
cd=td;
cq=tq;
q=cq;
cd;
判断圆是否在多边形内.ptolineseg（）函数的应用2
CircleInsidePolygon（int
center,double
radius,POINT
polygon[]）
q;
d;
q.x=0;
q.y=0;
d=ptopointset（vcount,polygon,center,q）;
if（d<
radius||fabs（d-radius）<
true;
else
false;
返回两个矢量l1和l2的夹角的余弦（-1
---
1）注意：
如果想从余弦求夹角的话，注意反余弦函数的定义域是从
0到pi
cosine（LINESEG
l1,LINESEG
l2）
（（（l1.e.x-l1.s.x）*（l2.e.x-l2.s.x）
（l1.e.y-l1.s.y）*（l2.e.y-l2.s.y））/（dist（l1.e,l1.s）*dist（l2.e,l2.s）））
返回线段l1与l2之间的夹角
单位：
弧度
范围（-pi，pi）
lsangle（LINESEG
o,s,e;
o.x=o.y=0;
s.x=l1.e.x-l1.s.x;
s.y=l1.e.y-l1.s.y;
e.x=l2.e.x-l2.s.x;
e.y=l2.e.y-l2.s.y;
angle（o,s,e）;
如果线段u和v相交（包括相交在端点处）时，返回true
//
//判断P1P2跨立Q1Q2的依据是：
P1
Q1
×
Q2
P2
0。
//判断Q1Q2跨立P1P2的依据是：
intersect（LINESEG
u,LINESEG
v）
（max（u.s.x,u.e.x）>
=min（v.s.x,v.e.x））&
//排斥实验
（max（v.s.x,v.e.x）>
=min（u.s.x,u.e.x））&
（max（u.s.y,u.e.y）>
=min（v.s.y,v.e.y））&
（max（v.s.y,v.e.y）>
=min（u.s.y,u.e.y））&
（multiply（v.s,u.e,u.s）*multiply（u.e,v.e,u.s）>
=0）&
//跨立实验
（multiply（u.s,v.e,v.s）*multiply（v.e,u.e,v.s）>
=0））;
（线段u和v相交）&
（交点不是双方的端点）
时返回true
intersect_A（LINESEG
（（intersect（u,v））&
（!
online（u,v.s））&
online（u,v.e））&
online（v,u.e））&
online（v,u.s）））;
线段v所在直线与线段u相交时返回true；
方法：
判断线段u是否跨立线段v
intersect_l（LINESEG
multiply（u.s,v.e,v.s）*multiply（v.e,u.e,v.s）>
=0;
根据已知两点坐标，求过这两点的直线解析方程：
a*x+b*y+c
（a
makeline（POINT
sign
1;
tl.a=p2.y-p1.y;
if（tl.a<
-1;
tl.a=sign*tl.a;
tl.b=sign*（p1.x-p2.x）;
tl.c=sign*（p1.y*p2.x-p1.x*p2.y）;
根据直线解析方程返回直线的斜率k,水平线返回
0,竖直线返回
1e200
slope（LINE
if（abs（l.a）
1e-20）
if（abs（l.b）
INF;
-（l.a/l.b）;
返回直线的倾斜角alpha
pi）
alpha（LINE
if（abs（l.a）<
EP）
if（abs（l.b）<
PI/2;
k=slope（l）;
if（k>
atan（k）;
PI+atan（k）;
求点p关于直线l的对称点
symmetry（LINE
tp.x=（（l.b*l.b-l.a*l.a）*p.x-2*l.a*l.b*p.y-2*l.a*l.c）/（l.a*l.a+l.b*l.b）;
tp.y=（（l.a*l.a-l.b*l.b）*p.y-2*l.a*l.b*p.x-2*l.b*l.c）/（l.a*l.a+l.b*l.b）;
如果两条直线
l1（a1*x+b1*y+c1
0）,
l2（a2*x+b2*y+c2
0）相交，返回true，且返回交点p
lineintersect（LINE
l1,LINE
l2,POINT
是
L1，L2
d=l1.a*l2.b-l2.a*l1.b;
if（abs（d）<
不相交
p.x
（l2.c*l1.b-l1.c*l2.b）/d;
p.y
（l2.a*l1.c-l1.a*l2.c）/d;
如果线段l1和l2相交，返回true且交点由（inter）返回，否则返回false
intersection（LINESEG
inter）
ll1,ll2;
ll1=makeline（l1.s,l1.e）;
ll2=makeline（l2.s,l2.e）;
if（lineintersect（ll1,ll2,inter））
returnonline（l1,inter）&
online（l2,inter）;
/******************************\
\******************************/
如果无特别说明，输入多边形顶点要求按逆时针排列
返回值：
输入的多边形是简单多边形，返回true
要
求：
输入顶点序列按逆时针排序
说
明：
简单多边形定义：
1：
循环排序中相邻线段对的交是他们之间共有的单个点
2：
不相邻的线段不相交
本程序默认第一个条件已经满足
issimple（int
i,cn;
l1,l2;
vcount;
l1.s=polygon[i];
l1.e=polygon[（i+1）%vcount];
cn=vcount-3;
while（cn）
l2.s=polygon[（i+2）%vcount];
l2.e=polygon[（i+3）%vcount];
if（intersect（l1,l2））
break;
cn--;
if（cn）
按输入顺序返回多边形顶点的凸凹性判断，bc[i]=1,iff:
第i个顶点是凸顶点
void
checkconvex（int
polygon[],bool
bc[]）
i,index=0;
tp=polygon[0];
for（i=1;
i+
升级会员 