太阳城集团

  • / 21
  • 下载费用:30 金币  

一种覆盖区域求交的确认方法及系统.pdf

摘要
申请专利号:

CN201710151236.9

申请日:

2017.03.14

公开号:

太阳城集团CN106778050A

公开日:

2017.05.31

当前法律状态:

实审

有效性:

审中

法律详情: 实质审查的生效IPC(主分类):G06F 19/00申请日:20170314|||公开
IPC分类号: G06F19/00(2011.01)I 主分类号: G06F19/00
申请人: 中国地质大学(武汉)
发明人: 吕建军; 黎杰; 胡楚丽; 关庆锋
地址: 430070 湖北省武汉市洪山区鲁磨路388号
优先权:
专利代理机构: 北京众达德权知识产权代理有限公司 11570 代理人: 刘杰
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

太阳城集团CN201710151236.9

授权太阳城集团号:

|||

法律状态太阳城集团日:

2017.06.23|||2017.05.31

法律状态类型:

实质审查的生效|||公开

摘要

本发明公开了一种覆盖区域求交的确认方法及系统。其中,该方法至少包括:获得覆盖区域A和覆盖区域B;判断所述覆盖区域A与所述覆盖区域B的位置关系;若所述覆盖区域A与所述覆盖区域B的位置关系为包含,获得被包含区域为相交区域;若所述覆盖区域A与所述覆盖区域B的位置关系为相交,基于交点获得所述覆盖区域A和所述覆盖区域B的相交区域。本发明通过判断两个覆盖区域的位置关系获得相交区域,实现了对多个卫星传感器对地观测覆盖区域的求交,能够作为对卫星传感器进行规划以及优化调度的可信依据。

权利要求书

