- 浏览: 531285 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (231)
- 一个操作系统的实现 (20)
- 汇编(NASM) (12)
- Linux编程 (11)
- 项目管理 (4)
- 计算机网络 (8)
- 设计模式(抽象&封装) (17)
- 数据结构和算法 (32)
- java基础 (6)
- UML细节 (2)
- C/C++ (31)
- Windows (2)
- 乱七八糟 (13)
- MyLaB (6)
- 系统程序员-成长计划 (8)
- POJ部分题目 (10)
- 数学 (6)
- 分布式 & 云计算 (2)
- python (13)
- 面试 (1)
- 链接、装载与库 (11)
- java并行编程 (3)
- 数据库 (0)
- 体系结构 (3)
- C++ template / STL (4)
- Linux环境和脚本 (6)
最新评论
-
chuanwang66:
默默水塘 写道typedef void(*Fun)(void) ...
C++虚函数表(转) -
默默水塘:
typedef void(*Fun)(void);
C++虚函数表(转) -
lishaoqingmn:
写的很好,例子简单明了,将观察者模式都表达了出来。
这里是ja ...
观察者模式——Observer
待续 《计算几何资料》为提纲
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度
,在多边形外部。
发表评论
-
快排备忘
2013-10-26 11:27 541http://hi.baidu.com/pluto455988 ... -
LRU简单实现C++
2013-10-17 10:52 3963页面置换算法: 在地址映射过程中,若在页面中发现所要访问的页 ... -
二叉树相关
2013-10-04 17:40 685本节主要是为了写二叉树类型题目练手的代码,重点培养运用“指针 ... -
双指针策略(《编程之美》3.5 最短摘要生成)
2013-03-26 15:17 2217本文源自《编程之美》3.5 最短摘要生成一课。 ... -
K-MEDOIDS聚类算法
2012-12-04 21:18 1917k-medoids聚类算法 (wiki上讲得很清楚啊:) ) ... -
搜索(三)——回溯
2012-11-23 15:23 1017一、回溯 和 深度搜索 ... -
哈希Hash
2012-11-21 14:42 967要点一:哈希表长度 的确定是个两难的问题:太短则容 ... -
状态压缩DP
2012-11-14 20:27 723引例、 例1、 例2、 例3、 ... -
模拟退火
2012-10-28 16:34 1195引用:http://www.cnblogs.com/heaad ... -
计算几何(二)——平面最近点对
2012-07-12 10:54 880参考资料: 为何这个问题采用分治法 http://blog ... -
气泡滚大——剔除线性数据中的杂质
2012-06-18 09:43 936这是一道Java的面试题,但是我总结了除了一种自称为“ ... -
深入理解二分查找(二、二分答案)
2012-04-29 16:24 7174二分答案 如果已知候选答案的范围[min,max ... -
P问题、NP问题和NPC问题
2012-04-25 16:36 1042这篇文章转自这里 ... -
RMQ(Range Minimum/Maximum Query)区间最值查询
2012-04-18 20:47 1538一、RMQ问题描述 和 几种解题思路 RMQ问题 (Rang ... -
后缀数组
2012-04-16 09:49 1486一、后缀数组 及其对应的名次数组 举例:S=&quo ... -
大整数运算(部分转载)
2012-04-12 21:36 1163待补充:“浮点数高精度运算” 参见这里==> ... -
单向链表相关
2012-04-10 16:42 948单向链表是微软笔试常考的,参考这里:http://www.c ... -
关键路径(AOE)
2012-04-10 08:05 1644前面这段话是引用别人的,后面代码是自己写的,有待完善: ... -
搜索(二)——双向BFS
2012-03-24 17:18 2993参考这篇文章,以下前 ... -
搜索(一)——剪枝
2012-03-24 11:46 1528参考文档:《搜索方法 ...
相关推荐
文章目录对极几何与基础矩阵一、对极几何二、基础矩阵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)二、求解图像...
1.1 编程的灵魂——数据结构+算法=程序 1.2 基本算法 1.3 数据结构(1)——入门 1.4 数据结构(2)——拓宽和应用举例 1.5 动态规划 1.6 状态空间搜索 第2章 数学方法与常见模型 2.1 代数方法和模型 2.2 数论基础 ...
第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;第二部分对链表、...
第三部分对排序、搜索数值计算、数据压缩、数据加密、图算法、几何算法等经典算法进行了精辟的分析和讲解。想要从事接触机器学习或者深度学习的同学,可以通过“算法精解”这本书夯实算法基础,为进一步学习基础学习...
第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;第二部分对链表、...
第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;第二部分对链表、...
全书共分为三部分:部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;...
第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习《算法精解:C语言描述》打下坚实的基础;...
第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习《算法精解:C语言描述》打下坚实的基础;...
6.5.3 实例分析3——网格重新划分算法MAPS 附录6.1 数学背景 附录6.2 演示 第三部分 动画制作 第7章 角色动画 7.1 简介 7.2 顶点动画与合成 7.3 骨架动画 7.4 低层次动画管理 7.4.1 行进的路径规划 7.4.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 骨架动画...
第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;第二部分对链表、...
第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;第二部分对链表、...
——算术和几何级数 ——斐波纳契(Fibonacci)数列 鸽洞原理 排列和组合 ——基本定义 ——Pascal 恒等式 ——二项式定理 求解递推关系式 ——常见实例 ——Master定理 学习目标: 1. 计算一个集合的排列和组合...
第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;第二部分对链表、...
计算机算法:枚举、排序、搜索、计数、贪心、动态规划、图论、数论、博弈论*、概率论*、计算几何*、字符串算法等。 数据结构:数组、对象/结构、字符串、队列、栈、树、图、堆、平衡树/线段树、复杂数据结构*、嵌套...
第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习《算法精解:C语言描述》打下坚实的基础;...
+ [计算几何思想](#计算几何思想) + [圆](#圆) + [半平面交](#半平面交) * [矩阵](#矩阵) + [矩阵](#矩阵-1) + [高斯消元](#高斯消元) * [数学方法](#数学方法) + [数学思想](#数学思想) + [数学归纳法](#...
书籍目录: 第1章 导论 1.1 计算机图形学的应用领域 1.1.1 计算机辅助设计 1.1.2 计算机艺术 1.1.3 虚拟现实 1.1.4 计算机辅助教学 ...第8章 分形几何 第9章 动态消隐 第10章 真实感图形 附录 参考文献