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

【模板】计算几何入门

来源

计算几何基本模板(二维)

目录

  • 基本设置
  • 点 + 向量
    • Point(Vector)
    • 点积(数量积、内积)
    • 向量积,叉积
    • 两点间距离
    • 向量的模
    • 单位向量
    • 两向量的夹角
    • 判断点在直线的哪边
    • 逆转角
  • 线
    • 直线表达式
    • Line
    • 判断三点共线
    • 点到直线的距离
    • 点到线段的距离
    • 判断点是否在线段上
    • 判断直线与线段是否相交
    • 判断两线段是否相交
    • 判断两直线平行
    • 求两直线交点
  • 多边形
    • 三角形面积
    • 三角形四心
    • 正弦定理 & 余弦定理
    • 正多边形性质
    • 求多边形面积
    • 判断点在多边形内
    • 判断凸多边形
    • Circle
    • 扇形面积
    • 点与圆位置关系
    • 直线与圆位置关系
    • 直线与圆交点
    • 圆与圆位置关系
    • 圆与圆交点
    • 求圆的切点
    • 三角形外接圆
    • 三角形内切圆
  • 网格
    • 线段整点个数
    • 多边形边整点个数
    • 多边形内整点个数
  • 极角排序
  • 凸包算法
  • 最小圆覆盖
  • 圆的面积并
  • 圆与多边形面积交
  • 自适应辛普森积分
  • 平面最近点对

基本设置

  • 使用long double提高精度
  • 定义常数eps=1e-8PI=acos(-1.0)
  • 实现sgn()函数处理浮点数精度判断

点 + 向量

Point(Vector)

struct Point { /*...*/ };
  • 包含坐标(x,y)和运算符重载

点积(Dot)

A ⃗ ⋅ B ⃗ = ∣ A ∣ ∣ B ∣ cos ⁡ θ \vec{A} \cdot \vec{B} = |A||B|\cos\theta A B =A∣∣Bcosθ

double operator*(Vector &A, Vector &B);

叉积(Cross)

A ⃗ × B ⃗ = ∣ A ∣ ∣ B ∣ sin ⁡ θ \vec{A} \times \vec{B} = |A||B|\sin\theta A ×B =A∣∣Bsinθ

double operator^(Vector &A, Vector &B);

两点间距离

d i s t ( A , B ) = ( A . x − B . x ) 2 + ( A . y − B . y ) 2 dist(A,B) = \sqrt{(A.x-B.x)^2 + (A.y-B.y)^2} dist(A,B)=(A.xB.x)2+(A.yB.y)2

向量模长

∣ A ∣ = A . x 2 + A . y 2 |A| = \sqrt{A.x^2 + A.y^2} A=A.x2+A.y2

单位向量

n o r m ( A ) = A ∣ A ∣ norm(A) = \frac{A}{|A|} norm(A)=AA

向量夹角

θ = arccos ⁡ ( A ⋅ B ∣ A ∣ ∣ B ∣ ) \theta = \arccos(\frac{A \cdot B}{|A||B|}) θ=arccos(A∣∣BAB)

点关于直线的位置判断

  • 使用叉积判断点在线段的左右关系

向量旋转

A ⃗ ′ = ( x cos ⁡ θ − y sin ⁡ θ , x sin ⁡ θ + y cos ⁡ θ ) \vec{A}' = (x\cos\theta - y\sin\theta, x\sin\theta + y\cos\theta) A =(xcosθysinθ,xsinθ+ycosθ)

线

直线表达式

  • 一般式: A x + B y + C = 0 Ax+By+C=0 Ax+By+C=0
  • 点向式: P ⃗ = P 0 + t d ⃗ \vec{P} = P_0 + t\vec{d} P =P0+td

Line结构体

struct Line { Point s, e; };

三点共线判断

( B − A ) × ( C − B ) = 0 (B-A) \times (C-B) = 0 (BA)×(CB)=0

点到直线距离

d = ∣ A B ⃗ × A P ⃗ ∣ ∣ A B ∣ d = \frac{|\vec{AB} \times \vec{AP}|}{|AB|} d=ABAB ×AP

点到线段距离

  • 分三种情况:垂直投影在线段内/外

点在线段上判断

  • 通过点积和叉积综合判断

直线与线段相交判断

  • 利用叉积符号判断端点位置