1.一种覆盖区域求交的确认方法,其特征在于,至少包括:
获得覆盖区域A和覆盖区域B;
判断所述覆盖区域A与所述覆盖区域B的位置关系;
若所述覆盖区域A与所述覆盖区域B的位置关系为包含,获得被包含区域为相交区域;
若所述覆盖区域A与所述覆盖区域B的位置关系为相交,基于交点获得所述覆盖区域A
和所述覆盖区域B的相交区域。
2.如权利要求1所述的方法,其特征在于,所述判断所述覆盖区域A与所述覆盖区域B的
位置关系,具体包括:
获得所述覆盖区域A的外包矩形RA和所述覆盖区域B的外包矩形RB;
判断所述外包矩形RA与所述外包矩形RB的位置关系;
根据所述外包矩形RA与所述外包矩形RB的位置关系判断所述覆盖区域A与所述覆盖区
域B的位置关系。
3.如权利要求2所述的方法,其特征在于,所述判断所述外包矩形RA与所述外包矩形RB
的位置关系,具体包括:
若满足条件{(xA<xB;(xA+wA)>(xB+wB))且(yA>yB;(yA-hA)<(yB-hB))}(1),则所述外包矩
形RA包含所述外包矩形RB;其中,xA为所述外包矩形RA左上角坐标的横坐标,yA为所述外包矩
形RA左上角坐标的纵坐标,wA为RA的水平长度,hA为RA的竖直长度,xB为所述外包矩形RB左上
角坐标的横坐标,yB为所述外包矩形RB左上角坐标的纵坐标,wB为RB的水平长度,hB为RB的竖
直长度;
若满足条件{(xA>xB;(xA+wA)<(xB+wB))且(yA<yB;(yA-hA)>(yB-hB))}(2),则所述外包矩
形RB包含所述外包矩形RA;
若满足条件{(xA<xB;(xA+wA)<xB)且(yA<yB;yA<(yB-hB))}(3)或条件{(xA<xB;(xA+wA)<xB)
且(yA>yB;(yA-hA)>yB)}(4)或条件{(xA>xB;(xB+wB)<xA)且(yA<yB;(yB-hB)>yA)}(5)或条件
{(xA>xB;(xB+wB)<xA)且(yA>yB;(yB-hB)>yA)}(6),则所述外包矩形RA和所述外包矩形RB相离;
若所述条件(1)、条件(2)、条件(3)、条件(4)、条件(5)和条件(6)均不满足,则所述外包
矩形RA和所述外包矩形RB相交;
所述根据所述外包矩形RA与所述外包矩形RB的位置关系判断所述覆盖区域A与所述覆
盖区域B的位置关系,具体包括:
如果所述外包矩形RA为被包含关系或相交关系,从所述覆盖区域A的顶点发射水平或竖
直的射线,通过判断所述射线与所述覆盖区域B的交点数量判断所述覆盖区域A与所述覆盖
区域B的位置关系;
若所有射线与所述覆盖区域B的交点数量都为1,则所述覆盖区域B包含所述覆盖区域
A;
若一部分射线与所述覆盖区域B的交点数量为1,另一部分射线与所述覆盖区域B的交
点数量为0和/或2,则所述覆盖区域A与所述覆盖区域B相交。
4.如权利要求1所述的方法,其特征在于,所述基于交点获得所述覆盖区域A和所述覆
盖区域B的相交区域,具体包括:
获得交点坐标;
标记所述交点的标识;
基于所述交点的标识遍历所述覆盖区域A和所述覆盖区域B的边获得所述覆盖区域A和
所述覆盖区域B的相交区域。
5.如权利要求4所述的方法,其特征在于,所述标记所述交点的标识,具体包括:
对于所述覆盖区域A的边pipi+1和所述覆盖区域B的边qjqj+1,计算叉积
如果所述叉积结果大于0,对于所述边pipi+1来说,将所述交点标记为第一标识;对于所
述边qjqj+1来说,将所述交点标记为第二标识;
如果所述叉积结果小于0,对于所述边pipi+1来说,将所述交点标记为所述第二标识;对
于所述边qjqj+1来说,将所述交点标记为所述第一标识;
如果所述叉积结果等于0,计算叉积若结果小于0,对于所述边pipi+1
来说,将所述交点标记为所述第一标识;对于所述边qjqj+1来说,将所述交点标记为所述第
二标识;
所述基于所述交点的标识遍历所述覆盖区域A和所述覆盖区域B的边获得所述覆盖区
域A和所述覆盖区域B的相交区域,具体包括:
从所述覆盖区域A的顶点出发,遍历所述覆盖区域A的边上的顶点和交点;当所述交点C
的标识为所述第一标识时,继续在所述覆盖区域A的边上遍历;当所述交点C的标识为所述
第二标识时,以相同方向在所述交点C所在的所述覆盖区域B的边上遍历各顶点和/或交点
直至遍历到相同的点,得到所述相交区域;
或,
从所述交点C出发,遍历所述覆盖区域A上的顶点和交点;当所述交点D的标识为所述第
一标识时,继续在所述覆盖区域A的边上遍历;当所述交点D的标识为所述第二标识时,以相
同方向在所述交点D所在的所述覆盖区域B的边上遍历各顶点和/或交点直至回到所述交点
C,得到所述相交区域。
6.一种覆盖区域求交的确认系统,其特征在于,至少包括:
数据获取模块,用于获得覆盖区域A和覆盖区域B;
判断模块,用于判断所述覆盖区域A与所述覆盖区域B的位置关系;
第一数据处理模块,用于若所述判断模块的判断结果为所述覆盖区域A与所述覆盖区
域B的位置关系为包含,获得被包含区域为相交区域;
第二数据处理模块,用于若所述判断模块的判断结果为所述覆盖区域A与所述覆盖区
域B的位置关系为相交,基于交点获得所述覆盖区域A和所述覆盖区域B的相交区域。
7.如权利要求6所述的系统,其特征在于,所述判断模块,具体包括:
外包矩形获取单元,用于获得所述覆盖区域A的外包矩形RA和所述覆盖区域B的外包矩
形RB;
判断单元,用于判断所述外包矩形RA与所述外包矩形RB的位置关系;
判定单元,用于根据所述外包矩形RA与所述外包矩形RB的位置关系判断所述覆盖区域A
与所述覆盖区域B的位置关系。
8.如权利要求7所述的系统,其特征在于,所述判断单元,具体包括:
第一判断子单元,用于若满足条件{(xA<xB;(xA+wA)>(xB+wB))且(yA>yB;(yA-hA)<(yB-
hB))}(1),则判定所述外包矩形RA包含所述外包矩形RB;其中,xA为所述外包矩形RA左上角坐
标的横坐标,yA为所述外包矩形RA左上角坐标的纵坐标,wA为RA的水平长度,hA为RA的竖直长
度,xB为所述外包矩形RB左上角坐标的横坐标,yB为所述外包矩形RB左上角坐标的纵坐标,wB
为RB的水平长度,hB为RB的竖直长度;
第二判断子单元,用于若满足条件{(xA>xB;(xA+wA)<(xB+wB))且(yA<yB;(yA-hA)>(yB-
hB))}(2),则判定所述外包矩形RB包含所述外包矩形RA;
第三判断子单元,用于若满足条件{(xA<xB;(xA+wA)<xB)且(yA<yB;yA<(yB-hB))}(3)或条
件{(xA<xB;(xA+wA)<xB)且(yA>yB;(yA-hA)>yB)}(4)或条件{(xA>xB;(xB+wB)<xA)且(yA<yB;(yB-
hB)>yA)}(5)或条件{(xA>xB;(xB+wB)<xA)且(yA>yB;(yB-hB)>yA)}(6),则判定所述外包矩形RA
和所述外包矩形RB相离;
第四判断子单元,用于若所述条件(1)、条件(2)、条件(3)、条件(4)、条件(5)和条件(6)
均不满足,则判定所述外包矩形RA和所述外包矩形RB相交;
所述判定单元,具体用于如果所述外包矩形RA为被包含关系或相交关系,从所述覆盖区
域A的顶点发射水平或竖直的射线,通过判断所述射线与所述覆盖区域B的交点数量判断所
述覆盖区域A与所述覆盖区域B的位置关系;若所有射线与所述覆盖区域B的交点数量都为
1,则判定所述覆盖区域B包含所述覆盖区域A;若一部分射线与所述覆盖区域B的交点数量
为1,另一部分射线与所述覆盖区域B的交点数量为0和/或2,则判定所述覆盖区域A与所述
覆盖区域B相交。
9.如权利要求6所述的系统,其特征在于,所述第二数据处理模块,具体包括:
交点坐标获取单元,用于若所述判断模块的判断结果为所述覆盖区域A与所述覆盖区
域B的位置关系为相交,获得交点坐标;
标记单元,用于标记所述交点的标识;
相交区域获取单元,用于基于所述交点的标识遍历所述覆盖区域A和所述覆盖区域B的
边获得所述覆盖区域A和所述覆盖区域B的相交区域。
10.如权利要求9所述的系统,其特征在于,所述标记单元,具体包括:
计算子单元,用于对于所述覆盖区域A的边pipi+1和所述覆盖区域B的边qjqj+1,计算叉积

