当前位置: 首页 > news >正文

判断点在多边形内的算法

在计算几何中,判定点是否在多边形内,是个非常有趣的问题。通常有两种方法:

一、Crossing Number(交叉数)

它计算从点P开始的射线穿过多边形边界的次数。当“交叉数”是偶数时,点在外面;当它是奇数时,点在里面。这种方法有时被称为“奇-偶”检验。

如果一个多边形是不自交的(称为“简单多边形”),那么这两种方法对任意点都给出相同的结果。但对于非简单多边形,这两种方法在某些情况下会给出不同的答案。如下图所示,当一个多边形与自身重叠时,对于重叠区域内的点,如果使用交叉数判断,它在外面;而使用环绕数判断则在里面。
在这里插入图片描述在这里插入图片描述
在上图中,绿色区域中的点,wn = 2,表示在多边形中重叠了2次。相比于Crossing number,winding number给出了更内蕴性的答案。

尽管如此,早些时候,crossing number方法应用的更广泛,因为最初计算几何专家们错误地认为crossing number比winding number计算起来更加高效。但事实并非如此,两者的时间复杂度完全一样。Franklin在2000年给出一个计算winding number的非常快的实现。因此,为了几何正确性和效率的原因,在确定一个多边形中的一个点时,wn算法应该总是首选的。

该方法计算从点P开始的射线穿过多边形边界的次数(不管穿过的方向)。如果这个数是偶数,那么点在外面;否则,当交叉数为奇数时,点在多边形内。其正确性很容易理解,因为每次射线穿过多边形边缘时,它的内外奇偶性都会发生变化(因为边界总是分隔内外)。最终,任何射线都在边界多边形之外结束。所以,如果点在多边形内,那么对边界的穿过次序一定是:out>…>in>out,因此交叉数一定是奇数;同样地,如果点在多边形外,那么对边界的穿过次序一定是in > out … > in > out,因此交叉数必是偶数。
在这里插入图片描述在实现crossing number的算法时,必须确保只计算改变奇偶性的交叉位置。特别是,对于射线穿过顶点的情况需要适当的处理。下图列举了射线与多边形可能的相交情况:
在这里插入图片描述
此外,必须确定多边形边界上的点P是在内部还是外部。一般约定:如果点在边的左侧,那么认为点P在内部;如果点在边的右侧,那么认为点P在外部。如果两个不同的多边形共享一个共同的边界线段,那么该线段上的一点将会在一个多边形或另一个多边形中,而不是同时在两个多边形中。这避免了许多可能发生的问题,特别是在计算机图形显示中。

一个简单的做法是选择一条x轴正方向的水平射线,对于这样一条射线,很容易计算多边形的边与它的交点。而且,很容易确定交点是否存在。算法只需沿着多边形的每一条边,依次计算交点,当相交时,cn增加1,从而计算出最终的总交叉数。

此外,相交测试必须遵循如下的规则,处理一些特殊情况(如上图):

  • 向上的边,包含起点,但不包含终点;
  • 向下的边,包含终点,但不包含起点;
  • 水平的边,不包含起点和终点;
  • 边与射线的交点必须严格在点P的右侧

按照上述规则,处理特殊的相交情况,就能得到正确的交叉数。其中,规则4将导致在边界右侧的点在多边形外部,在左侧的点将会被判定为在内部。

Crossing Number Pseudo-Code:
对于n个点组成的多边形V={V[0], V[1], …,V[n]},其中V[n]=V[0], 计算几何大牛Franklin给出了一个非常有名的实现:

typedef struct {int x, y;} Point;cn_PnPoly( Point P, Point V[], int n )
{int    cn = 0;    // the  crossing number counter// loop through all edges of the polygonfor (each edge E[i]:V[i]V[i+1] of the polygon) {if (E[i] crosses upward ala Rule #1|| E[i] crosses downward ala  Rule #2) {if (P.x <  x_intersect of E[i] with y=P.y)   // Rule #4++cn;   // a valid crossing to the right of P.x}}return (cn&1);    // 0 if even (out), and 1 if  odd (in)}

注意,对于满足规则1和2的向上和向下交叉的测试也排除了水平边缘(规则3)。总而言之,很多工作是通过几个测试完成的,这使得这个算法很优雅。

然而,交叉数方法的有效性是基于“约当曲线定理”(Jordan Curve Theorem),该定理表明,一条简单的闭合曲线将二维平面分成两个完全连通的分量:一个有界的“内”分量和一个无界的“外”分量。需要注意的是,曲线必须是简单的(没有自身交叉),否则可能有两个以上的组成部分,然后就不能保证跨越边界改变进出奇偶性。因此,该方法不适用于自相交的多边形。

二、Winding Number(环绕数)

它计算多边形绕着点P旋转的次数。只有当“圈数”wn = 0时,点才在外面; 否则,点在里面。

winding number方法能准确判定一个点是否在自交的封闭曲线内。该方法通过计算多边形有多少次环绕点P来实现。只有当多边形不环绕该点,也就是环绕数wn = 0时,一个点才在外面。

不妨定义:平面上的点P相对于任意连续封闭曲线的环绕数为{wn}(P,C)。对于一条水平向右的射线R,我们每一条与R相交的边需要判断其终点在R上面还是下面。如果边从下往上穿过R,wn+1;否则wn-1。所有边遍历一遍,最终得到总的f{wn}(P,C),如下图所示:
在这里插入图片描述

此外,我们没必要计算实际的交点,只需要使用如下方法判断当前穿过的边的环绕数应该+1还是-1:

如下图所示,如果一条边向上穿过射线R,那么P点在边ViVi+1的左侧;而对于一条向下的边,P点在边ViVi+1的右侧。
在这里插入图片描述

通过以上分析,容易给出如下的wn计算伪代码(和cn的计算一样使用相同的边相交规则):

 
typedef struct {int x, y;} Point;wn_PnPoly( Point P, Point V[], int n )
{int    wn = 0;    // the  winding number counter// loop through all edges of the polygonfor (each edge E[i]:V[i]V[i+1] of the polygon) {if (E[i] crosses upward ala Rule #1)  {if (P is  strictly left of E[i])    // Rule #4++wn;   // a valid up intersect right of P.x}elseif (E[i] crosses downward ala Rule  #2) {if (P is  strictly right of E[i])   // Rule #4--wn;   // a valid down intersect right of P.x}}return wn;    // =0 <=> P is outside the polygon}

显然,环绕数方法与交叉数方法有着相同的计算效率。但由于该方法更加具有普遍性,因此,在确定一个点是否在任意多边形内时,推荐使用Winding Number方法。

通过一些技巧可以进一步提高wn算法的效率,在下面给出的wn_PnPoly() 的实现中,我们可以看到这一点。在该代码中,所有完全在P以上或完全在P以下的边只经过两次不等式检验就被拒绝(没有交点)。然而,在目前流行的cn算法的实现中,需要3次不等式检验才能做到这一点。由于在实际应用中,大多数边都会被拒绝,因此进行比较的次数减少了大约33%(或更多)。在使用非常大的(1,000,000边)随机多边形(边长<多边形直径的1/10)和1000个随机测试点(在多边形的边界内)进行运行时测试时,测试结果表明wn算法的平均效率提高了20%。

相关文章:

判断点在多边形内的算法

在计算几何中&#xff0c;判定点是否在多边形内&#xff0c;是个非常有趣的问题。通常有两种方法&#xff1a; 一、Crossing Number&#xff08;交叉数&#xff09; 它计算从点P开始的射线穿过多边形边界的次数。当“交叉数”是偶数时&#xff0c;点在外面;当它是奇数时&…...

Network AIS Receiver R400N

目录 Introduction OVERVIEW BASIC FEATURES APPLICATIONS SPECIFICATIONS Introduction OVERVIEW The R400N provides a method of monitoring the position, speed and heading of AIS vessels within VHF range. It can decode of Class A, Class B, Aids to Navigat…...

JavaScript循环

JavaScript的循环有两种&#xff0c;一种是for循环&#xff0c;通过初始条件、结束条件和递增条件来循环执行语句块&#xff1a; var x 0; var i; for (i1; i<10000; i) { x x i; } x; // 50005000 for循环的3个条件都是可以省略的&#xff0c;如果没有退出循环的判断条件…...

9Proxy,跨境电商一站式解决方案

文章目录 跨境电商什么是跨境电商跨境电商的机遇跨境电商技术支撑 海外代理IP什么是海外代理IP海外代理IP的作用如何选择海外代理IP 9Proxy9Proxy的优势9Proxy的解决方案价格汇总搜索引擎优化市场调查多重核算数据抓取广告技术 价格上手体验注册登录下载安装数据采集 总结福利 …...

ObjectiveC-08-OOP面向对象程序设计-类的分离与组合

本节用一简短的文章来说下是ObjectiveC中的类。类其实是OOP中的一个概念&#xff0c;概念上简单来讲类是它是一组关系密切属性的集合&#xff0c;所谓的关系就是对现实事物的抽象。 上面提到的关系包括很多种&#xff0c;比如has a&#xff0c; is a&#xff0c;has some等&…...

Qt 总结

由于工作需要用到Qt。把过程中学习到的东西记录下来&#xff0c;希望能帮到他人和将来的自己。 由于需要快速实现需求&#xff0c;所以对Qt只是使用&#xff0c;并没有对原理的深入理解。 故此文只适合入门&#xff0c;不适合深入学习Qt。 文章目录 安装&维护示例&教…...

中间件复习之-RPC框架

什么是RPC框架&#xff1f; RPC(Remote Procedure Call):远程过程调用。当多个应用部署在多个服务器上时&#xff0c;由于他们不在一个内存空间上&#xff0c;因此需要网络来进行通信&#xff0c;而RPC允许它像调用本地方法一样调用远程服务。 RPC原理 服务消费方通过RPC客户…...

AcWing 787. 归并排序——算法基础课题解

AcWing 787. 归并排序 文章目录 题目描述CGo模板 题目描述 给定你一个长度为 n 的整数数列。 请你使用归并排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行&#xff0c;第一行包含整数 n。 第二行包含 n 个整数&#xff08;所有…...

力扣1379---找出克隆二叉树的相同节点(Java、DFS、简单题)

目录 题目描述&#xff1a; 思路描述&#xff1a; 代码&#xff1a; &#xff08;1&#xff09;&#xff1a; &#xff08;2&#xff09;&#xff1a; 题目描述&#xff1a; 给你两棵二叉树&#xff0c;原始树 original 和克隆树 cloned&#xff0c;以及一个位于原始树 ori…...

FLink学习(三)-DataStream

一、DataStream 1&#xff0c;支持序列化的类型有 基本类型&#xff0c;即 String、Long、Integer、Boolean、Array复合类型&#xff1a;Tuples、POJOs 和 Scala case classes Tuples Flink 自带有 Tuple0 到 Tuple25 类型 Tuple2<String, Integer> person Tuple2.…...

Failed to resolve import “Home/components/HomeNew.vue“. Does the file exist?

错误信息 [plugin:vite:import-analysis] Failed to resolve import "/apis/home.js" from "src/views/Home/components/HomeNew.vue". Does the file exist? 错误原因 路径错误 解决方法...

《价值》-张磊-高瓴资本-3-建立人脉和信任;顺应趋势,把握机遇;

第三章 价值投资初试炼 2005.6.1 创办高瓴资本 许多人问我为什么一直在创业&#xff0c;其实我倒没想到自己非要创业成功不可&#xff0c;只是觉得一定要做点事&#xff0c;做点有意义的事。归根到底&#xff0c;可能是“爱折腾&#xff0c;不满足现状&#xff0c;爱挑战自己”…...

游戏引擎中的物理应用

一、 角色控制器 Character Controller和普通的动态对象&#xff08;Dynamic Actor &#xff09;是不同的&#xff0c;主要的三个特点是: 它拥有可控制的刚体间的交互假设它是有无穷的摩擦力&#xff08;可以站停在位置上&#xff09;&#xff0c;没有弹性加速和刹车几乎立即…...

复现k8s黄金票据学习

1.什么是黄金票据 在 Kubernetes 中&#xff0c;"黄金票据"并不是一个常见的术语。可能你想了解的是服务账户&#xff08;Service Account&#xff09;。服务账户是 Kubernetes 中用于身份验证和授权的一种机制。它们允许 Pods 或其他工作负载在 Kubernetes 集群中与…...

08-JavaScript BOM定时器及JS动画

1. 设置定时器 1.1设置超时定时器 超时调用需要使用window对象的setTimeout()方法&#xff0c;该方法接受两个参数&#xff1a;调用函数或计算表达式和以毫秒为单位的时间&#xff08;即在执行代码前需要等待多少毫秒&#xff09;。 //setTimeout(callback, after) //callba…...

边缘计算盒子与云计算:谁更适合您的业务需求?

边缘计算盒子和云计算&#xff0c;这两个概念听起来可能有点复杂&#xff0c;但其实它们就是两种不同的数据处理方式。那谁更适合您的业务需求呢&#xff1f;咱们来详细说说。 边缘计算盒子&#xff0c;就像是个小型的数据处理中心&#xff0c;放在离你业务现场比较近的地方。它…...

浅聊什么是Redis?

需求&#xff1a;MySQL面临大量的查询&#xff0c;即读写操作&#xff0c;因此类比CPU&#xff0c;给数据加缓存&#xff0c;Redis诞生。应用程序从MySQL查询的数据&#xff0c;在Redis设置缓存&#xff08;记录在内存中&#xff0c;无需IO操作&#xff09;&#xff0c;后再需要…...

java算法day43 | ● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零

1049. 最后一块石头的重量 II 核心思想&#xff1a; 尽量让石头分成重量相同的两堆&#xff0c;相撞之后剩下的石头最小&#xff0c;这样就化解成01背包问题了。 是不是感觉和昨天讲解的416. 分割等和子集 (opens new window)非常像了。那么分成两堆石头&#xff0c;一堆石头的…...

练气第六天

问:ANR怎么分析&#xff1f; ANR问题&#xff0c;这其实是一个非常综合性的问题&#xff0c;因为anr会涉及CPU负载&#xff0c;内存空间大小&#xff0c;线程锁&#xff0c;GC回收&#xff0c;这里面每个点&#xff0c;都是非常考验我们基本功的。 分析ANR问题&#xff0c;需…...

认识 Redis 与 分布式

Redis 官网页面 Redis官网链接 Redis 的简介 Redis 是一个在内存中存储数据的中间件 一方面用于作为数据库&#xff0c;另一方面用于作为数据缓存&#xff0c;适用于分布式系统中 Redis 基于网络&#xff0c;进行进程间通信&#xff0c;把自己内存中的变量给别的进程&#xf…...

Linux初学(十二)AWK进阶

一、AWK 1.1 简介 AWK是Linux中重要的文本处理工具Linux三剑客只一处理的对象可以是一个具体的文件&#xff0c;也可以是一个命令的执行结果AWK按行读取文件&#xff0c;将每一行视为一条记录 案例一&#xff1a;获取系统中每个用户的uid 方法一&#xff1a;cat /etc/passwd |…...

文字识别 Optical Character Recognition,OCR CTC STN

文字识别 Optical Character Recognition,OCR 自然场景文本检测识别技术综述 将图片上的文字内容,智能识别成为可编辑的文本。 场景文字识别(Scene Text Recognition,STR) OCR(Optical Character Recognition, 光学字符识别)传统上指对输入扫描文档图像进行分析处理,识…...

四、MySQL读写分离之MyCAT

一、读写分离概述 1、什么是读写分离&#xff1a; 读写分离&#xff1a;就是将读写操作分发到不同的服务器&#xff0c;读操作分发到对应的服务器 &#xff08;slave&#xff09;&#xff0c;写操作分发到对应的服务器&#xff08;master&#xff09; ① M-S (主从) 架构下&…...

通讯录项目实现

引言&#xff1a;通过顺序表的逻辑实现通讯录。这里就不讲关于顺序表的函数了。如果有不明白的可以看我写的顺序表的博客。 目录 顺序表与通讯录的比较 各源文件文件大榄 Contact.c中通讯录相关函数的定义 初始化和销毁通讯录 添加联系人&#xff1a; 删除联系人&#xf…...

xss相关知识点与绕过思路总结

前言 对xss的绕过进行了系统的学习与实践后&#xff0c;重新审视一下xss&#xff0c;对他的绕过进行一个总结。 &#xff08;当然我也是个小白&#xff0c;这些也是我当时瞎鸡儿乱搞绕过了几个xss自己做的小总结&#xff09; 可能有点丑陋&#xff0c;献丑了。 好博客推荐 …...

深入解析语言模型:原理、实战与评估

引言 随着人工智能的飞速发展&#xff0c;语言模型作为自然语言处理&#xff08;NLP&#xff09;的核心技术之一&#xff0c;日益受到业界的广泛关注。本文旨在深入探讨语言模型的原理、实战应用以及评估方法&#xff0c;帮助读者更好地理解和应用这一技术。 一、语言模型原理…...

Elasticsearch 的索引优化常规项

优化常规项 https://blog.csdn.net/bairo007/article/details/132019575 1、按实际情况适当调整主分片的数量 如果主分片数量太少&#xff0c;会导致每个分片中的数据量过大&#xff0c;而且无法利用集群中所有节点的计算资源。如果主分片数量太多&#xff0c;会导致索引过度…...

【JavaParser笔记01】JavaParser解析Java源代码中的类信息(javadoc注释、类​​​​​​​名称)

这篇文章,主要介绍如何使用JavaParser解析Java源代码中的类信息(javadoc注释、类名称)。 目录 一、JavaParser依赖库 1.1、引入依赖 1.2、获取类注释信息...

Stable Diffusion扩散模型【详解】小白也能看懂!!

文章目录 1、Diffusion的整体过程2、加噪过程2.1 加噪的具体细节2.2 加噪过程的公式推导 3、去噪过程3.1 图像概率分布 4、损失函数5、 伪代码过程 此文涉及公式推导&#xff0c;需要参考这篇文章&#xff1a; Stable Diffusion扩散模型推导公式的基础知识 1、Diffusion的整体…...

关于rabbitmq的prefetch机制

消息预取机制&#xff08;Prefetch Mechanism&#xff09;是RabbitMQ中用于控制消息传递给消费者的一种机制。它定义了在一个信道上&#xff0c;消费者允许的最大未确认的消息数量。一旦未确认的消息数量达到了设置的预取值&#xff0c;RabbitMQ就会停止向该消费者发送更多消息…...

阿里巴巴武汉网站建设/适合奖励自己的网站免费

一直对时间函数有点兴趣,今天打开time.h看了一下.发现内容也不是太多.于是看了看.这是c库里的.C的,改日再看.一边看一边写了总结,呵呵,效果不错. 在 time.h 文件中。首先我们可以看到 typedef long time_t; 这就可以明确地知道 time_t是一个long型 而为什么要这样做呢&#xff…...

做网站vi系统是什么/合肥百度搜索优化

免费自动化测试软件 AlldayTest下载地址为&#xff1a; http://www.alldaytest.com/download.do?lancn 绿色免费版下载地址华军软件园也有AlldayTest兼具功能测试和性能测试&#xff0c;支持测试Web(html,ASP,JSP,PHP等),C#,VB,C,Activex,Silverlight,WPF等多种编程语言编写的…...

网站欢迎页面在线设计/人民网 疫情

一、环境准备 1、准备三台服务器 192.168.123.103 master 192.168.123.104 data1 192.168.123.105 data2 2、更改服务器hosts #vim /etc/hosts 127.0.0.1 localhost localhost.localdomain localhost4 localhost4.localdomain4 ::1 localhost local…...

app网站建设宣传方案/今日新闻最新头条

需求&#xff1a;爬取豆瓣小组所有话题&#xff08;话题title&#xff0c;内容&#xff0c;作者&#xff0c;发布时间&#xff09;&#xff0c;及回复&#xff08;最佳回复&#xff0c;普通回复&#xff0c;回复_回复&#xff0c;翻页回复&#xff0c;0回复&#xff09; 解决&a…...

虚拟网站建设/百度广告上的商家可靠吗

以下是在制定测试策略时要考虑的最常见的软件测试类型列表以及测试说明&#xff1a; 功能测试 - 这种类型的测试侧重于用户的体验。从测试 代码 的小组件到 UI 的完整端到端测试&#xff0c;功能测试可确保您的应用程序按预期工作。它有助于防止限制用户访问您的应用程序的问题…...

网站服务器做缓存吗/手机如何制作自己的网站

详解Linux交互式shell脚本中创建对话框实例教程 本教程我们通过实现来讲讲Linux交互式shell脚本中创建各种各样对话框&#xff0c;对话框在Linux中可以友好的提示操作者&#xff0c;感兴趣的朋友可以参考学习一下。 当你在终端环境下安装新的软件时&#xff0c;你可以经常看到信…...