线段相交判断

  1. 快速排斥试验
  2. 跨立试验

直线交点求解

t = ( C D ⃗ × C A ⃗ ) ( C D ⃗ × A B ⃗ ) t = \frac{(\vec{CD} \times \vec{CA})}{(\vec{CD} \times \vec{AB})} t=(CD ×AB )(CD ×CA )

多边形

三角形面积

  • 海伦公式
  • 叉积公式: 1 2 ∣ A B ⃗ × A C ⃗ ∣ \frac{1}{2}|\vec{AB} \times \vec{AC}| 21AB ×AC

多边形面积

  • 鞋带定理: 1 2 ∣ ∑ i = 0 n − 1 ( P i × P i + 1 ) ∣ \frac{1}{2}|\sum_{i=0}^{n-1}(P_i \times P_{i+1})| 21i=0n1(Pi×Pi+1)

点在多边形内判断

  • 射线法统计交点奇偶性
  • 凸多边形方向法

凸包求解(Andrew算法)

  1. 按坐标排序
  2. 维护上下凸壳

圆与点位置关系

  • 计算点到圆心距离与半径比较

直线与圆相交

  • 代数法解方程组求交点

圆与圆相交

  • 计算圆心距与半径关系

最小圆覆盖

  • 随机增量法逐步扩展

网格相关

线段整点计数

  • 利用GCD计算格点数

皮克定理

S = I + B 2 − 1 S = I + \frac{B}{2} - 1 S=I+2B1

高级算法

极角排序

  • 分象限处理,避免浮点误差

自适应辛普森积分

  • 自动划分区间积分

平面最近点对

  • 分治法结合归并排序

相关文章:

【模板】计算几何入门

来源 计算几何基本模板(二维) 目录 基本设置点 向量 Point(Vector)点积(数量积、内积)向量积,叉积两点间距离向量的模单位向量两向量的夹角判断点在直线的哪边逆转角 线 直线表达式Line判断…...

PostgreSQL 数据库中导入大量数据

在 PostgreSQL 数据库中导入大量数据,可根据数据来源和格式选择不同的方法。以下为你详细介绍几种常见的方式: 1. 使用 COPY 命令(适用于本地数据文件) COPY 命令是 PostgreSQL 内置的高效数据导入工具,适合处理本地的数据文件。 步骤 准备数据文件 确保你的数据文件格…...

DeepSeek和Kimi在Neo4j中的表现

以下是2个最近爆火的人工智能工具, DeepSeek:DeepSeek Kimi: Kimi - 会推理解析,能深度思考的AI助手 1、提示词: 你能帮我生成一个知识图谱吗,等一下我会给你一篇文章,帮我从内容中提取关键要素,然后以N…...

xQueueSendToBack的中文释义和裸机调用

如果不在 FreeRTOS 环境下运行,而是裸机环境中实现类似的功能,需要移除 xQueueSendToBack 的依赖,并直接调用 CAN 发送函数。以下是修改后的代码和实现思路: 1. FreeRTOS 中的 xQueueSendToBack 功能 作用:将消息发送…...

2025年- G24-Lc98-217.包含重复(使用hashSet解决)-java版

1.题目描述 2.思路 思路一: 我的想法是直接用集合来判断,如果集合的元素不能添加说明之前已经存在这个元素,也就是发现了重复元素,所以返回false。 补充一: Map、ArrayList的定义和声明 3.代码实现 class Soluti…...

【树莓派驱动验证步骤】

终端操作和输出: 清理项目 adaraspberrypi:~/mt3502 $ make clean make -C /lib/modules/6.6.51rpt-rpi-v8/build M/home/ada/mt3502 clean make[1]: 进入目录“/usr/src/linux-headers-6.6.51rpt-rpi-v8”CLEAN /home/ada/mt3502/Module.symvers make[1]: 离开…...

百度SEO和必应SEO优化方法

如需SEO服务,可以搜索:深圳市信科网络科技有限公司。 一、搜索引擎生态格局:流量入口的重新洗牌 2025 年,中国 PC 端搜索引擎市场正经历戏剧性变革。StatCounter 数据显示,必应凭借 Edge 浏览器的预装优势与 ChatGPT …...

2025年3月AI搜索发展动态与趋势分析:从技术革新到生态重构

