卫星系统算法课程设计 - 第一部分：城市时间窗口、间隙等_卫星对地时间窗口

  先看我上传的视频，看看是否是你们想要的效果：

【算法课设】 卫星系统 运行情况存档_哔哩哔哩_bilibili

【算法课设】存档2_哔哩哔哩_bilibili

注意：视频中没有画出地球那种越靠极点纬度线越短的情况，但面积计算是没有问题的，因为画图和计算分离，图只是可视化，但面积等数据用的是微积分。

1、问题背景

2、第一个问题----计算卫星与目标的时间窗口

 

 （本图取自本人的汇报ppt，希望对你们有帮助）

接下里将放出数据预处理代码，这些代码是使用c++写的，请自己用c++开一个空项目，将下列代码放入cpp中，把老师给的卫星数据放入项目文件，运行就能得到结果。目的是将卫星信息简化，将每个卫星每一秒的中心位置或者说圆心位置写入文件中。那么文件应该包含86400个经度纬度信息。

#include<iostream>
#include<cmath>
#include<fstream>
#include <stdio.h>
#include<stdlib.h>
#include<string>
#include<vector>
#include <typeinfo>//typeid
using namespace std;
 
double Radius[86400];//用于临时保存每一秒对应的半径
double test1[10];
double aveRadius[9];
 
 
 
double pingJun(double* radius)
{
	double cul = 0;
	for (int i = 0; i < 86400; i++)
	{
		cul += radius[i];
	}
	//f
	return (cul / (double)86400);
}
 
double HangLieShi(double a11, double a12, double a21, double a22)
{
	return (a11 * a22 - a12 * a21);
}
class myPoint
{
public:
	myPoint()
	{
		x = 0, y = 0;
	}
	myPoint(double x0, double y0) { x = x0; y = y0; }
	myPoint(myPoint& P) { x = P.x; y = P.y; }
	myPoint& operator=(const myPoint& P)
	{
		x = P.x;
		y = P.y;
		return *this;
	}
	~myPoint() {}
	void set(double x0, double y0)
	{
		x = x0;
		y = y0;
	}
	double x, y;
};
myPoint Position[9][86400];//第i个卫星的第j秒的圆心
class Line
{
public:
	Line(myPoint a0, myPoint b0) :a(a0), b(b0)
	{
		if (a.x == b.x) 
		{ 
			A = 0; 
			B = 1; 
			C = (a.y + b.y) / 2; 
		}
		else if (a.y == b.y) 
		{ 
			A = 1; 
		    B = 0; 
	     	C = (a.x + b.x) / 2; 
		}
		else
		{
			A = 1;
			B = (a.x - b.x) / (a.y - b.y);
			C = (a.x + b.x) / 2 + B * (a.y + b.y) / 2;
		}
	}
	~Line() {}
	myPoint a, b;
	double A, B, C;
};
 
 
class Circle
{
public:
	Circle()
	{
	}
	Circle(myPoint a0, myPoint b0, myPoint c0) :a1(a0), b1(b0), c1(c0) {}
	~Circle() {}
	double calculation(int number, int time);//计算圆心，半径
	void reSet(myPoint&a0, myPoint&b0, myPoint&c0)
	{
		a1 = a0; b1 = b0; c1 = c0;
	}
protected:
	myPoint a1, b1, c1;
	double x0, y0, R;
};
//number对应卫星编号，time即时刻，要将每个卫星每时刻对应的圆心坐标进行保存
double Circle::calculation(int number, int time)
{
	Line l1(a1, b1), l2(a1, c1);
	double J;
	J = HangLieShi(l1.A, l2.A, l1.B, l2.B);
	//简单来说呢，就是克莱姆法则求解方程
	//如果两个直线不同，说明可以使用克莱姆法则求解
	if (J)
	{
		//将向量的常量代替矩阵对应的值，求出圆心
		x0 = HangLieShi(l1.C, l2.C, l1.B, l2.B) / J;
		y0 = HangLieShi(l1.A, l2.A, l1.C, l2.C) / J;
		Position[number][time].set(x0, y0);
		//使用圆方程解半径
		R = sqrt((a1.x - x0) * (a1.x - x0) + (a1.y - y0) * (a1.y - y0));
	}
	else
	{
		return -1;
	}
	return R;
}
 
 
//读文件函数
void Read(int number, double &radius)
{
	ifstream  ifs;//流对象
	//读文件0-8
	if (0 <= number && 9 > number)
	{
		switch (number)
		{
		case 0:
		{
			ifs.open("SatCoverInfo_0.txt");
			break;
		}
		case 1:
		{
			ifs.open("SatCoverInfo_1.txt");
			break;
		}
		case 2:
		{
			ifs.open("SatCoverInfo_2.txt");
			break;
		}
		case 3:
		{
			ifs.open("SatCoverInfo_3.txt");
			break;
		}
		case 4:
		{
			ifs.open("SatCoverInfo_4.txt");
			break;
		}
		case 5:
		{
			ifs.open("SatCoverInfo_5.txt");
			break;
		}
		case 6:
		{
			ifs.open("SatCoverInfo_6.txt");
			break;
 
		}
		case 7:
		{
			ifs.open("SatCoverInfo_7.txt");
			break;
		}
		case 8:
		{
			ifs.open("SatCoverInfo_8.txt");
			break;
		}
		default:
		{
			return;
		}
 
		}
	}
	else
	{
		return;
	}
	//ifs.open("SatCoverInfo_0.txt");
	if (!ifs)
	{
		cout << "读取失败" << endl;
		return ;
	}
	//打开指定文件
	int getLineNum = 22;//每次读取22行
	double x = 0, y = 0;
	char name[20];
	myPoint a, b, c;
	Circle A;
	//读文件。
	for (int j = 0; j < 86400; j++)
	{
		for (int i = 0; i < getLineNum; i++)
		{
			if (i == 0)
			{
				ifs.getline(name, 20);
				continue;
			}
			ifs >> x >> y;
			if (i == 1)
			{
				a.set(x, y);
			}
			else if (i == 6)
			{
				b.set(x, y);
			}
			else if (i == 11)
			{
				c.set(x, y);
			}
			else if (i == 21)
			{
				ifs.getline(name, 20);
			}
		}
		A.reSet(a, b, c);
		Radius[j] = A.calculation(number, j);
	}
	ifs.close();
	radius = pingJun(Radius);
}
 
