[其他]：关于点到空间直线垂点的Lisp方法

lsjjm

最初由 陌生人 发布
[B](osnap entity pt "per")
osnap有这种用法？ [/B]

严格讲应该为(osnap pt "per").因为(osnap entity pt "per")返回
" warning: too many arguments: (OSNAP LL PT1 "per")"

eachy

最初由 lsjjm 发布
[B]

1."丢三落四"? 请指正?
2. 这是eachy重贴去年8月的贴子. "?.. [/B]

帖子相同，对程序的理解已经不同了，我的意思是说明一些公式方程的应用，单单理解点到直线的距离或者位置关系就没必要重贴了。

小菜

是的，上面看错了：)
osnap是不能有entity选项的

陌生人

最初由 lsjjm 发布
[B]

1."丢三落四"? 请指正?
2. 这是eachy重贴去年8月的贴子. "?.. [/B]

原贴 p0 没有用 (trans p0 1 0)，在ucs下返回结果是错误的

ea说的是，这是在研究几何关系的方程，只不过是用lsp表达出来。

dubing

搞GIS的朋友们，这是我多年以来看到的最好的资料。需要者快快搜藏

aeo

我在一个游戏网站上找到过. www.gameres.com

应该还有其他的。

引用里面的一句话:
   -----学会了?好样的！你又重新达到了大学一年级的水平~~~~~~~~~~~~

星星

太好的资料,谢谢楼主,谢谢版主,正在查找这方面资料,
倘若有用lisp写成的这方面基础程序就更好了,免得大家都在做一些重复性的工作.
让我们站在更高的起点上!

hxa

[php]
作者：kbsoft(景乐)    转贴自：csdn   

目录


㈠ 点的基本运算
1. 平面上两点之间距离 1
2. 判断两点是否重合   1
3. 矢量叉乘 1
4. 矢量点乘 2
5. 判断点是否在线段上 2
6. 求一点饶某点旋转后的坐标 2
7. 求矢量夹角 2

㈡ 线段及直线的基本运算
1. 点与线段的关系 3
2. 求点到线段所在直线垂线的垂足 4
3. 点到线段的最近点 4
4. 点到线段所在直线的距离 4
5. 点到折线集的最近距离 4
6. 判断圆是否在多边形内 5
7. 求矢量夹角余弦 5
8. 求线段之间的夹角 5
9. 判断线段是否相交 6
10.判断线段是否相交但不交在端点处 6
11.求线段所在直线的方程 6
12.求直线的斜率 7
13.求直线的倾斜角 7
14.求点关于某直线的对称点 7
15.判断两条直线是否相交及求直线交点 7
16.判断线段是否相交，如果相交返回交点 7

㈢ 多边形常用算法模块
1. 判断多边形是否简单多边形 8
2. 检查多边形顶点的凸凹性 9
3. 判断多边形是否凸多边形 9
4. 求多边形面积 9
5. 判断多边形顶点的排列方向，方法一 10
6. 判断多边形顶点的排列方向，方法二 10
7. 射线法判断点是否在多边形内 10
8. 判断点是否在凸多边形内 11
9. 寻找点集的graham算法 12
10.寻找点集凸包的卷包裹法 13
11.判断线段是否在多边形内 14
12.求简单多边形的重心 15
13.求凸多边形的重心 17
14.求肯定在给定多边形内的一个点 17
15.求从多边形外一点出发到该多边形的切线 18
16.判断多边形的核是否存在 19

㈣ 圆的基本运算
1 .点是否在圆内 20
2 .求不共线的三点所确定的圆 21

㈤ 矩形的基本运算
1.已知矩形三点坐标，求第4点坐标 22

㈥ 常用算法的描述 22

㈦ 补充
1．两圆关系： 24
2．判断圆是否在矩形内： 24
3．点到平面的距离： 25
4．点是否在直线同侧： 25
5．镜面反射线： 25
6．矩形包含： 26
7．两圆交点： 27
8．两圆公共面积： 28
9. 圆和直线关系： 29
10. 内切圆： 30
11. 求切点： 31
12. 线段的左右旋： 31
13．公式： 32


/* 需要包含的头文件 */
#include <cmath >

/* 常用的常量定义 */
const double INF = 1E200   
const double EP = 1E-10
const int MAXV = 300
const double PI = 3.14159265

