`

计算几何(一)——基础算法

 
阅读更多

待续 《计算几何资料》为提纲

1.

(1) 有向线段 : 如果一条线段的端点有次序之分,我们把这种线段称为有向线段(directed segment)。

(2) 矢量 :如果有向线段p1p2的起点p1在坐标原点,则称之为矢量(vector) p2

(3) (二维)矢量叉乘 : P=(x1,y1),  Q=(x2,y2) ==> P×Q

    随便的定义: 大小|x1  y1|, 方向右手法则

                                  |x2  y2|

    严格定义:(    将二维扩展到三维 P=(x1,y1,0), Q=(x2,y2,0)    )

                   P×Q=|i     j     k|=k*|x1  y1|

                              |x1  y1  0|      |x2  y2|

                              |x2  y2  0|

    P×Q>0,则P在Q的顺时针方向(指:Q沿顺时针方向相比沿逆时针方向更早到达P)

    P×Q<0,则P在Q的逆时针方向

    P×Q=0,则P和Q共线(同向或反向)

 

2. 折线段拐向 :利用二维矢量叉乘性质

 

3. “点”与“线段”关系

    设点Q,线段P1P2.

    点Q在线段上:共线(Q-P1)×(P2-P1)在P1,P2为对角顶点矩形内

 

2、3 代码:

#include<iostream>
using namespace std;

struct Point{
       double x;
       double y;
       Point(double a=0, double b=0){x=a;y=b;}
};

struct LineSeg{
       Point s;
       Point e;
       LineSeg(){}
       LineSeg(Point a, Point b){s=a;e=b;}
};

/*有向线段 dl<op,sp>×dl<op,ep>*/
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)); 
}

/*点在线段上*/
bool ptOnLine(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 );
}

int main(void){
    cout<<ptOnLine( LineSeg(*new Point(1,1), *new Point(2,2)), *new Point(1.5,1.5) )<<endl; //1
    cout<<ptOnLine( LineSeg(*new Point(1,1), *new Point(2,2)), *new Point(3,3) )<<endl;     //0
    cout<<ptOnLine( LineSeg(*new Point(1,1), *new Point(2,2)), *new Point(2,3) )<<endl;     //0
    
    cout<<ptOnLine( LineSeg(*new Point(1,1), *new Point(2,1)), *new Point(1.5,1) )<<endl;   //1
    cout<<ptOnLine( LineSeg(*new Point(1,1), *new Point(2,1)), *new Point(3,1) )<<endl;     //0
    
    cout<<ptOnLine( LineSeg(*new Point(1,1), *new Point(1,2)), *new Point(1,1.5) )<<endl;   //1
    cout<<ptOnLine( LineSeg(*new Point(1,1), *new Point(1,2)), *new Point(1,3) )<<endl;     //0
    
    system("pause");
    return 0;
}
 

12. “点”与“多边形”关系

(1)射线法——适用于任何多边形(凹凸),C:\Users\Administrator\Desktop\Test\计算几何\PointInPoly.cpp

    过此点向任意角度发一条射线,若与多边形的各条边交点个数之和为偶数,则此点在 多边形之外,否则在多边形之内。
    若有交点为多边形顶点则要另选一条射线重算

射线法代码:

#include<iostream>
#include<cmath>
using namespace std;

class CPoint{
public:
       CPoint(){this->x=x;this->y=y;}
       CPoint(double x, double y){
         this->x=x;
         this->y=y;
       }
       double x;
       double y;
};

//向右射线与线段关系:相交返回1,不相交返回0,在边上返回-1(-1时认为点在多边形内)
int IsIntersectant( CPoint ptStart, CPoint ptEnd, CPoint pd ){
  double tempx = 0;
  double tempy = 0;

  double startx = ptStart.x;   
  double starty = ptStart.y;
  double endx = ptEnd.x;   
  double endy = ptEnd.y;
 
  //横标范围[minX, maxX] 
  double maxX = startx;
  double minX = endx;
  if (startx<endx){
    minX = startx;
    maxX = endx;
  }
 
  //保证开始点在下(y坐标大),作为下端点
  if(starty<endy){
    double temp=starty;
    starty=endy;
    endy=temp;
   
    temp=startx;
    startx=endx;
    endx=temp;
  }
 
  //1. 没有交点 (特例一) 
  if((pd.y>starty && pd.y>endy) || (pd.y<starty && pd.y<endy)){
    //水平射线在该直线段的上下两端之外
    return 0;
  }
  if(pd.x>startx && pd.x>endx){
    //水平射线的起点在该直线段的右边
    return 0;
  }
 
  //2. 对于水平线段 : 在线段上返回-1,否则返回0 (特例二) 
  if (starty ==endy)
  {
    if (pd.x<=maxX&&pd.x>=minX)
      return -1;
    return 0;
  }
 
  //3. 非水平线段 
  //   3.1 (向右射线端点)pd在线段上: 通过三角形三边关系判断 
  tempx = pd.x - startx;
  tempy = pd.y - starty;
  double dStartToX = sqrt(tempx*tempx+tempy*tempy);
 
  tempx = pd.x - endx;
  tempy = pd.y - endy;
  double dXToEnd = sqrt(tempx*tempx+tempy*tempy);
 
  tempx = startx - endx;
  tempy = starty - endy;
  double dStarToEnd = sqrt(tempx*tempx+tempy*tempy);
 
  if (dStarToEnd == (dStartToX + dXToEnd)){
    return -1;
  }
  
  //   3.2 向右射线和线段不相交 
  //h_x记录点pd(x,y)引水平线与直线段所在直线的交点x坐标
  //注:直线两点式公式 (y-y1)/(y2-y1)=(x-x1)/(x2-x1),其中 x1≠x2, y1≠y2
  //          也可写作 y-y1=(y2-y1)/(x2-x1)*(x-x1),其中x1≠x2 
  double h_x=(pd.y-starty)*(endx-startx)/(endy-starty)+startx; //只需保证y1≠y2  
  if(pd.x>h_x){//pd点在交点的右边,则射线与线段不相交
    return 0;
  }
  
  //   3.3 向右射线和线段相交
  return 1;
}
 
/**点是否在多边形内 (射线法)*/
bool PtInPolygon( CPoint *ptList, int ptCount, CPoint pd ){
  if (ptCount<3){
    cout<<"注:多边形顶点至少有3个"<<endl; 
    return false;
  }
  
  int cross_num = 0;
  int iFlag = 0;
  //从点pd,向右引水平射线
 
  //除了末端点与首端点连接线,其他各条边的线段 -->与水平射线的交点和 cross_num
  for(int i=0;i<ptCount-1;i++)
  {
    iFlag = IsIntersectant(ptList[i], ptList[i+1], pd);
    if (iFlag < 0){
      return true;
    }else{
     cross_num += iFlag;
    }
  }
  //末端点与首端点连接线 --> 与水平射线的交点和 cross_num
  iFlag = IsIntersectant(ptList[ptCount-1], ptList[0], pd);
  if(iFlag < 0){
    return true;
  }else{
    cross_num += iFlag;
  }
 
  if(cross_num%2==1){
    //1. 交点个数为奇,则点在多边形内 
    return true;
  }else if(cross_num%2==0){
    //2. 交点个数为偶,则点不在多边形内 
    return false;
  }
  return false;
}

int main(void){   
    //如果先声明 CPoint ptList[5]; 必须提供无参构造函数 
    CPoint ptList[5]={CPoint(0,0),CPoint(2,0),CPoint(2,2),CPoint(1,1),CPoint(0,2)};
    int ptNum=5;
    
    cout<<PtInPolygon(ptList,ptNum,*new CPoint(1,1))<<endl;     //1
    cout<<PtInPolygon(ptList,ptNum,*new CPoint(0.5,1))<<endl;   //1
    cout<<PtInPolygon(ptList,ptNum,*new CPoint(1.5,1.1))<<endl; //1
    cout<<PtInPolygon(ptList,ptNum,*new CPoint(1,0))<<endl;     //1
    cout<<PtInPolygon(ptList,ptNum,*new CPoint(1,1.5))<<endl;   //0
    cout<<PtInPolygon(ptList,ptNum,*new CPoint(2.5,3))<<endl;   //0
    cout<<PtInPolygon(ptList,ptNum,*new CPoint(-1,-1))<<endl;   //0
    cout<<PtInPolygon(ptList,ptNum,*new CPoint(2,2))<<endl;     //1
    
    system("pause");
    return 0;
}

 

(2)叉乘判别法——适用于凸多边形,见 http://www.cppblog.com/w2001/archive/2011/06/17/31694.html

     想象一个凸多边形,其每一个边都将整个2D屏幕划分成为左右两边,连接每一边的第一个端点和要测试的点得到一 个矢量v,将两个2维矢量扩展成3维的,然后将该边与v叉乘,判断结果3维矢量中Z分量的符号是否发生变化,进而推导出点是否处于凸多边形内外。这里要注 意的是,多边形顶点究竟是左手序还是右手序,这对具体判断方式有影响。

 

(3)累积角度法——适用于任何多边形(凹凸):
    过此点连接多边形的每一顶点,各相邻边角度(±)之和为360度 ,则此点在多边形内。否则为0度 ,在多边形外部。

 

  • 大小: 38.5 KB
分享到:
评论

相关推荐

    计算机视觉——对极几何与基础矩阵

    文章目录对极几何与基础矩阵一、对极几何二、基础矩阵2.1归一化8点算法2.2算法总结三、实验求解图像的基础矩阵3.1实验要求3.2实验准备3.3实验代码3.4实验结果四、实验总结 对极几何与基础矩阵 一、对极几何 提到对极...

    计算机视觉——多视图几何

    文章目录一、关于对极几何1.1几个基本概念1.2本质矩阵(E)1.2.1 作用1.2.2 求解推导1.2.3 本质矩阵的性质1.3基础矩阵(F)1.3.1 作用1.3.2求解推导1.3.3基础矩阵的性质1.4八点算法求解基础矩阵(F)二、求解图像...

    算法艺术与信息学竞赛 刘汝佳 pdf

    1.1 编程的灵魂——数据结构+算法=程序 1.2 基本算法 1.3 数据结构(1)——入门 1.4 数据结构(2)——拓宽和应用举例 1.5 动态规划 1.6 状态空间搜索 第2章 数学方法与常见模型 2.1 代数方法和模型 2.2 数论基础 ...

    《算法精解:C语言描述》(Kyle Loudon[美] 著,肖翔、陈舸 译)

    第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;第二部分对链表、...

    算法精解.C语言描述

    第三部分对排序、搜索数值计算、数据压缩、数据加密、图算法、几何算法等经典算法进行了精辟的分析和讲解。想要从事接触机器学习或者深度学习的同学,可以通过“算法精解”这本书夯实算法基础,为进一步学习基础学习...

    算法精解:C语言描述中文版(高清)

    第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;第二部分对链表、...

    算法精解-c语言描述

    第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;第二部分对链表、...

    算法精解:C语言描述 PDF

    全书共分为三部分:部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;...

    算法精解-经典算法书籍

    第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习《算法精解:C语言描述》打下坚实的基础;...

    算法精解:C语言描述

    第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习《算法精解:C语言描述》打下坚实的基础;...

    3D游戏卷2:动画与高级实时渲染技术——2

    6.5.3 实例分析3——网格重新划分算法MAPS 附录6.1 数学背景 附录6.2 演示 第三部分 动画制作 第7章 角色动画 7.1 简介 7.2 顶点动画与合成 7.3 骨架动画 7.4 低层次动画管理 7.4.1 行进的路径规划 7.4.2 骨架动画...

    3D游戏卷2:动画与高级实时渲染技术——1

    6.5.3 实例分析3——网格重新划分算法MAPS 附录6.1 数学背景 附录6.2 演示 第三部分 动画制作 第7章 角色动画 7.1 简介 7.2 顶点动画与合成 7.3 骨架动画 7.4 低层次动画管理 7.4.1 行进的路径规划 7.4.2 骨架动画...

    算法精解(C语言描述)Kyle Loudon 机械工业出版

    第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;第二部分对链表、...

    算法精解C描述

    第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;第二部分对链表、...

    计算机要学哪些东西----(还有附赠哦)

    ——算术和几何级数 ——斐波纳契(Fibonacci)数列 鸽洞原理 排列和组合 ——基本定义 ——Pascal 恒等式 ——二项式定理 求解递推关系式 ——常见实例 ——Master定理 学习目标: 1. 计算一个集合的排列和组合...

    算法精解:C语言描述 chm 英文版

    第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;第二部分对链表、...

    【1.数据结构和算法学习目录】

    计算机算法:枚举、排序、搜索、计数、贪心、动态规划、图论、数论、博弈论*、概率论*、计算几何*、字符串算法等。 数据结构:数组、对象/结构、字符串、队列、栈、树、图、堆、平衡树/线段树、复杂数据结构*、嵌套...

    C语言描述(中文),完整扫描版

    第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习《算法精解:C语言描述》打下坚实的基础;...

    IOI国家集训队论文集1999-2019

    + [计算几何思想](#计算几何思想) + [圆](#圆) + [半平面交](#半平面交) * [矩阵](#矩阵) + [矩阵](#矩阵-1) + [高斯消元](#高斯消元) * [数学方法](#数学方法) + [数学思想](#数学思想) + [数学归纳法](#...

    计算机图形学基础教程(Visual C++版)——第6~10章

    书籍目录: 第1章 导论  1.1 计算机图形学的应用领域  1.1.1 计算机辅助设计  1.1.2 计算机艺术  1.1.3 虚拟现实  1.1.4 计算机辅助教学 ...第8章 分形几何 第9章 动态消隐 第10章 真实感图形 附录 参考文献

Global site tag (gtag.js) - Google Analytics