C语言实现的PNPoly算法代码例子
2023-06-13 09:15:37 时间
写C语言的实验用到的一个算法,判断一个点是否在多边形的内部。C的代码如下:
intpnpoly(intnvert,float*vertx,float*verty,floattestx,floattesty) { inti,j,c=0; for(i=0,j=nvert-1;i<nvert;j=i++){ if(((verty[i]>testy)!=(verty[j]>testy))&& (testx<(vertx[j]-vertx[i])*(testy-verty[i])/ (verty[j]-verty[i])+vertx[i])) c=!c; } returnc; }
其中nvert是多边形顶点的个数,vertx和verty分别是多边形顶点横、纵坐标的数组,textx和testy是待测点的坐标。这个算法是由W.RandolphFranklin提出的,根据Jordancurvetheorem,多边形将平面分为内外两个区域,假设待测点在多边形内部,从待测点引出一条射线必然会与多边形有至少一个交点。该射线与多边形第一次相交时将“冲出”多边形,第二次相交将“进入”多边形,依此类推,若射线与多边形有奇数个交点,则该点在多边形内部,反之则在外部。
PNPoly算法正是从待测点引出一条水平向右的射线,并计算与多边形的交点个数。解释一下这段代码:for(i=0,j=nvert-1;i<nvert;j=i++)循环的含义就是始终让j=i?1,如果i=0那么j=nvert?1,从而依次检验多边形的每条边。接下来的重点就是条件语句,(verty[i]>testy)!=(verty[j]>testy)很好理解,就是一条边上的两个顶点分别在待测点的上方和下方,通过这条语句可以知道从待测点向右引出的射线有可能与该条边相交(只要待测点在边的左侧即可)。
但具体判断相交就要交给解析几何了。建系写出该条边所在直线的方程:
变形一下:
代入待测点坐标,根据图形关系得到这个不等式:
也就是语句testx<vertx[j]-vertx[i])*(testy-verty[i])/(verty[j]-verty[i])+vertx[i]了.
相关文章
- c++面试选择题_C语言经典笔试题
- C语言再学习 — 创建excel文件
- C语言:求最大公约数和最小公倍数「建议收藏」
- 操作系统linux:银行家算法(C语言实现)
- 操作系统银行家算法C语言代码实现「建议收藏」
- 蓝桥杯算法训练 金陵十三钗(dp状态压缩)------C语言—菜鸟级
- 算法训练 格子操作(线段树)-----------C语言—菜鸟级
- 二分匹配 匈牙利算法 模板-------------------C语言——菜鸟级
- 蛇行矩阵 蛇形填数 回形取数 蛇行系类(C语言详解+图解)
- 一个c语言程序能实现几种算法_C语言实现算法
- 【安全算法之SHA256】SHA256摘要运算的C语言源码实现
- 【安全算法之DES】DES算法(支持ECB/CBC模式)的C语言源码实现
- C语言 | 动图演示十大经典排序算法(含代码)
- 抽丝剥茧C语言(高阶)结构体,枚举,联合+练习
- [C语言] 数据结构-算法效率的度量方法-事前分析估算方法详解编程语言
- C语言除法算法和取模运算的实现(多种算法,多种思路)
- C语言统计单词个数,单词个数算法
- 数组倒序排列,数组倒置,C语言数组倒序算法详解
- feof和ferror函数,C语言feof和ferror函数详解
- C语言归并排序算法
- C语言二分查找算法,折半查找算法
- C语言分块查找算法,索引顺序查找算法
- MySQL与C语言编程实战(c编程mysql)
- C语言与Oracle的数据库连接一步到位(C语言入库oracle)
- Oracle连接释放C语言实现(c oracle释放连接)
- 掌握C语言,Oracle数据录入技巧(c oracle录入)
- 对C语言中递归算法的深入解析