一、判断两封闭单连通图形A和B关系:
旋转法:取图形A内的任一点X,如果X是B内部的点,则说明A、B相交。否则,连接X和B的边界上点P作线段XP。从X出发,考察从线段XP,作状态(IA,IB),IA和IB非零与否分别表示在A和B的内部与否,初始时为(1, 0),经过A或B的边界分别使IA或IB翻转,如果出现(IA,IB)=(1,1)就说明A、B相交,否则说明A、B不相交。
二、判断一个点X是否在N边形内部:
圆环染色法:以X为起点,多边形各端点Pi为终点得向量XPi(i=0,1,...,N-1)。此后顺序考察各向量过程中,用到两个运算:以内角为准,到对比向量va相对于vb是顺时针还是逆时针的运算,返回1代表顺时针,-1表示逆时针,该运算可用向量积实现;三向量中间向量是否在两侧向量所夹内角中的判断,记作cr,可用解析法实现。记向量组XPi为v[i]。算法如下(经初步验证):
bool inpvec(const vector *v, int n)
{
int cl;
int s = 0;
int i, p;
for(i = 2, p = 1; i < n; i++)
if(cr(v, i, p, s)) p++;
return check(v, p, s);
}
bool cr(const vector *v, int ic, int io, int &s)
{
int g1 = v[ic].x * v[io].y - v[ic].y * v[io].x;
int g2 = (v[ic].x - v[io].x) * v[0].y - (v[ic].y - v[io].y) * v[0].x;
if(g1 < 0 && g2 >= 0 || g1 > 0 && g2 <= 0) return true;
if(g1 == 0) return false;
int dxc = v[ic].x * g2 - v[0].x * g1;
int dxo = v[io].x * g2 - v[0].x * g1;
int dyc = v[ic].y * g2 - v[0].y * g1;
int dyo = v[io].y * g2 - v[0].y * g1;
if(dxc < 0 && dxo > 0 || dxc > 0 && dxo < 0 ||
dyc < 0 && dyo > 0 || dyc > 0 && dyo < 0)
s += (g1 > 0)? 1 : -1;
return ((dxc != 0 || dyc != 0) && (dxo != 0 || dyo != 0));
}
bool check(const vector *v, int p, int s)
{
int g1 = v[1].x * v[0].y - v[1].y * v[0].x;
int g2 = v[0].x * v[p].y - v[0].y * v[p].x;
bool sd = (g1 > 0 && g2 > 0) || (g1 < 0 && g2 < 0);
return (s == 0 && sd ||s != 0 && !sd);
}
分享到:
相关推荐
DDA算法画一条直线,很简单的Java小程序,思路比较好。
以下是一个关于梯度投影算法的简单例子的matlab源码程序。 首先,定义一个随机的初始向量。接下来,我们需要计算初始向量的梯度。然后,我们将梯度投影到一个已知的向量上,以获得新的向量。我们可以不断迭代这个...
●什么是计算机算法,能够采用一种方式来描述计算机算法,以及如何评估算法。 ●在计算机中查找信息的简单方式。 ●在计算机中重排信息以使其以一种预定顺序排列的方法。(我们称这一任务为“排序”。) ●如何解决...
为适应此算法,空闲分区表(空闲区链)中的空闲分区要按从小到大进行排序,自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区,但造成许多小的空闲区。因为它要不断地找出能满足作业要求的、且...
第二部分,调研图神经网络算法,重点调研 graphsage 算法及其实现原理,并尝试 neo4j 跑出一班结果; 第三部分,图嵌入 graph embedding 算法调研,重点理解 node2vec 等图嵌入算法实现原理; 第四部分,以 PageRank...
这是一种称为 Apriori 算法的数据挖掘和机器学习算法。它接受输入并生成关联规则。 入门 克隆这个 repo 并启动generateDatabse.py 文件。 该文件将创建五个示例数据源用于测试目的。 您在 prject 文件夹中看到 .txt...
数字3对应为蚁群算法,数字2也对应蚁群算法是对前一算法的简化尝试。 数字1对应为遗传算法,采用了8种演化方式,三种杂交,5种变异,是否采用哪一种方式,主要由这种方式带来的突破数决定,突破数越大,采用该方法...
武科大算法设计试卷及答案 ...7、 回溯算法是尝试搜索算法中最为基本的一种算法,其采用了一种( )的思想作为其控制结构 。 8、 用分支限界法解决布线问题时,对问题解空间搜索尝试结束的标志是( )。
ngram 尝试算法 希望下载的人能继续编写下去。可以互相讨论
Boyer-Moore字符串搜索算法。它由Bob Boyer和J Strother Moore设计于1977年。此算法仅对搜索目标字符...它的效率来自于这样的事实:对于每一次失败的匹配尝试,算法都能够使用这些信息来排除尽可能多的无法匹配的位置。
算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有...
所谓回溯技术就是向人走迷宫一样,先选择一个前进方向尝试,一步步试探,在遇到死胡同不能再往前的时候就会退到上一个分支点,另选一个方向尝试,而在前进和回撤的路上都设置一些标记,以便能够正确返回,直到达到...
视频一个两部分,算法(一)主要集中在基础的数据结构、排序、查找算法。 相关主题有:并查集算法,二分查找,栈,队列,背包,插入排序,选择排序,希尔排序,快速排序, 三切分快排,归并排序,堆排序,二分堆,二...
针对网络入侵检测所处理数据特征维数高、入侵检测系统负荷大、检测速度慢等问题,提出了一种将自适应遗传算法与信息增益相结合的特征选择方法,并采用基于支持向量机的分类器作为自适应遗传算法中适应度函数的计算与...
A*算法是一种预测算法,主要用于寻路等,根据当前状态和目标状态之间的差异,预测到达目标需要多少开销,根据这个开销来判断下一次选择以那个状态开始。这个开销在八数码问题中可以以路程为标准。
线程池 5天不再惧怕多线程——第四天 信号量 5天不再惧怕多线程——第三天 互斥体 5天不再惧怕多线程——第二天 锁机制 5天不再惧怕多线程——第一天 尝试Thread 经典算法专题(21)经典算法题每日演练——第二十一题 ...
(1) 基本算法:单变量连续函数优化问题 (2) 文件输出优化结果和中间过程数据 (3) 设置指标参数计数器 (4) 图形输出坏解接受概率
猫群算法作为一种群智能优化算法,有较快的收敛速度、向他人学习等优点,但国内目前对它的研究还处在起步阶段,所以做这方面的尝试性研究。通过引入交换子概念和改进猫的行为模式将算法用于求解TSP。最后通过MATLAB...
这与 Firefox 使用的算法相同——它是一种不基于任何广为人知的算法的自制算法——尽管经过修改以生成 64 位散列值而不是 32 位散列值。它始终优于 rustc 本身中基于 FNV 的哈希——冲突率与 FNV 相似或略差,但哈希...