/* 基本几何结构 */
struct POINT
{
double x;
double y; POINT(double a=0, double b=0) { x=a; y=b;} file://constructor
};
struct LINESEG
{
POINT s;
POINT e; LINESEG(POINT a, POINT b) { s=a; e=b;}
LINESEG() { }
};
struct LINE           // 直线的解析方程 a*x+b*y+c=0  为统一表示，约定 a >= 0
{
   double a;
   double b;
   double c; LINE(double d1=1, double d2=-1, double d3=0) {a=d1; b=d2; c=d3;}
};

/********************\
*                    *
*   点的基本运算     *
*                    *
\********************/

double 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 p1,POINT p2)           // 判断两个点是否重合  
{
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<0:ep在矢量opsp的顺时针方向
*******************************************************************************/

double 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)的点积，如果两个矢量都非零矢量
r<0:两矢量夹角为锐角；r=0：两矢量夹角为直角；r>0:两矢量夹角为钝角
*******************************************************************************/
double dotmultiply(POINT p1,POINT p2,POINT p0)
{
return ((p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y));
}

/* 判断点p是否在线段l上，条件：(p在线段l所在的直线上)&& (点p在以线段l为对角线的矩形内) */
bool online(LINESEG l,POINT p)
{
return((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)<=0 ) ) );
}

// 返回点p以点o为圆心逆时针旋转alpha(单位：弧度)后所在的位置
POINT rotate(POINT o,double alpha,POINT p)
{
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;
return tp;
}

/* 返回顶角在o点，起始边为os，终止边为oe的夹角(单位：弧度)
角度小于pi，返回正值
角度大于pi，返回负值
可以用于求线段之间的夹角
*/
double angle(POINT o,POINT s,POINT e)
{
double cosfi,fi,norm;
double dsx = s.x - o.x;
double dsy = s.y - o.y;
double dex = e.x - o.x;
double dey = e.y - o.y;

cosfi=dsx*dex+dsy*dey;
norm=(dsx*dsx+dey*dey)*(dex*dex+dey*dey);
cosfi /= sqrt( norm );

if (cosfi >=  1.0 ) return 0;
  if (cosfi <= -1.0 ) return -3.1415926;

fi=acos(cosfi);
if (dsx*dey-dsy*dex>0) return fi;      // 说明矢量os 在矢量 oe的顺时针方向
  return -fi;
}



/*****************************\
  *                             *
  *      线段及直线的基本运算   *
  *                             *
  \*****************************/

/* 判断点与线段的关系,用途很广泛
本函数是根据下面的公式写的，P是点C到线段AB所在直线的垂足

                AC dot AB
        r =     ---------
                 ||AB||^2
             (Cx-Ax)(Bx-Ax) + (Cy-Ay)(By-Ay)
          = -------------------------------
                          L^2

    r has the following meaning:

        r=0      P = A
        r=1      P = B
        r<0 P is on the backward extension of AB
r>1      P is on the forward extension of AB
        0<r<1 P is interior to AB
*/
double relation(POINT p,LINESEG l)
{
LINESEG tl;
tl.s=l.s;
tl.e=p;
return dotmultiply(tl.e,l.e,l.s)/(dist(l.s,l.e)*dist(l.s,l.e));
}

// 求点C到线段AB所在直线的垂足 P
POINT perpendicular(POINT p,LINESEG l)
{
double r=relation(p,l);
POINT tp;
tp.x=l.s.x+r*(l.e.x-l.s.x);
tp.y=l.s.y+r*(l.e.y-l.s.y);
return tp;
}
/* 求点p到线段l的最短距离,并返回线段上距该点最近的点np
注意：np是线段l上到点p最近的点，不一定是垂足 */
double ptolinesegdist(POINT p,LINESEG l,POINT &np)
{
double r=relation(p,l);
if(r<0)
{
np=l.s;
return dist(p,l.s);
}
if(r>1)
{
np=l.e;
return dist(p,l.e);
}
np=perpendicular(p,l);
return dist(p,np);
}

// 求点p到线段l所在直线的距离,请注意本函数与上个函数的区别  
double ptoldist(POINT p,LINESEG l)
{
return abs(multiply(p,l.e,l.s))/dist(l.s,l.e);
}

