一种用于多卫星传感器对地观测覆盖区域求并确认方法

摘要

一种用于多卫星传感器对地观测覆盖区域求并确认方法，包括以下步骤：获得卫星传感器对地观测的覆盖区域；建立覆盖区域的外包矩形，判断外包矩形的位置关系；判断覆盖区域的初始位置关系；判断覆盖区域内是否存在内部空洞；当覆盖区域内均不存在内部空洞时：若覆盖区域为包含关系，则用于包含的覆盖区域为合并区域；若覆盖区域为相交关系，则进行交点计算并标记交点的标识，通过遍历规则，确定合并区域以及内部空洞；当覆盖区域内存在内部空洞时，判断内部空洞与覆盖区域的位置关系：若覆盖区域为相交关系，进行交点计算并标记交点的标识，通过遍历规则，确定合并区域以及内部空洞；若覆盖区域为包含关系，确定用于包含的覆盖区域为合并区域。

权利要求

1.一种用于多卫星传感器对地观测覆盖区域求并确认方法，其特征在于，包括以下步骤：

获得所有选定的卫星传感器对地观测的覆盖区域，对所述覆盖区域进行组合；

建立所述覆盖区域的外包矩形，判断每一组合中的外包矩形的位置关系；

根据所述外包矩形的位置关系判断覆盖区域的初始位置关系，所述初始位置关系包括相交、相离和包含：对于一组合内的覆盖区域A和覆盖区域B，如果覆盖区域A的外包矩形RA和覆盖区域B的外包矩形RB为相交关系，则判断覆盖区域A与覆盖区域B的位置关系为相交或相离；如果外包矩形RA为被包含关系，从覆盖区域A的顶点发射水平或竖直的射线，通过判断射线与覆盖区域B的交点数量判断覆盖区域A与覆盖区域B的位置关系；若所有射线与覆盖区域B的交点数量都为1，则覆盖区域B包含覆盖区域A；若一部分射线与覆盖区域B的交点数量为1，另一部分射线与覆盖区域B的交点数量为0或2，则覆盖区域A与覆盖区域B相交；

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

判断覆盖区域内是否存在未检测到的区域，将该未检测到的区域定义为内部空洞；

当某一组合内的覆盖区域均不存在内部空洞时：若某一组合内的覆盖区域的位置关系为相离，则继续计算下一个组合；若某一组合内的覆盖区域的位置关系为包含，则确定用于包含的覆盖区域为合并区域；若某一组合内的覆盖区域的位置关系为相交，则对组合内的覆盖区域进行交点计算，将交点记录在覆盖区域上，标记交点的标识；通过对带交点的覆盖区域进行遍历，确定覆盖区域的合并区域以及合并后出现的内部空洞；

当一组合的覆盖区域内存在内部空洞时，根据覆盖区域的位置关系判断内部空洞与覆盖区域的位置关系，进而初步判断并得到覆盖区域合并后产生的内部空洞区域；若覆盖区域的位置关系为相交，则对组合内的覆盖区域进行交点计算，将交点记录在覆盖区域上，标记交点的标识；通过对带交点的覆盖区域进行遍历，确定覆盖区域的合并区域以及合并后出现的内部空洞；若覆盖区域的位置关系为包含，确定用于包含的覆盖区域为合并区域，并根据内部空洞与覆盖区域的位置关系判断合并区域的内部空洞。

2.如权利要求1所述的用于多卫星传感器对地观测覆盖区域求并确认方法，其特征在于：所述判断外包矩形的位置关系包括以下步骤：设一组合内包括覆盖区域A和覆盖区域B，建立覆盖区域A的外包矩形RA和覆盖区域B的外包矩形RB，

若满足条件{(xA(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-hB))}(2)，则外包矩形RB包含外包矩形RA；

若满足条件{(xAyB；(yA-hA)>yB)}(4)，条件{(xA>xB；(xB+wB)yB；(yB-hB)>yA)}(6)中的任一条件，则外包矩形RA和外包矩形RB相离；

若条件(1)、条件(2)、条件(3)、条件(4)、条件(5)和条件(6)中的任一条件均不满足，则外包矩形RA和外包矩形RB相交。

3.如权利要求2所述的用于多卫星传感器对地观测覆盖区域求并确认方法，其特征在于：所述标记交点的标识包括以下步骤：对于所述覆盖区域A的边pipi+1和所述覆盖区域B的边qjqj+1，计算叉积

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

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