025年3月AI搜索发展动态与趋势分析:从技术革新到生态重构 一、行业动态:巨头布局与技术升级 谷歌推出“AI模式”,重新定义搜索体验 谷歌上线全新“AI模式”,集成多模态交互与实时数据能力,用户可通过文本、图片或语音…...

封闭图形个数

0封闭图形个数 - 蓝桥云课 小蓝对蓝桥王国的数字大小规则十分感兴趣。现在,他将给定你n个数a1, a2, ..., an,请你按照蓝桥王国的数字大小规则,将这n数从小到大排序,并输出排序后结果。 输入格式 第一行包含一个整数n&#xff0…...

VSCode 抽风之 两个conda环境同时在被激活

出现了神奇的(toolsZCH)(base) 提示符,如下图所示: 原因大概是:conda 环境的双重激活:可能是 conda 环境没有被正确清理或初始化,导致 base 和 toolsZCH 同时被激活。 解决办法就是 :conda deactivate 两次…...

Django 生产环境静态文件处理

python manage.py collectstatic 是 Django 提供的一个非常重要的管理命令,用于将项目中的静态文件收集到一个指定的目录中。这在部署 Django 项目时尤其重要,因为静态文件需要被 Web 服务器(如 Nginx 或 Apache)提供服务&#xf…...

语法: result=frexp(value, exp);

