Cell-Based Preprocessing Algorithm for Fast Satellite Coverage Calculation

Grid coverage calculations are a commonly used analysis tool for Earth-observation and communication satellite missions. A dynamic coverage calculation by a maneuverable satellite instrument over a wide pointing domain requires a fast coverage calculator. Given an arbitrary target grid of points on the Earth’s surface, the basic coverage calculation problem is to compute the access intervals of the satellite instrument with each point on the grid over the mission period. The access is computed using either the line of sight or a particular instrument field of view (FOV) geometry. Grid coverage calculations can be computationally intensive for high-resolution grids due to the large number of point containment queries needed to establish access. In this article, we introduce a preprocessing algorithm to accelerate grid coverage calculations. The target grid is first sorted into the cells of a preprocessing grid, which has equal latitude spacing and equal longitude spacing along a given latitude, with the longitude spacing increasing towards the poles to ensure roughly equal cell area. Due to the equal spacing property, the grid cells can be indexed directly using the bounding box of the instrument footprint on the Earth’s surface in latitude and longitude. Our method considers rectangular, conical, and spherical-polygon instrument profiles, which together can account for most practical instrument geometries. The preprocessing algorithm ensures that the number of point containment operations is proportional only to the average number of points inside the satellite footprint, rather than the total number of points in the target grid. This leads to dramatic runtime improvements, especially when the access area is only a small fraction of the Earth’s surface, as is typically the case for Earth-observation satellites. Results show 1-2 orders of magnitude improvement in runtime over the commonly used brute-force approach. We analyze the runtime performance with respect to the resolution of the preprocessing grid for various footprint sizes, and suggest a way to obtain the optimal resolution. To support the algorithm development, we also provide an overview of several geometric formulas for representing instrument profiles and projecting them onto the Earth’s surface using a spherical Earth model.

I. Introduction

Coverage analysis is an essential aspect of satellite mission design and operation. Broadly speaking, coverage analysis refers to the process of evaluating the spatial and/or temporal extent of a satellite instrument’s access to ground regions. The precise meaning of ‘access’ may depend on the nature of the analysis; in the most basic sense, it refers to geometric access (i.e., line-of-sight to the instrument), but it may also be understood more broadly in the context of mission constraints or objectives to refer to geometric access which also meets a required quality or capacity threshold. In a mission design context, coverage analysis can be used to evaluate fundamental performance parameters like percent coverage or revisit time, and aid in the calculation of expected observation data metrics such as signal to noise ratio or noise equivalent delta temperature [1]. It may also be used in active mission operations to support automated satellite planning and scheduling operations. For example, observational priorities may be dictated by numerical science models which operate on a dense spatial grid. The D-SHIELD (distributed spacecraft with heuristic intelligence to enable logistical decisions) project is a recent example of this approach [2]. The D-SHIELD science simulator module produces a dynamic observation value index over an approximately 2 million point grid which, together with access intervals generated by a coverage calculator module, serves as input to the planning and scheduling of satellite ground-station operations. Grids derived from science data products (e.g., the USGS Wildlands Fire Potential Index, available at a spatial resolution of 1km [3]) may often contain a number of points on the order of 1-10 million, motivating the need for a fast coverage computation solution.