void Write(int number)
{
	ofstream  ofs;//流对象
	//读文件0-8
	if (0 <= number && 9 > number)
	{
		switch (number)
		{
		case 0:
		{
			ofs.open("Position_0.txt");
			break;
		}
		case 1:
		{
			ofs.open("Position_1.txt");
			break;
		}
		case 2:
		{
			ofs.open("Position_2.txt");
			break;
		}
		case 3:
		{
			ofs.open("Position_3.txt");
			break;
		}
		case 4:
		{
			ofs.open("Position_4.txt");
			break;
		}
		case 5:
		{
			ofs.open("Position_5.txt");
			break;
		}
		case 6:
		{
			ofs.open("Position_6.txt");
			break;
 
		}
		case 7:
		{
			ofs.open("Position_7.txt");
			break;
		}
		case 8:
		{
			ofs.open("Position_8.txt");
			break;
		}
		default:
		{
			return;
		}
 
		}
	}
	else
	{
		return;
	}
	//是否打开成功
	if (!ofs)
	{
		cout << "读取失败" << endl;
		return;
	}
 
	for (int j = 0; j < 86400; j++)
	{
		ofs << Position[number][j].x << "         " << Position[number][j].y<<endl;
	}
}
 
int main()
{
	
	for (int i = 0; i < 9; i++)
	{
		Read(i, aveRadius[i]);
		Write(i);
	}
	for (int i = 0; i < 9; i++)
	{
		cout << "第" << i<< "个卫星区域平均半径为：" << aveRadius[i] << endl;
	}
	//一下的注释代码是最开始使用来求平均半径的
	//Read(3, aveRadius[3]);
	//Write(3);
	//cout << "平均半径为：" << aveRadius[3] << endl;
	return 0;
}
 

  那么以上，我们就可以把第0到第8个卫星的位置信息写入文件中，第0个卫星的文件是Position_0，第1是Position_1，后面同理。

  然后这里我直接给出9个卫星的平均半径，之后在qt中直接用这个半径作为每个卫星的半径就可以了。卫星服务区的半径是：7.0068。

