数学之美--不规则多边形相交计算
前言
我决定写一些技术类的文章,想了半天都不知道从何入手,从编程语言方面来看C#,Java,C++以及python等我的基本功很差;如果从应用角度来完成某些的话,虽然工作流是我的长项,但是如果需要完整来描述工作流的话,我又要死掉无数的脑细胞.无果
最后在看Google的blog的时候突发奇想:我也可以来写写”数学之美”,虽然我的大学数学学的并不好,但本文涉及的数学知识基本都是高中的.我也不排斥各位对于本文的问题有更好的解决方案.
Ok,let’s go!
问题
时光回溯到2004年4月,我刚进入X公司不久,公司当时已经开始做广东某地区国土局的MIS.对方提出了一个要求:他们给出两组坐标,这两组坐标分别代表两个采矿区,他们要求我们提供一个计算功能可以算出这两个物理矿区是否有重叠.
说的简单点就是:
1. 已知两个不规则多边形;
2. 计算出两个多边形是否相交;
3. 给出算法.
用下面的图来表示一下:
<shapetype id="_x0000_t75" path="m@4@5l@4@11@9@11@9@5xe" o:spt="75" coordsize="21600,21600" stroked="f" filled="f" o:preferrelative="t"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></path><lock aspectratio="t" v:ext="edit"></lock></shapetype><shape id="_x0000_i1025" style="WIDTH: 225pt; HEIGHT: 96.75pt" type="#_x0000_t75"><imagedata o:title="1" src="file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image001.jpg"></imagedata></shape>
“效果<chmetcnv w:st="on" unitname="”" sourcevalue="1" hasspace="False" negative="False" numbertype="1" tcsc="0"><font face="Times New Roman"><strong style="mso-bidi-font-weight: normal"><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%">1</span></strong><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%">”</span></font></chmetcnv>表示”图<chmetcnv w:st="on" unitname="”" sourcevalue="1" hasspace="False" negative="False" numbertype="1" tcsc="0"><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%"><font face="Times New Roman">1”</font></span></chmetcnv>和”图<chmetcnv w:st="on" unitname="”" sourcevalue="2" hasspace="False" negative="False" numbertype="1" tcsc="0"><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%"><font face="Times New Roman">2”</font></span></chmetcnv>两个图并没有相交
<shape id="_x0000_i1026" style="WIDTH: 289.5pt; HEIGHT: 96.75pt" type="#_x0000_t75"><imagedata o:title="2" src="file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image002.jpg"></imagedata></shape>
“效果<chmetcnv w:st="on" unitname="”" sourcevalue="2" hasspace="False" negative="False" numbertype="1" tcsc="0"><strong style="mso-bidi-font-weight: normal"><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%"><font face="Times New Roman">2”</font></span></strong></chmetcnv>表示由于”图<chmetcnv w:st="on" unitname="”" sourcevalue="1" hasspace="False" negative="False" numbertype="1" tcsc="0"><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%"><font face="Times New Roman">1”</font></span></chmetcnv>的右平移和”图<chmetcnv w:st="on" unitname="”" sourcevalue="2" hasspace="False" negative="False" numbertype="1" tcsc="0"><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%"><font face="Times New Roman">2”</font></span></chmetcnv>相交并且有重叠的区域.
当然还有效果<chmetcnv w:st="on" unitname="”" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0"><strong style="mso-bidi-font-weight: normal"><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%">3</span></strong><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%">”</span></chmetcnv>’图<chmetcnv w:st="on" unitname="’" sourcevalue="1" hasspace="False" negative="False" numbertype="1" tcsc="0"><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%"><font face="Times New Roman">1’</font></span></chmetcnv>放大后完全容纳’图<chmetcnv w:st="on" unitname="’" sourcevalue="2" hasspace="False" negative="False" numbertype="1" tcsc="0"><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%">2’</span></chmetcnv>”和效果<chmetcnv w:st="on" unitname="”" sourcevalue="4" hasspace="False" negative="False" numbertype="1" tcsc="0"><strong style="mso-bidi-font-weight: normal"><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%">4</span></strong><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%">”</span></chmetcnv>’图<chmetcnv w:st="on" unitname="’" sourcevalue="1" hasspace="False" negative="False" numbertype="1" tcsc="0"><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%"><font face="Times New Roman">1’</font></span></chmetcnv>和’图<chmetcnv w:st="on" unitname="’" sourcevalue="2" hasspace="False" negative="False" numbertype="1" tcsc="0"><span lang="EN-US" style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%"><font face="Times New Roman">2’</font></span></chmetcnv>完全一样,产生重合”,但是在这里我们不考虑那么多.
X公司不是专门做GIS的,没有专业的工具可用.也没有人做过GIS,在我接手之前已经有几个人花了无数的时间去解决这个问题,都没有成功.
这些人的学历都比我高,包括X公司当时的副总经理原来是教大学数学的.所以我才会在自己的blog回复某个评论时说”本科生和研究生未必不能来做编码”,因为这么多年来我看过很多本科生,研究生,甚至博士的编码都不合格.
当时把这个问题交给我或许他们都是在尝试运气,只不过他们的运气确实比较好.
我暂时写到这里,把这个问题放三天,看看各位同学对于”两个不规则多边形是否相交”有好的解决方法和思路!
一方面真诚的欢迎大家提出自己的思路,另一方面也看看CSDNer的水平,呵呵.
PS:1,不能使用专业的GIS系统来解决这个问题;2,解决问题的方法不能超过大学水平.
(本文不涉及商业机密,所以发表本文不涉及职业道德和相关保密条例)
分享到:
相关推荐
ACM算法 计算几何基础 用于计算不规则多边形,凹多边形和凸多边形
简单多边形的相交、合并算法。仅支持简单凹凸多边形。所谓简单多边形即多边形内部不含环的多边形。这个demo程序只是介绍了多边形相交、合并的算法,针对简单凹凸多边形可以正常处理。算法仅供参考! 如需要支持内部...
用vc + mapobjects开发的源代码,用鼠标对多边形进行操作,实现了多边形的相交计算功能。
四年级下册数学课件--第四单元认识多边形复习青岛版.pdf
C#不规则多边形面积周长计算
保护私有信息的计算几何是一类特殊的安全多方计算问题,在军事、商业等领域具有重要的应用前景。...基于该协议,提出保护私有信息的两多边形相交面积计算协议;分析和证明上述协议的正确性、安全性和复杂性。
简单的不规则封闭多边形面积计算方法。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
8--[画任意多边形].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码8--[画任意多边形].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码8--[画任意多边形].zip源码scratch2.0 3.0编程项目源文件源码...
geojson-area, 计算geojson多边形或者多重多边形的面积 geojson区域计算任意 GeoJSON 几何图形内的区域。用法npm install @mapbox/geojson-area示例var geojsonArea = require('@mapb
点击鼠标绘制不规则多边形,并计算面积.自己复习几何的时候研究实现的一个小功能,无端被涨价了10倍...
用JS代码实现了多边形之间的相交关系判断,包含了线与多边形,多边形与多边形的相交判断
多边形相交运算源码-polygon intersection Operational source
使用qt计算地理平面下椭圆坐标的 不规则、不封闭 多边形面积。
四班级下册数学教案-9 .1 探究多边形 ︳冀教版(2021秋 ).docx
自己用VC++作的多边形程序,包括求面积、凹凸性、凸包、两多边形相交等。
OpenGL 凸多边形截取线段 Cyrus-Beck 算法 OpenGL 凸多边形截取线段 Cyrus-Beck 算法 OpenGL 凸多边形截取线段 Cyrus-Beck 算法 OpenGL 凸多边形截取线段 Cyrus-Beck 算法 OpenGL 凸多边形截取线段 Cyrus-Beck 算法 ...
7-7(添加自定义多边形).7z
五年级上册数学试题-第六单元 《多边形的面积》 同步练习 (扫描版 有答案)人教新课标2014秋.doc
五年级上册数学试题- 第六单元 《多边形的面积》 同步练习 (扫描版 有答案)人教新课标2014秋.doc