{"id":365131,"date":"2024-05-21T02:31:33","date_gmt":"2024-05-21T02:31:33","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=365131"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=365131","title":{"rendered":"<span>\u041c\u0435\u0442\u043e\u0434 \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u043c\u0430\u0440\u0448\u0430 (Fast Marching Method)<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<h2>\u0412\u0441\u0442\u0443\u043f\u043b\u0435\u043d\u0438\u0435<\/h2>\n<p>\u041c\u0435\u0442\u043e\u0434 \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u043c\u0430\u0440\u0448\u0430 (Fast Marching Method)  \u0431\u044b\u043b \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d \u0414\u0436\u0435\u0439\u043c\u0441\u043e\u043c \u0421\u0435\u0442\u0438\u0430\u043d\u043e\u043c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043a\u0440\u0430\u0435\u0432\u044b\u0445 \u0437\u0430\u0434\u0430\u0447 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u042d\u0439\u043a\u043e\u043d\u0430\u043b\u0430.<\/p>\n<p>\u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u0440\u0430\u0441\u0447\u0451\u0442\u0430 \u043f\u043e\u043b\u0435\u0439 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 (Distance Field) \u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438. \u0417\u0430\u0434\u0430\u0447\u0430 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438 &#8212; \u043e\u0431\u044a\u044f\u0441\u043d\u0438\u0442\u044c \u043f\u0440\u0438\u043d\u0446\u0438\u043f \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u0443\u044e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e. \u0414\u043b\u044f \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u0433\u043e \u0447\u0442\u0435\u043d\u0438\u044f, \u0432 \u043a\u043e\u043d\u0446\u0435 \u0441\u0442\u0430\u0442\u044c\u0438 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u044b \u0441\u0441\u044b\u043b\u043a\u0438 \u043d\u0430 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0438.<\/p>\n<h2>\u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 FMM<\/h2>\n<p>\u041e\u0431\u044b\u0447\u043d\u043e \u0432 \u0441\u0442\u0430\u0442\u044c\u044f\u0445 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u044e\u0442 \u044d\u0442\u043e\u0442 \u043c\u0435\u0442\u043e\u0434 \u043a\u0430\u043a &#171;\u043c\u0430\u0441\u043b\u044f\u043d\u043e\u0435 \u043f\u044f\u0442\u043d\u043e&#187; \u0440\u0430\u0441\u0442\u0435\u043a\u0430\u044e\u0449\u0435\u0435\u0441\u044f \u043f\u043e \u043f\u043e\u0432\u0435\u0440\u0445\u043d\u043e\u0441\u0442\u0438. \u041d\u0430 \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u043d \u043f\u0440\u0438\u043c\u0435\u0440 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0432\u043e\u043b\u043d\u044b \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/lz\/rt\/71\/lzrt71jxz7twv3ta9czqvxgyc6i.png\" alt=\"\u0420\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0432\u043e\u043b\u043d \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435.\" title=\"\u0420\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0432\u043e\u043b\u043d \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435.\" width=\"600\" height=\"600\" data-src=\"https:\/\/habrastorage.org\/webt\/lz\/rt\/71\/lzrt71jxz7twv3ta9czqvxgyc6i.png\"\/><\/p>\n<div><figcaption>\u0420\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0432\u043e\u043b\u043d \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435.<\/figcaption><\/div>\n<\/figure>\n<p>\u041c\u0430\u0441\u043b\u043e \u0440\u0430\u0441\u0442\u0435\u043a\u0430\u0435\u0442\u0441\u044f \u043f\u043e \u043f\u043e\u0432\u0435\u0440\u0445\u043d\u043e\u0441\u0442\u0438 \u0441 \u0440\u0430\u0437\u043d\u043e\u0439 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c\u044e, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"F(\\vec{x})\" alt=\"F(\\vec{x})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d92\/c5b\/fef\/d92c5bfefb40f4e21f13fdd5a663f023.svg\" width=\"40\" height=\"22\"\/>.\u041f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e <img class=\"formula inline\" source=\"F(\\vec{x}) > 0&#8243; alt=&#187;F(\\vec{x}) > 0&#8243; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5d9\/cc0\/ee6\/5d9cc0ee61b64557b956fff861de423b.svg&#187; width=&#187;76&#8243; height=&#187;22&#8243;\/> \u0432\u0441\u044e\u0434\u0443 \u043a\u0440\u043e\u043c\u0435 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438. \u0415\u0441\u043b\u0438 \u044d\u0442\u043e \u043d\u0435 \u0442\u0430\u043a, \u0442\u043e \u0434\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043d\u0435\u043b\u044c\u0437\u044f. \u0415\u0441\u043b\u0438 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u0430, \u0442\u043e \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u042d\u0439\u043a\u043e\u043d\u0430\u043b\u0430 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0435\u0442 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439. \u0414\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u0432\u0440\u0435\u043c\u044f <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"T _ {i,j}\" alt=\"T _ {i,j}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ef1\/e6a\/444\/ef1e6a444ccbb6def9ec709f002e0aa7.svg\" width=\"27\" height=\"22\"\/>\u043f\u0440\u0438\u0431\u044b\u0442\u0438\u044f \u0432 \u0442\u043e\u0447\u043a\u0443. \u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c FMM \u0434\u043b\u044f \u0434\u0432\u0443\u0445\u043c\u0435\u0440\u043d\u043e\u0433\u043e \u0441\u043b\u0443\u0447\u0430\u044f, \u043d\u043e \u043c\u0435\u0442\u043e\u0434 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0438 \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0435\u0439.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"||\\nabla u(x)||=F(x), \\ x\\in \\Omega \\ \\ \u0423\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435\\ \\ \u042d\u0439\u043a\u043e\u043d\u0430\u043b\u0430. \\\\ u|_{\\partial \\Omega}=0; \\ \\ \\\\\\Omega \\ \\ \u0435\u0441\u0442\u044c \\ \\ \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \\ \\  \u0432\\ \\  \\mathbb{R}^n.\" alt=\"||\\nabla u(x)||=F(x), \\ x\\in \\Omega \\ \\ \u0423\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435\\ \\ \u042d\u0439\u043a\u043e\u043d\u0430\u043b\u0430. \\\\ u|_{\\partial \\Omega}=0; \\ \\ \\\\\\Omega \\ \\ \u0435\u0441\u0442\u044c \\ \\ \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \\ \\  \u0432\\ \\  \\mathbb{R}^n.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ffc\/2a3\/634\/ffc2a363404d735525a72ae250087221.svg\" width=\"697\" height=\"82\"\/><\/p>\n<p>\u0413\u0440\u0430\u0434\u0438\u0435\u043d\u0442(\u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u0432\u0440\u0435\u043c\u0435\u043d\u0438) \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u0435\u0432\u043a\u043b\u0438\u0434\u043e\u0432\u0430 \u043d\u043e\u0440\u043c\u0430:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"||\\nabla T||=1\/F\" alt=\"||\\nabla T||=1\/F\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c44\/e3f\/890\/c44e3f8908d15e38e70b7ee4a2737d89.svg\" width=\"111\" height=\"22\"\/><\/p>\n<p>\u0414\u043b\u044f \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0442\u044c \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0432 \u043d\u0430\u0431\u043e\u0440 \u0443\u0437\u043b\u043e\u0432, \u0433\u0434\u0435 \u043a\u0430\u0436\u0434\u044b\u0439 \u043f\u0438\u043a\u0441\u0435\u043b\u044c \u044d\u0442\u043e \u0443\u0437\u0435\u043b. \u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0442\u044c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"T _ {i,j}\" alt=\"T _ {i,j}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/734\/99a\/63f\/73499a63f8e414e6114e64f8e2533ed7.svg\" width=\"27\" height=\"22\"\/> \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u0443\u0437\u043b\u043e\u0432. \u0411\u0443\u0434\u0435\u043c \u0431\u0440\u0430\u0442\u044c \u0443\u0437\u0435\u043b \u0441\u043f\u0440\u0430\u0432\u0430, \u0441\u043b\u0435\u0432\u0430, \u0441\u0432\u0435\u0440\u0445\u0443 \u0438 \u0441\u043d\u0438\u0437\u0443. \u0414\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b, \u0443\u0437\u043b\u044b \u0438\u043c\u0435\u044e\u0442 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u044f \u0447\u0430\u0441\u0442\u0435\u0439 \u0441\u0432\u0435\u0442\u0430.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/tr\/wa\/2s\/trwa2s1ia_ysf8oib2-v_o4wzmy.png\" alt=\"\u0421\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0443\u0437\u043b\u044b. \u0417\u0430\u043a\u0440\u0430\u0448\u0435\u043d \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b.\" title=\"\u0421\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0443\u0437\u043b\u044b. \u0417\u0430\u043a\u0440\u0430\u0448\u0435\u043d \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b.\" width=\"600\" height=\"600\" data-src=\"https:\/\/habrastorage.org\/webt\/tr\/wa\/2s\/trwa2s1ia_ysf8oib2-v_o4wzmy.png\"\/><\/p>\n<div><figcaption>\u0421\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0443\u0437\u043b\u044b. \u0417\u0430\u043a\u0440\u0430\u0448\u0435\u043d \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b.<\/figcaption><\/div>\n<\/figure>\n<p>\u0417\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0437\u0430\u0434\u0430\u0451\u0442\u0441\u044f \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435\u043c:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(1)\\ \\ ||\\nabla T||^2 = [max(V _{a} - V _{b},V _{a} - V _{c},0)^2 + max(V _{a} - V _{d},V _{a} - V _{e},0)^2]\" alt=\"(1)\\ \\ ||\\nabla T||^2 = [max(V _{a} - V _{b},V _{a} - V _{c},0)^2 + max(V _{a} - V _{d},V _{a} - V _{e},0)^2]\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/53f\/b34\/a97\/53fb34a97734294284f33e8f208c9982.svg\" width=\"585\" height=\"26\"\/><\/p>\n<p>\u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0441\u0430\u043c\u043e\u0435 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438\u0437 \u0434\u0432\u0443\u0445:<\/p>\n<p><img class=\"formula\" source=\"V _{b} &lt; V _{c} \\ \\ =>  \\ \\ V _{a} &#8212; V _{b} > V _{a} &#8212; V _{c}&#187; alt=&#187;V _{b} &lt; V _{c} \\ \\ =>  \\ \\ V _{a} &#8212; V _{b} > V _{a} &#8212; V _{c}&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/af2\/3f5\/458\/af23f5458e9fe1073f258b069c31ac97.svg&#187; width=&#187;276&#8243; height=&#187;20&#8243;\/><\/p>\n<p>\u0420\u0430\u0441\u043f\u0438\u0448\u0435\u043c \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435, \u0437\u0430\u043c\u0435\u043d\u044f\u044f \u0443\u0441\u043b\u043e\u0432\u043d\u044b\u0435 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"[max(T _{i,j} - T _{i-1,j},T _{i,j} - T _{i+1,j},0)^2 + max(T _{i,j} - T _{i,j-1},T _{i,j} - T _{i,j+1},0)^2]^{\\frac{1}{2}}={\\frac1{F_{i,j}}}\" alt=\"[max(T _{i,j} - T _{i-1,j},T _{i,j} - T _{i+1,j},0)^2 + max(T _{i,j} - T _{i,j-1},T _{i,j} - T _{i,j+1},0)^2]^{\\frac{1}{2}}={\\frac1{F_{i,j}}}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/403\/2bd\/641\/4032bd641267cc1e976ce6b72b6587ed.svg\" width=\"669\" height=\"47\"\/><\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u0441\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044e \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u043e\u0433\u043e \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f, \u0433\u0434\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"T _ {i,j}\" alt=\"T _ {i,j}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ebf\/938\/5cf\/ebf9385cfe6c64066682abb4e874796e.svg\" width=\"27\" height=\"22\"\/>&#8212; \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430. \u0414\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0435\u0442\u043e\u0434 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0439 \u0432 \u0440\u0430\u0431\u043e\u0442\u0435 R. Kimmel and J.A. Sethian (1996):<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(2) \\ \\ a = min(T _ {i - 1, j}, T _ {i + 1, j}), \\ \\ b = min(T _ {i, j - 1} ,T _ {i, j + 1})\" alt=\"(2) \\ \\ a = min(T _ {i - 1, j}, T _ {i + 1, j}), \\ \\ b = min(T _ {i, j - 1} ,T _ {i, j + 1})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/19d\/c8f\/448\/19dc8f4481fadecc959222e4c502ce9b.svg\" width=\"419\" height=\"23\"\/><img class=\"formula\" source=\"IF \\ \\ \\frac1{F _ {i,j}} > |a-b|,\\ \\ then \\ \\ T_{i,j} = \\frac{a+b+\\sqrt{2 * (\\frac1{F_{i,j}})^2 &#8212; (a-b)^2}}{2}&#187; alt=&#187;IF \\ \\ \\frac1{F _ {i,j}} > |a-b|,\\ \\ then \\ \\ T_{i,j} = \\frac{a+b+\\sqrt{2 * (\\frac1{F_{i,j}})^2 &#8212; (a-b)^2}}{2}&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5f8\/798\/680\/5f87986801a0e5b36ff7ad4d342c768d.svg&#187; width=&#187;527&#8243; height=&#187;66&#8243;\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"Otherwise\\ \\  T_{i,j}=(\\frac{1}{F_{i,j}})^2+min(a,b)\" alt=\"Otherwise\\ \\  T_{i,j}=(\\frac{1}{F_{i,j}})^2+min(a,b)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/082\/c87\/21f\/082c8721f9dd10df43d591e129587892.svg\" width=\"312\" height=\"47\"\/><\/p>\n<p>\u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u0432\u044b\u0431\u0438\u0440\u0430\u044f \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u043e \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u0440\u043e\u0439\u0434\u0451\u0442 \u0432\u0441\u0435 \u0443\u0437\u043b\u044b.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/1ad\/69e\/461\/1ad69e46149fd46bc4a6431b33799881.png\" alt=\"\u0420\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432 \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435.\" title=\"\u0420\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432 \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435.\" width=\"1000\" height=\"1000\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1ad\/69e\/461\/1ad69e46149fd46bc4a6431b33799881.png\"\/><\/p>\n<div><figcaption>\u0420\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432 \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435.<\/figcaption><\/div>\n<\/figure>\n<h2>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 FMM<\/h2>\n<p>\u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043d\u0430\u0431\u043e\u0440 \u0443\u0437\u043b\u043e\u0432 \u0434\u043b\u044f \u0440\u0430\u0441\u0447\u0451\u0442\u0430 \u043f\u043e\u043b\u0435\u0439 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439. \u041c\u043e\u0436\u043d\u043e \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438\u0445, \u0430 \u043c\u043e\u0436\u043d\u043e \u0432\u0437\u044f\u0442\u044c \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0438 \u043a\u043e\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0435\u0433\u043e \u0432 \u043d\u0430\u0431\u043e\u0440 \u0443\u0437\u043b\u043e\u0432.<\/p>\n<p>\u0412\u043e\u0442 \u043f\u0440\u0438\u043c\u0435\u0440 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b Node. \u0412\u0435\u0441\u044c \u043a\u043e\u0434 \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d \u043d\u0430 C#.<\/p>\n<pre><code class=\"cs\">public enum StateNode {     KNOWN,     NEIGHBOUR,     FAR,     BLOCK,     WAY }  public struct Node {     public int x;     public int y;     public StateNode state;     public double distance; }<\/code><\/pre>\n<p>KNOWN \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u043f\u043e\u043c\u0435\u0447\u0430\u0442\u044c \u0443\u0436\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0435 \u0443\u0437\u043b\u044b,<br \/>NEIGHBOUR &#8212; \u0441\u043e\u0441\u0435\u0434\u0438 \u0443\u0436\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432,<br \/>FAR &#8212; \u043d\u0435 \u043f\u043e\u0441\u0435\u0449\u0451\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b,<br \/>BLOCK &#8212; \u043f\u0440\u0435\u043f\u044f\u0442\u0441\u0442\u0432\u0438\u0435(\u0443\u0437\u0435\u043b, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043a\u0430\u043a \u043f\u0443\u0442\u044c),<br \/>WAY &#8212; \u0443\u0437\u0435\u043b \u043f\u0443\u0442\u0438(\u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0434\u043b\u044f \u0440\u0438\u0441\u043e\u0432\u0430\u043d\u0438\u044f \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u0438\u0437 \u0442\u043e\u0447\u043a\u0438 \u0410 \u0434\u043e \u0411, \u043d\u043e \u043d\u0435\u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u0435\u043d \u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u043a\u0430\u0440\u0442\u044b \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439).<\/p>\n<p>\u0421\u0430\u043c Node \u0438\u043c\u0435\u0435\u0442 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b x, y, \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0438 \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 distance. \u041c\u043e\u0436\u043d\u043e \u0442\u0430\u043a\u0436\u0435 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0442\u044c \u0432 \u0443\u0437\u043b\u0430\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0446\u0432\u0435\u0442\u0430 \u043f\u0438\u043a\u0441\u0435\u043b\u044f, \u0434\u043b\u044f \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u044f.<\/p>\n<p>\u0423\u0437\u043b\u044b \u0431\u0443\u0434\u0435\u043c \u043f\u043e\u043c\u0435\u0449\u0430\u0442\u044c \u0432<\/p>\n<pre><code class=\"cs\">List&lt;List&lt;Node>> nodes = new List&lt;List&lt;Node>>();<\/code><\/pre>\n<p>\u0422\u0430\u043a\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u043e\u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u043e\u0449\u0435 \u043e\u0431\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f \u043a \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c \u0443\u0437\u043b\u0430\u043c. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440:<\/p>\n<pre><code class=\"cs\">int x = node.x; int y = node.y + 1; Node node_neighbour = nodes[x - 1][y - 1]; \/\/ \u0441\u043e\u0441\u0435\u0434 \u0441\u0432\u0435\u0440\u0445\u0443<\/code><\/pre>\n<p>\u041f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0441\u043f\u0438\u0441\u043a\u0438 \u0443\u0437\u043b\u043e\u0432 \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u043d\u044b\u043c\u0438 \u0441\u043f\u043e\u0441\u043e\u0431\u0430\u043c\u0438 \u0438 \u044d\u0442\u043e \u043d\u0435 \u0442\u0430\u043a \u0432\u0430\u0436\u043d\u043e, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u044f \u043e\u043f\u0438\u0448\u0443 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0441\u0430\u043c\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0430 \u0432 \u043a\u043e\u043d\u0446\u0435 \u0441\u0442\u0430\u0442\u044c\u0438 \u043f\u043e\u043a\u0430\u0436\u0443 \u043f\u0440\u0438\u043c\u0435\u0440 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u044f.<\/p>\n<p>\u0422\u0430\u043a \u0436\u0435 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435 \u0443\u0437\u043b\u044b \u0441 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c DISTANCE. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c &#171;\u0434\u0432\u043e\u0438\u0447\u043d\u0443\u044e \u043a\u0443\u0447\u0443.&#187; \u0420\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u0443\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043b\u044e\u0431\u044b\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u043c, \u0433\u043b\u0430\u0432\u043d\u043e\u0435, \u0447\u0442\u043e\u0431\u044b \u043c\u044b \u043c\u043e\u0433\u043b\u0438 \u043b\u0435\u0433\u043a\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u0442\u0443\u0434\u0430 \u0443\u0437\u043b\u044b \u0438 \u0434\u043e\u0441\u0442\u0430\u0432\u0430\u0442\u044c \u043e\u0442 \u0442\u0443\u0434\u0430 \u0443\u0437\u0435\u043b \u0441 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c DISTANCE.<\/p>\n<pre><code class=\"cs\">\/\/ \u0432\u0437\u044f\u0442\u044c \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 neighbour Node min_neighbour = binaryHeapNodeClass.getMinimum(); \/\/ \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0443\u0437\u043b\u0430 \u0432 \u043a\u0443\u0447\u0443 binaryHeapNodeClass.add(node); \/\/ \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0443\u0437\u043b\u043e\u0432 \u0432 \u043a\u0443\u0447\u0435 binaryHeapNodeClass.heapSize; \/\/ \u043f\u0435\u0440\u0435\u0441\u0442\u0440\u043e\u0439\u043a\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u0441\u043b\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u0430 \u0432 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0438. binaryHeapNodeClass.heapify(0);<\/code><\/pre>\n<h2>\u0421\u0430\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c<\/h2>\n<p>\u041f\u0435\u0440\u0435\u0434 \u043d\u0430\u0447\u0430\u043b\u043e\u043c \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0433\u043e \u0446\u0438\u043a\u043b\u0430, \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u043f\u0435\u0440\u0432\u044b\u0435 \u0443\u0437\u043b\u044b \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u0443\u044e \u043a\u0443\u0447\u0443. \u041f\u0435\u0440\u0432\u044b\u043c\u0438 neighbours \u0431\u0443\u0434\u0443\u0442 \u0443\u0436\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0435 \u0443\u0437\u043b\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0432\u0445\u043e\u0434\u043d\u044b\u043c\u0438 \u0434\u0430\u043d\u043d\u044b\u043c\u0438:<\/p>\n<pre><code class=\"cs\">private void AddKnowNodeFromImage() {     for(int i = 0; i &lt; nodes.Count; i++) \/\/ immage height     {         for(int j = 0; j &lt; nodes[0].Count; j++) \/\/ image width         {             if (nodes[i][j].state == StateNode.KNOWN) \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0447\u0442\u043e \u044d\u0442\u043e \u043d\u0443\u0436\u043d\u044b\u0439 \u0443\u0437\u0435\u043b             {                 Node node_know = nodes[i][j];                 node_know.distance = 0;                 node_know.state = StateNode.NEIGHBOUR;                 nodes[i][j] = node_know;                 binaryHeapNodeClass.add(node_know); \/\/ \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0443\u0437\u043b\u044b \u0432 \u043a\u0443\u0447\u0443             }         }     } }<\/code><\/pre>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c:<\/p>\n<ol>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0434\u0432\u043e\u0438\u0447\u043d\u0430\u044f \u043a\u0443\u0447\u0430 \u043d\u0435 \u043f\u0443\u0441\u0442\u0430, \u0442\u043e \u043d\u0430\u0447\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u0415\u0441\u043b\u0438 \u043f\u0443\u0441\u0442\u0430 &#8212; \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c.<\/p>\n<\/li>\n<li>\n<p>\u0412\u0437\u044f\u0442\u044c neighbour \u0441 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c distance \u0438\u0437 \u043a\u0443\u0447\u0438 \u0438 \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u0435\u0433\u043e \u0438\u0437 \u043a\u0443\u0447\u0438.<\/p>\n<\/li>\n<li>\n<p>\u0412\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0434\u043b\u044f \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u044d\u0442\u043e\u0433\u043e \u0443\u0437\u043b\u0430.<\/p>\n<\/li>\n<li>\n<p>\u041f\u0435\u0440\u0435\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u044d\u0442\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0432 \u043a\u0443\u0447\u0443. \u0421\u0430\u043c \u044d\u0442\u043e\u0442 \u0443\u0437\u0435\u043b \u043f\u043e\u043c\u0435\u0442\u0438\u0442\u044c \u043a\u0430\u043a KNOW \u0438 \u043e\u0431\u043d\u043e\u0432\u0438\u0442\u044c \u0435\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0432 \u043e\u0431\u0449\u0435\u043c \u0441\u043f\u0438\u0441\u043a\u0435 \u0443\u0437\u043b\u043e\u0432.<\/p>\n<\/li>\n<li>\n<p>\u041f\u0435\u0440\u0435\u0439\u0442\u0438 \u043a \u0448\u0430\u0433\u0443 1.<\/p>\n<\/li>\n<\/ol>\n<pre><code class=\"cs\">while(binaryHeapNodeClass.heapSize > 0) { \/\/ \u0432\u0437\u044f\u0442\u044c \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 neighbour(\u0443\u0437\u0435\u043b \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0443\u0434\u0430\u043b\u044f\u0435\u0442\u0441\u044f \u0438\u0437 \u043a\u0443\u0447\u0438) Node min_neighbour = binaryHeapNodeClass.getMinimum(); binaryHeapNodeClass.heapify(0);  \/\/ \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \/\/ \u043f\u0435\u0440\u0435\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0432 neighbours CalculateNeighboursThisNode(min_neighbour);  \/\/ \u043f\u043e\u043c\u0435\u0442\u0438\u0442\u044c \u0443\u0437\u0435\u043b \u043a\u0430\u043a KNOW min_neighbour.state = StateNode.KNOWN; nodes[min_neighbour.x - 1][min_neigh.y - 1] = min_neighbour;  \/\/ \u043f\u043e\u0432\u0442\u043e\u0440\u0438\u0442\u044c }<\/code><\/pre>\n<p>\u041c\u044b \u0431\u0435\u0440\u0451\u043c \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0441\u0432\u0435\u0440\u0445\u0443, \u0441\u043f\u0440\u0430\u0432\u0430, \u0441\u043d\u0438\u0437\u0443 \u0438 \u0441\u043b\u0435\u0432\u0430, \u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0438\u0445 \u0432 \u043a\u0443\u0447\u0443 . \u0415\u0441\u043b\u0438 \u0443\u0437\u0435\u043b \u0432\u044b\u0448\u0435\u043b \u0437\u0430 \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0441\u0435\u0442\u043a\u0438, \u0442\u043e \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c.<\/p>\n<pre><code class=\"cs\">private void CalculateNeighboursThisNode(Node node) { TryNeighbourNode(node.x, node.y + 1);  TryNeighbourNode(node.x, node.y - 1);  TryNeighbourNode(node.x - 1, node.y);  TryNeighbourNode(node.x + 1, node.y); }  private void TryNeighbourNode(int x, int y) { try { Node node = nodes[x - 1][y - 1];  if (node.state == StateNode.FAR) \/\/ \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0447\u0442\u043e \u0443\u0437\u0435\u043b \u043d\u0435 \u043f\u043e\u0441\u0435\u0449\u0451\u043d\u043d\u044b\u0439 { Node node_neighbour = node;  node_neighbour.state = StateNode.NEIGHBOUR; \/\/\u0440\u0430\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u043b\u044f \u044d\u0442\u043e \u0443\u0437\u043b\u0430 node_neighbour = CalculateDistanceThisNode(node_neighbour);   nodes[x - 1][y-1] = node_neighbour;  binaryHeapNodeClass.add(node_neighbour); \/\/ \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0432 \u043a\u0443\u0447\u0443 } }   catch (ArgumentOutOfRangeException) { \/\/ \u0415\u0441\u043b\u0438 \u0443\u0437\u043b\u0430 \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u0442\u043e \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c }  }<\/code><\/pre>\n<p>\u0414\u0430\u043b\u0435\u0435 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043f\u0440\u0438\u043c\u0435\u0440 \u0440\u0430\u0441\u0447\u0451\u0442\u0430 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u043b\u044f \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430. \u0415\u0441\u043b\u0438 \u043c\u044b \u0432\u044b\u0448\u043b\u0438 \u0437\u0430 \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0441\u043f\u0438\u0441\u043a\u0430, \u0442\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0443\u0437\u0435\u043b \u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c.<\/p>\n<pre><code class=\"cs\">private Node CalculateDistanceThisNode(Node node) {  Node neighbours_North = TryNode(node.x, node.y + 1);  Node neighbours_South = TryNode(node.x, node.y - 1);  double a = Math.Min(neighbours_North.distance,neighbours_South.distance);  Node neighbours_West = TryNode(node.x - 1, node.y);  Node neighbours_East = TryNode(node.x + 1, node.y);  double b = Math.Min(neighbours_West.distance, neighbours_East.distance);  double T = CalculateDistance(a, b);  return node;  }  private Node TryNode(int x, int y) { Node node; try { node = nodes[x - 1][y - 1]; }  catch (ArgumentOutOfRangeException) { node = new Node() { \/\/ \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u0435\u043c \u043c\u0430\u043a\u0441. \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 distance = double.PositiveInfinity  }; }  return node; }  public double CalculateDistance(double a, double b) {   \/\/ \u0431\u043b\u043e\u043a \u0441 \u0444\u043e\u0440\u043c\u0443\u043b\u0430\u043c\u0438 (2) double F = 1; double T;  if(F > Math.Abs(a - b)) { T = (a + b + Math.Sqrt(2 * 1\/F * 1\/F - (a-b)*(a-b) )) \/ 2; } else { T = 1\/F*1\/F + Math.Min(a, b); }  return T; }<\/code><\/pre>\n<p>\u042f \u0432\u0437\u044f\u043b \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0443 \u0438\u0437 \u0418\u043d\u0442\u0435\u0440\u043d\u0435\u0442\u0430 \u0438 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043b \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0432 \u0443\u0437\u043b\u044b. \u0421\u0442\u0435\u043d\u043a\u0438 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 \u043f\u043e\u043c\u0435\u0442\u0438\u043b \u043a\u0430\u043a BLOCK, \u0442\u043e \u0435\u0441\u0442\u044c \u0443\u0437\u043b\u044b \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u043f\u0443\u0442\u0438 \u0438 \u0440\u0430\u0441\u0447\u0451\u0442\u0430 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439. \u0426\u0432\u0435\u0442 \u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043e\u0442 \u0437\u0435\u043b\u0451\u043d\u043e\u0433\u043e \u043a \u0444\u0438\u043e\u043b\u0435\u0442\u043e\u0432\u043e\u043c\u0443. \u0423\u0447\u0438\u0442\u044b\u0432\u0430\u0439\u0442\u0435, \u0447\u0442\u043e \u0432\u0441\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f distance \u043f\u0440\u0438 \u0440\u0435\u043d\u0434\u0435\u0440\u0435 \u043d\u043e\u0440\u043c\u0430\u043b\u0438\u0437\u0443\u044e\u0442\u0441\u044f, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0442\u044c \u0434\u0432\u0430 \u0440\u0430\u0437\u043d\u044b\u0445 \u0440\u0438\u0441\u0443\u043d\u043a\u0430 \u043d\u0435\u043b\u044c\u0437\u044f.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/3j\/hj\/cz\/3jhjcz9hzl8k89sd3kdhho2jh7g.png\" width=\"1200\" height=\"1200\" data-src=\"https:\/\/habrastorage.org\/webt\/3j\/hj\/cz\/3jhjcz9hzl8k89sd3kdhho2jh7g.png\"\/><\/figure>\n<p>\u0418\u0437 \u0440\u0438\u0441\u0443\u043d\u043a\u0430 \u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0434\u043e\u043b\u044c\u0448\u0435 \u0432\u0441\u0435\u0433\u043e \u0438\u0434\u0442\u0438 \u0434\u043e \u0446\u0435\u043d\u0442\u0440\u0430 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 \u0438 \u0434\u043e \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b \u043f\u0435\u0440\u0435\u0433\u043e\u0440\u043e\u0434\u043a\u0438 \u0432 \u043d\u0430\u0447\u0430\u043b\u0435.<\/p>\n<h2>\u041f\u043e\u0438\u0441\u043a \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u0434\u043e \u0442\u043e\u0447\u043a\u0438  <\/h2>\n<p>\u0414\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438, \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0434\u0442\u0438 \u0432 \u043e\u0431\u0440\u0430\u0442\u043d\u0443\u044e \u0441\u0442\u043e\u0440\u043e\u043d\u0443 &#8212; \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0434\u043e \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439. \u041c\u044b \u0431\u0443\u0434\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0442\u044c\u0441\u044f \u043f\u043e \u0443\u0437\u043b\u0430\u043c \u043f\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0451\u043d\u043d\u043e\u043c\u0443 \u043f\u0440\u0430\u0432\u0438\u043b\u0443. \u041f\u0443\u0442\u044c \u0438\u0437 \u043f\u043e\u0441\u0435\u0449\u0451\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432 \u0438 \u0431\u0443\u0434\u0435\u0442 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u043c.<\/p>\n<p>\u041d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043e\u0442\u0431\u0438\u0440\u0430\u0442\u044c \u0443\u0437\u043b\u044b, \u0433\u0434\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 distance \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442\u0441\u044f, \u0438 \u0438\u0437 \u043d\u0438\u0445 \u0432\u044b\u0431\u0438\u0440\u0430\u0442\u044c \u0443\u0437\u043b\u044b \u0441 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c distance. \u041c\u044b \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u043c \u0438\u0434\u0442\u0438 \u043f\u043e \u0443\u0437\u043b\u0430\u043c, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u043e\u043f\u0430\u0434\u0451\u043c \u043d\u0430 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0443\u0437\u0435\u043b(\u043e\u043d \u0438\u043c\u0435\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 distance = 0).<\/p>\n<pre><code class=\"cs\">Node way_node = target_node; \/\/ target node \u044d\u0442\u043e \u0443\u0437\u0435\u043b \u0434\u043e \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0443\u0436\u043d\u043e \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043f\u0443\u0442\u044c  while (way_node.distance != 0) { way_node = GetNextWayNode(way_node); \/\/ \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0443\u0437\u0435\u043b way_nodes.Add(way_node); \/\/ \u043f\u043e\u043c\u0435\u0449\u0430\u0435\u043c \u0443\u0437\u0435\u043b \u0432 \"\u0443\u0437\u043b\u044b \u043f\u0443\u0442\u0438\" }  AddSizeWayLine(3);<\/code><\/pre>\n<p>\u0414\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0443\u0437\u043b\u0430 \u0441 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c distance \u043f\u043e\u043c\u0435\u0449\u0430\u0435\u043c \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0443\u0437\u043b\u044b \u0432 \u0431\u0438\u043d\u0430\u0440\u043d\u0443\u044e \u043a\u0443\u0447\u0443.<\/p>\n<pre><code class=\"cs\">private Node GetNextWayNode(Node node) { int x = node.x - 1; int y = node.y - 1;  List&lt;Node> neighbours = new List&lt;Node>();  Node node_1 = TryGetNeighbourNode(x, y + 1); \/\/ top Node node_2 = TryGetNeighbourNode(x + 1,y + 1); \/\/top-right Node node_3 = TryGetNeighbourNode(x + 1,y); \/\/ right Node node_4 = TryGetNeighbourNode(x + 1, y - 1); \/\/down-right Node node_5 = TryGetNeighbourNode(x, y - 1); \/\/ down Node node_6 = TryGetNeighbourNode(x - 1, y - 1); \/\/ down-left Node node_7 = TryGetNeighbourNode(x - 1, y); \/\/left Node node_8 = TryGetNeighbourNode(x - 1, y + 1); \/\/ top-left  neighbours.Add(node_1); neighbours.Add(node_2); neighbours.Add(node_3); neighbours.Add(node_4); neighbours.Add(node_5); neighbours.Add(node_6); neighbours.Add(node_7); neighbours.Add(node_8);   foreach (Node node_max in neighbours) { \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0447\u0442\u043e distance \u044d\u0442\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u043c\u0435\u043d\u044c\u0448\u0435 \u0447\u0435\u043c \u0443 \u0443\u0437\u043b\u0430 \u043f\u0443\u0442\u0438, \u0438 \u0443\u0437\u0435\u043b \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 if(node_max.distance &lt; node.distance &amp;&amp; node_max.distance != -1) { binaryHeapNode.add(node_max); \/\/ \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0432 \u0431\u0438\u043d\u0430\u0440\u043d\u0443\u044e \u043a\u0443\u0447\u0443 } }  Node node_next = binaryHeapNode.getMinimum(); \/\/ \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0443\u0437\u0435\u043b \u0438\u0437 \u043a\u0443\u0447\u0438 binaryHeapNode.heapify(0); \/\/ \u043f\u0435\u0440\u0435\u0441\u0442\u0440\u0430\u0438\u0432\u0430\u0435\u043c \u043a\u0443\u0447\u0443 \u043f\u043e\u0441\u043b\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u0430 return node_next; }  private Node TryGetNeighbourNode(int x, int y) { Node node = new Node();  try { node = nodes[x][y]; } catch (ArgumentOutOfRangeException) { node.distance = -1; \/\/ \u0435\u0441\u043b\u0438 \u0443\u0437\u043b\u0430 \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u0442\u043e \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 -1 }  return node; }<\/code><\/pre>\n<p>\u0415\u0441\u043b\u0438 \u0431\u0440\u0430\u0442\u044c \u043f\u0443\u0442\u044c \u0432 1 \u043f\u0438\u043a\u0441\u0435\u043b\u044c, \u0442\u043e \u043f\u0443\u0442\u044c \u0431\u0443\u0434\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u0442\u043e\u043d\u043a\u0438\u043c \u0438 \u0435\u0433\u043e \u0431\u0443\u0434\u0435\u0442 \u0442\u044f\u0436\u0435\u043b\u043e \u0443\u0432\u0438\u0434\u0435\u0442\u044c. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u043c \u0448\u0438\u0440\u0438\u043d\u0443 \u043f\u0443\u0442\u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u0438 AddSizeWayLine()<\/p>\n<pre><code class=\"cs\">private void AddSizeWayLine(int size) { foreach(Node way_node in way_nodes) \/\/ \u0431\u0435\u0440\u0451\u043c \u0443\u0437\u043b\u044b \u043f\u0443\u0442\u0438 { List&lt;Node> nodes_neighbours = new List&lt;Node>();  int node_x = way_node.x - 1; int node_y = way_node.y - 1;  for(int i = 1; i &lt;= size; i++) \/\/ \u0431\u0435\u0440\u0451\u043c \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0443\u0437\u043b\u044b \u043f\u0443\u0442\u0438 { Node node_1 = nodes[node_x][node_y + i]; Node node_2 = nodes[node_x + i][node_y]; Node node_3 = nodes[node_x][node_y - i]; Node node_4 = nodes[node_x - i][node_y];  nodes_neighbours.Add(node_1); nodes_neighbours.Add(node_2); nodes_neighbours.Add(node_3); nodes_neighbours.Add(node_4); }  foreach(Node neighbour in nodes_neighbours) \/\/ \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u0435\u043c \u0443\u0437\u043b\u0430\u043c \u0441\u0442\u0430\u0442\u0443\u0441 WAY { if(neighbour.state == StateNode.KNOWN) \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0447\u0442\u043e \u0443\u0437\u043b\u044b \u043d\u0435 BLOCK  { Node new_node = neighbour; new_node.state = StateNode.WAY; nodes[neighbour.x - 1][neighbour.y - 1] = new_node; } } } }<\/code><\/pre>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/bd\/sa\/ts\/bdsatstiq2xewkcfr8kpcdhihzm.png\" alt=\"\u041a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c\" title=\"\u041a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c\" width=\"1200\" height=\"1200\" data-src=\"https:\/\/habrastorage.org\/webt\/bd\/sa\/ts\/bdsatstiq2xewkcfr8kpcdhihzm.png\"\/><\/p>\n<div><figcaption>\u041a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c<\/figcaption><\/div>\n<\/figure>\n<h2>\u0420\u0430\u0441\u0447\u0451\u0442 \u043e\u0448\u0438\u0431\u043a\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439  <\/h2>\n<p>\u0414\u043b\u044f \u0440\u0430\u0441\u0447\u0451\u0442\u0430 \u043e\u0448\u0438\u0431\u043a\u0438 \u0432\u043e\u0437\u044c\u043c\u0451\u043c \u0442\u043e\u0447\u043a\u0443 \u043f\u043e \u0446\u0435\u043d\u0442\u0440\u0443 \u0438 \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u0430\u0435\u043c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430.<br \/>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430:<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/9s\/th\/wd\/9sthwdghmzzrykv8gq4rlelutxq.png\" alt=\"1001x1001 \u043f\u0438\u043a\u0441\u0435\u043b\u0435\u0439. \u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 709,2054797499496\" title=\"1001x1001 \u043f\u0438\u043a\u0441\u0435\u043b\u0435\u0439. \u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 709,2054797499496\" width=\"1001\" height=\"1001\" data-src=\"https:\/\/habrastorage.org\/webt\/9s\/th\/wd\/9sthwdghmzzrykv8gq4rlelutxq.png\"\/><\/p>\n<div><figcaption>1001&#215;1001 \u043f\u0438\u043a\u0441\u0435\u043b\u0435\u0439. \u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 709,2054797499496<\/figcaption><\/div>\n<\/figure>\n<p>\u0414\u043b\u044f \u0440\u0430\u0441\u0447\u0451\u0442\u0430 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0442\u0435\u043e\u0440\u0435\u043c\u0443 \u041f\u0438\u0444\u0430\u0433\u043e\u0440\u0430:<\/p>\n<pre><code class=\"cs\">Node know_node; \/\/ \u043d\u0430\u0448\u0430 \u0442\u043e\u0447\u043a\u0430 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435  private double CalculateErrorThisNode(Node node) { double real_distance = CalculateRealDistance(node); \/\/ \u0440\u0430\u0441\u0447\u0451\u0442 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f double error = Math.Abs(real_distance - node.distance); \/\/ \u0440\u0430\u0441\u0447\u0451\u0442 \u043e\u0448\u0438\u0431\u043a\u0438  return error; }  private double CalculateRealDistance(Node node) { double real_distance = Math.Sqrt((node.x - know_node.x) * (node.x - know_node.x)    + (node.y - know_node.y) * (node.y - know_node.y));  return real_distance; }<\/code><\/pre>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/kp\/po\/fk\/kppofkbxzoysnaqjkvle0pqjpx8.png\" alt=\"\u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u0430\u044f \u043e\u0448\u0438\u0431\u043a\u0430 2,098698563402081\" title=\"\u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u0430\u044f \u043e\u0448\u0438\u0431\u043a\u0430 2,098698563402081\" width=\"1001\" height=\"1001\" data-src=\"https:\/\/habrastorage.org\/webt\/kp\/po\/fk\/kppofkbxzoysnaqjkvle0pqjpx8.png\"\/><\/p>\n<div><figcaption>\u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u0430\u044f \u043e\u0448\u0438\u0431\u043a\u0430 2,098698563402081<\/figcaption><\/div>\n<\/figure>\n<p>\u0412\u0438\u0434\u043d\u043e, \u0447\u0442\u043e 0 \u043e\u0448\u0438\u0431\u043a\u0430(\u0431\u0435\u043b\u044b\u0439 \u0446\u0432\u0435\u0442) \u043d\u0430 \u0433\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0430\u043b\u044f\u0445 \u0438 \u0432\u0435\u0440\u0442\u0438\u043a\u0430\u043b\u044f\u0445, \u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u043e\u0448\u0438\u0431\u043a\u0430 (\u0444\u0438\u043e\u043b\u0435\u0442\u043e\u0432\u044b\u0439) \u043d\u0430 \u0434\u0438\u0430\u0433\u043e\u043d\u0430\u043b\u044f\u0445.<\/p>\n<h2>\u041f\u0440\u0438\u043c\u0435\u0440 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u044f \u0432 \u0443\u0437\u043b\u044b<\/h2>\n<pre><code class=\"cs\">struct Pixel {     public byte r, g, b, a;     public int x, y; }  public List&lt;List&lt;Node>> GetListNodes() { return nodes; }  public void ConvertToNode() {     byte[] bytes_image = image.Data;      GeneratePixel(bytes_image);      for (int i = 0; i &lt; image.Height; i++)     {         nodes.Add(new List&lt;Node>());            for (int j = 0; j &lt; image.Width; j++)         {             Node node = new Node()             {                 x = i+1,                 y = j+1,                 distance = double.PositiveInfinity,                 state = StateNode.FAR             };            \/\/ \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043f\u0438\u043a\u0441\u0435\u043b\u044c \u0441\u043e\u043e\u0442\u0432\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u0434\u0430\u043d\u043d\u043e\u043c\u0443 \u0443\u0437\u043b\u0443             Pixel pixel = pixels[image.Height * (j) + i];            \/\/ \u0438\u0449\u0435\u043c \u043f\u0438\u043a\u0441\u0435\u043b\u0438 \u043d\u0435 \u0431\u0435\u043b\u043e\u0433\u043e \u0446\u0432\u0435\u0442\u0430 \u0438 \u043f\u043e\u043c\u0435\u0447\u0430\u0435\u043c \u0438\u0445 \u043a\u0430\u043a KNOWN           \/\/ \u0432 \u043c\u043e\u0451\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0447\u0451\u0440\u043d\u043e\u0435 \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u043d\u0430 \u0431\u0435\u043b\u043e\u043c \u0444\u043e\u043d\u0435             if (pixel.r != 255 || pixel.g != 255 || pixel.b != 255)             {                 node.state = StateNode.KNOWN;             }              nodes[i].Add(node);          }      } }  private void GeneratePixel(byte[] bytes_image) {     int index_pixel = 0;     int x = 1, y = 1;      for (int i = 0; i &lt; bytes_image.Length; i += 4)     {         Pixel pixel = new Pixel()         {             r = bytes_image[i],             g = bytes_image[i + 1],             b = bytes_image[i + 2],             a = bytes_image[i + 3],              x = x,             y = y         };          index_pixel++;         x++;          if (index_pixel % image.Height == 0)         {             y++;             x = 1;         }         pixels.Add(pixel);     } }<\/code><\/pre>\n<h2>\u0414\u0440\u0443\u0433\u0438\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430<\/h2>\n<figure class=\"bordered full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/d50\/f99\/6c4\/d50f996c4e95ec2e94a77d452e548e84.png\" alt=\"\u0426\u0432\u0435\u0442 \u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043e\u0442 \u0446\u0432\u0435\u0442\u0430 \u043c\u043e\u0440\u0441\u043a\u043e\u0439 \u0432\u043e\u043b\u043d\u044b \u0434\u043e \u0436\u0451\u043b\u0442\u043e\u0433\u043e\" title=\"\u0426\u0432\u0435\u0442 \u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043e\u0442 \u0446\u0432\u0435\u0442\u0430 \u043c\u043e\u0440\u0441\u043a\u043e\u0439 \u0432\u043e\u043b\u043d\u044b \u0434\u043e \u0436\u0451\u043b\u0442\u043e\u0433\u043e\" width=\"520\" height=\"520\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d50\/f99\/6c4\/d50f996c4e95ec2e94a77d452e548e84.png\"\/><\/p>\n<div><figcaption>\u0426\u0432\u0435\u0442 \u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043e\u0442 \u0446\u0432\u0435\u0442\u0430 \u043c\u043e\u0440\u0441\u043a\u043e\u0439 \u0432\u043e\u043b\u043d\u044b \u0434\u043e \u0436\u0451\u043b\u0442\u043e\u0433\u043e<\/figcaption><\/div>\n<\/figure>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/bba\/d67\/a27\/bbad67a27d3649544cfb5116bbcf1797.png\" alt=\"\u0426\u0432\u0435\u0442 \u043e\u0442 \u0446\u0432\u0435\u0442\u0430 \u043c\u043e\u0440\u0441\u043a\u043e\u0439 \u0432\u043e\u043b\u043d\u044b \u0434\u043e \u0436\u0451\u043b\u0442\u043e\u0433\u043e\" title=\"\u0426\u0432\u0435\u0442 \u043e\u0442 \u0446\u0432\u0435\u0442\u0430 \u043c\u043e\u0440\u0441\u043a\u043e\u0439 \u0432\u043e\u043b\u043d\u044b \u0434\u043e \u0436\u0451\u043b\u0442\u043e\u0433\u043e\" width=\"500\" height=\"500\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bba\/d67\/a27\/bbad67a27d3649544cfb5116bbcf1797.png\"\/><\/p>\n<div><figcaption>\u0426\u0432\u0435\u0442 \u043e\u0442 \u0446\u0432\u0435\u0442\u0430 \u043c\u043e\u0440\u0441\u043a\u043e\u0439 \u0432\u043e\u043b\u043d\u044b \u0434\u043e \u0436\u0451\u043b\u0442\u043e\u0433\u043e<\/figcaption><\/div>\n<\/figure>\n<h2>\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0438<\/h2>\n<p>R. Kimmel and J.A. Sethian (1996). Fast Marching Methods for Computing Distance Maps and Shortest Paths.<br \/>Jakob Andreas B\u00e6rentzen (2001). On the implementation of fast marching methods for 3D lattices.<br \/><a href=\"http:\/\/essay.utwente.nl\/75601\/1\/Alblas_BA_EWI.pdf\" rel=\"noopener noreferrer nofollow\">Dieuwertje Alblas (2018). Implementing and analysing the fast marching method<\/a><\/p>\n<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/785990\/\"> https:\/\/habr.com\/ru\/articles\/785990\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<h2>\u0412\u0441\u0442\u0443\u043f\u043b\u0435\u043d\u0438\u0435<\/h2>\n<p>\u041c\u0435\u0442\u043e\u0434 \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u043c\u0430\u0440\u0448\u0430 (Fast Marching Method)  \u0431\u044b\u043b \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d \u0414\u0436\u0435\u0439\u043c\u0441\u043e\u043c \u0421\u0435\u0442\u0438\u0430\u043d\u043e\u043c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043a\u0440\u0430\u0435\u0432\u044b\u0445 \u0437\u0430\u0434\u0430\u0447 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u042d\u0439\u043a\u043e\u043d\u0430\u043b\u0430.<\/p>\n<p>\u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u0440\u0430\u0441\u0447\u0451\u0442\u0430 \u043f\u043e\u043b\u0435\u0439 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 (Distance Field) \u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438. \u0417\u0430\u0434\u0430\u0447\u0430 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438 &#8212; \u043e\u0431\u044a\u044f\u0441\u043d\u0438\u0442\u044c \u043f\u0440\u0438\u043d\u0446\u0438\u043f \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u0443\u044e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e. \u0414\u043b\u044f \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u0433\u043e \u0447\u0442\u0435\u043d\u0438\u044f, \u0432 \u043a\u043e\u043d\u0446\u0435 \u0441\u0442\u0430\u0442\u044c\u0438 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u044b \u0441\u0441\u044b\u043b\u043a\u0438 \u043d\u0430 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0438.<\/p>\n<h2>\u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 FMM<\/h2>\n<p>\u041e\u0431\u044b\u0447\u043d\u043e \u0432 \u0441\u0442\u0430\u0442\u044c\u044f\u0445 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u044e\u0442 \u044d\u0442\u043e\u0442 \u043c\u0435\u0442\u043e\u0434 \u043a\u0430\u043a &#171;\u043c\u0430\u0441\u043b\u044f\u043d\u043e\u0435 \u043f\u044f\u0442\u043d\u043e&#187; \u0440\u0430\u0441\u0442\u0435\u043a\u0430\u044e\u0449\u0435\u0435\u0441\u044f \u043f\u043e \u043f\u043e\u0432\u0435\u0440\u0445\u043d\u043e\u0441\u0442\u0438. \u041d\u0430 \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u043d \u043f\u0440\u0438\u043c\u0435\u0440 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0432\u043e\u043b\u043d\u044b \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435.<\/p>\n<figure class=\"full-width\">\n<div><figcaption>\u0420\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0432\u043e\u043b\u043d \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435.<\/figcaption><\/div>\n<\/figure>\n<p>\u041c\u0430\u0441\u043b\u043e \u0440\u0430\u0441\u0442\u0435\u043a\u0430\u0435\u0442\u0441\u044f \u043f\u043e \u043f\u043e\u0432\u0435\u0440\u0445\u043d\u043e\u0441\u0442\u0438 \u0441 \u0440\u0430\u0437\u043d\u043e\u0439 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c\u044e, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 .\u041f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e  0&#8243; alt=&#187;F(\\vec{x}) > 0&#8243; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5d9\/cc0\/ee6\/5d9cc0ee61b64557b956fff861de423b.svg&#187; width=&#187;76&#8243; height=&#187;22&#8243;\/> \u0432\u0441\u044e\u0434\u0443 \u043a\u0440\u043e\u043c\u0435 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438. \u0415\u0441\u043b\u0438 \u044d\u0442\u043e \u043d\u0435 \u0442\u0430\u043a, \u0442\u043e \u0434\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043d\u0435\u043b\u044c\u0437\u044f. \u0415\u0441\u043b\u0438 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u0430, \u0442\u043e \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u042d\u0439\u043a\u043e\u043d\u0430\u043b\u0430 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0435\u0442 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439. \u0414\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u0432\u0440\u0435\u043c\u044f \u043f\u0440\u0438\u0431\u044b\u0442\u0438\u044f \u0432 \u0442\u043e\u0447\u043a\u0443. \u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c FMM \u0434\u043b\u044f \u0434\u0432\u0443\u0445\u043c\u0435\u0440\u043d\u043e\u0433\u043e \u0441\u043b\u0443\u0447\u0430\u044f, \u043d\u043e \u043c\u0435\u0442\u043e\u0434 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0438 \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0435\u0439.<\/p>\n<p>\u0413\u0440\u0430\u0434\u0438\u0435\u043d\u0442(\u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u0432\u0440\u0435\u043c\u0435\u043d\u0438) \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u0435\u0432\u043a\u043b\u0438\u0434\u043e\u0432\u0430 \u043d\u043e\u0440\u043c\u0430:<\/p>\n<p>\u0414\u043b\u044f \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0442\u044c \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0432 \u043d\u0430\u0431\u043e\u0440 \u0443\u0437\u043b\u043e\u0432, \u0433\u0434\u0435 \u043a\u0430\u0436\u0434\u044b\u0439 \u043f\u0438\u043a\u0441\u0435\u043b\u044c \u044d\u0442\u043e \u0443\u0437\u0435\u043b. \u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0442\u044c  \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u0443\u0437\u043b\u043e\u0432. \u0411\u0443\u0434\u0435\u043c \u0431\u0440\u0430\u0442\u044c \u0443\u0437\u0435\u043b \u0441\u043f\u0440\u0430\u0432\u0430, \u0441\u043b\u0435\u0432\u0430, \u0441\u0432\u0435\u0440\u0445\u0443 \u0438 \u0441\u043d\u0438\u0437\u0443. \u0414\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b, \u0443\u0437\u043b\u044b \u0438\u043c\u0435\u044e\u0442 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u044f \u0447\u0430\u0441\u0442\u0435\u0439 \u0441\u0432\u0435\u0442\u0430.<\/p>\n<figure class=\"full-width\">\n<div><figcaption>\u0421\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0443\u0437\u043b\u044b. \u0417\u0430\u043a\u0440\u0430\u0448\u0435\u043d \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b.<\/figcaption><\/div>\n<\/figure>\n<p>\u0417\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0437\u0430\u0434\u0430\u0451\u0442\u0441\u044f \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435\u043c:<\/p>\n<p>\u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0441\u0430\u043c\u043e\u0435 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438\u0437 \u0434\u0432\u0443\u0445:<\/p>\n<p>  \\ \\ V _{a} &#8212; V _{b} > V _{a} &#8212; V _{c}&#187; alt=&#187;V _{b} &lt; V _{c} \\ \\ =>  \\ \\ V _{a} &#8212; V _{b} > V _{a} &#8212; V _{c}&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/af2\/3f5\/458\/af23f5458e9fe1073f258b069c31ac97.svg&#187; width=&#187;276&#8243; height=&#187;20&#8243;\/><\/p>\n<p>\u0420\u0430\u0441\u043f\u0438\u0448\u0435\u043c \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435, \u0437\u0430\u043c\u0435\u043d\u044f\u044f \u0443\u0441\u043b\u043e\u0432\u043d\u044b\u0435 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f:<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u0441\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044e \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u043e\u0433\u043e \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f, \u0433\u0434\u0435 &#8212; \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430. \u0414\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0435\u0442\u043e\u0434 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0439 \u0432 \u0440\u0430\u0431\u043e\u0442\u0435 R. Kimmel and J.A. Sethian (1996):<\/p>\n<p> |a-b|,\\ \\ then \\ \\ T_{i,j} = \\frac{a+b+\\sqrt{2 * (\\frac1{F_{i,j}})^2 &#8212; (a-b)^2}}{2}&#187; alt=&#187;IF \\ \\ \\frac1{F _ {i,j}} > |a-b|,\\ \\ then \\ \\ T_{i,j} = \\frac{a+b+\\sqrt{2 * (\\frac1{F_{i,j}})^2 &#8212; (a-b)^2}}{2}&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5f8\/798\/680\/5f87986801a0e5b36ff7ad4d342c768d.svg&#187; width=&#187;527&#8243; height=&#187;66&#8243;\/><\/p>\n<p>\u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u0432\u044b\u0431\u0438\u0440\u0430\u044f \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u043e \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u0440\u043e\u0439\u0434\u0451\u0442 \u0432\u0441\u0435 \u0443\u0437\u043b\u044b.<\/p>\n<figure class=\"full-width\">\n<div><figcaption>\u0420\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432 \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435.<\/figcaption><\/div>\n<\/figure>\n<h2>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 FMM<\/h2>\n<p>\u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043d\u0430\u0431\u043e\u0440 \u0443\u0437\u043b\u043e\u0432 \u0434\u043b\u044f \u0440\u0430\u0441\u0447\u0451\u0442\u0430 \u043f\u043e\u043b\u0435\u0439 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439. \u041c\u043e\u0436\u043d\u043e \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438\u0445, \u0430 \u043c\u043e\u0436\u043d\u043e \u0432\u0437\u044f\u0442\u044c \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0438 \u043a\u043e\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0435\u0433\u043e \u0432 \u043d\u0430\u0431\u043e\u0440 \u0443\u0437\u043b\u043e\u0432.<\/p>\n<p>\u0412\u043e\u0442 \u043f\u0440\u0438\u043c\u0435\u0440 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b Node. \u0412\u0435\u0441\u044c \u043a\u043e\u0434 \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d \u043d\u0430 C#.<\/p>\n<pre><code class=\"cs\">public enum StateNode {     KNOWN,     NEIGHBOUR,     FAR,     BLOCK,     WAY }  public struct Node {     public int x;     public int y;     public StateNode state;     public double distance; }<\/code><\/pre>\n<p>KNOWN \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u043f\u043e\u043c\u0435\u0447\u0430\u0442\u044c \u0443\u0436\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0435 \u0443\u0437\u043b\u044b,<br \/>NEIGHBOUR &#8212; \u0441\u043e\u0441\u0435\u0434\u0438 \u0443\u0436\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432,<br \/>FAR &#8212; \u043d\u0435 \u043f\u043e\u0441\u0435\u0449\u0451\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b,<br \/>BLOCK &#8212; \u043f\u0440\u0435\u043f\u044f\u0442\u0441\u0442\u0432\u0438\u0435(\u0443\u0437\u0435\u043b, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043a\u0430\u043a \u043f\u0443\u0442\u044c),<br \/>WAY &#8212; \u0443\u0437\u0435\u043b \u043f\u0443\u0442\u0438(\u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0434\u043b\u044f \u0440\u0438\u0441\u043e\u0432\u0430\u043d\u0438\u044f \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u0438\u0437 \u0442\u043e\u0447\u043a\u0438 \u0410 \u0434\u043e \u0411, \u043d\u043e \u043d\u0435\u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u0435\u043d \u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u043a\u0430\u0440\u0442\u044b \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439).<\/p>\n<p>\u0421\u0430\u043c Node \u0438\u043c\u0435\u0435\u0442 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b x, y, \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0438 \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 distance. \u041c\u043e\u0436\u043d\u043e \u0442\u0430\u043a\u0436\u0435 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0442\u044c \u0432 \u0443\u0437\u043b\u0430\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0446\u0432\u0435\u0442\u0430 \u043f\u0438\u043a\u0441\u0435\u043b\u044f, \u0434\u043b\u044f \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u044f.<\/p>\n<p>\u0423\u0437\u043b\u044b \u0431\u0443\u0434\u0435\u043c \u043f\u043e\u043c\u0435\u0449\u0430\u0442\u044c \u0432<\/p>\n<pre><code class=\"cs\">List&lt;List&lt;Node>> nodes = new List&lt;List&lt;Node>>();<\/code><\/pre>\n<p>\u0422\u0430\u043a\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u043e\u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u043e\u0449\u0435 \u043e\u0431\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f \u043a \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c \u0443\u0437\u043b\u0430\u043c. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440:<\/p>\n<pre><code class=\"cs\">int x = node.x; int y = node.y + 1; Node node_neighbour = nodes[x - 1][y - 1]; \/\/ \u0441\u043e\u0441\u0435\u0434 \u0441\u0432\u0435\u0440\u0445\u0443<\/code><\/pre>\n<p>\u041f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0441\u043f\u0438\u0441\u043a\u0438 \u0443\u0437\u043b\u043e\u0432 \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u043d\u044b\u043c\u0438 \u0441\u043f\u043e\u0441\u043e\u0431\u0430\u043c\u0438 \u0438 \u044d\u0442\u043e \u043d\u0435 \u0442\u0430\u043a \u0432\u0430\u0436\u043d\u043e, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u044f \u043e\u043f\u0438\u0448\u0443 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0441\u0430\u043c\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0430 \u0432 \u043a\u043e\u043d\u0446\u0435 \u0441\u0442\u0430\u0442\u044c\u0438 \u043f\u043e\u043a\u0430\u0436\u0443 \u043f\u0440\u0438\u043c\u0435\u0440 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u044f.<\/p>\n<p>\u0422\u0430\u043a \u0436\u0435 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435 \u0443\u0437\u043b\u044b \u0441 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c DISTANCE. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c &#171;\u0434\u0432\u043e\u0438\u0447\u043d\u0443\u044e \u043a\u0443\u0447\u0443.&#187; \u0420\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u0443\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043b\u044e\u0431\u044b\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u043c, \u0433\u043b\u0430\u0432\u043d\u043e\u0435, \u0447\u0442\u043e\u0431\u044b \u043c\u044b \u043c\u043e\u0433\u043b\u0438 \u043b\u0435\u0433\u043a\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u0442\u0443\u0434\u0430 \u0443\u0437\u043b\u044b \u0438 \u0434\u043e\u0441\u0442\u0430\u0432\u0430\u0442\u044c \u043e\u0442 \u0442\u0443\u0434\u0430 \u0443\u0437\u0435\u043b \u0441 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c DISTANCE.<\/p>\n<pre><code class=\"cs\">\/\/ \u0432\u0437\u044f\u0442\u044c \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 neighbour Node min_neighbour = binaryHeapNodeClass.getMinimum(); \/\/ \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0443\u0437\u043b\u0430 \u0432 \u043a\u0443\u0447\u0443 binaryHeapNodeClass.add(node); \/\/ \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0443\u0437\u043b\u043e\u0432 \u0432 \u043a\u0443\u0447\u0435 binaryHeapNodeClass.heapSize; \/\/ \u043f\u0435\u0440\u0435\u0441\u0442\u0440\u043e\u0439\u043a\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u0441\u043b\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u0430 \u0432 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0438. binaryHeapNodeClass.heapify(0);<\/code><\/pre>\n<h2>\u0421\u0430\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c<\/h2>\n<p>\u041f\u0435\u0440\u0435\u0434 \u043d\u0430\u0447\u0430\u043b\u043e\u043c \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0433\u043e \u0446\u0438\u043a\u043b\u0430, \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u043f\u0435\u0440\u0432\u044b\u0435 \u0443\u0437\u043b\u044b \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u0443\u044e \u043a\u0443\u0447\u0443. \u041f\u0435\u0440\u0432\u044b\u043c\u0438 neighbours \u0431\u0443\u0434\u0443\u0442 \u0443\u0436\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0435 \u0443\u0437\u043b\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0432\u0445\u043e\u0434\u043d\u044b\u043c\u0438 \u0434\u0430\u043d\u043d\u044b\u043c\u0438:<\/p>\n<pre><code class=\"cs\">private void AddKnowNodeFromImage() {     for(int i = 0; i &lt; nodes.Count; i++) \/\/ immage height     {         for(int j = 0; j &lt; nodes[0].Count; j++) \/\/ image width         {             if (nodes[i][j].state == StateNode.KNOWN) \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0447\u0442\u043e \u044d\u0442\u043e \u043d\u0443\u0436\u043d\u044b\u0439 \u0443\u0437\u0435\u043b             {                 Node node_know = nodes[i][j];                 node_know.distance = 0;                 node_know.state = StateNode.NEIGHBOUR;                 nodes[i][j] = node_know;                 binaryHeapNodeClass.add(node_know); \/\/ \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0443\u0437\u043b\u044b \u0432 \u043a\u0443\u0447\u0443             }         }     } }<\/code><\/pre>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c:<\/p>\n<ol>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0434\u0432\u043e\u0438\u0447\u043d\u0430\u044f \u043a\u0443\u0447\u0430 \u043d\u0435 \u043f\u0443\u0441\u0442\u0430, \u0442\u043e \u043d\u0430\u0447\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u0415\u0441\u043b\u0438 \u043f\u0443\u0441\u0442\u0430 &#8212; \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c.<\/p>\n<\/li>\n<li>\n<p>\u0412\u0437\u044f\u0442\u044c neighbour \u0441 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c distance \u0438\u0437 \u043a\u0443\u0447\u0438 \u0438 \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u0435\u0433\u043e \u0438\u0437 \u043a\u0443\u0447\u0438.<\/p>\n<\/li>\n<li>\n<p>\u0412\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0434\u043b\u044f \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u044d\u0442\u043e\u0433\u043e \u0443\u0437\u043b\u0430.<\/p>\n<\/li>\n<li>\n<p>\u041f\u0435\u0440\u0435\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u044d\u0442\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0432 \u043a\u0443\u0447\u0443. \u0421\u0430\u043c \u044d\u0442\u043e\u0442 \u0443\u0437\u0435\u043b \u043f\u043e\u043c\u0435\u0442\u0438\u0442\u044c \u043a\u0430\u043a KNOW \u0438 \u043e\u0431\u043d\u043e\u0432\u0438\u0442\u044c \u0435\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0432 \u043e\u0431\u0449\u0435\u043c \u0441\u043f\u0438\u0441\u043a\u0435 \u0443\u0437\u043b\u043e\u0432.<\/p>\n<\/li>\n<li>\n<p>\u041f\u0435\u0440\u0435\u0439\u0442\u0438 \u043a \u0448\u0430\u0433\u0443 1.<\/p>\n<\/li>\n<\/ol>\n<pre><code class=\"cs\">while(binaryHeapNodeClass.heapSize > 0) { \/\/ \u0432\u0437\u044f\u0442\u044c \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 neighbour(\u0443\u0437\u0435\u043b \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0443\u0434\u0430\u043b\u044f\u0435\u0442\u0441\u044f \u0438\u0437 \u043a\u0443\u0447\u0438) Node min_neighbour = binaryHeapNodeClass.getMinimum(); binaryHeapNodeClass.heapify(0);  \/\/ \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \/\/ \u043f\u0435\u0440\u0435\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0432 neighbours CalculateNeighboursThisNode(min_neighbour);  \/\/ \u043f\u043e\u043c\u0435\u0442\u0438\u0442\u044c \u0443\u0437\u0435\u043b \u043a\u0430\u043a KNOW min_neighbour.state = StateNode.KNOWN; nodes[min_neighbour.x - 1][min_neigh.y - 1] = min_neighbour;  \/\/ \u043f\u043e\u0432\u0442\u043e\u0440\u0438\u0442\u044c }<\/code><\/pre>\n<p>\u041c\u044b \u0431\u0435\u0440\u0451\u043c \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0441\u0432\u0435\u0440\u0445\u0443, \u0441\u043f\u0440\u0430\u0432\u0430, \u0441\u043d\u0438\u0437\u0443 \u0438 \u0441\u043b\u0435\u0432\u0430, \u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0438\u0445 \u0432 \u043a\u0443\u0447\u0443 . \u0415\u0441\u043b\u0438 \u0443\u0437\u0435\u043b \u0432\u044b\u0448\u0435\u043b \u0437\u0430 \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0441\u0435\u0442\u043a\u0438, \u0442\u043e \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c.<\/p>\n<pre><code class=\"cs\">private void CalculateNeighboursThisNode(Node node) { TryNeighbourNode(node.x, node.y + 1);  TryNeighbourNode(node.x, node.y - 1);  TryNeighbourNode(node.x - 1, node.y);  TryNeighbourNode(node.x + 1, node.y); }  private void TryNeighbourNode(int x, int y) { try { Node node = nodes[x - 1][y - 1];  if (node.state == StateNode.FAR) \/\/ \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0447\u0442\u043e \u0443\u0437\u0435\u043b \u043d\u0435 \u043f\u043e\u0441\u0435\u0449\u0451\u043d\u043d\u044b\u0439 { Node node_neighbour = node;  node_neighbour.state = StateNode.NEIGHBOUR; \/\/\u0440\u0430\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u043b\u044f \u044d\u0442\u043e \u0443\u0437\u043b\u0430 node_neighbour = CalculateDistanceThisNode(node_neighbour);   nodes[x - 1][y-1] = node_neighbour;  binaryHeapNodeClass.add(node_neighbour); \/\/ \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0432 \u043a\u0443\u0447\u0443 } }   catch (ArgumentOutOfRangeException) { \/\/ \u0415\u0441\u043b\u0438 \u0443\u0437\u043b\u0430 \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u0442\u043e \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c }  }<\/code><\/pre>\n<p>\u0414\u0430\u043b\u0435\u0435 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043f\u0440\u0438\u043c\u0435\u0440 \u0440\u0430\u0441\u0447\u0451\u0442\u0430 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u043b\u044f \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430. \u0415\u0441\u043b\u0438 \u043c\u044b \u0432\u044b\u0448\u043b\u0438 \u0437\u0430 \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0441\u043f\u0438\u0441\u043a\u0430, \u0442\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0443\u0437\u0435\u043b \u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c.<\/p>\n<pre><code class=\"cs\">private Node CalculateDistanceThisNode(Node node) {  Node neighbours_North = TryNode(node.x, node.y + 1);  Node neighbours_South = TryNode(node.x, node.y - 1);  double a = Math.Min(neighbours_North.distance,neighbours_South.distance);  Node neighbours_West = TryNode(node.x - 1, node.y);  Node neighbours_East = TryNode(node.x + 1, node.y);  double b = Math.Min(neighbours_West.distance, neighbours_East.distance);  double T = CalculateDistance(a, b);  return node;  }  private Node TryNode(int x, int y) { Node node; try { node = nodes[x - 1][y - 1]; }  catch (ArgumentOutOfRangeException) { node = new Node() { \/\/ \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u0435\u043c \u043c\u0430\u043a\u0441. \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 distance = double.PositiveInfinity  }; }  return node; }  public double CalculateDistance(double a, double b) {   \/\/ \u0431\u043b\u043e\u043a \u0441 \u0444\u043e\u0440\u043c\u0443\u043b\u0430\u043c\u0438 (2) double F = 1; double T;  if(F > Math.Abs(a - b)) { T = (a + b + Math.Sqrt(2 * 1\/F * 1\/F - (a-b)*(a-b) )) \/ 2; } else { T = 1\/F*1\/F + Math.Min(a, b); }  return T; }<\/code><\/pre>\n<p>\u042f \u0432\u0437\u044f\u043b \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0443 \u0438\u0437 \u0418\u043d\u0442\u0435\u0440\u043d\u0435\u0442\u0430 \u0438 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043b \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0432 \u0443\u0437\u043b\u044b. \u0421\u0442\u0435\u043d\u043a\u0438 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 \u043f\u043e\u043c\u0435\u0442\u0438\u043b \u043a\u0430\u043a BLOCK, \u0442\u043e \u0435\u0441\u0442\u044c \u0443\u0437\u043b\u044b \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u043f\u0443\u0442\u0438 \u0438 \u0440\u0430\u0441\u0447\u0451\u0442\u0430 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439. \u0426\u0432\u0435\u0442 \u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043e\u0442 \u0437\u0435\u043b\u0451\u043d\u043e\u0433\u043e \u043a \u0444\u0438\u043e\u043b\u0435\u0442\u043e\u0432\u043e\u043c\u0443. \u0423\u0447\u0438\u0442\u044b\u0432\u0430\u0439\u0442\u0435, \u0447\u0442\u043e \u0432\u0441\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f distance \u043f\u0440\u0438 \u0440\u0435\u043d\u0434\u0435\u0440\u0435 \u043d\u043e\u0440\u043c\u0430\u043b\u0438\u0437\u0443\u044e\u0442\u0441\u044f, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0442\u044c \u0434\u0432\u0430 \u0440\u0430\u0437\u043d\u044b\u0445 \u0440\u0438\u0441\u0443\u043d\u043a\u0430 \u043d\u0435\u043b\u044c\u0437\u044f.<\/p>\n<figure class=\"full-width\"><\/figure>\n<p>\u0418\u0437 \u0440\u0438\u0441\u0443\u043d\u043a\u0430 \u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0434\u043e\u043b\u044c\u0448\u0435 \u0432\u0441\u0435\u0433\u043e \u0438\u0434\u0442\u0438 \u0434\u043e \u0446\u0435\u043d\u0442\u0440\u0430 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 \u0438 \u0434\u043e \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b \u043f\u0435\u0440\u0435\u0433\u043e\u0440\u043e\u0434\u043a\u0438 \u0432 \u043d\u0430\u0447\u0430\u043b\u0435.<\/p>\n<h2>\u041f\u043e\u0438\u0441\u043a \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u0434\u043e \u0442\u043e\u0447\u043a\u0438  <\/h2>\n<p>\u0414\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438, \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0434\u0442\u0438 \u0432 \u043e\u0431\u0440\u0430\u0442\u043d\u0443\u044e \u0441\u0442\u043e\u0440\u043e\u043d\u0443 &#8212; \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0434\u043e \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439. \u041c\u044b \u0431\u0443\u0434\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0442\u044c\u0441\u044f \u043f\u043e \u0443\u0437\u043b\u0430\u043c \u043f\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0451\u043d\u043d\u043e\u043c\u0443 \u043f\u0440\u0430\u0432\u0438\u043b\u0443. \u041f\u0443\u0442\u044c \u0438\u0437 \u043f\u043e\u0441\u0435\u0449\u0451\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432 \u0438 \u0431\u0443\u0434\u0435\u0442 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u043c.<\/p>\n<p>\u041d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043e\u0442\u0431\u0438\u0440\u0430\u0442\u044c \u0443\u0437\u043b\u044b, \u0433\u0434\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 distance \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442\u0441\u044f, \u0438 \u0438\u0437 \u043d\u0438\u0445 \u0432\u044b\u0431\u0438\u0440\u0430\u0442\u044c \u0443\u0437\u043b\u044b \u0441 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c distance. \u041c\u044b \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u043c \u0438\u0434\u0442\u0438 \u043f\u043e \u0443\u0437\u043b\u0430\u043c, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u043e\u043f\u0430\u0434\u0451\u043c \u043d\u0430 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0443\u0437\u0435\u043b(\u043e\u043d \u0438\u043c\u0435\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 distance = 0).<\/p>\n<pre><code class=\"cs\">Node way_node = target_node; \/\/ target node \u044d\u0442\u043e \u0443\u0437\u0435\u043b \u0434\u043e \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0443\u0436\u043d\u043e \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043f\u0443\u0442\u044c  while (way_node.distance != 0) { way_node = GetNextWayNode(way_node); \/\/ \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0443\u0437\u0435\u043b way_nodes.Add(way_node); \/\/ \u043f\u043e\u043c\u0435\u0449\u0430\u0435\u043c \u0443\u0437\u0435\u043b \u0432 \"\u0443\u0437\u043b\u044b \u043f\u0443\u0442\u0438\" }  AddSizeWayLine(3);<\/code><\/pre>\n<p>\u0414\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0443\u0437\u043b\u0430 \u0441 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c distance \u043f\u043e\u043c\u0435\u0449\u0430\u0435\u043c \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0443\u0437\u043b\u044b \u0432 \u0431\u0438\u043d\u0430\u0440\u043d\u0443\u044e \u043a\u0443\u0447\u0443.<\/p>\n<pre><code class=\"cs\">private Node GetNextWayNode(Node node) { int x = node.x - 1; int y = node.y - 1;  List&lt;Node> neighbours = new List&lt;Node>();  Node node_1 = TryGetNeighbourNode(x, y + 1); \/\/ top Node node_2 = TryGetNeighbourNode(x + 1,y + 1); \/\/top-right Node node_3 = TryGetNeighbourNode(x + 1,y); \/\/ right Node node_4 = TryGetNeighbourNode(x + 1, y - 1); \/\/down-right Node node_5 = TryGetNeighbourNode(x, y - 1); \/\/ down Node node_6 = TryGetNeighbourNode(x - 1, y - 1); \/\/ down-left Node node_7 = TryGetNeighbourNode(x - 1, y); \/\/left Node node_8 = TryGetNeighbourNode(x - 1, y + 1); \/\/ top-left  neighbours.Add(node_1);<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-365131","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/365131","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=365131"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/365131\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=365131"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=365131"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=365131"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}