2.2、求城市时间窗口与时间间隙

  时间窗口，比如0 - 86399秒内，第1秒-第400秒该城市被卫星服务（只要被9个卫星的其中一个服务就是被服务），那么产生一个时间窗口[1，400]，那么第0秒和第401秒是不被服务的。

  我下面再讲的仔细些，包含代码，先写城市City类，成员变量有：城市名称、经度、纬度、时间窗口的QVector。然后写一个时间窗口TimeSlot类，成员变量：startTime、overTime、length。

[startTime，overTime]，length = overTime - startTime + 1。

然后卫星的类Satellite，成员变量：double *x,double *y。

qt的代码如下：

city.h

#ifndef CITY_H
#define CITY_H
 
#include"timeslot.h"
#include<QVector>
//这是一个城市的类
class City
{
 
public:
    double longitude;//城市的经度
    double latitude;//城市的纬度
    QString name;//城市的名字
    QVector<TimeSlot> slot;//该城市的时间窗口，后面会计算，出现一个窗口时候就会push进去一个窗口
 
public:
    City();
 
};
 
//保存城市的表
class CityList
{
public:
    City city[19];//一共有19个城市
    //构造函数
    CityList();
    int location(QString n);//传入名字，定位
 
};
 
 
 
#endif // CITY_H

city.cpp

#include "city.h"
 
City::City()
{
    this->longitude = 0;
    this->latitude = 0;
    name = "";
}
 
 
CityList::CityList()
{
    city[0].name = "奥克兰";
    city[0].longitude = 237.87;//-122.13
    city[0].latitude = 37.47;
    //
    city[1].name = "敖德萨";
    city[1].longitude = 30.46;
    city[1].latitude = 46.3;
    //
    city[2].name = "冈山";
    city[2].longitude = 133.54;
    city[2].latitude = 34.4;
    //
    city[3].name = "俄克拉荷马城";
    city[3].longitude = 262.68;//-97.32
    city[3].latitude = 35.29;
    //
    city[4].name = "鄂木斯克";
    city[4].longitude = 55;
    city[4].latitude = 73.22;
    //
    city[5].name = "奥拉涅斯塔克";
    city[5].longitude = 290.42;//69.58
    city[5].latitude = 12.3;
    //
    city[6].name = "奥拉多";
    city[6].longitude = 278.78;//-81.22
    city[6].latitude = 28.3;
    //
    city[7].name = "大阪";
    city[7].longitude = 135.3;
    city[7].latitude = 34.4;
    //
    city[8].name = "奥斯陆";
    city[8].longitude = 10.41;
    city[5].latitude = 159.56;
    //
    city[9].name = "渥太华";
    city[9].longitude = 284.57;//-75.43
    city[9].latitude = 45.25;
    //
    city[10].name = "瓦拉杜古";
    city[10].longitude = 358.6;//-1.4
    city[10].latitude = 12.2;
    //
    city[11].name = "帕果帕果";
    city[11].longitude = 189.58;//-170.42
    city[11].latitude = -14.16;
    //
    city[12].name = "巨港";
    city[12].longitude = 104.5;
    city[12].latitude = -2.59;
    //
    city[13].name = "波赫恩";
    city[13].longitude = 158.1;
    city[13].latitude = 6.55;
    //
    city[14].name = "帕尔马";
    city[14].longitude = 2.39;
    city[14].latitude = 39.26;
    //
    city[15].name = "巴拿马";
    city[15].longitude = 280.7;//-79.3
    city[15].latitude = 8.57;
    //
    city[16].name = "帕皮提";
    city[16].longitude = 210.66;//
    city[16].latitude = -17.32;
    //
    city[17].name = "帕拉马里博";
    city[17].longitude = 304.86;//55.14
    city[17].latitude = 5.52;
    //
    city[18].name = "巴黎";
    city[18].longitude = 2.2;
    city[18].latitude = 48.51;
}
 
 
int CityList::location(QString n)
{
    for(int i = 0; i < 19; i++)
    {
        if(city[i].name == n)
        {
            return i;
        }
    }
    return -1;
}
 
 
 
 

