{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T03:29:19Z","timestamp":1780543759729,"version":"3.54.1"},"reference-count":23,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T00:00:00Z","timestamp":1561075200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the National Key Research and Development Program of China","award":["(Grant Nos. 2018YFB0505300 and 2017YFB0503703)."],"award-info":[{"award-number":["(Grant Nos. 2018YFB0505300 and 2017YFB0503703)."]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["(Grant NO. 41801301)"],"award-info":[{"award-number":["(Grant NO. 41801301)"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Flight conflict detection is fundamental to flight dispatch, trajectory planning, and flight safety control. An ever-increasing aircraft population and higher speeds, particularly the emergence of hypersonic\/supersonic aircrafts, are challenging the timeliness and accuracy of flight conflict detection. Traditional trajectory conflict detection algorithms rely on traversing multivariate equations of every two trajectories, in order to yield the conflict result and involve extensive computation and high algorithmic complexity; these algorithms are often unable to provide the flight conflict solutions required quickly enough. In this paper, we present a novel, low-altitude flight conflict detection algorithm, based on the multi-level grid spatiotemporal index, that transforms the traditional trajectory-traversing multivariate conflict computation into a grid conflict state query of distributed grid databases. Essentially, this is a method of exchanging \"storage space\" for \"computational time\". First, we build the spatiotemporal subdivision and encoding model based on the airspace. The model describes the geometries of the trajectories, low-altitude obstacles, or dangerous fields and identifies the grid with grid codes. Next, we design a database table structure of the grid and create a grid database. Finally, we establish a multilevel grid spatiotemporal index, design a query optimization scheme, and examine the flight conflict detection results from the grid database. Experimental verification confirms that the computation efficiency of our algorithm is one order of magnitude higher than those of traditional methods. Our algorithm can perform real-time (dynamic\/static) conflict detection on both individual aircraft and aircraft flying in formation with more efficient trajectory planning and airspace utilization.<\/jats:p>","DOI":"10.3390\/ijgi8060289","type":"journal-article","created":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T11:54:31Z","timestamp":1561118071000},"page":"289","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["A Low-Altitude Flight Conflict Detection Algorithm Based on a Multilevel Grid Spatiotemporal Index"],"prefix":"10.3390","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5308-1551","authenticated-orcid":false,"given":"Shuangxi","family":"Miao","sequence":"first","affiliation":[{"name":"College of Engineering, Peking University, Beijing 100871, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chengqi","family":"Cheng","sequence":"additional","affiliation":[{"name":"College of Engineering, Peking University, Beijing 100871, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Weixin","family":"Zhai","sequence":"additional","affiliation":[{"name":"Academy for Advanced Interdisciplinary Studies, Peking University, Beijing 100871, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fuhu","family":"Ren","sequence":"additional","affiliation":[{"name":"Beijing Institute of Big Data Research, Beijing 100871, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bo","family":"Zhang","sequence":"additional","affiliation":[{"name":"Heilongjiang Institute of Geography Information Engineering, Harbin 150081, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuang","family":"Li","sequence":"additional","affiliation":[{"name":"Institute of Remote Sensing and GIS, Peking University, Beijing 100871, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Junxiao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Faculty of Geosciences and Environmental Engineering, Southwest Jiaotong University, Chengdu 611756, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huangchuang","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Engineering, Peking University, Beijing 100871, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,6,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Zhao, Y., and Wan, J. (2019). Analysis of development and evolution rules of civil aviation in China based on life cycle theory. PLoS ONE, 14.","DOI":"10.1371\/journal.pone.0212338"},{"key":"ref_2","first-page":"208","article-title":"Impact of GPS and ADS-B Reported Accuracy on Conflict Detection Performance in Dense Traffic","volume":"57","author":"Gariel","year":"2019","journal-title":"AIAA J."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1016\/j.trc.2008.12.002","article-title":"An ensemble approach for conflict detection in free flight by data mining","volume":"17","author":"Alam","year":"2009","journal-title":"Transp. Res. Part C"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1109\/TAES.2018.2867698","article-title":"Multiple Model Method for Aircraft Conflict Detection and Resolution in Intent and Weather Uncertainty","volume":"55","author":"Jilkov","year":"2019","journal-title":"IEEE Trans. Aerosp. Electron. Syst."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1231","DOI":"10.1109\/TVT.2018.2889459","article-title":"Improved Conflict Detection and Resolution for Service UAVs in Shared Airspace","volume":"68","author":"Ho","year":"2019","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"42846","DOI":"10.1109\/ACCESS.2019.2908028","article-title":"Distributed Conflict-Detection and Resolution Algorithms for Multiple UAVs Based on Key-Node Selection and Strategy Coordination","volume":"7","author":"Wan","year":"2019","journal-title":"IEEE Access"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0097-8493(91)90005-3","article-title":"A highly parallel architecture for real time collision detection in flight simulation","volume":"15","author":"Bickerstaff","year":"1991","journal-title":"Comput. Graph."},{"key":"ref_8","unstructured":"Chiang, Y.J., Klosowski, J.T., Lee, C., and Mitchel, J.S.B. (1997, January 12). Geometric Algorithms for Conflict Detection and Resolution in Air Traffic Management. Proceedings of the 36th IEEE Conference on Decision and Control, San Diego, CA, USA."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1017\/S0001924000027779","article-title":"Airspace design: Towards a rigorous specification of conflict complexity based on computational geometry","volume":"103","author":"Fulton","year":"2016","journal-title":"Aeronaut. J."},{"key":"ref_10","first-page":"446","article-title":"Delaunay method for free flight conflict detection","volume":"17","author":"Xing","year":"2002","journal-title":"J. Data Acquis. Process."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1145\/331524.331528","article-title":"Analysis of a bounding box heuristic for object intersection","volume":"46","author":"Zhou","year":"1999","journal-title":"J. Assoc. Comput. Mach."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1007\/978-3-540-45072-6_4","article-title":"Bkd-Tree: A Dynamic Scalable kd-Tree","volume":"Volume 2750","author":"Procopiuc","year":"2003","journal-title":"Proceedings of the International Symposium on Spatial and Temporal Databases"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1109\/6979.898224","article-title":"A probabilistic approach to aircraft conflict detection","volume":"1","author":"Prandini","year":"2000","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Jardin, M.R. (2005). Grid-Based Strategic Air Traffic Conflict Detection: AIAA-2005-5826, AIAA.","DOI":"10.2514\/6.2005-5826"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Hu, J., Prandini, M., and Sastry, S. (2003). Aircraft Conflict Detection in Presence of Spatially Correlated Wind Perturbations: AIAA-2003-5339, AIAA.","DOI":"10.2514\/6.2003-5339"},{"key":"ref_16","first-page":"16","article-title":"Central Place Indexing: Hierarchical Linear Indexing Systems for Mixed-Aperture Hexagonal Discrete Global Grid Systems","volume":"54","author":"Sahr","year":"2019","journal-title":"Cartogr. Int. J. Geogr. Inf. Geovis."},{"key":"ref_17","first-page":"1","article-title":"A SVM Approach of Aircraft Conflict Detection in Free Flight","volume":"9","author":"Jiang","year":"2018","journal-title":"J. Adv. Transp."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1559\/152304003100011090","article-title":"Geodesic discrete global grid systems","volume":"30","author":"Sahr","year":"2003","journal-title":"Cartogr. Geogr. Inf. Sci."},{"key":"ref_19","first-page":"29","article-title":"Modeling methods and basic problems of discrete global grids","volume":"28","author":"Zhao","year":"2012","journal-title":"Geogr. Geo-Inf. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Cheng, C., Tong, X., Chen, B., and Zhai, W. (2016). A Subdivision Method to Unify the Existing Latitude and Longitude Grids. ISPRS Int. J. Geo-Inf., 5.","DOI":"10.3390\/ijgi5090161"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Sun, Z.Q., and Cheng, C.Q. (2015, January 19\u201321). 3D integrated representation model and visualization based on the global discrete voxel\u2014GeoSOT3D. Proceedings of the 23rd International Conference on Geoinformatics, Wuhan, China.","DOI":"10.1109\/GEOINFORMATICS.2015.7378564"},{"key":"ref_22","unstructured":"Longley, P. (2005). Geographic Information Systems and Science, John Wiley & Sons Inc."},{"key":"ref_23","unstructured":"Ben, J. (2010, January 22\u201323). An Effective Search Scheme for Gnutella-Like P2P Networks. Proceedings of the 2nd International Workshop on Intelligent Systems and Applications, Wuhan, China."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/8\/6\/289\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:00:27Z","timestamp":1760187627000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/8\/6\/289"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,21]]},"references-count":23,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2019,6]]}},"alternative-id":["ijgi8060289"],"URL":"https:\/\/doi.org\/10.3390\/ijgi8060289","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,21]]}}}