如果所述叉积结果等于0，计算叉积 若结果小于0，对于所述边pipi+1来

说，将所述交点标记为所述第一标识；对于所述边qjqj+1来说，将所述交点标记为所述第二标识。

4.如权利要求3所述的用于多卫星传感器对地观测覆盖区域求并确认方法，其特征在于：所述对带交点的覆盖区域进行遍历具体包括：覆盖区域包括主覆盖区域和副覆盖区域，从主覆盖区域的顶点出发，遍历主覆盖区域的边上的顶点和交点；当一交点的标识为第二标识时，继续在主覆盖区域的边上遍历；当一交点的标识为第一标识时，以主覆盖区域的顶点出发方向在该交点所在的副覆盖区域的边上遍历各顶点或交点直至遍历到相同的点，得到合并区域；或从初始交点出发，遍历主覆盖区域上的顶点和交点；当另一交点的标识为第二标识时，继续在主覆盖区域的边上遍历；当另一交点的标识为第一标识时，以主覆盖区域的顶点出发方向在另一交点所在的副覆盖区域的边上遍历各顶点或交点直至回到初始交点，得到合并区域；

将主覆盖区域上的顶点和交点与合并区域上的点进行对比，若某一点的标识为第二标识但该某一点不在合并区域内，则从该某一点出发，在主覆盖区域的边上进行遍历，直至遍历到标识为第一标识的另一点，确定该某一点、另一点及它们之间的点构成了内部空洞。

5.如权利要求4所述的用于多卫星传感器对地观测覆盖区域求并确认方法，其特征在于：所述初步判断覆盖区域合并后产生的内部空洞区域包括以下步骤：设覆盖区域A内存在内部空洞Ta：若覆盖区域B包含覆盖区域A，则覆盖区域A和覆盖区域B合并后的合并区域不存在内部空洞；若覆盖区域A包含覆盖区域B且内部空洞Ta与覆盖区域B相交，则确定内部空洞Ta减去内部空洞Ta与覆盖区域B相交的部分为覆盖区域A和覆盖区域B合并后的内部空洞；若覆盖区域A包含覆盖区域B且内部空洞Ta包含覆盖区域B，则判断覆盖区域A和覆盖区域B实际的位置关系为相离；若覆盖区域A包含覆盖区域B且覆盖区域B包含内部空洞Ta，则覆盖区域A和覆盖区域B合并后的合并区域不存在内部空洞；若覆盖区域A包含覆盖区域B且内部空洞Ta与覆盖区域B相离，则覆盖区域A和覆盖区域B合并后的合并区域的内部空洞为Ta；若覆盖区域A与覆盖区域B相交且覆盖区域B包含内部空洞Ta，则覆盖区域A和覆盖区域B合并后的合并区域不存在内部空洞；若覆盖区域A与覆盖区域B相交且覆盖区域B与内部空洞Ta相交，则确定内部空洞Ta减去内部空洞Ta与覆盖区域B相交的部分为覆盖区域A和覆盖区域B合并后的内部空洞；若覆盖区域A与覆盖区域B相交且覆盖区域B与内部空洞Ta相离，则覆盖区域A和覆盖区域B合并后的合并区域的内部空洞为Ta或者Ta及新生成的内部空洞。

说明书

一种用于多卫星传感器对地观测覆盖区域求并确认方法

技术领域

[0001] 本发明涉及智慧地球对地观测领域，尤其涉及一种用于多卫星传感器对地观测覆盖区域求并确认方法。

背景技术

[0002] 据科学家估计，到2020年前后，世界上会有七万亿个有线或无线的传感器，它们通过网络组织起来，以满足人们的即时需要。在地理信息科学的场模型下，由于传感器无处不在，因此认为地球上的任何地理空间位置都有被观测的需求，整个地球表面上都存在着一个连续的观测能力信息场，需要发掘符合要求的传感器进行观测，而传感器所具备的观测能力即为传感器发掘的重要依据。观测空间范围作为传感器观测能力的一个重要部分，不同的空间范围内存在着不同类型以及不同数量的传感器，因此不同的空间范围内的观测能力也不相同，如何确定某个空间范围内的观测能力对传感器的发掘以及规划有着重要的意义。

