بهبود ترمیم خودکار چندضلعیهای مسطح در سیستمهای اطلاعات جغرافیایی

نوع مقاله : علمی - پژوهشی

نویسندگان

1 استادیار دانشگاه خوارزمی، دانشکده علوم ریاضی وکامپیوتر،گروه علوم کامپیوتر، تهران، ایران

2 کارشناس ارشد مهندسی کامپیوتر(نرم افزار)، مؤسسه آموزش عالی علمی کاربردی جهادکشاورزی، سازمان تحقیقات، آموزش و ترویج کشاورزی، تهران، ایران

چکیده

ترمیم چندضلعی­های نادرست برای استفاده در نرم­افزارهای سیستم اطلاعات جغرافیایی، کاری نیمه خودکار و وقت­گیر است. ترمیم خودکار چند ضلعی، تفسیر چند ضلعی­های مبهم و نادرست و از بین بردن کلیه اشکالات موجود براساس تعریف­ها و استاندارهای جهانی است که کاربردهای زیادی در نرم افزارهای مرتبط با سیستم اطلاعات جغرافیایی دارد. با توجه به پیچیدگی محاسبات و حجم داده­ها در کار با مه داده­ها ، همیشه رقابتی بین سرعت و میزان حافظه مصرفی وجود دارد. در این مقاله ضمن معرفی استاندارد مشخصات عوارض ساده در چندضلعی ها، با استفاده از مثلث­بندی دلونی و توابع جی.تی.اس در جاوا و با کمک بانک اطلاعات  H2روشی ارائه شده است که چندضلعی­ها را در قالب یک فایل CSV از ورودی دریافت کرده و با اعمال الگوریتم­های کارا چندضلعی های موجود را بررسی و به شکل خودکار ترمیم می­کنیم. چندضلعی­های موجود در مجموعه داده­های مکانی به شکل خودکار و در زمانی بهینه و با مصرف حداقل حافظه بررسی و در صورت نیاز ترمیم می شوند. نتایج نشان می­دهد این روش نسبت به نمونه های پیشین، باعث بهبود نسبی در سرعت اجرا و در هنگام کار با داده های بزرگ صرفه­جویی متوسط بیش از 50 درصد در حافظه اصلی را نشان می­دهد

عنوان مقاله [English]

Improved Automatic Polygonal Restoration in Geographic Information Systems

نویسندگان [English]

  • K Borna 1
  • F Fathi 2
1 Assistant Prof. of Kharazmi University, Faculty of Mathematics and Computer Science, Dep. of Computer Science, Tehran
2 M.Sc. of Computer Engineering (Software), Institute of Technical and Vocational Higher Education, Agriculture Jihad, Agricultural Research, Education and Extension Organization (AREEO), Tehran
چکیده [English]

Repairing incorrect polygons for use in GIS software is semi-automated and time-consuming.Automatic polygon repair, interpretation of obscure polygons, and elimination of all existing bugsbased on definitions and global standards that have many uses in software related to GIS. Due to thecomplexity of the computation and data volumes in working with big data, there is always acompetition between the speed and the amount of memory used. In this paper, while introducing thestandard of the characteristics of simple complications in polygons, using Delaunay Triangulation andGTS functions in Java and with the help of the H2 database, a method is presented that receivespolygons in the form of a file in the CSV format and applies several effective algorithms toautomatically repair them. The polygons in the spatial data set are automated at optimal time and withminimal memory consumption and are repaired if necessary. The results show that this method,compared with the previous ones, our method leads to relative improvement in execution speed andprovides more than 50 percent saving (in average) in the main memory while working with big data.