第一标记子单元,用于如果所述叉积结果大于0,对于所述边pipi+1来说,将所述交点标
记为第一标识;对于所述边qjqj+1来说,将所述交点标记为第二标识;
第二标记子单元,用于如果所述叉积结果小于0,对于所述边pipi+1来说,将所述交点标
记为所述第二标识;对于所述边qjqj++来说,将所述交点标记为所述第一标识;
第三标记子单元,用于如果所述叉积结果等于0,计算叉积若结果小
于0,对于所述边pipi+1来说,将所述交点标记为所述第一标识;对于所述边qjqj+1来说,将所
述交点标记为所述第二标识;
所述相交区域获取单元,具体包括:
第一遍历子单元,用于从所述覆盖区域A的顶点出发,遍历所述覆盖区域A的边上的顶
点和交点;当所述交点C的标识为所述第一标识时,继续在所述覆盖区域A的边上遍历;当所
述交点C的标识为所述第二标识时,以相同方向在所述交点C所在的所述覆盖区域B的边上
遍历各顶点和/或交点直至遍历到相同的点,得到所述相交区域;
第二遍历子单元,用于从所述交点C出发,遍历所述覆盖区域A上的顶点和交点;当所述
交点D的标识为所述第一标识时,继续在所述覆盖区域A的边上遍历;当所述交点D的标识为
所述第二标识时,以相同方向在所述交点D所在的所述覆盖区域B的边上遍历各顶点和/或
交点直至回到所述交点C,得到所述相交区域。

说明书

一种覆盖区域求交的确认方法及系统

技术领域

本发明涉及数据处理技术领域,尤其涉及一种覆盖区域求交的确认方法及系统。

背景技术

传感器技术作为现代太阳城集团技术的三大基础之一,无处不在,它可以实现对地球观
测太阳城集团的采集。据科学家估计,到2020年前后,世界上将会有七万亿个有线或无线的传感
器,它们通过网络组织起来,以满足人们的即时需求。在地理太阳城集团科学的场模型中,由于传
感器无处不在,因此认为地球上的任何地理空间位置都有被观测的需求,整个地球表面上
都存在着一个连续的观测能力太阳城集团场。观测空间范围是传感器观测能力的一个重要部分,
不同的空间范围内存在着不同类型以及不同数量的传感器,因此,不同的空间范围内的传
感器的观测能力也不相同,如何确定某个空间范围内的传感器的观测能力对传感器的发掘
以及规划有着重要的意义。

卫星遥感传感器作为对地观测的一个重要工具,目前已经有了对某一时刻的单个
卫星传感器对地观测覆盖范围的模拟仿真计算方法了,由此可以确定某个空间范围内的单
个传感器的观测能力。但是,如果考虑到多个传感器进行协同观测,那么这些传感器在所观
测到的公共空间范围中就具备了多传感器的协同观测能力,根据这些传感器所具备的观测
能力就能对这些卫星传感器进行最优的规划调度。从技术角度上讲,求解多个卫星传感器
观测覆盖的公共区域的问题实际上就是多个多边形求交的问题。

目前,针对多个卫星传感器的协同观测能力定量评定的需求,还没有针对多个卫
星传感器对地观测覆盖求交的确认方法。

发明内容

本发明通过提供一种覆盖区域求交的确认方法及系统,实现了对多个卫星传感器
对地观测覆盖区域的求交的技术效果。

本发明提供了一种覆盖区域求交的确认方法,至少包括:

获得覆盖区域A和覆盖区域B;

判断所述覆盖区域A与所述覆盖区域B的位置关系;

若所述覆盖区域A与所述覆盖区域B的位置关系为包含,获得被包含区域为相交区
域;

若所述覆盖区域A与所述覆盖区域B的位置关系为相交,基于交点获得所述覆盖区
域A和所述覆盖区域B的相交区域。

进一步地,所述判断所述覆盖区域A与所述覆盖区域B的位置关系,具体包括:

获得所述覆盖区域A的外包矩形RA和所述覆盖区域B的外包矩形RB;

判断所述外包矩形RA与所述外包矩形RB的位置关系;

根据所述外包矩形RA与所述外包矩形RB的位置关系判断所述覆盖区域A与所述覆
盖区域B的位置关系。

进一步地,所述判断所述外包矩形RA与所述外包矩形RB的位置关系,具体包括:

若满足条件{(xA<xB;(xA+wA)>(xB+wB))且(yA>yB;(yA-hA)<(yB-hB))}(1),则所述外
包矩形RA包含所述外包矩形RB;其中,xA为所述外包矩形RA左上角坐标的横坐标,yA为所述外
包矩形RA左上角坐标的纵坐标,wA为RA的水平长度,hA为RA的竖直长度,xB为所述外包矩形RB
左上角坐标的横坐标,yB为所述外包矩形RB左上角坐标的纵坐标,wB为RB的水平长度,hB为RB
的竖直长度;

若满足条件{(xA>xB;(xA+wA)<(xB+wB))且(yA<yB;(yA-hA)>(yB-hB))}(2),则所述外
包矩形RB包含所述外包矩形RA;

若满足条件{(xA<xB;(xA+wA)<xB)且(yA<yB;yA<(yB-hB))}(3)或条件{(xA<xB;(xA+
wA)<xB)且(yA>yB;(yA-hA)>yB)}(4)或条件{(xA>xB;(xB+wB)<xA)且(yA<yB;(yB-hB)>yA)}(5)或
条件{(xA>xB;(xB+wB)<xA)且(yA>yB;(yB-hB)>yA)}(6),则所述外包矩形RA和所述外包矩形RB
相离;

若所述条件(1)、条件(2)、条件(3)、条件(4)、条件(5)和条件(6)均不满足,则所述
外包矩形RA和所述外包矩形RB相交;

所述根据所述外包矩形RA与所述外包矩形RB的位置关系判断所述覆盖区域A与所
述覆盖区域B的位置关系,具体包括:

如果所述外包矩形RA为被包含关系或相交关系,从所述覆盖区域A的顶点发射水
平或竖直的射线,通过判断所述射线与所述覆盖区域B的交点数量判断所述覆盖区域A与所
述覆盖区域B的位置关系;

若所有射线与所述覆盖区域B的交点数量都为1,则所述覆盖区域B包含所述覆盖
区域A;

若一部分射线与所述覆盖区域B的交点数量为1,另一部分射线与所述覆盖区域B
的交点数量为0和/或2,则所述覆盖区域A与所述覆盖区域B相交。

进一步地,所述基于交点获得所述覆盖区域A和所述覆盖区域B的相交区域,具体
包括:

获得交点坐标;

标记所述交点的标识;

基于所述交点的标识遍历所述覆盖区域A和所述覆盖区域B的边获得所述覆盖区
域A和所述覆盖区域B的相交区域。

进一步地,所述标记所述交点的标识,具体包括:

对于所述覆盖区域A的边pipi+1和所述覆盖区域B的边qjqj+1,计算叉积

如果所述叉积结果大于0,对于所述边pipi+1来说,将所述交点标记为第一标识;对
于所述边qjqj+1来说,将所述交点标记为第二标识;

如果所述叉积结果小于0,对于所述边pipi+1来说,将所述交点标记为所述第二标
识;对于所述边qjqj+1来说,将所述交点标记为所述第一标识;

如果所述叉积结果等于0,计算叉积若结果小于0,对于所述边
pipi++来说,将所述交点标记为所述第一标识;对于所述边qjqj++来说,将所述交点标记为所
述第二标识;

所述基于所述交点的标识遍历所述覆盖区域A和所述覆盖区域B的边获得所述覆
盖区域A和所述覆盖区域B的相交区域,具体包括:

从所述覆盖区域A的顶点出发,遍历所述覆盖区域A的边上的顶点和交点;当所述
交点C的标识为所述第一标识时,继续在所述覆盖区域A的边上遍历;当所述交点C的标识为
所述第二标识时,以相同方向在所述交点C所在的所述覆盖区域B的边上遍历各顶点和/或
交点直至遍历到相同的点,得到所述相交区域;

或,

从所述交点C出发,遍历所述覆盖区域A上的顶点和交点;当所述交点D的标识为所
述第一标识时,继续在所述覆盖区域A的边上遍历;当所述交点D的标识为所述第二标识时,
以相同方向在所述交点D所在的所述覆盖区域B的边上遍历各顶点和/或交点直至回到所述
交点C,得到所述相交区域。

本发明提供的覆盖区域求交的确认系统,至少包括:

数据获取模块,用于获得覆盖区域A和覆盖区域B;

判断模块,用于判断所述覆盖区域A与所述覆盖区域B的位置关系;

第一数据处理模块,用于若所述判断模块的判断结果为所述覆盖区域A与所述覆
盖区域B的位置关系为包含,获得被包含区域为相交区域;

第二数据处理模块,用于若所述判断模块的判断结果为所述覆盖区域A与所述覆
盖区域B的位置关系为相交,基于交点获得所述覆盖区域A和所述覆盖区域B的相交区域。

进一步地,所述判断模块,具体包括:

外包矩形获取单元,用于获得所述覆盖区域A的外包矩形RA和所述覆盖区域B的外
包矩形RB;

判断单元,用于判断所述外包矩形RA与所述外包矩形RB的位置关系;

判定单元,用于根据所述外包矩形RA与所述外包矩形RB的位置关系判断所述覆盖
区域A与所述覆盖区域B的位置关系。

进一步地,所述判断单元,具体包括:

第一判断子单元,用于若满足条件{(xA<xB;(xA+wA)>(xB+wB))且(yA>yB;(yA-hA)<
(yB-hB))}(1),则判定所述外包矩形RA包含所述外包矩形RB;其中,xA为所述外包矩形RA左上
角坐标的横坐标,yA为所述外包矩形RA左上角坐标的纵坐标,wA为RA的水平长度,hA为RA的竖
直长度,xB为所述外包矩形RB左上角坐标的横坐标,yB为所述外包矩形RB左上角坐标的纵坐
标,wB为RB的水平长度,hB为RB的竖直长度;

第二判断子单元,用于若满足条件{(xA>xB;(xA+wA)<(xB+wB))且(yA<yB;(yA-hA)>
(yB-hB))}(2),则判定所述外包矩形RB包含所述外包矩形RA;

第三判断子单元,用于若满足条件{(xA<xB;(xA+wA)<xB)且(yA<yB;yA<(yB-hB))}(3)
或条件{(xA<xB;(xA+wA)<xB)且(yA>yB;(yA-hA)>yB)}(4)或条件{(xA>xB;(xB+wB)<xA)且(yA<yB;
(yB-hB)>yA)}(5)或条件{(xA>xB;(xB+wB)<xA)且(yA>yB;(yB-hB)>yA)}(6),则判定所述外包矩
形RA和所述外包矩形RB相离;

第四判断子单元,用于若所述条件(1)、条件(2)、条件(3)、条件(4)、条件(5)和条
件(6)均不满足,则判定所述外包矩形RA和所述外包矩形RB相交;

所述判定单元,具体用于如果所述外包矩形RA为被包含关系或相交关系,从所述
覆盖区域A的顶点发射水平或竖直的射线,通过判断所述射线与所述覆盖区域B的交点数量
判断所述覆盖区域A与所述覆盖区域B的位置关系;若所有射线与所述覆盖区域B的交点数
量都为1,则判定所述覆盖区域B包含所述覆盖区域A;若一部分射线与所述覆盖区域B的交
点数量为1,另一部分射线与所述覆盖区域B的交点数量为0和/或2,则判定所述覆盖区域A
与所述覆盖区域B相交。

进一步地,所述第二数据处理模块,具体包括:

交点坐标获取单元,用于若所述判断模块的判断结果为所述覆盖区域A与所述覆
盖区域B的位置关系为相交,获得交点坐标;

标记单元,用于标记所述交点的标识;

相交区域获取单元,用于基于所述交点的标识遍历所述覆盖区域A和所述覆盖区
域B的边获得所述覆盖区域A和所述覆盖区域B的相交区域。

进一步地,所述标记单元,具体包括:

计算子单元,用于对于所述覆盖区域A的边pipi+1和所述覆盖区域B的边qjqj+1,计算
叉积

第一标记子单元,用于如果所述叉积结果大于0,对于所述边pipi+1来说,将所述交
点标记为第一标识;对于所述边qjqj+1来说,将所述交点标记为第二标识;