[0003] 卫星遥感传感器作为对地观测的一个重要工具，目前已经有对某一时刻的单个卫星传感器对地观测覆盖范围的模拟仿真的计算方法，通过现有的计算方法可以确定某个空间范围内所具有的单个传感器观测能力，但是如果考虑到多传感器进行协同观测，那么这些传感器所能观测到的全部空间范围中就具备了多传感器的协同观测能力，根据这些区域所具备的观测能力就能对这些卫星传感器进行最优的规划调度。从技术角度讲，求解多卫星传感器观测覆盖的全部区域的问题实际上就是多个多边形求并的问题，已知的有效算法如Weiler算法，它能对凹凸多边形进行有效的求并，但是它却没有考虑到边重合、顶点重合等特殊情况；此外如Sutherland-Hodgeman等算法也能对多边形进行有效的裁剪，但这些算法却要求多边形是矩形，在多数实际情况下并不适用。综上可知目前关于多边形求并的算法要么就是限定了多边形的形状、要么就是不能考虑到一些较为常见的特殊情况。针对多卫星传感器协同观测能力定量评定的需求，目前正缺乏针对多个卫星传感器对地观测覆盖区域求并确认方法。

发明内容

[0004] 有鉴于此，本发明提供了一种用于多卫星传感器对地观测覆盖区域求并确认方法，实现了对多个卫星传感器对地观测覆盖区域的求并的技术效果。

[0005] 本发明提供一种用于多卫星传感器对地观测覆盖区域求并确认方法，包括以下步骤：

[0006] 获得所有选定的卫星传感器对地观测的覆盖区域，对所述覆盖区域进行组合；

[0007] 建立所述覆盖区域的外包矩形，判断每一组合中的外包矩形的位置关系；

[0008] 根据所述外包矩形的位置关系判断覆盖区域的初始位置关系，所述初始位置关系包括相交、相离和包含：对于一组合内的覆盖区域A和覆盖区域B，如果覆盖区域A的外包矩形RA和覆盖区域B的外包矩形RB为相交关系，则判断覆盖区域A与覆盖区域B的位置关系为相交或相离；如果外包矩形RA为被包含关系，从覆盖区域A的顶点发射水平或竖直的射线，通过判断射线与覆盖区域B的交点数量判断覆盖区域A与覆盖区域B的位置关系；若所有射线与覆盖区域B的交点数量都为1，则覆盖区域B包含覆盖区域A；若一部分射线与覆盖区域B的交点数量为1，另一部分射线与覆盖区域B的交点数量为0或2，则覆盖区域A与覆盖区域B相交；若所有射线与覆盖区域B的交点数量都为0或2，则覆盖区域A与覆盖区域B相离；

[0009] 判断覆盖区域内是否存在未检测到的区域，将该未检测到的区域定义为内部空洞；

[0010] 当某一组合内的覆盖区域均不存在内部空洞时：若某一组合内的覆盖区域的位置关系为相离，则继续计算下一个组合；若某一组合内的覆盖区域的位置关系为包含，则确定用于包含的覆盖区域为合并区域；若某一组合内的覆盖区域的位置关系为相交，则对组合内的覆盖区域进行交点计算，将交点记录在覆盖区域上，标记交点的标识；通过对带交点的覆盖区域进行遍历，确定覆盖区域的合并区域以及合并后出现的内部空洞；

[0011] 当一组合的覆盖区域内存在内部空洞时，根据覆盖区域的位置关系判断内部空洞与覆盖区域的位置关系，进而初步判断并得到覆盖区域合并后产生的内部空洞区域；若覆盖区域的位置关系为相交，则对组合内的覆盖区域进行交点计算，将交点记录在覆盖区域上，标记交点的标识；通过对带交点的覆盖区域进行遍历，确定覆盖区域的合并区域以及合并后出现的内部空洞；若覆盖区域的位置关系为包含，确定用于包含的覆盖区域为合并区域，并根据内部空洞与覆盖区域的位置关系判断合并区域的内部空洞。

[0012] 进一步地，所述判断外包矩形的位置关系包括以下步骤：

[0013] 设一组合内包括覆盖区域A和覆盖区域B，建立覆盖区域A的外包矩形RA和覆盖区域B的外包矩形RB，

