C语言实现的PNPoly算法代码例子

写C语言的实验用到的一个算法，判断一个点是否在多边形的内部。C的代码如下：

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, 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;
    }
  return c;
}

其中nvert是多边形顶点的个数，vertx和verty分别是多边形顶点横、纵坐标的数组，textx和testy是待测点的坐标。这个算法是由W. Randolph Franklin提出的，根据Jordan curve theorem，多边形将平面分为内外两个区域，假设待测点在多边形内部，从待测点引出一条射线必然会与多边形有至少一个交点。该射线与多边形第一次相交时将“冲出”多边形，第二次相交将“进入”多边形，依此类推，若射线与多边形有奇数个交点，则该点在多边形内部，反之则在外部。

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]了.

赞 (0)

相关推荐

  • C语言实现字符串匹配KMP算法

    C语言实现字符串匹配KMP算法

    字符串匹配是计算机的基本任务之一. 举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"? 下面的的KMP算法的解释步骤 1. 首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较.因为B与A不匹配,所以搜索词后移一位. 2. 因为B与A不匹配,搜索词再往后移. 3. 就这样,直到字符

  • C语言位图算法详解

    C语言位图算法详解

    本文详细讲述了位图算法的定义与C语言实现方法,分享给大家供大家参考之用.具体如下: 位图法定义: 位图法就是bitmap的缩写,所谓bitmap,是用每一位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况.通常是用来判断某个数据存不存在的. 例如,要判断一千万个人的状态,每个人只有两种状态:男人,女人,可以用0,1表示.那么就可以开一个int数组,一个int有32个位,就可以表示32个人.操作的时候可以使用位操作.   数据结构: unsigned int bit[N]; 在这个数组

  • 纯C语言：贪心Prim算法生成树问题源码分享

    复制代码 代码如下: #include <iostream.h>#define MAX 100#define MAXCOST 100000 int graph[MAX][MAX]; int Prim(int graph[MAX][MAX], int n){ /* lowcost[i]记录以i为终点的边的最小权值,当lowcost[i]=0时表示终点i加入生成树 */ int lowcost[MAX]; /* mst[i]记录对应lowcost[i]的起点 */ int mst[MAX]; in

  • C程序实现整数的素数和分解问题

    C程序实现整数的素数和分解问题

    本文以实例形式讲述了C程序实现整数的素数和分解问题,分享给大家供大家参考之用.具体方法如下: 要求:对于一个给定的整数,输出所有这种素数的和分解式,对于同构的分解只输出一次(比如5只有一个分解2+3,而3+2是2+3的同构分解式). 例如: 对于整数8,可以作为如下三种分解: (1) 8 = 2 + 2 + 2 + 2 (2) 8 = 2 + 3 + 3 (3) 8 = 3 + 5   看到此题时,我的头一反应是求解背包问题 思路如下: f(N, array) = f(N - array[i],

  • C语言实现的排列组合问题的通用算法、解决方法

    尽管排列组合是生活中经常遇到的问题,可在程序设计时,不深入思考或者经验不足都让人无从下手.由于排列组合问题总是先取组合再排列,并且单纯的排列问题相对简单,所以本文仅对组合问题的实现进行详细讨论.以在n个数中选取m(0<m<=n)个数为例,问题可分解为: 1. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止. 2. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m. 很明显,上述方法是一个递归的过程,也

  • c语言实现冒泡排序、希尔排序等多种算法示例

    实现以下排序 插入排序O(n^2) 冒泡排序 O(n^2) 选择排序 O(n^2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 希尔排序 O(n^1.25) 1.插入排序 O(n^2) 一般来说,插入排序都采用in-place在数组上实现.具体算法描述如下:⒈ 从第一个元素开始,该元素可以认为已经被排序⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置⒋ 重复步骤3,直到找到已排序的元素

  • C语言对堆排序一个算法思路和实现代码

    算法思想简单描述: 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称之为堆.在这里只讨论满足前者条件的堆. 由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项.完全二叉树可以很直观地表示堆的结构.堆顶为根,其它为左子树.右子树. 初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的

  • 马尔可夫链算法（markov算法）的awk、C++、C语言实现代码

    1. 问题描述 马尔可夫链算法用于生成一段随机的英文,其思想非常简单.首先读入数据,然后将读入的数据分成前缀和后缀两部分,通过前缀来随机获取后缀,籍此产生一段可读的随机英文. 为了说明方便,假设我们有如下一段话:   复制代码 代码如下: Show your flowcharts and conceal your tables and I will be mystified. Show your tables and your flowcharts will be obvious. 假设前缀的长

  • C语言的数字游戏算法效率问题探讨实例

    最近做了这样一个题目,感觉挺有趣~题目如下: 问题描述 Winder 最近在玩一个数字游戏,该游戏是在一个n*m 的网格上进行的,每个格子上有 一个数字,代表这个格子的数值.玩家需要从网格的左上角的格子走到右下角的格子,每次 只能向右或者向下走,并且不能回头.玩家每经过一个格子可以选择分值是否加上该格子的 数值,每次游戏的初始分数都是0. Winder 想知道在每场游戏,他最多能够得到多少分值.但是,Winder 很懒,所以你必 须帮他来完成这件事. 数据输入 输入第一行两个正整数N 和M(0<

  • C语言实现排序算法之归并排序详解

    排序算法中的归并排序(Merge Sort)是利用"归并"技术来进行排序.归并是指将若干个已排序的子文件合并成一个有序的文件. 一.实现原理: 1.算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中. (1)合并过程 合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置.合并时依次比较R[i

  • C语言快速幂取模算法小结

    C语言快速幂取模算法小结

    本文实例汇总了C语言实现的快速幂取模算法,是比较常见的算法.分享给大家供大家参考之用.具体如下: 首先,所谓的快速幂,实际上是快速幂取模的缩写,简单的说,就是快速的求一个幂式的模(余).在程序设计过程中,经常要去求一些大数对于某个数的余数,为了得到更快.计算范围更大的算法,产生了快速幂取模算法.我们先从简单的例子入手:求abmodc 算法1.直接设计这个算法: int ans = 1; for(int i = 1;i<=b;i++) { ans = ans * a; } ans = ans %

  • c语言实现单链表算法示例分享

    复制代码 代码如下: #include <stdio.h>#include <stdlib.h>typedef char DataType;typedef struct Node{    DataType data;    struct Node * Next;}ListNode,* LinkList;void Judement(LinkList head){ //判断分配内存    if (!head){        printf("Overflow.");

随机推荐