第二标记子单元,用于如果所述叉积结果小于0,对于所述边pipi+1来说,将所述交
点标记为所述第二标识;对于所述边qjqj+1来说,将所述交点标记为所述第一标识;

第三标记子单元,用于如果所述叉积结果等于0,计算叉积若结
果小于0,对于所述边pipi+1来说,将所述交点标记为所述第一标识;对于所述边qjqj+1来说,
将所述交点标记为所述第二标识;

所述相交区域获取单元,具体包括:

第一遍历子单元,用于从所述覆盖区域A的顶点出发,遍历所述覆盖区域A的边上
的顶点和交点;当所述交点C的标识为所述第一标识时,继续在所述覆盖区域A的边上遍历;
当所述交点C的标识为所述第二标识时,以相同方向在所述交点C所在的所述覆盖区域B的
边上遍历各顶点和/或交点直至遍历到相同的点,得到所述相交区域;

第二遍历子单元,用于从所述交点C出发,遍历所述覆盖区域A上的顶点和交点;当
所述交点D的标识为所述第一标识时,继续在所述覆盖区域A的边上遍历;当所述交点D的标
识为所述第二标识时,以相同方向在所述交点D所在的所述覆盖区域B的边上遍历各顶点
和/或交点直至回到所述交点C,得到所述相交区域。

本发明中提供的一个或多个技术方案,至少具有如下技术效果或优点:

通过判断两个覆盖区域的位置关系获得相交区域,实现了对多个卫星传感器对地
观测覆盖区域的求交,能够作为对卫星传感器进行规划以及优化调度的可信依据。通过本
发明可以穷举多个卫星传感器对地观测的覆盖区域的所有数量级的组合区域,并且把多个
观测覆盖区域求交的问题转换成两两区域求交的问题,从而免去了多个区域同时求交计算
所带来的复杂性。

附图说明

图1为本发明实施例提供的覆盖区域求交的确认方法的流程图;

图2为本发明实施例提供的覆盖区域求交的确认方法中卫星传感器观测覆盖区域
示意图;

图3为本发明实施例提供的覆盖区域求交的确认方法中卫星传感器观测覆盖区域
的初始位置判断示意图;

图4为本发明实施例提供的覆盖区域求交的确认方法中两个多边形求交点示意
图;

图5为本发明实施例提供的覆盖区域求交的确认方法中多边形结点遍历示意图;

图6为本发明实施例提供的覆盖区域求交的确认系统的模块图。

具体实施方式

本发明实施例通过提供一种覆盖区域求交的确认方法及系统,实现了对多个卫星
传感器对地观测覆盖区域的求交的技术效果。

本发明实施例中的技术方案为解决上述问题,总体思路如下:

通过判断两个覆盖区域的位置关系获得相交区域,实现了对多个卫星传感器对地
观测覆盖区域的求交,能够作为对卫星传感器进行规划以及优化调度的可信依据。通过本
发明实施例可以穷举多个卫星传感器对地观测的覆盖区域的所有数量级的组合区域,并且
把多个观测覆盖区域求交的问题转换成两两区域求交的问题,从而免去了多个区域同时求
交计算所带来的复杂性。

为了更好地理解上述技术方案,下面将结合说明书附图以及具体的实施方式对上
述技术方案进行详细的说明。

参见图1,本发明实施例提供的覆盖区域求交的确认方法,至少包括:

步骤S110:获得覆盖区域A和覆盖区域B;

步骤S120:判断覆盖区域A与覆盖区域B的位置关系;

若覆盖区域A与覆盖区域B的位置关系为包含,获得被包含区域为相交区域;

若覆盖区域A与覆盖区域B的位置关系为相交,基于交点获得覆盖区域A和覆盖区
域B的相交区域;

若覆盖区域A与覆盖区域B的位置关系为相离,说明覆盖区域A与覆盖区域B不存在
相交区域。

其中,判断覆盖区域A与覆盖区域B的位置关系的过程具体包括:

获得覆盖区域A的外包矩形RA和覆盖区域B的外包矩形RB;

判断外包矩形RA与外包矩形RB的位置关系;

根据外包矩形RA与外包矩形RB的位置关系判断覆盖区域A与覆盖区域B的位置关
系。

具体地,对判断外包矩形RA与外包矩形RB的位置关系的过程进行具体说明:

若满足条件{(xA<xB;(xA+wA)>(xB+wB))且(yA>yB;(yA-hA)<(yB-hB))}(1),则外包矩
形RA包含外包矩形RB;其中,xA为外包矩形RA左上角坐标的横坐标,yA为外包矩形RA左上角坐
标的纵坐标,wA为RA的水平长度,hA为RA的竖直长度,xB为外包矩形RB左上角坐标的横坐标,
yB为外包矩形RB左上角坐标的纵坐标,wB为RB的水平长度,hB为RB的竖直长度;

若满足条件{(xA>xB;(xA+wA)<(xB+wB))且(yA<yB;(yA-hA)>(yB-hB))}(2),则外包矩
形RB包含外包矩形RA;

若满足条件{(xA<xB;(xA+wA)<xB)且(yA<yB;yA<(yB-hB))}(3)或条件{(xA<xB;(xA+wA)
<xB)且(yA>yB;(yA-hA)>yB)}(4)或条件{(xA>xB;(xB+wB)<xA)且(yA<yB;(yB-hB)>yA)}(5)或条
件{(xA>xB;(xB+wB)<xA)且(yA>yB;(yB-hB)>yA)}(6),则外包矩形RA和外包矩形RB相离;

若条件(1)、条件(2)、条件(3)、条件(4)、条件(5)和条件(6)均不满足,则外包矩形
RA和外包矩形RB相交;

对根据外包矩形RA与外包矩形RB的位置关系判断覆盖区域A与覆盖区域B的位置关
系的过程进行具体说明:

如果外包矩形RA为被包含关系或相交关系,从覆盖区域A的顶点发射水平或竖直
的射线,通过判断射线与覆盖区域B的交点数量判断覆盖区域A与覆盖区域B的位置关系;

这里需要说明的是,当发射水平射线时,如果射线与覆盖区域B的竖直方向上的极
值顶点相交,则记交点数量为2;如果射线与覆盖区域B的非竖直方向上的极值顶点相交,则
记交点数量为1;当发射竖直射线时,如果射线与覆盖区域B的水平方向上的极值顶点相交,
则记交点数量为2;如果射线与覆盖区域B的非水平方向上的极值顶点相交,则记交点数量
为1;没有交点则记为0。

具体地,

若所有射线与覆盖区域B的交点数量都为1,则覆盖区域B包含覆盖区域A;

若一部分射线与覆盖区域B的交点数量为1,另一部分射线与覆盖区域B的交点数
量为0和/或2,则覆盖区域A与覆盖区域B相交;

若所有射线与覆盖区域B的交点数量都为0和/或2,则覆盖区域A与覆盖区域B相
离。

在本实施例中,若覆盖区域A与覆盖区域B的位置关系为相交,基于交点获得覆盖
区域A和覆盖区域B的相交区域,具体包括:

获得交点坐标;

标记交点的标识;

基于交点的标识遍历覆盖区域A和覆盖区域B的边获得覆盖区域A和覆盖区域B的
相交区域。

其中,获得交点坐标的步骤,具体包括:

对于覆盖区域A的边pipi+1和覆盖区域B的边qjqj+1,计算叉积:

如果d1*d2<0且d3*d4<0,则说明边pipi+1和边qjqj+1相交;如果{dn=0且
dn+1≠0(n=1或n=3)},当n=1时,若满足条件
且则说明边pipi+1和边qjqj+1相交;当n=3时,
若满足条件且
则说明边pipi+1和边qjqj+1相交;如果{dn=0且dn-1≠0(n=2或n=4)},当n=2时,
若满足条件且
则说明边pipi+1和边qjqj+1相交;当n=4时,若满足条件

则说明边pipi+1和边qjqj+1相交;其中,为点pi的横坐标,为点qi的横坐标,为点pi的
纵坐标,为点qi的纵坐标。在确定了两条边相交以后,先求出这两条边的截距方程,再基
于截距方程利用克拉默法则求出交点的坐标。

标记交点的标识的步骤,具体包括:

对于覆盖区域A的边pipi+1和覆盖区域B的边qjqj+1,计算叉积

如果叉积结果大于0,对于边pipi+1来说,将交点标记为第一标识;对于边qjqj+1来
说,将交点标记为第二标识;

如果叉积结果小于0,对于边pipi+1来说,将交点标记为第二标识;对于边qjqj+1来
说,将交点标记为第一标识;

如果叉积结果等于0,计算叉积若结果小于0,对于边pipi+1来说,
将交点标记为第一标识;对于边qjqj+1来说,将交点标记为第二标识。由于两边相交,因而不
存在叉积结果大于或等于0的情况。

需要说明的是,一条边上求出的交点数量可能为多个,但求出交点的顺序不一定
是按照顶点排列顺序的,因此,在求出一条边上的交点后,需要先计算出这条边上所有交点
到边起始点的欧氏距离,通过欧式距离从近到远进行排序,再记录到相应的边上。如果一个
多边形的任意一条边pipi+1与另一个多边形的任意连续的两条边qjqj+1和qj+1qj+2交于同一点
qj+1,则交点qj+1的标识记为边pipi+1与边qj+1qj+2相交时的标识。

通过以上步骤,便能得到带交点的多边形(覆盖区域),该多边形的形状与原多边
形的形状完全相同,作用是对其结点进行遍历得到相交区域。

基于交点的标识遍历覆盖区域A和覆盖区域B的边获得覆盖区域A和覆盖区域B的
相交区域,具体包括:

从覆盖区域A的顶点出发,遍历覆盖区域A的边上的顶点和交点;当交点C的标识为
第一标识时,继续在覆盖区域A的边上遍历;当交点C的标识为第二标识时,以相同方向在交
点C所在的覆盖区域B的边上遍历各顶点和/或交点直至遍历到相同的点,得到相交区域;

或,

从交点C出发,遍历覆盖区域A上的顶点和交点;当交点D的标识为第一标识时,继
续在覆盖区域A的边上遍历;当交点D的标识为第二标识时,以相同方向在交点D所在的覆盖
区域B的边上遍历各顶点和/或交点直至回到交点C,得到相交区域。

这里需要说明的是,每遍历到一个顶点或交点时,判断该点与起始点是否相同,并
且判断是否构成环;如果构成环,则遍历结束,相交区域被求出;如果没构成环,则继续遍
历。

下面通过一个实施例(对多卫星传感器对地观测的覆盖区域求交)对本发明实施
例进行说明:

(1)对所有选定的n个卫星传感器的观测覆盖区域进行从1到n的数字编号,表示为
集合S={1,2,…,n},然后对S进行不同数量的组合,组合的数量为因此,最多
会有t个相交区域,通过组合把问题简化为求t次两个多边形交集的问题;

具体地,首先对S内的元素进行两两组合,结果表达为集合:

S2={(x,y)|(x∈S,y∈S;x≠y)}

然后把S2中的两两组合的元素作为一个整体,进行三个元素的组合,结果表达为
集合:

S3=((x,y),w)|((x,y)∈S2,w∈S;x≠y≠w)}

按照上述规则,一直进行数量递增的组合,直到组合为集合:

Sn={((x,y,w,…,m),n)|((x,y,w,…,m)∈Sn-1,n∈S;x≠y…m≠n}=S

由排列组合的定义易知共有组合数量由于每次求组合都相当于求
两两多边形间的组合,因此,该问题就转换成了每次求两个“多边形”之间交集的问题。比如
有集合S={1,2,3,4},那么:

S2={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

S3={((1,2),3),((1,2),4),((1,3),4),((2,3),4)}

S4={((1,2,3),4)}=S

如图2所示,卫星1、卫星2和卫星3在地球表面的观测覆盖区域两两间都存在交集
(相交区域)且存在共同的交集。

(2)对(1)中得到的每一个组合进行初始位置关系(相交、相离、包含)的判定。如果
是相离关系,对下一个组合进行计算;如果是包含关系,则把被包含的多边形记为求交得到
的多边形,对下一个组合进行计算;如果是相交关系,则进一步计算相交所形成的区域;

如图3所示,多边形A与多边形B1到B6分别形成了6种不同的位置关系。其中,实线
为多边形原本的形状,虚线为外包矩形。首先看A与B1,由于它们的外包矩形完全相离,因此
它们的关系是相离;其次看A与B2,A的外包矩形包含了B2,因此,对B2的所有顶点都发射一
条向右的射线,判断其与A的交点,明显所有射线与A的交点都是1个,因此B2被A完全包含,
B2作为它们的相交区域;用同样的方法看A与B3-B6,它们的位置关系都可以通过上述方法
求出。

(3)在对相交区域的计算过程中,通过使用特定的规则对求交的两个多边形进行
交点计算并记录以分别生成带交点的多边形。具体地,求出两个多边形的交点(顶点也可记
为交点),并把交点记录到相应的位置以得到带交点的多边形,同时标记交点的标识。具体
的标记方式为:因多边形的边以相同方向排列,以顺时针方向为例,第一标识为“出”点的标
识,第二标识为“入”点的标识。对于相交的两条边p1p2和q1q2,如果q1q2的起始点在p1p2的左
边或q1q2的终点在p1p2的右边,则它们的交点为“入”点,反之则为“出”点。把两个多边形分
成主多边形和副多边形,主多边形中的入点标记为1,出点标记为-1,副多边形则相反;逆时
针方向则与顺时针方向相反。需要说明的是,一条边上的交点数量可能为多个,但求出交点
的顺序不一定是按照边顶点顺序的,因此,在求出一条边上的交点后,需要先对交点进行排
序,再记录到相应位置。如果一个多边形的一条边p1p2与另一个多边形连续的两条边q1q2和
q2q3交于一点,则该点的出入标识为p1p2与q2q3相交时的出入标识。

如图4中的多边形1与多边形2相交,其中有两个地方需要注意,首先是多边形1的
边p1p2和边p2p3与多边形2的边q1q2相交于同一点p2,按照上述规则,点p2的出入标识应该是
边p2p3与边q1q2相交时的出入标识,计算出该点为出点(-1);其次是多边形2的边q4q1与多边
形1的边p1p2和边p4p1相交于点m、t,由于计算出交点的先后顺序是m、t,但实际排列的顺序
应该是t、m,因此,需要对m、t进行排序,依据m与t到q4的距离从近到远进行排序,这样便得
到了q4、t、m、q1的顶点顺序,最后求交得到的多边形如图中表格内所示。

(4)通过使用特定的遍历规则,对(3)中生成的两个带交点的多边形的结点进行遍
历,从而得到相交所形成的多边形;然后计算下一个组合多边形,直到所有组合都被计算
完;

具体过程如下:

1)从主多边形的第一个顶点开始顺序遍历,直到遇到顶点的标识为-1(即第一标
识,表示“出“点)的点时便开始记录。首先记录该点,然后继续遍历主多边形的下一个点;

2)如果遇到的点的标识为0或-1(即第二标识,表示“入“点),则记录该点,然后判
断此时记录的集合是否构成环(第一个点与最后一个点是否相等且点数是否大于3);如果
构成环,则遍历结束,相交区域被求出;如果没构成环,则继续遍历主多边形的下一个点;如
果遇到的点的出入标识为1,记录该点,然后进入下一步;

3)进入到副多边形中坐标等于2)中出入标识为1的位置开始遍历,如果该点的出
入标识为1或0,记录该点并判断是否构成环;如果构成环,则遍历结束,相交区域被求出,否
则继续遍历副多边形的下一个点;如果遇到的点的出入标识为-1,则记录该点,然后返回到
主多边形中等于该点的位置;

4)返回到3)中所述的主多边形的位置后,按照2)3)步骤对主、副多边形进行遍历,
直至记录的集合构成环,就得到了所求相交区域的坐标集合。

参见图5,按照上述规则对图4中多边形相交所生成的带交点的坐标序列进行遍
历,从p1开始,遇到第一个标识为-1的点为m,记录m。然后继续遍历,遇到点p2,标识为-1,记
录并继续遍历。遇到点s,标识为1,记录并进入多边形2中的点s处,遍历到点n,标识为-1,记
录并返回到多边形1中的点n处,继续遍历。遇到点p4,标识为0,记录并继续遍历。遇到点t,
标识为1,记录并进入到多边形2中的点t处,遍历遇到点m,记录点m并判断出此时记录已经
构成环,即第一个点与最后一个点都是m且结点数量大于3,遍历结束,相交区域被找出,其
坐标序列为:m、p2、s、n、p4、t、m。

参见图6,本发明实施例提供的覆盖区域求交的确认系统,至少包括:

数据获取模块100,用于获得覆盖区域A和覆盖区域B;

判断模块200,用于判断覆盖区域A与覆盖区域B的位置关系;

在本实施例中,判断模块200,具体包括:

外包矩形获取单元,用于获得覆盖区域A的外包矩形RA和覆盖区域B的外包矩形RB;

判断单元,用于判断外包矩形RA与外包矩形RB的位置关系;

判定单元,用于根据外包矩形RA与外包矩形RB的位置关系判断覆盖区域A与覆盖区
域B的位置关系。