[0014] 若满足条件{(xA(xB+wB))且(yA>yB；(yA-hA)<(yB-hB))}(1)，则外包矩形RA包含外包矩形RB；

[0015] 式中，xA为外包矩形RA左上角坐标的横坐标，yA为外包矩形RA左上角坐标的纵坐标，wA为RA的水平长度，hA为RA的竖直长度，xB为外包矩形RB左上角坐标的横坐标，yB为外包矩形RB左上角坐标的纵坐标，wB为RB的水平长度，hB为RB的竖直长度；

[0016] 若满足条件{(xA>xB；(xA+wA)<(xB+wB))且(yA(yB-hB))}(2)，则外包矩形RB包含外包矩形RA；

[0017] 若满足条件{(xAyB；(yA-hA)>yB)}(4)，条件{(xA>xB；(xB+wB)yB；(yB-hB)>yA)}(6)中的任一条件，则外包矩形RA和外包矩形RB相离；

[0018] 若条件(1)、条件(2)、条件(3)、条件(4)、条件(5)和条件(6)中的任一条件均不满足，则外包矩形RA和外包矩形RB相交。

[0019] 进一步地，所述标记交点的标识包括以下步骤：

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

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

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

[0023] 如果所述叉积结果等于0，计算叉积 若结果小于0，对于所述边pipi+1来说，将所述交点标记为所述第一标识；对于所述边qjqj+1来说，将所述交点标记为所述第二标识。

[0024] 进一步地，所述对带交点的覆盖区域进行遍历具体包括：

[0025] 覆盖区域包括主覆盖区域和副覆盖区域，从主覆盖区域的顶点出发，遍历主覆盖区域的边上的顶点和交点；当一交点的标识为第二标识时，继续在主覆盖区域的边上遍历；当一交点的标识为第一标识时，以主覆盖区域的顶点出发方向在该交点所在的副覆盖区域的边上遍历各顶点或交点直至遍历到相同的点，得到合并区域；或从初始交点出发，遍历主覆盖区域上的顶点和交点；当另一交点的标识为第二标识时，继续在主覆盖区域的边上遍历；当另一交点的标识为第一标识时，以主覆盖区域的顶点出发方向在另一交点所在的副覆盖区域的边上遍历各顶点或交点直至回到初始交点，得到合并区域；

[0026] 将主覆盖区域上的顶点和交点与合并区域上的点进行对比，若某一点的标识为第二标识但该某一点不在合并区域内，则从该某一点出发，在主覆盖区域的边上进行遍历，直至遍历到标识为第一标识的另一点，确定该某一点、另一点及它们之间的点构成了内部空洞。

[0027] 进一步地，所述初步判断覆盖区域合并后产生的内部空洞区域包括以下步骤：

[0028] 设覆盖区域A内存在内部空洞Ta：若覆盖区域B包含覆盖区域A，则覆盖区域A和覆盖区域B合并后的合并区域不存在内部空洞；若覆盖区域A包含覆盖区域B且内部空洞Ta与a a覆盖区域B相交，则确定内部空洞T减去内部空洞T与覆盖区域B相交的部分为覆盖区域A和覆盖区域B合并后的内部空洞；若覆盖区域A包含覆盖区域B且内部空洞Ta包含覆盖区域B，则判断覆盖区域A和覆盖区域B实际的位置关系为相离；若覆盖区域A包含覆盖区域B且覆盖区域B包含内部空洞Ta，则覆盖区域A和覆盖区域B合并后的合并区域不存在内部空洞；若覆盖区域A包含覆盖区域B且内部空洞Ta与覆盖区域B相离，则覆盖区域A和覆盖区域B合并后的合并区域的内部空洞为Ta；若覆盖区域A与覆盖区域B相交且覆盖区域B包含内部空洞Ta，则覆盖区域A和覆盖区域B合并后的合并区域不存在内部空洞；若覆盖区域A与覆盖区域B相交且覆盖区域B与内部空洞Ta相交，则确定内部空洞Ta减去内部空洞Ta与覆盖区域B相交的部分为覆盖区域A和覆盖区域B合并后的内部空洞；若覆盖区域A与覆盖区域B相交且覆盖区域B与内部空洞Ta相离，则覆盖区域A和覆盖区域B合并后的合并区域的内部空洞为Ta或者Ta及新生成的内部空洞。

