当前位置: 首页 > 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 大战的当事人&…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...