Simulação de Monte Carlo em redes triangulares irregulares / Monte Carlo simulation in triangular irregular networks

Alex de Lima Teodoro da Penha, Vagner Braga Nunes Coelho

Abstract


As Redes Triangulares Irregulares (TINs) são uma das formas mais utilizadas para representar topologia de superfície quando se trabalha com Modelos Digitais de Terreno (DTM) ou Sistemas de Informação Geográfica (GIS). Dada esta forma de representação, este artigo investiga uma demonstração probabilística para quantificar como a precisão de cada ponto ? (sigma) pode ser considerada ambígua, do ponto de vista topológico, em qualquer nova Triangulação Delaunay 2D. Para o conseguir, esta investigação concebeu uma demonstração inicial de que, existe uma precisão máxima para a qual a topologia da rede permanece constante numa nova Triangulação Delaunay, em cada ponto e no TIN como um todo. A abordagem metodológica foi experimental, com várias experiências matemáticas realizadas utilizando o método de Simulação de Monte Carlo. Primeiro, para cada ponto da rede, e depois, para todos os pontos da rede, para variados ?. As experiências culminaram em ajudar a resolver o problema da existência do máximo ? para o qual a probabilidade de ocorrência em topologia de NIF constante é de 100%. Os resultados matemáticos deram origem à seguinte afirmação: Considerando um NIF gerado pela Triangulação Delaunay, se algum ponto de coordenadas (x_i,y_i ) numa Rede Triangular Irregular for perturbado (ou seja, tem o seu lugar alterado), de acordo com uma distribuição Normal N(?,?^2 ), então, existe um valor ?_max (sigma máximo) para o qual a topologia da rede permanece constante. Por exemplo, verificou-se que ?_(max.1) de um ponto existe e é obtido por ?_(max.1)=0.30866, e noutro ponto, ?_(max.2)=0.2. Os resultados indicam também o seguinte para o TIN: Cada Rede Triangular Irregular bidimensional gerada pela Triangulação Delaunay tem um valor ?_* (sigma asterisco) para o qual a topologia da rede permanece constante. Neste trabalho, simulando o pior caso de uma Rede Triangular Irregular: ?_*=0,2. Finalmente, conclui-se que existe o máximo de ? para cada ponto, bem como para a rede como um todo. No entanto, os resultados precisam de ser testados em redes mais extensas para provar (ou não) se isso sempre aconteceu. Esta investigação faz avançar os conhecimentos sobre o TIN combinando técnicas de simulação e topologia de rede.


Keywords


Redes Triangulares Irregulares, Simulação de Monte Carlo, Topologia, TIN, Triangulação de Delaunay, Triangular Irregular Network, Monte Carlo Simulation, Topology, Delaunay Triangulation.

References


Amar, J. G.: The Monte Carlo method in science and engineering, Comput. Sci. Eng., 8 (2), 9–19, doi:10.1109/MCSE.2006.34, 2006.

Casanova, M., Câmara, G., Davis, C., Vinhas, L. e Queiroz, G. R. de: Bancos de Dados Geográficos, MundoGEO, Curitiba., 2005.

Carmel, Y., Paz, S., Jahashan, F., Shoshany, M., 2009. Assessing fire risk using Monte Carlo simulations of fire spread. For. Ecol. Manag. 257, 370–377. https://doi.org/10.1016/j.foreco.2008.09.039

Cheng, X., Thaeler, A., Xue, G., Chen, D., 2004. TPS: A time-based positioning scheme for outdoor wireless sensor networks. Presented at the Proceedings - IEEE INFOCOM, pp. 2685–2696. https://doi.org/10.1109/INFCOM.2004.1354687

Florinsky, I.V., 2002. Errors of signal processing in digital terrain modelling. Int. J. Geogr. Inf. Sci. 16, 475–501. https://doi.org/10.1080/13658810210129139

Gosciewski, D., 2013. Selection of interpolation parameters depending on the location of measurement points. GIScience Remote Sens. 50, 515–526. https://doi.org/10.1080/15481603.2013.827369

Gugiu, D., Dumitrache, I., 2005. Monte Carlo estimation of the dose and heating of cobalt adjuster rods irradiated in the CANDU 6 reactor core. Radiat. Prot. Dosimetry 116, 69–72. https://doi.org/10.1093/rpd/nci270

Hamid, H.M., Al-Azawi, F.W., Abbas, Z.D., Hassan, S.T., Makki, Z.F., 2019. Producing a geographical information system (GIS) model for the preliminary location of groundwater wells for the regions of al Najaf government. Plant Arch. 19, 3515–3521.

Hegeman, J.W., Sardeshmukh, V.B., Sugumaran, R., Armstrong, M.P., 2014. Distributed LiDAR data processing in a high-memory cloud-computing environment. Ann. GIS 20, 255–264. https://doi.org/10.1080/19475683.2014.923046

Kalyanam, R., Zhao, L., Song, C., Biehl, L., Kearney, D., Kim, I.L., Shin, J., Villoria, N., Merwade, V., 2019. MyGeoHub—A sustainable and evolving geospatial science gateway. Future Gener. Comput. Syst. 94, 820–832. https://doi.org/10.1016/j.future.2018.02.005

Kamel Boulos, M.N., Geraghty, E.M., 2020. Geographical tracking and mapping of coronavirus disease COVID-19/severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) epidemic and associated events around the world: How 21st century GIS technologies are supporting the global fight against outbreaks and epidemics. Int. J. Health Geogr. 19. https://doi.org/10.1186/s12942-020-00202-8