[0029] 本发明提供的技术方案带来的有益效果是：

[0030] (1)本发明通过判断覆盖区域的位置关系获得合并区域，实现了对多个卫星传感器对地观测覆盖区域的求并，能够作为对卫星传感器进行规划以及优化调度的可信依据；

[0031] (2)通过本发明可以穷举多个卫星传感器对地观测的覆盖区域的所有数量级的组合区域，并且把多个观测覆盖区域求并的问题转换成两两区域求并的问题，从而免去了多个区域同时求并计算所带来的复杂性；

[0032] (3)本发明基于交点的标识，确定了覆盖区域的合并区域，并识别了生成内部空洞的情况，准确度高。

附图说明

[0033] 图1是本发明用于多卫星传感器对地观测覆盖区域求并确认方法的流程图。

[0034] 图2是本发明一实施例用于多卫星传感器对地观测覆盖区域求并确认方法中两个多边形求交点示意图。

[0035] 图3是本发明一实施例用于多卫星传感器对地观测覆盖区域求并确认方法中多边形交点遍历示意图。

[0036] 图4是本发明一实施例用于多卫星传感器对地观测覆盖区域求并确认方法中判断内部空洞与覆盖区域位置关系的示意图。

具体实施方式

[0037] 为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明实施方式作进一步地描述。

[0038] 请参考图1和图2，本发明的实施例提供了一种用于多卫星传感器对地观测覆盖区域求并确认方法，包括以下步骤：

[0039] 步骤S101,获得所有选定的卫星传感器对地观测的覆盖区域，对覆盖区域进行组合。

[0040] 一实施例中，将每个卫星传感器对地观测的覆盖区域看作一个多边形，对所有选定的n个卫星传感器对地观测的覆盖区域进行从1到n的数字编号，数字编号构成集合S＝{1,2,…,n}，然后对集合S进行不同数量的组合，组合的数量为 因此，最多会有个合并区域，通过组合把问题简化为求 次两个多边形并集的问题；

[0041] 具体地，首先对集合S内的元素进行两两组合，结果表达为集合：

[0042] S2＝{(x,y)|(x∈S,y∈S；x≠y)}

[0043] 然后把集合S2中的两两组合的元素作为一个整体，进行三个元素的组合，结果表达为集合：

[0044] S3＝(((x，y)iw)|((x，y)∈S2,w∈S；x≠y≠w)}

[0045] 按照上述规则，一直进行数量递增的组合，直到组合为集合：

[0046] Sn＝{((x，y，w，...，m)，n)|((x，y，w，...，m)∈Sn-1，n∈S；x≠y...m≠n}＝S[0047] 由排列组合的定义易知共有组合数量 由于每次求组合都相当于求两两多边形间的组合，因此，该问题就转换成了每次求两个“多边形”之间并集的问题。

[0048] 例如有集合S＝{1，2，3，4}，那么：

[0049] S2＝{(1，2)，(1，3)，(1，4)，(2，3)，(2，4)，(3，4)}

[0050] S3＝{((1，2)，3)，((1，2)，4)，((1，3)，4)，((2，3)，4)}

[0051] S4＝{((1，2，3)，4)}＝S

[0052] 步骤S102，建立所有覆盖区域的外包矩形，判断每一组合中的外包矩形的位置关系。

[0053] 一实施例中，选择一个组合，该组合包括覆盖区域A和覆盖区域B，建立覆盖区域A的外包矩形RA和覆盖区域B的外包矩形RB，参考图2，覆盖区域A为一多边形，其外包矩形RA为一虚线表示的长方形，覆盖区域B为一长方形，外包矩形RB与覆盖区域B重叠。

[0054] 对外包矩形RA与外包矩形RB，判断它们的位置关系包括以下步骤：

[0055] 2.1若满足条件{(xA＜xB；(xA+wA)＞(xB+wB))且(yA＞yB；(yA-hA)＜(yB-hB))}(1)，则外包矩形RA包含外包矩形RB；

[0056] 式中，xA为外包矩形RA左上角坐标的横坐标，yA为外包矩形RA左上角坐标的纵坐标，wA为RA的水平长度，hA为RA的竖直长度，xB为外包矩形RB左上角坐标的横坐标，yB为外包矩形RB左上角坐标的纵坐标，wB为RB的水平长度，hB为RB的竖直长度；

[0057] 2.2若满足条件{(xA＞xB；(xA+wA)＜(xB+wB))且(yA＜yB；(yA-hA)＞(yB-hB))}(2)，则外包矩形RB包含外包矩形RA；

[0058] 2.3若满足条件{)xA＜xB；(xA+wA)＜xB)}(3)，条件{(yA＞yB；(yA-hA)＞yB)}(4)，条件{(xA＞xB；(xB+wB)＜xA)}(5)，和条件{(yA＞yB；(yB-hB)＞yA)}(6)中的任一条件，则外包矩形RA和外包矩形RB相离；

