图论之毕克定理证明

article/2025/7/3 21:21:15

毕克定理是小学四年级奥赛内容,无意间从一本教材上看到,觉得定理蛮有意思,也和自己从事的工作有一些关联,就在网上找了一些证明资料,结合自己的思考,稍微挖掘了以下,聊以记录。

毕克定理是指一个计算点阵中顶点在格点上的多边形面积公式,该公式可以表示为S=N+L÷2-1,其中N表示多边形内部的点数,L表示多边形落在格点边界上的点数,S表示多边形的面积。

公式默认一个小正方形边长为1,即面积为1,若一个格点正方形边长为2(面积为4)时,需要在原有公式的基础上乘4.

1.定理大概描述:

给定一个网格,每个格子由边长为1的单位正方形组成。网格内有一个多边形,并且多边形的顶点都在网格的交点处,也就是说顶点没有一个落在了单位正方形的边上或者单位正方形的内部,记多边形的面积为S,多边形内部的点的个数为I,多边形边上的点数为A,则:

S=I+\frac{A}{2} -1

证明,以下图为例,红色的点是内点,分布在边缘线条上的点是边点。

首先用割补,将其补充为一个矩形,假设矩形面积为S,边缘三角形的面积分别如图所示,则不规则多边形面积为:

S_{poly}=S-S1-S2-S3-S4-S5

1、证明步骤

(1)首先,证明对长方形是成立的;

(2)接着,再证明对直角三角形是成立的;

(3)然后,继续证明对任意三角形也是成立的;

(4)最后,证明对于两个图形的组合还是成立的。

首先证明(4)

假设任意一个多边形的面积都有:

S=I+\frac{A}{2} -1

 对多边形1来说:

S_1=I_1+\frac{A_1}{2} -1

对多边形2来说:

S_2=I_2+\frac{A_2}{2} -1

如果多边形1和2共享一条边,这个边有n个边点,则按照公式,由1和2组合拼成的图形为:

\\S=(I_1+I_2+(n-2)) + \frac{A_1 -n +A_2-n +2}{2}-1 = I_1+I_2-2+\frac{A_1+A_2+2}{2}-1=I_1+I_2+\frac{A_1+A_2}{2}-2=S_1+S_2

得证。

其次证明对长方形是成立的:

长方形的长、宽长度分别为x,y.

\\I=(x-1)(y-1) \\A=2(x+y) \\S=I+\frac{A}{2}-1=(x-1)(y-1)+\frac{2(x+y)}{2}-1 = 1-(x+y)+xy +(x+y)-1 = xy

成立。

关于A的计算方式,可以参考欧拉定理,面数F=1, 所以定点数等于线段数。举行的定点数等于线段数。

对于三角形同样成立,先看直接三角形,将红色的直角三角形补为矩形:

 假设对角线穿过的点为n.则对于红色三角形来说:

I=\frac{(x-1)(y-1)-(n-2)}{2}

A=x+y+n-1

则:

\\ S=I+\frac{A}{2}-1 =\frac{(x-1)(y-1)-(n-2)}{2} +\frac{x+y+n-1}{2} -1=\frac{xy-x-y+1-n+2+x+y+n-1 - 2}{2}=\frac{xy}{2}

成立。

对于任意三角形可以由 1个长方形 = 若干直角三角形 + 此三角形拼接而成,用上面拆解的方法同理可证。

x_1,x_2,x_3,x_4,x_5,x_6 为长度,n_1,n_2,n_3为三角形三个边经过的点的个数,I_1,I_2,I_3为三个直角三角形的内点个数,则:

S_{\Delta}= S-S_1-S_2-S_3

S=x\cdot y

S_1=I_1+\frac{x_1+x_2+n_1-1}{2}-1

S_2=I_2+\frac{x_3+x_4+n_2-1}{2}-1

S_3=I_3+\frac{x_5+x_6+n_3-1}{2}-1

分别用几何法和毕克定力求不规则三角形面积:

几何法:

\\S_{\Delta}= S-S_1-S_2-S_3=xy-(I_1+I_2+I_3)-\frac{(x_1+x_2+n_1-1)+(x_3+x_4+n_2-1)+(x_5+x_6+n_3-1)}{2} -3

毕克定理法:

\\ S_{\Delta} = (x-1)(y-1)-(I_1+I_2+I_3)-(n_1-2+n_2-2+n_3-2) + \frac{n_1+n_2+n_3-3}{2}-1 \\ =xy-(x+y)-(I_1+I_2+I_3)-(n_1-2+n_2-2+n_3-2) + \frac{n_1+n_2+n_3-3}{2} \\ =xy-(x+y)-(I_1+I_2+I_3)-\frac{n_1+n_2+n_3-9}{2}

接下来化简几何法:

因为:

\\ \frac{(x_1+x_2+n_1-1)+(x_3+x_4+n_2-1)+(x_5+x_6+n_3-1)}{2}=\frac{(x_1+x_2+x_3+x_4+x_5+x_6)+(n_1+n_2+n_3-3)}{2}=\frac{2(x+y)+(n_1+n_2+n_3-3)}{2}=(x+y)+\frac{(n_1+n_2+n_3-3)}{2}

所以:

\\ S_{\Delta}= S-S_1-S_2-S_3=xy-(I_1+I_2+I_3)-\frac{(x_1+x_2+n_1-1)+(x_3+x_4+n_2-1)+(x_5+x_6+n_3-1)}{2} -3 \\ =xy-(I_1+I_2+I3)-(x+y)-\frac{(n_1+n_2+n_3-3)}{2}-3 \\ = xy-(x+y)-(I_1+I_2+I3)-\frac{(n_1+n_2+n_3-9)}{2}

可以看到,两种方法,最终都化成了形式:

xy-(x+y)-(I_1+I_2+I3)-\frac{(n_1+n_2+n_3-9)}{2}

所以,命题得到证明,不规则三角形同样适用毕克定理。

在毕克定理中,又分为棱形网格和三角形网格,我们下面证明对棱形网络也成立。

证明棱形网络符合毕克定理

初等几何我们知道,四边形不是稳定的形状,四边形是可以通过固定一边,平移另一边来变化面积和和形状。在线性代数中,这种变化叫做线性变换,因为它没有改变平行和0点不动的性质。我们可以考虑对下图进行这种变换:

你会看到,一个三角形,在经过这种变换后,仍然是个三角形,并且他的内点,外点和边缘点的数量和相对位置没有任何变化,只是图形面积同比例的缩小。对比如下三角形,在变换前后,内点和边缘点的数量没有任何变化。

由于是线性变换,任何一部分的面积都以相同的比例缩小,所以以小棱形计的格点多边形仍然满足毕克定理,这是线性变换的自然推论。

所以,对于棱形组成的网格,也可以应用毕克定理。

对于三角形成立

为了方便,以等边三角形为例(任意三角形都可以,其实等边三角形没有对证明带来额外信息,只是方便画图)。

前面证明了任意三角形符合毕克定理,而基于任意三角形之上添加新的边,组成新的形状,每一步也都证明了符合毕克定理,所以无论由三角形组成的面多么复杂,最终的图形也都会符合毕克定理,证明结束。

或者用前面的结论,两个正三角形组成一个棱形,符合毕克定理,而且棱形分解成正三角形,没有带来额外的内点和外点的变化,只是最小面积单元从棱形变为了原来的一半,正三角形的面积。

所以如果以正三角形计,相对于原来棱形的公式,最后结果要乘以2。棱形面积是正三角形的2倍。

证明完成后,看下图求大的三角形面积,是不是就很简单了?

只要将图形分解成棱形或者正三角形,应用毕克定理即可解决这个问题,不赘述。

思考:

由于任何不规则图形都可以分解成三角形和矩形,矩形也可以进一步分解成三角形,所以其实这个问题只要考虑三角形即可。所以,实际上只要证明前面的结论3和4,便可证明毕克定理。

联想:

实际上,由于任何不规则图形都可以分解成三角形,矩形这个条件可以变的更弱一些,我们只需要证明毕克定理适用于不规则三角形以及结论4即可推导出毕克定理的普适性结论。因为联想到GPU的设计,任何图元都可以分解为三角形平面的组合。所以自然所有的格点几何图形也都适用于毕克定理这个结论。

二维空间中最简单的面就是三角形面,GPU的流水线在顶点处理和光栅化阶段,就是将几何图元分解成一个一个的三角形处理的,并且PIPELINE算法也会针对三角形进行特殊优化。

无论多么复杂的几何形状,都可以看成无限多个微小三角形拼接而成的。

图7


参考资料

「图形基础」笔记2. 图形处理单元GPU_gpu画图为什么都是三角形形状_周婕的博客-CSDN博客

结束!


http://chatgpt.dhexx.cn/article/oWPi6LDJ.shtml

相关文章

chapter 4 能带理论 energy band

继承自chapter 3 的自由电子模型: 4.1 单电子近似 One electron approximation 列出电子运动的薛定谔方程: E Ψ − ℏ 2 2 m ∇ 2 Ψ U Ψ E \Psi -\frac{\hbar^2}{2m} \nabla^2 \Psi U \Psi EΨ−2mℏ2​∇2ΨUΨ 根据电子在晶体中运动的实际情…

能带图最好的理解——克朗尼格-朋奈模型(Kronig-Penney模型)

布洛赫波函数 整体的思想还是基于建模,大家应该都知道在自由电子模型中,能量和波矢的关系 那么大家的第一个疑问首先是,空间结构的周期性应该反应在空间坐标上,为什么K空间也会满足周期性呢? 这里面就不得不说&…

固体物理-复习重点