FREXP()是C语言里的内部函数,根据需要了解。 语法: resultfrexp(value, &exp); 参数: value是一个浮点数; exp是一个有符号的整型数; 返回值: 返回值result是一个浮点数,其有效范围是 0.5(含)到 1.0(不含&…...

ArcGIS Pro 制作风台路径图:从数据到可视化

一、引言 台风,作为自然界极具破坏力的气象现象之一,其路径的精准预测与直观呈现对于防灾减灾工作至关重要。 在数字化时代,借助专业的地理信息系统(GIS)软件,如 ArcGIS Pro,我们能够高效地将…...

#pandas #python#数据标注 pd.crosstab()

题目: device_status.txt 存储了工业互联网平台上收集的设备运行状态数据,数 据中有以下内容: device_id:设备编号,字符串类型,长度为 8 status_time:状态时间,日期时间类型&…...

self Attention为何除以根号dk?(全新角度)

全网最独特解析:self Attention为何除根号dk? 一、假设条件:查询向量和键向量服从正态分布 假设查询向量 q i q_i qi​和键向量 k j k_j kj​的每个分量均为独立同分布的随机变量,且服从标准正态分布,即:…...

SpringBoot @Scheduled注解详解

Scheduled 是 Spring Framework 中用于实现定时任务的核心注解,能够方便地配置方法在特定时间或周期执行。以下是详细解析: 1. 启用定时任务‌ 在 Spring Boot 中,需在配置类添加 EnableScheduling 注解以启用定时任务支持: Co…...

在大数据开发中spark是指什么?

hello宝子们...我们是艾斯视觉擅长ui设计和前端数字孪生、大数据、三维建模、三维动画10年经验!希望我的分享能帮助到您!如需帮助可以评论关注私信我们一起探讨!致敬感谢感恩! 在数字经济蓬勃发展的今天,数据已成为驱动商业决策、科学研究和城市治理的核心燃料。面对…...

从点灯开始的51单片机生活

陵谷纷纭新事改&#xff0c;筑台土石未应迟。 目录 sfr与sbit&#xff1f;不靠定时器的delay_ms延时函数所谓寄存器 sfr与sbit&#xff1f; 这第一课咱们主要来先理解一下sfr与sbit&#xff0c;以下可能是咱们这些新手朋友常见的点灯代码&#xff1a; #include<regx52.h&g…...

AI大模型落地:昆仑技术的东方解法

DeepSeek的横空出世&#xff0c;一举打破“算力封锁”的神话&#xff0c;标志着中国AI企业在AI大模型技术路径上取得彻底突破。 不过&#xff0c;DeepSeek等AI大模型的突破&#xff0c;固然大幅推动AI产业的整体发展&#xff0c;但算力基础设施能否跟上&#xff0c;也将决定未…...

Spring Boot 与 MyBatis Plus 整合 KWDB 实现 JDBC 数据访问

​ 引言 本文主要介绍如何在 IDEA 中搭建一个使用 Maven 管理的 Spring Boot 应用项目工程&#xff0c;并结合在本地搭建的 KWDB 数据库&#xff08;版本为&#xff1a;2.0.3&#xff09;来演示 Spring Boot 与 MyBatis Plus 的集成&#xff0c;以及对 KWDB 数据库的数据操作…...

VSCode+arm-none-eabi-gcc交叉编译+CMake构建+OpenOCD(基于STM32的标准库/HAL库)

前言&#xff1a;什么是CMake&#xff1f; Answer&#xff1a;简而言之&#xff0c;CMake是Make的maker。 一、CMake的安装 进入CMake官网的下载地址Get the Software&#xff0c;根据系统安装对应的Binary distributions。 或者在CMake——国内镜像获取二进制镜像安装包。 …...

MarsCode AI实战:利用DeepSeek 快速搭建你的口语学习搭子

资料来源&#xff1a;火山引擎-开发者社区 成品抢先看&#xff01; 自从MarsCode AI Chat模型全新升级&#xff0c;接入 Deepseek-R1、Deepseek-V3和豆包大模型1.5 三大模型&#xff0c;越来越多朋友注意到了AI编程能给我们带来的无限可能&#xff0c;也开始跃跃欲试想要尝试从…...

导出的使用

一.导出的具体使用步骤 1.在web开发中&#xff0c;导出是很常见的一个功能&#xff0c;当我进行个人项目练习的时候&#xff0c;导出的时候无法控制列宽以及居中样式&#xff0c;后续发现导出插件无法进行修改&#xff0c;整个插件较为简便易懂的同时&#xff0c;对于EX的控制…...

【OCR】总结github上开源 OCR 工具:让文字识别更简单

前言 在数字化的时代&#xff0c;光学字符识别&#xff08;OCR&#xff09;技术成为了我们处理文档、图像文字信息的得力助手。它能够将图像中的文字信息转换为可编辑和可处理的文本数据&#xff0c;极大地提高了信息处理的效率。今天&#xff0c;我要给大家介绍一些优秀的开源…...

struts1+struts2项目兼容升级到了spring boot 2.7

原项目比较复杂&#xff0c;集成了各种框架&#xff08;struts1 struts2 spring3等&#xff09;&#xff0c;趁工作之余练练手&#xff0c;学习一下springboot。大概花了一周时间才调通。 一、调整jar版本&#xff0c;寻找合适的版本。 第一步、首先原项目JDK6&#xff0c;要…...

Odoo 18 中的列表(list) 、表单(Form)、数据透视表、图表视图、看板视图、活动视图、日历视图等综合应用实例

Odoo 18 中的 视图应用实例 在 Odoo 中&#xff0c;视图是用户界面中表示业务对象的重要组成部分。无论您是扩展现有功能还是创建全新的功能&#xff0c;业务对象都至关重要。这些对象通过不同类型的视图向用户展示&#xff0c;而 Odoo 会根据 XML 描述动态生成这些视图。 列…...

单元测试mock

一、背景 现在有A类,B类,C类&#xff0c;A类依赖B类,依赖C类&#xff0c;如果想要测试A类中的某个方法的业务逻辑。A类依赖其他类&#xff0c;则把其他类给mock&#xff0c;然后A类需要真实对象。这样就可以测试A类中的方法。 举例&#xff1a;Ticket类需要调用Flight类和Pas…...

PDF文件转Markdown,基于开源项目marker

​ 首先我们来问下deepseek 为啥要选marker呢 基于深度学习&#xff0c;一看就逼格拉满。搞科研必备&#xff0c;效果应该不会太差。跟其他的阿猫阿狗工具没法比。 看下官网 https://github.com/VikParuchuri/marker ​ 一看头像是个印度佬&#xff0c;自吹——又快又好。…...

mysql中find_in_set()函数用法详解及增强函数

MySQL的 FIND_IN_SET()函数是一种特殊的函数&#xff0c;它主要用于搜索一个字符串在一个逗号分隔的字符串列表中的位置。 函数的基本语法 FIND_IN_SET(str, strlist) 其中&#xff0c;str是你想要查找的字符串&#xff0c;而 strlist是一个包含多个以逗号分隔的字符串的列表…...

深入理解 JavaScript/TypeScript 中的假值(Falsy Values)与逻辑判断 ✨

&#x1f579;️ 深入理解 JavaScript/TypeScript 中的假值&#xff08;Falsy Values&#xff09;与逻辑判断 在 JavaScript/TypeScript 开发中&#xff0c;if (!value) 是最常见的条件判断之一。它看似简单&#xff0c;却隐藏着语言的核心设计逻辑&#xff0c;也是许多开发者…...

批量合并 PPT 文件,支持合并成单个文件也支持按文件夹合并

合并多个 PPT 为一个 PPT 文档是我们经常会碰到的需求&#xff0c;合并后不仅更容易管理&#xff0c;在某些场景&#xff08;比如批量打印&#xff09;下也非常的有用&#xff0c;那当我们需要批量合并多个 PPT 文档地时候&#xff0c;我们有没有比较高效的方法呢&#xff1f;今…...

Java复习

在开篇前首先申明一下&#xff0c;本文虽不够系统&#xff0c;但复习够用&#xff0c;尤其是快速回忆( •̀ ω •́ )✧与提问。 主打一个速度。 本文将会从Java的基础语法、面向对象、API、字符串、集合、进阶...等六方面讲起。 一、Java的基础语法&#xff1a; 1、Java入门…...

keepalived+nginx+tomcat高可用

1.要求 角色主机名软件IP地址用户client192.168.72.90keepalivedvip192.168.72.100mastermasterkeepalived, nginx192.168.72.30backupbackupkeepalived, nginx192.168.72.32webtomcat1tomcat192.168.72.41webtomcat2tomcat192.168.72.42 1.搭建Tomcat 1.1下载jdk wget http…...

RK3568 Android11 sh366006驱动

sh366006.c /* 谁愿压抑心中怒愤冲动咒骂这虚与伪与假从没信要屈膝面对生命纵没有别人帮一生只靠我双手让我放声疯狂叫囔今天的他 呼风可改雨不可一世太嚣张 --《不可一世》Beyond */ #include <linux/module.h> #include <linux/init.h> #include <linux/fs.h…...

实现分布式锁需要考虑哪些问题?

&#x1f512; 什么是分布式锁&#xff1f; 分布式锁是在分布式系统中控制共享资源访问的机制&#xff0c;用于解决高并发场景下数据不一致、操作冲突等问题。核心目标是保证跨进程 / 跨节点的互斥性&#xff0c;常见实现方案包括&#xff1a;数据库锁、Redis 锁、ZooKeeper 锁…...

【UI设计】一些好用的免费图标素材网站

阿里巴巴矢量图标库https://www.iconfont.cn/国内最大的矢量图标库之一&#xff0c;拥有 800 万 图标资源。特色功能包括团队协作、多端适配、定制化编辑等&#xff0c;适合企业级项目、电商设计、中文产品开发等场景。IconParkhttps://iconpark.oceanengine.com/home字节跳动…...

mysql-大批量插入数据的三种方式和使用场景

1.批量插入三种方式 INSERT INTO … SELECTINSERT INTO … VALUES (…)LOAD DATA INFILE ‘/path/to/datafile.csv’ INTO TABLE table_name 2.批量插入 2.1 INSERT INTO … SELECT 用途&#xff1a;从另一个表中选择数据并插入到目标表中。 语法示例&#xff1a; INSERT …...

创建自己的github.io

1、创建GitHub账号 GitHub地址&#xff1a;https://github.com/ 点击Sign up创建账号 如果已创建&#xff0c;点击Sign in登录 2、创建仓库 假设Owner为username&#xff0c;则Repository name为username.github.io说明&#xff1a; 1、Owner为用户名 2、Repository name为仓…...

Oracle 常用语法汇总

系列文章目录 本文对Oracle 常用的语法进行汇总 文章目录 系列文章目录一、Oracle 表&表字段操作&#xff1a;1.1 DDL语句(数据定义语言)Create、Alter、Drop、Truncate&#xff1a;1.1.1 建表&#xff1a;建表&#xff1a;注释COMMENT :表中字段的约束&#xff1a;表中字…...

java小白日记38(集合-List)

List接口基本介绍 List接口是collection接口的子接口 &#xff08;1&#xff09;List集合类中元素有序&#xff08;即添加顺序和取出顺序一致&#xff09;、且可以重复 &#xff08;2&#xff09;List集合中的每个元素都有其对应的顺序索引&#xff0c;即支持索引 &#xf…...

高能ISP模块功能说明

先看一些常见缩写&#xff1a; BPS&#xff1a;Bayer processing segment CPP&#xff1a;Camera post processor DE&#xff1a;Detailed enhancement EIS&#xff1a;Electronic image stabilization IFE&#xff1a;Image front-end engine IPE&#xff1a;Image-proc…...

单臂路由实验

单臂路由实验 文章目录 单臂路由实验单臂路由简介工作原理优点与缺点应用场景 实验拓扑实验需求&#xff1a;实验步骤&#xff1a;1.PC 配置 IP 地址2.PC3 属于 Vlan10&#xff0c;PC4 属于 Vlan20&#xff0c;配置单臂路由实现 Vlan10 和 Vlan20 三层互通2.1.在 SW2 上创建 Vl…...

SpringMVC全局异常处理机制

异常处理机制 异常处理的两种方式&#xff1a; 编程式异常处理&#xff1a;是指在代码中显式地编写处理异常的逻辑。它通常涉及到对异常类型的检测及其处理&#xff0c;例如使用 try-catch 块来捕获异常&#xff0c;然后在 catch 块中编写特定的处理代码&#xff0c;或者在 f…...

UDS诊断、ECU刷写、自动化测试、车联网测试、DTC故障注入测试、坏境测试、可靠性测试、压力测试、性能测试等

每日直播时间&#xff1a;&#xff08;直播方式&#xff1a;腾讯会议&#xff09; 周一到周五&#xff1a;20&#xff1a;00-23&#xff1a;00 周六与周日&#xff1a;9&#xff1a;00-17&#xff1a;00 向进腾讯会议学习的&#xff0c;可以关注我并后台留言 直播内容&#xff…...

C++的常用容器嵌套

在 C 中&#xff0c;数据结构之间的嵌套是非常常见的&#xff0c;尤其是在处理复杂数据时。以下是几种最常用的数据结构嵌套方式及其典型应用场景的总结&#xff1a; 1. std::vector 嵌套 std::vector 定义&#xff1a;std::vector<std::vector<T>>。用途&#xf…...

Mac - Cursor 配置 + GPT 4.0/4.5/o1/o3/Deepseek Api 使用

前言 新换了电脑&#xff0c;所以需要新配置一些环境。已经安装好了Goland&#xff0c;但近期可能有GoJava前端的需求&#xff0c;所以使用Cursor。 除去学校各种奇奇怪怪&#xff0c;这已经是一年多来配置的第4台Windows和第四台Mac的Golang环境了。。。且是自己工作外买的第…...

【数据挖掘】Python基础环境安装配置

【数据挖掘】Python基础环境安装配置 一、摘要二、安装Python3.13.2三、安装Jupyter Notebook四、安装Numpy和Pandas以及matplotlib五、安装scikit-learn库和seaborn库 一、摘要 本文主要介绍如何在Windows上安装Python3.13.2&#xff0c;然后基于该Python版本安装Jupyter not…...

详解string类+迭代器

迭代器 概念&#xff1a;在 C 中&#xff0c;迭代器是访问容器&#xff08;如数组、列表、向量、字符串等&#xff09;元素的一种方式。迭代器提供了一种统一的接口&#xff0c;使得你可以使用相同的代码来遍历不同类型的容器。迭代器本质上是一个指针或者指针的封装&#xff0…...

OpenCV DNN 模块使用指南

OpenCV DNN 模块使用指南 一、模块概述 OpenCV 的 DNN&#xff08;深度神经网络&#xff09;模块为开发者提供了强大的深度学习功能&#xff0c;能够加载并运行多种格式的预训练深度学习模型。此模块广泛应用于图像分类、目标检测、语义分割等众多计算机视觉任务。接下来&…...

温度(Temperature)在大模型输出中的作用与底层原理

温度&#xff08;Temperature&#xff09;在大模型输出中的作用与底层原理 在深度学习领域&#xff0c;尤其是自然语言处理&#xff08;NLP&#xff09;中&#xff0c;大型语言模型&#xff08;LLM&#xff09;的输出生成通常依赖于概率分布的采样。温度&#xff08;temperatu…...