判断点在多边形内(射线法)

2023-05-16

射线法,用来判断点在多边形的内外,适用于任意多边形
时间复杂度:O(n)
从该点引出一条水平射线,观察射线与多变形的交点个数.
当射线与多边形的交点个数是奇数时,P在多边形内; 偶数时,P在多边形外。

我们通常将射线设为水平向右(哪个方向都可以,只是水平容易写一点而已)

在这里插入图片描述
图一这种情况计两次或者不计都可
图二这种情况只计一次
图三这种情况也是计两次或者不计都可

最后,根据点数判断点P在多边形内外。

注意:点必须有顺序,顺时针或逆时针
代码:
你品,你仔细品(逃

const double EPS=1e-9;
inline int sgn(double a){ return a < -EPS ? -1 : a > EPS; }
inline int cmp(double a, double b){ return sgn(a-b); }
struct Point;
struct Line;
typedef Point Vector;
struct Point{
    double x,y;
    Point(){}
    Point(double a, double b):x(a),y(b){}
    double len(){return sqrt(x*x+y*y);}
    bool onSegment(Line l);
    int inPolygon(Point poly[]);
    void read(){scanf("%lf%lf",&x,&y);}
    Point operator+(Vector v){return {x+v.x,y+v.y};}
    Vector operator-(Point p){return {x-p.x,y-p.y};}
    double operator^(Vector v){return x*v.y-y*v.x;}//叉乘
    double operator*(Vector v){return x*v.x+y*v.y;}//点乘
};
bool Point::onSegment(Line l){
    Vector v1=l.s-*this;
    Vector v2=l.e-*this;
    return sgn(v1^v2)==0&&sgn(v1*v2)<=0;
}
int Point::inPolygon(Point poly[]){//判断点是否在多边形内,若点在多边形内返回1,在多边形外部返回0,在多边形上返回-1
    int wn = 0;
    for(int i = 1; i <= n; ++i){
        if(onSegment({poly[i], poly[i%n+1]})) return -1;
        int k = sgn((poly[i%n+1] - poly[i])^(*this - poly[i]));
        int d1 = sgn(poly[i].y - y);
        int d2 = sgn(poly[i%n+1].y - y);
        if(k > 0 && d1 <= 0 && d2 > 0) wn++;
        if(k < 0 && d2 <= 0 && d1 > 0) wn++;
    }
    return wn%2;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

判断点在多边形内(射线法) 的相关文章

  • Docker安装Xfce桌面环境(轻量可视化操作系统)

    0 Xfce是什么 xff1f Xfce是一个适用于类UNIX操作系统的轻量级桌面环境 它的目标是快速而低廉的系统资源 xff0c 同时仍然具有视觉吸引力和用户友好性 具体参考官网 https www xfce org 项目地址 xff1a
  • Linux系统常用快捷键及VNC基本使用命令

    Linux系统常用快捷键及VNC基本使用命令 文章目录 Linux系统常用快捷键及VNC基本使用命令Linux系统的特点Linux树型目录结构Linux系统常用命令VNC常用命令 Linux系统的特点 多任务系统 在linux系统中可以同时
  • 【docker】docker学习(3)——Dockerfile的常用语法和编写实战

    大家好 xff0c 我是好学的小师弟 xff0c 今天和大家分享下Dockerfile的常用语法和编写实战 插曲 xff1a 在学习Dockerfile之前 xff0c 我们先讲解下docker save 和docker load 这两个命
  • 1.2 安装 docker 容器并配置镜像加速器

    1 2 1 实验环境准备 实验环境 xff1a CENTOS7 9 64 位 主机名 xff1a hou 主机 ip 10 0 8 120 xff08 这个 ip 大家可以根据自己所在环境去配置 xff0c 配置成静态 IP xff09 4
  • 弯管参数计算及编程实现

    船舶软件建立三维管道模型后 xff0c 需要自动生成管子加工信息 xff0c 这样就提高了设计效率 其中弯管参数主要是下料长度 xff0c 弯角和转角 下料长度是由各管段实长 xff0c 即管子中心线长度 xff0c 减去弯管部分切线长再加
  • 完整版数据库系统概论(第五版)-课后答案-免费网盘自提

    包含全部的课后答案与复习笔记 xff01 大家伙不挂科不被刷 xff0c 一起冲 xff01 虽然这个我也是找的别人的 xff0c 但是真的好用 xff01 百度网盘 https pan baidu com s 1Ux07PWvPb k3l
  • 踩坑笔记:安装Gazebo11

    安装环境 xff1a ubuntu18 04 在我上一篇博客中 xff0c 我们安装了ROS Melodic amp amp Ros2 Dashing 在我想要安装Gazebo11时候出现了错误 一 依赖错误 安装Gazebo11 xff1
  • 在keil5中调试串口遇到的问题

    1 问题 在keil5中调试stm32串口实验时 xff0c 向单片机的串口1发送数据 xff0c 观察串口1的寄存器 xff0c 此时串口1的中断服务函数会遇到无法进入下图if 的情况 xff0c 此时观察串口1寄存器 RXEN 的值 由
  • 树莓派在上电后一直重启进入不了系统桌面

    问题描述 树莓派在上电后一直重启进入不了系统桌面 xff0c 在检查了各种接口没问题后解决办法 原因分析与解决方案 xff1a 用了键盘 鼠标 显示器后5v 1A的插头不行 xff0c 换了ipad用的5V 2A的充电器后就可以开启了 xf
  • 树莓派连接“手机热点“或“WiFi“ 后无法上网,以及连接“手机热点“或“WiFi“时VNC连接失败问题

    问题描述 之前一直在开热点 xff0c 通过电脑端VNC控制树莓派拍摄照片 xff0c 今天突然发现树莓派上不去网 xff0c 所以就试着尝试解决了一下 xff0c 心路历程如下 xff1a 要么就是树莓派连不上网 xff0c 要么就是连上
  • 相机标定和双目相机标定标定原理推导及效果展示

    文章目录 前言一 相机标定1 相机的四个坐标系2 相机的畸变 二 张正友标定法1 求解内参矩阵与外参矩阵的积2 求解内参矩阵3 求解外参矩阵4 标定相机的畸变参数5 双目标定6 极线矫正 xff08 立体校正 xff09 三 视差图与深度图
  • keras:tensor从全连接层输出到卷积层

    一 tensor从卷积层输出到全连接层 用过keras的都知道 xff0c 想从卷积层输出tensor到全连接层 xff0c 只需加一层 xff1a model add Flatten shape就不会出现错误 二 但是如果从全连接层输出t
  • 保研面试复习之数据结构篇

    数据项 数据元素和数据结构的概念 数据项是组成数据元素的 xff0c 有独立含义的 xff0c 不可分割的最小单位 数据元素是数据的基本单位 数据结构是带结构的数据元素的集合 数据结构包括逻辑结构和存储结构两个层次 数据结构的三要素是逻辑结
  • 视觉里程计的重定位问题1——SVO的重定位部分

    SVO的重定位部分代码解析与分析 SVO的重定位功能体现在 xff1a 运动跟踪丢失后通过与上一关键帧匹配以及地图点投影 xff0c 找回当前相机位姿 由于没有后端和回环 xff0c SVO的重定位并不是回环校正后的重定位 代码部分被放在运
  • 组合导航(一):定位技术分类与介绍

    组合导航 xff08 一 xff09 xff1a 导航定位技术分类与介绍 一 定位技术分类1 1 基于相对测量的定位 xff08 航位推算 xff09 1 2 基于绝对测量的定位1 3 组合定位 一 定位技术分类 1 1 基于相对测量的定位
  • git bash可以正常commit,但是 VSCode 里不能正常commit使用的解决方法

    问题描述 同一路径下的源码 xff0c 使用git bash可以正常commit xff0c 但是使用vscode提交commit就会一直卡住 xff0c 转圈圈 参考方案链接 xff1a VS CODE GIT 500 问题处理 pudn
  • 组合导航(四):惯性导航系统

    1 惯性导航系统的物理平台2 惯性测量单元IMU3 惯性传感器的测量值3 1静止状态下的加速度测量3 2静止与运动状态下的角速度测量 4 惯性传感器误差4 1 系统误差 xff08 可通过实验进行校正 xff09 4 2 随机误差4 3 惯
  • 组合导航(七):卡尔曼滤波

    Kalman滤波1 离散卡尔曼滤波2 卡尔曼滤波的流程2 1 预测与时间更新2 2 测量更新与校正 3 卡尔曼滤波 算法步骤4 非线性卡尔曼滤波4 1 线性化kalman滤波4 2 扩展kalman滤波 5 卡尔曼滤波发散控制5 1 KF过
  • 组合导航(八):INS/GPS组合导航

    INS GPS组合导航1 误差反馈1 1 开环INS GPS架构1 2 闭环INS GPS架构 2 组合导航的类型2 1 松耦合 的INS GPS组合导航2 2 紧耦合 的INS GPS组合导航2 3 深度耦合的 INS GPS组合导航 3
  • 组合导航(九):三维简化的INS/GPS组合导航系统

    简化INS与GPS组合系统在三维路面上的导航1 MEMS级IMU的三维定位的性能分析2 解决MEMS级IMU在路面导航中存在的问题3 三维简化的惯性传感器系统3 1 3D RISS概述3 2 xff08 轮式车辆 xff09 采用3D RI

随机推荐

  • PX4安装与编译

    第一步 xff1a 下载源码 下载方式一 xff1a git clone https github com PX4 Firmware git recursive 默认下载版本为master 下载时间比较长 xff0c 包含各种包以及依赖工具
  • PX4:【系统架构】

    PX4系统架构 由两个层组成 xff1a 一是飞行控制栈 xff08 flight stack xff09 二是中间件 xff08 middleware xff09 flight stack xff1a 集成了各种自主无人机的制导 导航以及
  • PX4:【uORB通讯机制】

    uORB xff1a Micro Object Request Broker PX4进程间的通讯机制 xff1a 多对多的信息发布与订阅方式 发布消息 xff1a 1 公告 advertise xff1a 相当于初始化 xff0c 在发布消
  • PX4:【传感器校准】

    sensor的校准校准步骤 xff1a 文件目录 xff1a 代码入口 xff1a 求解模型计算公式 sensor的校准 校准步骤 xff1a 首先通过地面站QGC进行校准 xff0c QGC将校准参数设置到sh文件中 此后再基于QGC的校
  • PX4:【sensor_combined】

    功能介绍消息内容sensor combined 产生机制 amp 代码流程 功能介绍 sensor combined 是一个冗余传感器集合的消息 xff0c 通过订阅多个传感器的数据 xff0c 将冗余的数据经过VoteSensorsUpd
  • PX4:【地面站传感器数据校准】

    上电 gt rsC 运行 sensor start commander start 入口函数 xff1a 位于commander文件夹中 Commader cpp Commander run xff08 xff09 commander lo
  • Windows和Linux双系统安装教程

    最近刚刚完成了Windows和Linux双系统 xff08 这里以Ubuntu安装为例 xff09 的安装 xff0c 应某奔同学要求 xff0c 这里简单记录下安装过程 系统启动盘准备Windows系统安装分出给Linux系统的磁盘空间安
  • MSCKF系列论文阅读与代码流程

    MSCKF原理与代码总结 算法原理前端理论 xff08 图像的特征提取与跟踪 xff09 后端理论 xff08 误差状态卡尔曼滤波模型 xff09 1 IMU状态预测1 1 IMU状态传播 xff08 p v q 4阶Runge Kutta
  • open_vins(二):rosbag精度测试

    一 xff0e ros读取与轨迹保存二 xff0e euroc数据集测试三 结论 一 xff0e ros读取与轨迹保存 运行open vins launch 读取ros数据包 xff1a roslaunch pgeneva ros eth
  • open_vins(三):imu静止初始化

    一 xff0e 静止初始化原理二 xff0e 理论公式三 xff0e 相关代码四 xff0e 小结 xff1a 初始化是指在系统启动阶段 xff0c 需要估计重力方向 gravity direction 加速度计以及陀螺仪biases ac
  • ros数据集录制:rosbag record

    1 查看话题 查看topic列表 xff1a rostopic list 打印topic内容 xff1a rostopic echo topic xff12 话题录制rosbag record 用于在ros系统中录取系统中其他ros节点发出
  • git pull的时候:您对下列文件的本地修改将被合并操作覆盖,请在合并前提交或贮藏您的修改。 正在终止

    使用git pull的时候报错 xff1a 更新 span class token number 008728 span e span class token punctuation span span class token number
  • 使用webpack-dev-server自动打包并实现debug调试

    webpack dev server 是一个开发服务器 xff0c 它的功能就是可以实现热加载 xff0c 并且自动刷新浏览器 准备工作 xff1a 创建一个程序目录test xff0c 将html页面拷贝进来 xff0c 在目录下新建sr
  • ROS实现串口GPS数据的解析与通信

    1 配置串口 配置串口时 xff0c 利用ROS自带的serial功能包进行串口数据的读取 xff0c 具体来说就是创建一个串口对象 xff0c 用成员函数read进行读取 xff0c 需要注意的是其中Timeout的设置以及read在调用
  • sumo之使用netedit绘制路网并进行简单模拟

    1 基本路网的构建 xff08 十字路口 xff09 在下载完成sumo后 xff0c bin目录下有一个可以运行的nete exe xff0c 点击可以进入界面进行路网的编辑 xff0c 编辑生成 net xml文件 点击进去后 xff0
  • sumo之模拟行人

    在前面的文章中介绍了模拟车辆以及交通工具 公共汽车 xff0c 在道路上除了车辆外还有行人参与 在本文中介绍添加行人 详细的方法和参数可以前往官网查看 本部分的模拟路网全部沿用上次公共汽车模拟的环境 xff0c 只需要对部分代码进行修改 首
  • 【开发工具】VScode连接远程服务器+设置免密登录

    文章目录 前言连接远程服务器免密登录注意事项参考资料 前言 本文介绍如何使用VScode搭建自己的远程开发平台 xff0c 以便于我们可以随时拿着自己心爱的PC xff0c 去开发让自己脱发的项目 连接远程服务器 首先 xff0c 我们去官
  • 2.3、Segment Routing基础之IGP Segment 类型详解

    本文将重点介绍IGP Segment 分发场景下常见的几种Segment类型 xff0c 同时为各位介绍了这些Segment类型在在Segment Routing转发过程中的转发动作以及转发特性 本文将对各位理解Segment Routin
  • IDEA日常填坑:Cannot resolve plugin org.apache.maven.plugins:maven-war-plugin

    问题描述 xff1a 我太难了o o xff0c 这个问题竟然困扰了我一个下午加上一个晚上 xff0c 为了解决它 xff0c 估计浏览器都要被我弄崩了吧 xff0c 此前我将所能找到的方法全都试了个遍 xff0c 甚至是将 IDEA 卸载
  • 判断点在多边形内(射线法)

    射线法 用来判断点在多边形的内外 适用于任意多边形 时间复杂度 xff1a O n 从该点引出一条水平射线 xff0c 观察射线与多变形的交点个数 当射线与多边形的交点个数是奇数时 xff0c P在多边形内 偶数时 xff0c P在多边形外