[0059] 2.4若条件(1)、条件(2)、条件(3)、条件(4)、条件(5)和条件(6)中的任一条件均不满足，则外包矩形RA和外包矩形RB相交。

[0060] 参考图2，一实施例中，(xA>xB；(xA+wA)<(xB+wB))且(yA(yB-hB))，说明外包矩形RA包含外包矩形RB。

[0061] 步骤S103，根据外包矩形的位置关系判断覆盖区域的初始位置关系，初始位置关系包括相交、相离和包含。

[0062] 一实施例中，根据外包矩形RA与外包矩形RB的位置关系判断覆盖区域A与覆盖区域B的位置关系，包括以下步骤：

[0063] 如果外包矩形RA和外包矩形RB为相交关系，则判断覆盖区域A与覆盖区域B的位置关系为相交或相离；如果外包矩形RA为被包含关系，从覆盖区域A的顶点发射水平或竖直的射线，通过判断射线与覆盖区域B的交点数量判断覆盖区域A与覆盖区域B的位置关系；

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

[0065] 若所有射线与覆盖区域B的交点数量都为1，则覆盖区域B包含覆盖区域A；

[0066] 若一部分射线与覆盖区域B的交点数量为1，另一部分射线与覆盖区域B的交点数量为0或2，则覆盖区域A与覆盖区域B相交；

[0067] 若所有射线与覆盖区域B的交点数量都为0或2，则覆盖区域A与覆盖区域B相离。

[0068] 参考图2，一实施例中，外包矩形RB为被包含关系，覆盖区域B为多边形q1q2q3q4,覆盖区域A为多边形p1p2p3p4p5p；,从覆盖区域B的顶点q3发射一条水平向右的射线l1，该射线l1与覆盖区域A的交点数量为0，从覆盖区域B的顶点q4发射一条水平向右的射线l2，该射线l2与覆盖区域A的交点数量为1，由此判断覆盖区域A和覆盖区域B相交。

[0069] 步骤S104，判断覆盖区域内是否存在未检测到的区域，将该未检测到的区域定义为内部空洞。

[0070] 步骤S105，当某一组合内的覆盖区域均不存在内部空洞时：

[0071] 5.1若某一组合内的覆盖区域的位置关系为相离，则继续计算下一个组合；

[0072] 5.2若某一组合内的覆盖区域的位置关系为包含，则确定用于包含的覆盖区域为合并区域；

[0073] 5.3若某一组合内的覆盖区域的位置关系为相交，进行以下步骤的计算：

[0074] 5.3.1对组合内的覆盖区域进行交点计算，将交点记录在覆盖区域上，并标记交点的标识；

[0075] 交点计算包括以下步骤：

[0076] 参考图2，一实施例中，对于覆盖区域A的边pipi+1和覆盖区域B的边qjqj+1，计算叉积表示为d1, 表示为d2， 表示为d3，表示为d4；如果 且
则说明边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的纵坐标。在确定了两条边相交以后，先求出这两条边的截距方程，再基于截距方程利用克拉默法则求出交点的坐标。

[0077] 标记交点的标识具体包括：

[0078] 对于覆盖区域A的边pipi+1和覆盖区域B的边qjqj+1，计算叉积

[0079] 如果叉积 大于0，对于边pipi+1来说，将pipi+1和qjqj+1的交点标记为第一标识；对于边qjqj+1来说，将pipi+1和qjqj+1的交点标记为第二标识；

[0080] 如果叉积 小于0，对于边pipi+1来说，将pipi+1和qjqj+1的交点标记为第二标识；对于边qjqj+1来说，将pipi+1和qjqj+1的交点标记为第一标识；

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

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

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