timeslot.h

#ifndef TIMESLOT_H
#define TIMESLOT_H
 
 
//如题，这是一个时间段的类，用于保存各城市各时间窗口的值（开始时间、结束时间、时间长度）
class TimeSlot
{
public:
    int startTime;
    int overTime;
    int length;
public:
    TimeSlot();
    TimeSlot(int s, int o);
    void set(int start, int over);
};
 
//时间间隙
class TimeGap
{
 
};
 
#endif // TIMESLOT_H

timeslot.cpp

#include "timeslot.h"
 
TimeSlot::TimeSlot()
{
    startTime = 0;
    overTime = 0;
    length = 0;
}
TimeSlot::TimeSlot(int s, int o)
{
    startTime = s;
    overTime = o;
    length = overTime - startTime + 1;
}
 
void TimeSlot::set(int start, int over)
{
    startTime = start;
    overTime = over;
    //[1, 5]的长度是 5 - 1 + 1
    //对于区间[l, r],长度为 r - l + 1
    length = overTime - startTime + 1;
 
}

satellite.h

#ifndef SATELLITE_H
#define SATELLITE_H
 
//卫星的类，保存半径与中心坐标，但由分析情况来看，半径已经不需要了
class Satellite
{
public:
    double *x;
    double *y;
public:
    Satellite();
    ~Satellite();
 
 
};
 
#endif // SATELLITE_H

satellite.cpp

#include "satellite.h"
 
Satellite::Satellite()
{
    x = new double[86400];
    y = new double[86400];
}
 
Satellite::~Satellite()
{
    delete []x;
    delete []y;
}

2.2.1、时间窗口求解方法

mianwindow.cpp中的，主要看方法，代码的注释非常超级终极无敌tm详细，我认为我说的再多用处也不大，不如你们好好看看这个代码。

解释：设置bool类型的变量flag，一开始设置为false 若某一刻城市被服务，将flag置为true。 若某一刻不被服务，同时flag为true，说明产生了一个时间窗口 通过timeSlot的构造函数创建对象，将其 push_back到该城市的vector<timeSlor>容器中。同时flag置为false。

然后我此处只求了时间窗口，还有时间间隙呢，那么时间间隙我不太懂意思，有两种解释。

一：城市不被服务的时间段就是时间间隙。

二、两个时间窗口之间产生一个时间间隙。

请自己体会，我在课设中用的是第二种解释，你们可以去问老师到底是哪种。

只要弄明白下列代码，基本没什么问题了，时间间隙大不了你们自己写一个timeGap，或者通过方法用窗口求间隙，很简单的。当时我就是懒得再写一个timeGap了，现在想想，确实写一个会比较好。

  时间窗口最大最小值、累计值就不要多说了吧？你好好想想TimeSlot里我为什么要写length，tnn的遍历一遍这个城市的QVctor<TimeSlot>容器不就有最大最小和累计了吗！！！！

间隙同理哈。