晶体:是由离子,原子或分子(统称为粒子)有规律的排列而成的,具有周期性和对称性 非晶体:有序度仅限于几个原子,不具有长程有序性和对称性 点阵:格点的总体称为点阵 晶格:晶…

图书馆管理系统用例图

第一次画用例图,多多指教

网上选课系统用例图

转载于:https://www.cnblogs.com/whs2818388/p/4925219.html

学生成绩系统用例图模型

在uml模型共享平台上发布了一个学生成绩系统的需求,并且绘制出了用例图,如下图,欢迎大家参与讨论,该系统全部模型查看连接http://euml.trufun.net/ 本文转自 trufun 51CTO博客,原文链接:http://blog.51cto.…

UML用例图分析——铁路售票系统

该文档就是对简单铁路售票系统,写的用例图和用例规约。下面是目录个人水平有限,有需要的可以下载参考。有事可留言。下载链接:点击下载文档

简单的图书管理系统用例图(UML)

运用工具:Presson 自我评价:简单肤浅还可能是不规范的,初次接触用例图若有 错误请指出! 此外:本人至今是软件工程大一新生,希望能认识更多志同道合的人共同努力,交流学习经验&#xff0c…

“远程网络教学系统”UML用例图(练习题)

“远程网络教学系统”UML用例图(练习题) 题目用例图学生用户教师用户系统管理员 用例文档的示例学生用户的示例:学生用户查找课件教师用户的示例:教师用户登录系统管理员的示例:系统管理员维护网站页面 题目 “远程网…

UML基础、建模与设计实战笔记03第3、4章建模工具简介,常见uml建模工具,创建模块,创建类,用例图,参与者,用例,用例描述,用例之间的可视化表示,用例图建模技术及应用,进销存系统用例图

1、常见uml建模工具 建模工具应该具有的功能 绘图存储一致性检查对模型进行组织导航写作支持代码生成逆向项目集成支持多种抽象层和开发过程文档生成脚本编程 工具主要有 Rose PowerDesinger 2、StarUML的模型、视与图 starUML中清晰地区分了模型(model&#x…

UML实例(二):在线购物系统用例图

2019独角兽企业重金招聘Python工程师标准>>> 一、用例图 二、用例描述 用例名:添加购物车商品 简述:顾客有购买商品的意图,但是觉得需要考虑时,可执行添加购物车商品操作。 参与者:消费者 包含:无 扩展:无 继承:无 前置条件:顾客必须登录成功。 细节:在主…

使用Rational Rose创建BBS论坛用例图

📚文章目录 📫实训任务:创建BBS论坛用例图和类图。 📫任务:根据以上描述文字以及“会员相关的功能操作”图,构思并画出会员用户功能操作用例图。 📫实训任务:创建BBS论坛用例图和类…

网上投稿系统用例图

---------------------------------------------------------------------------------------------------------------------------- 也许你感兴趣的是我画这个图的工具: EA下载地址: EA8.0(Enterprise Architect)汉化版注册码中文教程.zip EA备份地址: E…

学生选课系统用例图,以及部分代码实现

上学期软件导论做的文档,学生选课系统,在文档的基础上,再代码实现以下 背景——用例图:一个基础的学生选课系统 ER图设计如下:(学生和课程是n - m的关系,可修改的原图找不到了,悉知) 库表设计&…

棋牌管理系统用例图

转载于:https://www.cnblogs.com/pgone/p/7867810.html

Rational Rose学习笔记02:创建用例图

文章目录 一、用例图概念二、用例图三元素(一)参与者(Actor)(二)用例(Use Case)(三)关系(Relation)1、关联关系(Associati…

医院预约挂号系统业务建模+系统用例图

医院预约挂号系统业务建模 [综合案例:医院预约挂号系统]现要开发 一个通用的“医院预约挂号系统”,其开发 背景和问题陈述如下。 为了规范和推动医院预约挂号服务,卫生部29年8月在其官方网站发布了(关于在公立医院施行预约诊疗服务工作的意见(征求意见…

员工考勤系统业务建模+系统用例图

【员工考勤系统】 现要为某单位开发一款“员工考勤系统”,其开发背景和问题如下。 作为 Acme 公司的信息主管,你被委托开发一款新的考勤系统。要求新系统允许员工 记录电子的考勤信息并自动产生员工的工资支付信息。 新系统运行在整个公司内部的每名员…

售后服务工单系统用例图时序图

工单用例图 1,工单系统整体用例图 2,工单信息用例图 3,派单信息用例图 4,过程信息用例图 5,完工信息用例图 工单时序图 1,创建时序图 2,派单时序图 3,接单时序图 4,过程时…

怎么画系统用例图?(内含图例)

系统用例图的画法 文中所有图例的的需求描述如下: 系统的借阅者为学生和教师,系统为借阅者提供查询图书、借阅图书、归还图书的服务。学生最多可借阅5本,教师最多可借阅20本。在借阅和归还图书时,要先“验证借阅者的身份”。归还…