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

判断点在多边形内部

0. 介绍

网上资料很多,只简单介绍下,方便自己今后的理解。

1. 射线法

从该点引一条射线出来,如果和多边形有偶数个交点,则点在多边形外部。

因为有入必有出,所以从外部引进来的射线一定是交多边形偶数个点。

如图

在这里插入图片描述

这种方法唯一注意点是处理,引出的这条射线包括了多边形的边或者端点。

对此为了保证不重复,我们忽略在该射线上的边,和终点在该射线上的点。

实现

#define MIN(x,y) (x < y ? x : y)
#define MAX(x,y) (x > y ? x : y)
#define INSIDE 0
#define OUTSIDE 1typedef struct {double x,y;
} Point;int InsidePolygon(Point *polygon,int N,Point p)
{int counter = 0;int i;double xinters;Point p1,p2;p1 = polygon[0];for (i=1;i<=N;i++) {p2 = polygon[i % N];if (p.y > MIN(p1.y,p2.y)) // 确保了点在多边形端点上,点的相邻边只被计算了一次。{if (p.y <= MAX(p1.y,p2.y)) {if (p.x <= MAX(p1.x,p2.x)) {// 为使得水平射线与边相交的条件 // y_0 < y <= y_1// min(x_0,x_1) < xif (p1.y != p2.y) {xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;// 判断点是否在这条边的左侧if (p1.x == p2.x || p.x <= xinters)counter++;}}}}p1 = p2;}if (counter % 2 == 0)return(OUTSIDE);elsereturn(INSIDE);
}

判断点在边的左侧的示意图

在这里插入图片描述

2. 内角和

当点在多边形内时,内角和为 2 π 2 \pi 2π

实现参考

typedef struct {int h,v;
} Point;int InsidePolygon(Point *polygon,int n,Point p)
{int i;double angle=0;Point p1,p2;for (i=0;i<n;i++) {p1.h = polygon[i].h - p.h;p1.v = polygon[i].v - p.v;p2.h = polygon[(i+1)%n].h - p.h;p2.v = polygon[(i+1)%n].v - p.v;angle += Angle2D(p1.h,p1.v,p2.h,p2.v);}if (ABS(angle) < PI)return(FALSE);elsereturn(TRUE);
}/*Return the angle between two vectors on a planeThe angle is from vector 1 to vector 2, positive anticlockwiseThe result is between -pi -> pi
*/
double Angle2D(double x1, double y1, double x2, double y2)
{double dtheta,theta1,theta2;theta1 = atan2(y1,x1);theta2 = atan2(y2,x2);dtheta = theta2 - theta1;while (dtheta > PI)dtheta -= TWOPI;while (dtheta < -PI)dtheta += TWOPI;return(dtheta);
}

3. 同侧法

当多边形为凸多边形时,我们可以判断该点是否在各个边形成的直线的一侧;

来判断点是否在多边形的内部。实际上就是一个线性规划问题。

凹多边形的凹角附近不满足该条件。

只需要判断

( x − x 0 ) ( y 1 − y 0 ) + ( y − y 0 ) ( x 0 − x 1 ) (x-x_0)(y_1-y_0)+(y-y_0)(x_0-x_1) (xx0)(y1y0)+(yy0)(x0x1)

的值即可判断,点在多边形边的哪一侧。

给定两个点 P 0 ( x 0 , y 0 ) , P 1 ( x 1 , y 1 ) P_0(x_0,y_0),P_1(x_1,y_1) P0(x0,y0),P1(x1,y1),直线一般方程 A x + B y + c = 0 Ax+By+c=0 Ax+By+c=0推导。

  1. x 0 = x 1 x_0=x_1 x0=x1
    x − x 0 = 0 x-x_0=0 xx0=0
  2. x 0 ≠ x 1 x_0 \ne x_1 x0=x1
    直线点斜式方程 y = k x + b k = y 1 − y 0 x 1 − x 0 带入 P 0 , P 1 b = y 0 − k x 0 b = y 1 − k x 1 2 b = ( y 0 + y 1 ) − k ( x 0 + x 1 ) 带入 k ,化简得到 b = x 1 y 0 − x 0 y 1 x 1 − x 0 化为一般式子得到 ( y 1 − y 0 ) x + ( x 0 − x 1 ) y + x 1 y 0 − x 0 y 1 = 0 更加统一的形式 ( y 1 − y 0 ) ( x − x 0 ) + x 0 y 1 − x 0 y 0 + ( x 0 − x 1 ) ( y − y 0 ) + x 0 y 0 − x 1 y 0 + x 1 y 0 − x 0 y 1 = 0 合并化简得到 ( x − x 0 ) ( y 1 − y 0 ) − ( y − y 0 ) ( x 1 − x 0 ) = 0 直线点斜式方程y=kx+b\\ k=\frac{y_1- y_0}{x_1-x_0}\\ 带入P_0,P_1\\ b=y_0-kx_0\\ b=y_1-kx_1\\ 2b=(y_0+y_1)-k(x_0+x_1)\\ 带入k,化简得到\\ b=\frac{x_1y_0-x_0y_1}{x_1-x_0}\\ 化为一般式子得到\\ (y_1-y_0)x+(x_0-x_1)y+x_1y_0-x_0y_1=0\\ 更加统一的形式\\(y_1-y_0)(x-x_0)+x_0y_1-x_0y_0+\\(x_0-x_1)(y-y_0)+x_0y_0-x_1y_0+x_1y_0-x_0y_1=0\\ 合并化简得到\\ (x-x_0)(y_1-y_0)-(y-y_0)(x_1-x_0)=0 直线点斜式方程y=kx+bk=x1x0y1y0带入P0,P1b=y0kx0b=y1kx12b=(y0+y1)k(x0+x1)带入k,化简得到b=x1x0x1y0x0y1化为一般式子得到(y1y0)x+(x0x1)y+x1y0x0y1=0更加统一的形式(y1y0)(xx0)+x0y1x0y0+(x0x1)(yy0)+x0y0x1y0+x1y0x0y1=0合并化简得到(xx0)(y1y0)(yy0)(x1x0)=0
  3. x 0 = x 1 x_0=x_1 x0=x1代入 ( x − x 0 ) ( y 1 − y 0 ) − ( y − y 0 ) ( x 1 − x 0 ) = 0 (x-x_0)(y_1-y_0)-(y-y_0)(x_1-x_0)=0 (xx0)(y1y0)(yy0)(x1x0)=0;
    得到 x − x 0 = 0 x-x_0=0 xx0=0

归纳可得直线一般式方程
( y 1 − y 0 ) x + ( x 0 − x 1 ) y + x 1 y 0 − x 0 y 1 = 0 或 ( x − x 0 ) ( y 1 − y 0 ) − ( y − y 0 ) ( x 1 − x 0 ) = 0 (y_1-y_0)x+(x_0-x_1)y+x_1y_0-x_0y_1=0\\ 或\\ (x-x_0)(y_1-y_0)-(y-y_0)(x_1-x_0)=0 (y1y0)x+(x0x1)y+x1y0x0y1=0(xx0)(y1y0)(yy0)(x1x0)=0

4. 原文

eecs

相关文章:

判断点在多边形内部

0. 介绍 网上资料很多&#xff0c;只简单介绍下&#xff0c;方便自己今后的理解。 1. 射线法 从该点引一条射线出来&#xff0c;如果和多边形有偶数个交点&#xff0c;则点在多边形外部。 因为有入必有出&#xff0c;所以从外部引进来的射线一定是交多边形偶数个点。 如图…...

livox雷达斜装修改

fast_lio中的mid360.yaml中的外参 extrinsic_est_en: false # true: enable the online estimation of IMU-LiDAR extrinsicextrinsic_T: [ -0.011, -0.02329, 0.04412 ]extrinsic_R: [ 1, 0, 0,...

【Spring】初识 Spring AOP(面向切面编程)

目录 1、介绍AOP 1.1、AOP的定义 1.2、AOP的作用 1.3、AOP的核心概念及术语 2、AOP实现示例 3、EnableAspectJAutoProxy注解 1、介绍AOP 1.1、AOP的定义 AOP&#xff08;Aspect Orient Programming&#xff09;&#xff0c;直译过来就是面向切面编程&#xff0c;AOP 是一…...

k8s各个组件的作用

Kubernetes&#xff08;K8s&#xff09;是一个开源的容器编排平台&#xff0c;用于自动化计算机容器化应用程序的部署、扩展和管理。以下是 Kubernetes 中的关键组件及其作用&#xff1a; API 服务器&#xff08;API Server&#xff09;&#xff1a; 作为集群中所有资源操作的入…...

Spring Cloud 整合Sentinel

1、引入依赖 版本说明 alibaba/spring-cloud-alibaba Wiki GitHub 父pom <spring.cloud.version>Hoxton.SR12</spring.cloud.version> <spring.cloud.alibaba.version>2.2.10-RC1</spring.cloud.alibaba.version>Sentinel应用直接引用starter <…...

Java入门基础学习笔记4——开发Helloworld入门程序

Java程序开发的三个步骤&#xff1a; 1&#xff09;编写代码 2&#xff09;编译代码 3&#xff09;运行代码 注意事项&#xff1a; 第一个java程序建议使用记事本来编写。 建议代码文件名全英文、首字母大写、满足驼峰模式&#xff0c;源代码文件的后缀必须是.java 注意&a…...

了解WebSocket

1.概念&#xff1a; WebSocket是一种在单个TCP连接上进行全双工通信的协议&#xff0c;属于应用层协议。 WebSocket使得客户端和服务器之间的数据交换变得更加简单&#xff0c;允许服务端主动向客户端推送数据。在WebSocket API中&#xff0c;浏览器和服务器只需要完成一次握…...

从开发角度理解漏洞成因(02)

文章目录 文件上传类需求文件上传漏洞 文件下载类需求文件下载漏洞 扩展 留言板类&#xff08;XSS漏洞&#xff09;需求XSS漏洞 登录类需求cookie伪造漏洞万能密码登录 持续更新中… 文章中代码资源已上传资源&#xff0c;如需要打包好的请点击PHP开发漏洞环境&#xff08;SQL注…...

Web实时通信的学习之旅:轮询、WebSocket、SSE的区别以及优缺点

文章目录 一、通信机制1、轮询1.1、短轮询1.2、长轮询 2、Websocket3、Server-Sent Events 二、区别1、连接方式2、协议3、兼容性4、安全性5、优缺点5.1、WebSocket 的优点&#xff1a;5.2、WebSocket 的缺点&#xff1a;5.3、SSE 的优点&#xff1a;5.4、SSE 的缺点&#xff1…...

TMS320F280049 CLB模块--LUT4 OUTLUT(4)

LUT4 示意图如下&#xff1a; OUTLUT 示意图如下&#xff1a; 寄存器 参考文档&#xff1a; TMS320F28004x Real-Time Microcontrollers Technical Reference Manual (Rev. G)...

功能测试_分类_用例_方法

总结 测试分类 按阶段分类 是否查看源代码分类 是否运行分类 是否自动化 其他分类 软件质量模型 开发模型-瀑布模型 测试过程模型 v w 测试用例八大要素 用例编号 用例标题 …...

[沫忘录]MySQL 锁

[沫忘录]MySQL 锁 锁能够协调多线程或多进程并发访问某资源产生的数据冲突与错乱。而在数据库中&#xff0c;锁也是协调数据库访问的有效工具。 全局锁 能够锁住当前服务器所有数据库及其表。后续所有事务都只能进行读操作&#xff0c;而不能进行写操作或表属性更改。 典型…...

噪声嵌入提升语言模型微调性能

在自然语言处理&#xff08;NLP&#xff09;的快速发展中&#xff0c;大模型&#xff08;LLMs&#xff09;的微调技术一直是研究的热点。最近&#xff0c;一篇名为《NEFTUNE: NOISY EMBEDDINGS IMPROVE INSTRUCTION FINETUNING》的论文提出了一种新颖的方法&#xff0c;通过在训…...

XML文档基本语法

XML文档基本语法包括以下几个知识点&#xff1a; 开始标记&#xff08;Start Tag&#xff09;&#xff1a;开始标记是XML元素的起始符号&#xff0c;由左尖括号&#xff08;<&#xff09;和元素名称组成。例如&#xff0c;是一个开始标记&#xff0c;表示一个名为"book…...

git开发工作流程

git开发工作流程 &#xff08;1&#xff09;先将远程代码pull到本地 &#xff08;2&#xff09;在本地上分支上进行开发 &#xff08;3&#xff09;开发完之后&#xff0c;push到远程分支 &#xff08;4&#xff09;由远程的master进行所有分支合并...

JDK生成https配置

keytool -genkey -v -alias tomcat -keyalg RSA -keystore D:\https证书\weChat.keystore -validity 36500 -keypass 250250 keytool -importkeystore -srcstoretype JKS -srckeystore D:\https证书\weChat.keystore -srcstorepass 250250 -srcalias tomcat -srckeypass 25025…...

通过 Java 操作 redis -- set 集合基本命令

目录 使用命令 sadd &#xff0c;smembers 使用命令 sismember 使用命令 scard 使用命令 spop 使用命令 sinter&#xff0c;sinterstore&#xff0c;sunion&#xff0c;sunionstore&#xff0c;sdiff&#xff0c;sdiffstore 关于 redis set 集合类型的相关命令推荐看Redis …...

WebSocket前后端建立以及使用

1、什么是WebSocket WebSocket 是一种在 Web 应用程序中实现双向通信的协议。它提供了一种持久化的连接&#xff0c;允许服务器主动向客户端推送数据&#xff0c;同时也允许客户端向服务器发送数据&#xff0c;实现了实时的双向通信。 这部分直接说你可能听不懂&#xff1b;我…...

C++数据结构之链表树图的存储

本文主要介绍用数组存储&#xff0c;结构只做简单介绍 目录 文章目录 前言 结构体实现 1、链表的存储 2、树的存储 3、图的存储 数组实现 1、链表实现 2、树和图的实现 总结 前言 在正常工程中&#xff0c;我们通常使用结构体或者类&#xff0c;来定义并使用如链表…...

又一位互联网大佬转行当网红,能写进简历么?

最近半个月&#xff0c;有两个中年男人仿佛住进了热搜。 一个是刚刚辟谣自己“卡里没有冰冷的 40 亿”的雷军&#xff0c;另一个则是在今年年初就高呼“如果有可能&#xff0c;企业家都要去当网红”的 360 创始人周鸿祎。 他也确实做到了。 先是作为当年 3Q 大战的当事人&…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...