/* 计算点到折线集的最近距离,并返回最近点.
注意：调用的是ptolineseg()函数 */
double ptopointset(int vcount,POINT pointset[],POINT p,POINT &q)
{
int i;
double cd=double(INF),td;
LINESEG l;
POINT tq,cq;

for(i=0;i<vcount-1;i++)
{
l.s=pointset;
l.e=pointset[i+1];
td=ptolinesegdist(p,l,tq);
if(td<cd)
{
cd=td;
cq=tq;
}
}
q=cq;
return cd;
}
/* 判断圆是否在多边形内.ptolineseg()函数的应用2 */
bool CircleInsidePolygon(int vcount,POINT center,double radius,POINT polygon[])
{
POINT q;
double d;
q.x=0;
q.y=0;
d=ptopointset(vcount,polygon,center,q);
if(d<radius||fabs(d-radius)<EP)
return true;
else
return false;
}

/* 返回两个矢量l1和l2的夹角的余弦(-1 --- 1)注意：如果想从余弦求夹角的话，注意反余弦函数的定义域是从 0到pi */
double cosine(LINESEG l1,LINESEG l2)
{
return (((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)
double lsangle(LINESEG l1,LINESEG l2)
{
POINT 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;
return angle(o,s,e);
}
// 如果线段u和v相交(包括相交在端点处)时，返回true
bool intersect(LINESEG u,LINESEG v)
{
return( (max(u.s.x,u.e.x)>=min(v.s.x,v.e.x))&&                     file://排斥实验
        (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)&&         file://跨立实验
        (multiply(u.s,v.e,v.s)*multiply(v.e,u.e,v.s)>=0));
}


//  (线段u和v相交)&&(交点不是双方的端点) 时返回true   
bool intersect_A(LINESEG u,LINESEG v)
{
return((intersect(u,v))&&
       (!online(u,v.s))&&
       (!online(u,v.e))&&
       (!online(v,u.e))&&
       (!online(v,u.s)));
}


// 线段v所在直线与线段u相交时返回true；方法：判断线段u是否跨立线段v  
bool intersect_l(LINESEG u,LINESEG v)
{
return multiply(u.s,v.e,v.s)*multiply(v.e,u.e,v.s)>=0;
}

// 根据已知两点坐标，求过这两点的直线解析方程： a*x+b*y+c = 0  (a >= 0)  
LINE makeline(POINT p1,POINT p2)
{
   LINE tl;
   int sign = 1;
   tl.a=p2.y-p1.y;
   if(tl.a<0)
{
sign = -1;
tl.a=sign*tl.a;
}
tl.b=sign*(p1.x-p2.x);
tl.c=sign*(p1.y*p2.x-p1.x*p2.y);
return tl;
}

// 根据直线解析方程返回直线的斜率k,水平线返回 0,竖直线返回 1e200
double slope(LINE l)
{
if(abs(l.a) < 1e-20)return 0;
if(abs(l.b) < 1e-20)return INF;
return -(l.a/l.b);
}

// 返回直线的倾斜角alpha ( 0 - pi)
double alpha(LINE l)
{
if(abs(l.a)< EP)return 0;
if(abs(l.b)< EP)return PI/2;
double k=slope(l);
if(k>0)
      return atan(k);
   else
      return PI+atan(k);
}

// 求点p关于直线l的对称点  
POINT symmetry(LINE l,POINT p)
{
   POINT tp;
   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);
   return tp;
}

// 如果两条直线 l1(a1*x+b1*y+c1 = 0), l2(a2*x+b2*y+c2 = 0)相交，返回true，且返回交点p  
bool lineintersect(LINE l1,LINE l2,POINT &p) // 是 L1，L2
{
   double d=l1.a*l2.b-l2.a*l1.b;
   if(abs(d)<EP) // 不相交
return false;
p.x = (l2.c*l1.b-l1.c*l2.b)/d;
p.y = (l2.a*l1.c-l1.a*l2.c)/d;
return true;
}

// 如果线段l1和l2相交，返回true且交点由(inter)返回，否则返回false
bool intersection(LINESEG l1,LINESEG l2,POINT &inter)
{
LINE ll1,ll2;
ll1=makeline(l1.s,l1.e);
ll2=makeline(l2.s,l2.e);
if(lineintersect(ll1,ll2,inter))
{
return online(l1,inter);
}
else
return false;
}
[/php]

dubing

CSDN 资源: http://expert.csdn.net/Expert/topic/2483/2483852.xml
来源之一：http://www.gameres.com/Articles/Program/Abstract/Geometry.htm

misdi

eachy
你好执著!
我还是很久很久以前问的这个问题,你坚持到现在,服气,佩服!
我现在单位无宽带,上网少了,现在看到很感动的.

topyjs

不错

wjcrw

j