[0084] 参考图2，一实施例中，具体的标记方式为：因多边形的边以相同方向排列，以顺时针方向为例，第一标识为“出”点的标识，第二标识为“入”点的标识。对于相交的两条边p1p2和q1q2，如果q1q2的起始点在p1p2的左边或q1q2的终点在p1p2的右边，则它们的交点为“入”点，反之则为“出”点，把两个多边形分成主多边形和副多边形，主多边形中的入点标记为1，出点标记为-1，副多边形则相反，将主多边形和副多边形中不是交点的点标记为0；逆时针方向则与顺时针方向相反。需要说明的是，一条边上的交点数量可能为多个，但求出交点的顺序不一定是按照边顶点顺序的，因此，在求出一条边上的交点后，需要先对交点进行排序，再记录到相应位置，如果一个多边形的一条边p1p2与另一个多边形连续的两条边q1q2和q2q3交于一点，则该点的标识为p1p2与q2q3相交时的标识。

[0085] 如图2所示，多边形A以及多边形B相交，其中需要注意的有两个地方，首先是多边形A的边p1p2与多边形B的边q1q2、q2q3相交于同一点q2，按照上述规则，q2点的标识应该是p1p2与q2q3相交时的标识，计算出该点为入点；其次是多边形A的边p4p5与多边形B的边q2q3、q4q1相交于点n、p，由于计算出交点的先后顺序是n、p，但实际上排列顺序应该是p、n，因此需要对n、p进行排序，依据m与p到p4的距离从近到远进行排序，这样便得到了p4、p、n、p5的顶点顺序，最后求并得到的多边形坐标序列如图2中表格内所示。

[0086] 5.3.2通过对带交点的覆盖区域进行遍历，确定覆盖区域的合并区域以及合并后出现的内部空洞。

[0087] 对带交点的覆盖区域进行遍历具体包括：

[0088] 覆盖区域包括主覆盖区域和副覆盖区域，从主覆盖区域的顶点出发，遍历主覆盖区域的边上的顶点和交点；当一交点的标识为第二标识时，继续在主覆盖区域的边上遍历；当一交点的标识为第一标识时，以主覆盖区域的顶点出发方向在该交点所在的副覆盖区域的边上遍历各顶点或交点直至遍历到相同的点，得到合并区域；或从初始交点出发，遍历主覆盖区域上的顶点和交点；当另一交点的标识为第二标识时，继续在主覆盖区域的边上遍历；当另一交点的标识为第一标识时，以主覆盖区域的顶点出发方向在另一交点所在的副覆盖区域的边上遍历各顶点或交点直至回到初始交点，得到合并区域；

[0089] 将主覆盖区域上的顶点和交点与合并区域上的点进行对比，若某一点的标识为第二标识但该某一点不在合并区域内，则从该某一点出发，在主覆盖区域的边上进行遍历，直至遍历到标识为第一标识的另一点，确定该某一点、另一点及它们之间的点构成了内部空洞。

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

[0091] 参考图2，一实施例中：

[0092] 1)从主多边形A的第一个顶点开始顺序遍历，直到遇到顶点的标识为1(即第二标识，表示“入”点)的点时便开始记录，首先记录该点，然后继续遍历主多边形A的下一个点；

[0093] 2)如果遇到的点的标识为0或1，则记录该点，然后判断此时记录的集合是否构成环(第一个点与最后一个点相等)，如果构成环，则遍历结束，合并区域被求出，如果没构成环，则继续遍历主多边形A的下一个点；如果遇到的点的标识为-1，记录该点，然后进入下一步；

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

[0095] 4)返回到3)中的主多边形A的位置后，按照2)3)步骤对主多边形A、副多边形B进行遍历，直至记录的集合构成环，就得到了所求合并区域的坐标集合，如果到最后一个点也没构成环，则返回到第一个点继续遍历，直至记录的集合构成环，就得到了所求合并区域的坐标集合；

[0096] 5)用主多边形A的坐标与生成的合并区域的坐标一一对比标识，如果某个坐标在主多边形A中标识为1但该坐标不在合并区域坐标集合中，那么判断生成了内部空洞，从主多边形A中的该坐标开始遍历，直到遇到一个标识为-1的坐标，则从坐标标识为1到这个标识为-1之间的点集合则为内部空洞的坐标集合。