其中,判断单元具体包括:

第一判断子单元,用于若满足条件{(xA<xB;(xA+wA)>(xB+wB))且(yA>yB;(yA-hA)<
(yB-hB))}(1),则判定外包矩形RA包含外包矩形RB;其中,xA为外包矩形RA左上角坐标的横坐
标,yA为外包矩形RA左上角坐标的纵坐标,wA为RA的水平长度,hA为RA的竖直长度,xB为外包
矩形RB左上角坐标的横坐标,yB为外包矩形RB左上角坐标的纵坐标,wB为RB的水平长度,hB为
RB的竖直长度;

第二判断子单元,用于若满足条件{(xA>xB;(xA+wA)<(xB+wB))且(yA<yB;(yA-hA)>
(yB-hB))}(2),则判定外包矩形RB包含外包矩形RA;

第三判断子单元,用于若满足条件{(xA<xB;(xA+wA)<xB)且(yA<yB;yA<(yB-hB))}(3)
或条件{(xA<xB;(xA+wA)<xB)且(yA>yB;(yA-hA)>yB)}(4)或条件{(xA>xB;(xB+wB)<xA)且(yA<yB;
(yB-hB)>yA)}(5)或条件{(xA>xB;(xB+wB)<xA)且(yA>yB;(yB-hB)>yA)}(6),则判定外包矩形RA
和外包矩形RB相离;

第四判断子单元,用于若条件(1)、条件(2)、条件(3)、条件(4)、条件(5)和条件(6)
均不满足,则判定外包矩形RA和外包矩形RB相交;

判定单元,具体用于如果外包矩形RA为被包含关系或相交关系,从覆盖区域A的顶
点发射水平或竖直的射线,通过判断射线与覆盖区域B的交点数量判断所述覆盖区域A与覆
盖区域B的位置关系;若所有射线与所述覆盖区域B的交点数量都为1,则判定覆盖区域B包
含覆盖区域A;若一部分射线与覆盖区域B的交点数量为1,另一部分射线与覆盖区域B的交
点数量为0和/或2,则判定覆盖区域A与覆盖区域B相交。

第一数据处理模块300,用于若判断模块200的判断结果为覆盖区域A与覆盖区域B
的位置关系为包含,获得被包含区域为相交区域;

第二数据处理模块400,用于若判断模块200的判断结果为覆盖区域A与覆盖区域B
的位置关系为相交,基于交点获得覆盖区域A和覆盖区域B的相交区域。

在本实施例中,第二数据处理模块400,具体包括:

交点坐标获取单元,用于若判断模块200的判断结果为覆盖区域A与覆盖区域B的
位置关系为相交,获得交点坐标;

标记单元,用于标记交点的标识;

相交区域获取单元,用于基于交点的标识遍历覆盖区域A和覆盖区域B的边获得覆
盖区域A和覆盖区域B的相交区域。

其中,标记单元具体包括:

计算子单元,用于对于覆盖区域A的边pipi+1和覆盖区域B的边qjqj+1,计算叉积

第一标记子单元,用于如果叉积结果大于0,对于边pipi+1来说,将交点标记为第一
标识;对于边qjqj+1来说,将交点标记为第二标识;

第二标记子单元,用于如果叉积结果小于0,对于边pipi+1来说,将交点标记为第二
标识;对于边qjqj+1来说,将交点标记为第一标识;

第三标记子单元,用于如果叉积结果等于0,计算叉积若结果小
于0,对于边pipi+1来说,将交点标记为第一标识;对于边qjqj+1来说,将交点标记为第二标识;

相交区域获取单元,具体包括:

第一遍历子单元,用于从覆盖区域A的顶点出发,遍历覆盖区域A的边上的顶点和
交点;当交点C的标识为第一标识时,继续在覆盖区域A的边上遍历;当交点C的标识为第二
标识时,以相同方向在交点C所在的覆盖区域B的边上遍历各顶点和/或交点直至遍历到相
同的点,得到相交区域;

第二遍历子单元,用于从交点C出发,遍历覆盖区域A上的顶点和交点;当交点D的
标识为第一标识时,继续在覆盖区域A的边上遍历;当交点D的标识为第二标识时,以相同方
向在交点D所在的覆盖区域B的边上遍历各顶点和/或交点直至回到交点C,得到相交区域。

【技术效果】

通过判断两个覆盖区域的位置关系获得相交区域,实现了对多个卫星传感器对地
观测覆盖区域的求交,能够作为对卫星传感器进行规划以及优化调度的可信依据。通过本
发明实施例可以穷举多个卫星传感器对地观测的覆盖区域的所有数量级的组合区域,并且
把多个观测覆盖区域求交的问题转换成两两区域求交的问题,从而免去了多个区域同时求
交计算所带来的复杂性。

本领域内的技术人员应明白,本发明的实施例可提供为方法、系统、或计算机程序
产品。因此,本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实
施例的形式。而且,本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机
可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产
品的形式。

本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程
图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流
程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序
指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产
生一个机器,使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实
现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特
定方式工作的计算机可读存储器中,使得存储在该计算机可读存储器中的指令产生包括指
令装置的制造品,该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或
多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上,使得在计
算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理,从而在计算机或
其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一
个方框或多个方框中指定的功能的步骤。

尽管已描述了本发明的优选实施例,但本领域内的技术人员一旦得知了基本创造
性概念,则可对这些实施例作出另外的变更和修改。所以,所附权利要求意欲解释为包括优
选实施例以及落入本发明范围的所有变更和修改。

显然,本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精
神和范围。这样,倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围
之内,则本发明也意图包含这些改动和变型在内。

关 键 词:
一种 覆盖 区域 确认 方法 系统
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
太阳城集团本文
本文标题:一种覆盖区域求交的确认方法及系统.pdf
链接地址:http://zh228.com/p-6019688.html
太阳城集团我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
葡京赌场|welcome document.write ('');