//读取卫星信息
void MainWindow::ReadFile(int number)
{
    ifstream ifs;
    switch (number)
    {
    case 0:
    {
        ifs.open("D:/vc/z/myEarth/Position_0.txt");
        break;
    }
    case 1:
    {
        ifs.open("D:/vc/z/myEarth/Position_1.txt");
        break;
    }
    case 2:
    {
        ifs.open("D:/vc/z/myEarth/Position_2.txt");
        break;
    }
    case 3:
    {
        ifs.open("D:/vc/z/myEarth/Position_3.txt");
        break;
    }
    case 4:
    {
        ifs.open("D:/vc/z/myEarth/Position_4.txt");
        break;
    }
    case 5:
    {
        ifs.open("D:/vc/z/myEarth/Position_5.txt");
        break;
    }
    case 6:
    {
        ifs.open("D:/vc/z/myEarth/Position_6.txt");
        break;
 
    }
    case 7:
    {
        ifs.open("D:/vc/z/myEarth/Position_7.txt");
        break;
    }
    case 8:
    {
        ifs.open("D:/vc/z/myEarth/Position_8.txt");
        break;
    }
    default:
    {
        return;
    }
    }
    //将每一秒的信息读入
    for(int i = 0; i < 86400; i++)
    {
        ifs>>satellite[number].x[i]>>satellite[number].y[i];//读入第number个卫星的第i时刻的位置信息
    }
    ifs.close();
}
//求平方
double culSquare(double a)
{
    return a*a;
}
 
 
//请在mainwindow的构造函数中执行sInit()，初始化，这样我们一运行就把所有城市的时间窗口求完了
void MainWindow::sInit()
{
    //其实半径甚至就是一样
    /*
    satellite[0].radius = 7.00681;
    satellite[1].radius = 7.00679;
    satellite[2].radius = 7.00681;
    satellite[3].radius = 7.0068;
    satellite[4].radius = 7.0068;
    satellite[5].radius = 7.00682;
    satellite[6].radius = 7.00679;
    satellite[7].radius = 7.0068;
    satellite[8].radius = 7.00682;
    */
    //一个循环  每个卫星每秒钟对应的x ，y读进来
    for(int i = 0; i < 9; i++)
    {
       ReadFile(i);
    }
    int start = 0;
    //将各城市的时间窗口计算出来,外循环遍历城市
    for(int i = 0; i < 19; i++)
    {
        bool flag = false;//记录城市是否被卫星星座覆盖
        //中间循环遍历时间
       for(int j = 0; j < 86400; j++)
       {
           //内层循环遍历卫星，时间复杂度较高。
           int number =0;//当前时间段未提供服务的卫星个数
           for(int k = 0; k < 9; k++)
           {
               //判断城市是否在该卫星的搜索范围内，看方程（x-x0）*（x-x0） + (y-y0)*(y-y0)是否小于等于radius
               //第i个城市的x-该卫星的x，即经度longitude，y即纬度latitude
               //第k个卫星在第j秒的数值
               if((culSquare(theCityList.city[i].longitude - satellite[k].x[j]) + culSquare(theCityList.city[i].latitude - satellite[k].y[j])) <= culSquare(radius))
               {
                   //如果该时间段处在星座范围内，且flag标记false,说明此时刻开始进入星座的范围
                   if(!flag)
                   {
                       start = j;//j就是当前时间
                       flag = true;//标记被覆盖
                   }
                   break;//退出当前卫星循环，因为只要有一个卫星提供就算星座在提供
               }
               //执行到这一步，说明此卫星没有提供服务，Number++
               number++;
               //若9个
              if(flag && number == 9)
              {
                  //此时不再星座内，但是flag却为true，说明有了一个时间窗口出现
                  //传入start，和结束时间j - 1
                  TimeSlot t(start, j - 1);
                  //把tpush给该城市的时间窗口VEctor
                  theCityList.city[i].slot.push_back(t);
                  //然后把flag置为false
                  flag = false;
              }
 
           }
       }
    }
 
    /*
    ifstream ifs1;
    ifs1.open("D:/vc/z/myEarth/us.txt");
    for(int i = 0; i < 3369; i++)
    {
        ifs1>>point[i].longitude>>point[i].latitude;
    }
    ifs1.close();
    */
}

3、最后

最后一篇文章我会把全部资源发到百度云，里面包含克莱姆法则的预处理、最重要的qt源程序本体、还有美国多边形的分割。如果你们现在弄的不是美国，也不要紧张，我会把这种类似问题的方法讲解的一清二楚。不过我看学长弄的是求区域时间间隙最小最大点啥的，用了粒子群优化算法那个，我怀疑你们应该搞的是别的。不过我还是会把这种某国、某区域多边形的分割方法放出来，万一你们今年搞的是什么英国、澳大利亚啥的呢hh。