[0097] 如图3所示，按照上述规则对图2中多边形相交所生成的带交点的坐标序列进行遍历，从p1开始，遇到第一个标识为1的点为q2，记录q2，然后继续遍历，遇到点p2到p4，出入性质为0，记录并继续遍历，遇到点p，标识为-1，记录并进入多边形B中p点处，遍历到点q，标识为1，记录并返回到多边形A中的点q处，继续遍历，遇到点p；到p1，标识为0，记录并继续遍历，此时多边形A已经遍历到最后一个点(即第一个点)，依旧没构成环，则继续从头开始遍历，遍历到q2，并判断出此时记录已经构成环，第一个点与最后一个点都是q2，遍历结束，合并区域被找出,其坐标序列为:q2、p2、q3、p3、p4、p、q、p；、p1、q2。之后，再检测其是否生成了内部空洞，通过多边形A的坐标与求并后区域的坐标一一对比，发现多边形A中的点n标识为1且不在求并后的区域坐标中，因为判断生成了内部空洞，从点n开始遍历直到遇到第一个出点m，则它们以及它们之间的点构成了内部空洞，从图3中可以看到内部空洞坐标序列为：n、p5、m。

[0098] 步骤S106，当一组合的覆盖区域内存在内部空洞时，根据覆盖区域的位置关系判断内部空洞与覆盖区域的位置关系,并根据内部空洞与覆盖区域的位置关系初步判断覆盖区域合并后产生的内部空洞区域；

[0099] 参考图4，一实施例中，以四边形代表覆盖区域B，以A字多边形代表覆盖区域A，以三角形代表内部空洞Ta，覆盖区域A内存在内部空洞Ta：若覆盖区域B包含覆盖区域A，则覆盖区域A和覆盖区域B合并后的合并区域不存在内部空洞；若覆盖区域A包含覆盖区域B且内部空洞Ta与覆盖区域B相交，则确定内部空洞Ta减去内部空洞Ta与覆盖区域B相交的部分为覆a盖区域A和覆盖区域B合并后的内部空洞；若覆盖区域A包含覆盖区域B且内部空洞T包含覆盖区域B，则判断覆盖区域A和覆盖区域B实际的位置关系为相离；若覆盖区域A包含覆盖区域B且覆盖区域B包含内部空洞Ta，则覆盖区域A和覆盖区域B合并后的合并区域不存在内部空洞；若覆盖区域A包含覆盖区域B且内部空洞Ta与覆盖区域B相离，则覆盖区域A和覆盖区域B合并后的合并区域的内部空洞为Ta；若覆盖区域A与覆盖区域B相交且覆盖区域B包含内部空洞Ta，则覆盖区域A和覆盖区域B合并后的合并区域不存在内部空洞；若覆盖区域A与覆盖区域B相交且覆盖区域B与内部空洞Ta相交，则确定内部空洞Ta减去内部空洞Ta与覆盖区域B相交的部分为覆盖区域A和覆盖区域B合并后的内部空洞；若覆盖区域A与覆盖区域B相交且覆盖区域B与内部空洞Ta相离，则覆盖区域A和覆盖区域B合并后的合并区域的内部空洞为Ta或者Ta及新生成的内部空洞。

[0100] 6.1若覆盖区域的位置关系为相交，根据步骤5.3.1中的交点计算和交点的标识及步骤5.3.2中对覆盖区域进行遍历确定覆盖区域的合并区域以及合并后出现的内部空洞。

[0101] 6.2若覆盖区域的位置关系为包含，确定用于包含的覆盖区域为合并区域，并根据内部空洞与覆盖区域的位置关系判断合并区域的内部空洞。

[0102] 本发明通过判断覆盖区域的位置关系获得合并区域，实现了对多个卫星传感器对地观测覆盖区域的求并，能够作为对卫星传感器进行规划以及优化调度的可信依据；通过本发明可以穷举多个卫星传感器对地观测的覆盖区域的所有数量级的组合区域，并且把多个观测覆盖区域求并的问题转换成两两区域求并的问题，从而免去了多个区域同时求并计算所带来的复杂性；本发明基于交点的标识，确定了覆盖区域的合并区域，并识别了生成内部空洞的情况，准确度高。

[0103] 在不冲突的情况下，本文中上述实施例及实施例中的特征可以相互结合。

[0104] 以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。