کلیدواژه‌ها [English]

  • Delaunay triangulation
  • Repair polygon
  • Spatial database
  • GIS
  1. Blandford, D.K., Blelloch, G.E., Cardoze, D.E. & Kadow, C., 2005, Compact Representationsof Simplicial Meshes in Two and Three Dimensions, International Journalof Computational Geometry and Applications, 15(1), PP. 3–24.
  2. Bolstad, P.V. & Smith, J.L., 1992, Errors in GIS: Assessing Spatial Data Accuracy, Journal of Forestry, 90, 11 (1992), PP. 21–29.
  3. Cho, S., Xavier Punithan, M., Gim, J. & Huhd, Y., 2014, Tagging-the-Triangle Algorithm for Partitioning Features with Inconsistent Boundaries, International Journal of Geographical Information Science, Vol. 28, No. 12, PP. 2533–2550, http://dx.doi.org/10.1080/13658816.2014.937716.
  4. Deng, M., Chen, Xi., Lia, W., Kusanagi, M., N. Phien, H., 2003, Modelling Error Propagation for Spatial Consistency, Journal of Geospatial Engineering, 5 (2), PP. 51–60.
  5. Fu, Z., Liu, S., Tian, Z. & Xu, H., 2012, Distributed Spatial Index Based on Multilevel R-Tree, Bull. Surv. Mapp., 11, PP. 42–46.
  6. Isenburg, M., Liu, Y., Shewchuk, J.R. & Snoeyink, J., 2006, Streaming Computation of Delaunay Triangulations, ACM Transactions on Graphics, 25(3), PP. 1049–1056.
  7. ISO, 2003, ISO/TC 211/WG 2, ISO/CD 19107, Geographic information — Spatial schema.
  8. JTS, Java Topology Suite, http://tsusiatsoftware. net/jts/main.html.
  9. Ledoux, A. & Ohori, K.A., 2017, Solving the Horizontal Conflation Problem with a Constrained Delaunay Triangulation, Journal of Geographical Systems, Vol. 19, Issue 1, PP. 21–42
  10. Ledoux, H.,Ohori, K.A. & Meijers, M., 2014, A Triangulation-Based Approach to Automatically Repair GIS Polygon, Computer & Geosciences, Vol. 66, Issue C, PP. 121–131
  11. Li, X. & Zheng, W., 2013, Parallel Spatial Index Algorithm Based on Hilbert Partition, Proceedings of the 5th International Conference on Computational and Information Sciences (ICCIS), PP. 876–879.
  12. OGC, 1999, Open GIS Consortium, Inc., Open GIS Simple Features Specification For SQL, Revision 1.1, Open GIS Project Document, 99-049, 5 May 1999.
  13. OGC, 2011, OpenGIS® Implementation Standard for Geographic information - Simple feature access - Part 1: Common architecture.
  14. Ohori, K.A., Ledoux, H. & Meijers, M., 2012, Validation and Automatic Repair of Planar Partitions Using Aconstrained Triangulation, Photogramm. Fernerkund. Geoinf., 1(October(5)), PP. 613–630.
  15. Ohori, A., 2010, Validation and automatic Repair of Palanar Partitions Using a Constrained Triangulation, M, Sc in Geomatics, Pelft University of Technology in Helsinki.
  16. Oosterom, p., Quak, W. & Tijssen, T., 2005, About Invalid, Valid and Clean Polygons, Developments in Spatial Data Handling, PP. 1–16.
  17. Preparata, F.P. & Shamos, M.I., 1985, Computational Geometry, an Introduction, Springer-Verlag, New York Berlin Heidelberg Tokyo.
  18. Rodriguez, M.A., Bertossi, L.E. & Caniupan, M., 2013, Consistent Query Answering under Spatial Semantic Constraints, Information Systems, 38 (2), PP. 244–263.
  19. Rodriguez, M.A., Brisaboa, N., Meza, J. & Luaces, M.R., 2010, Measuring Consistency with Respect to Topological Dependency Constraints, In: Proceedings of the 18th SIGSPATIAL international conference on advances in geographic information systems (GIS’10), San Jose, CA. New York: ACM, PP. 182–191.
  20. Servigne, S., Ubeda, T., Puricelli, A. & Laurini, R., 2000, A Methodology for Spatial Consistency Improvement of Geographic Databases, GeoInformatica, 4 (1), PP. 7–34.
  21. Wang, Y., Liu, Z., Liao, H. & Li, C., 2015, Improving the Performance of GIS Polygon Overlay Computation with MapReduce for Spatial Big Dada Processing, Cluster Computing, Vol. 18, Issue 2, PP. 507–516.
  22. Xie, Z., Tian, G., Wu, L. & Xia, L., 2010, A Framework for Correcting Geographical Boundary Inconsistency, In: The 18th international conference on geoinformatics: GIScience in change, geoinformatics 2010, 18–20 June, Peking University, Beijing. IEEE, 1–5.
  23. Yvinec, M., 2010, 2D Triangulations, in ‘CGAL User and Reference Manual, 3.6 edn, CGAL Editorial Board.
  24. Zlatanova, S. & Stoter, J., 2006, The Role of DBMS in the New Generation GIS Architecture, Frontiers of Geographic Information Technology, Springer, Chapter 8, PP. 155–180.