Kastrisios, C., Tsoulos, L., 2018. Voronoi tessellation on the ellipsoidal earth for vector data. Int. J. Geogr. Inf. Sci. 32, 1541–1557. https://doi.org/10.1080/13658816.2018.1434890

Kim, J.O., Yu, K., Heo, J., Lee, W.H., 2010. A new method for matching objects in two different geospatial datasets based on the geographic context. Comput. Geosci. 36, 1115–1122. https://doi.org/10.1016/j.cageo.2010.04.003

Li, R., Archinal, B.A., Arvidson, R.E., Bell, J., Christensen, P., Crumpler, L., Des Marais, D.J., Di, K., Duxbury, T., Golombek, M.P., Grant, J.A., Greeley, R., Guinn, J., Johnson, A., Kirk, R.L., Maimone, M., Matthies, L.H., Malin, M., Parker, T., Sims, M., Thompson, S., Squyres, S.W., Soderblom, L.A., 2006. Spirit rover localization and topographic mapping at the landing site of Gusev crater, Mars. J. Geophys. Res. E Planets 111. https://doi.org/10.1029/2005JE002483

Liu, Z.-P., Yang, B., Liu, J., He, H.-J., 2017. Three-dimensional limit equilibrium method based on GRASS GIS and TIN sliding surface. Yantu LixueRock Soil Mech. 38, 221–228. https://doi.org/10.16285/j.rsm.2017.01.028

Martínez, D., Velho, L., Carvalho, P.C., 2005. Computing geodesics on triangular meshes. Comput. Graph. Pergamon 29, 667–675. https://doi.org/10.1016/j.cag.2005.08.003

Mazuelas, S., Bahillo, A., Lorenzo, R.M., Fernandez, P., Lago, F.A., Garcia, E., Blas, J., Abril, E.J., 2009. Robust Indoor Positioning Provided by Real-Time RSSI Values in Unmodified WLAN Networks. IEEE J. Sel. Top. Signal Process. 3, 821–831. https://doi.org/10.1109/JSTSP.2009.2029191

Merlemis, N., Kesidis, A.L., Sianoudis, I., 2021. Measurement of laser beam spatial profile by laser scanning. Eur. J. Phys. 42. https://doi.org/10.1088/1361-6404/abba01

Mollalo, A., Vahedi, B., Rivera, K.M., 2020. GIS-based spatial modeling of COVID-19 incidence rate in the continental United States. Sci. Total Environ. 728. https://doi.org/10.1016/j.scitotenv.2020.138884

Reuter, H.I., Nelson, A., Jarvis, A., 2007. An evaluation of void?filling interpolation methods for SRTM data. Int. J. Geogr. Inf. Sci. 21, 983–1008. https://doi.org/10.1080/13658810601169899

Sharp, N., Soliman, Y., Crane, K., 2019. Navigating intrinsic triangulations. ACM Trans. Graph. 38. https://doi.org/10.1145/3306346.3322979

Sikka, G., Yenneti, K., Singh, R.B., 2021. IGU-YECG special issue: Geospatiality and sustainable development goals. Geogr. Environ. Sustain. 14, 6–8.

Wal?dzik, K., Ma?dziuk, J., 2018. Applying hybrid Monte Carlo Tree Search methods to Risk-Aware Project Scheduling Problem. Inf. Sci. 460–461, 450–468. https://doi.org/10.1016/j.ins.2017.08.049

Wang, Y., Peterson, B.S., Staib, L.H., 2000. Shape-based 3D surface correspondence using geodesics and local geometry. Presented at the Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 644–651.

Erciyes, K.: Distributed Graph Algorithms for Computer Networks, Springer-Verlag London, London, 2013.

Felgueiras, C.; Goodchild, M. F.: Two papers on triangulated surface modeling: Technical Report 95-2, National Center for Geographic Information and Analysis - NCGIA, University of California, Santa Barbara, CA, USA. [online] Available from: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.6645 (Accessed 26 November 2013), 1995.

Fernandes, M. do C.; Menezes, P. M. L. de: Comparação Entre Métodos Para Geração de MDE Para a Obtenção de Observações em Superfície Real no Maciço da Tijuca - RJ, Rev. Bras. Cartogr., 57(02), 154–161, 2005.

Goodchild, M. F. Attribute accuracy. In: Guptill, S.C. and Morrison, J.L. (eds.), Elements of Spatial Data Quality. Amsterdam: Elsevier, pp. 59–79, 1995.

Mark, S. and Mordechai, S.: Applications of Monte Carlo Method in Science and Engineering, InTech, Rijeka, Croatia. [online] Available from: www.intechopen.com, 2011.

Marsaglia, G. and Tsang, W. W.: The Ziggurat Method for Generating Random Variables, J. Stat. Softw., 5(8), 1–7 [online] Available from: http://www.jstatsoft.org/v05/i08/, 2000.

Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N. and Teller, A. H.: Equation of State Calculations by Fast Computing Machines, J. Chem. Phys., 21(6), 1087–1092, 1953.

Tsai V. J. D. 1993, Delaunay triangulations in TIN creations: an overview and a linear-time algorithm. International Journal of Geographical Information Systems, 7, 501-524.

Zeiler, M.: Modeling Our World: The ESRI Guide to Geodatabase Design, Environmental Systems Research Institute, Inc., Redlands, California, EUA, 1999.




DOI: https://doi.org/10.34117/bjdv7n10-277

Refbacks

  • There are currently no refbacks.