{"id":773,"date":"2021-08-18T14:36:20","date_gmt":"2021-08-18T14:36:20","guid":{"rendered":"http:\/\/summergeometry.org\/sgi2021\/?p=773"},"modified":"2021-08-18T14:36:22","modified_gmt":"2021-08-18T14:36:22","slug":"upper-bound-for-the-hausdorff-distance","status":"publish","type":"post","link":"https:\/\/summergeometry.org\/sgi2021\/upper-bound-for-the-hausdorff-distance\/","title":{"rendered":"Upper bound for the Hausdorff distance"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Last week I was working on the project \u201cRobust computation of the Hausdorff distance between triangle meshes\u201d under Dr. <a href=\"http:\/\/mtm.ufsc.br\/~leo\/\">Leonardo Sacht<\/a>\u2019s supervision with TA <a href=\"https:\/\/www.egr.msu.edu\/~amezqui3\/aboutme.html\">Erik Amezquita<\/a> and SGI fellows Bryce Van Ross and Deniz Ozbay.\u00a0<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">If we have triangle meshes \\( A, B \\), then  \\( h(A,B) = \\max_{p \\in A}d(p,B) \\) is called the Hausdorff distance from  \\( A\\)  to  \\( B \\), where \\(d\\) is Euclidean distance. In general case, this function is not symmetric, so the final metric is defined as \\(H(a,b) = \\max(h(A,B), h(B,A))\\).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The Hausdorff distance is very significant in Geometry Processing on the grounds that it may be used for determining the difference between two meshes. The method that we are studying is called the \u201cbranch-and-bound\u201d method. The main idea is to calculate the common lower bound for distance from the whole mesh <strong> <\/strong>\\( A\\)<strong> <\/strong>to mesh  \\(B\\)  and individual upper bounds for  distances from every triangle mesh \\(T_{A}\\) of mesh  \\( A \\) to mesh \\(B\\). If the upper bounds of some triangles is smaller than the lower bound, then we throw them away and consider the remaining subdivided ones.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">My task was to code the function that returns the upper bounds for distances from every triangle mesh \\(T_{A}\\) of mesh  \\( A \\) to mesh \\(B\\).  We are going to use the distances between vertices of triangle mesh  \\(T_{A}\\)  and triangle inequality to find the upper bound: \\[u( T_{A}, B) = \\max_{j = 1}^{3}(\\max(|v_{j} &#8211; v_{j + 1}|, |v_{j} &#8211; v_{j + 2}|) + \\min_{b \\in B}(|v_{j} &#8211; b|))\\] where \\(v_{1}, v_{2}, v_{3}\\) are the vertices of triangle mesh  \\(T_{A}\\) .<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">This is how the implemented algorithm looks like in Matlab:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"815\" height=\"712\" src=\"http:\/\/summergeometry.org\/sgi2021\/wp-content\/uploads\/2021\/08\/screen.png\" alt=\"\" class=\"wp-image-920\" srcset=\"https:\/\/summergeometry.org\/sgi2021\/wp-content\/uploads\/2021\/08\/screen.png 815w, https:\/\/summergeometry.org\/sgi2021\/wp-content\/uploads\/2021\/08\/screen-300x262.png 300w, https:\/\/summergeometry.org\/sgi2021\/wp-content\/uploads\/2021\/08\/screen-768x671.png 768w\" sizes=\"auto, (max-width: 815px) 100vw, 815px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">I really enjoyed working on the project this week with my team, TA and supervisor. I am looking forward to continuing work and improving what we have already done.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Last week I was working on the project \u201cRobust computation of the Hausdorff distance between triangle meshes\u201d under Dr. Leonardo Sacht\u2019s supervision with TA Erik Amezquita and SGI fellows Bryce Van Ross and Deniz Ozbay.\u00a0 If we have triangle meshes \\( A, B \\), then \\( h(A,B) = \\max_{p \\in A}d(p,B) \\) is called the [&hellip;]<\/p>\n","protected":false},"author":8,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[25],"tags":[65,64],"class_list":["post-773","post","type-post","status-publish","format-standard","hentry","category-sgi-research-projects","tag-hausdorff-2","tag-hausdorff_distance"],"_links":{"self":[{"href":"https:\/\/summergeometry.org\/sgi2021\/wp-json\/wp\/v2\/posts\/773","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/summergeometry.org\/sgi2021\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/summergeometry.org\/sgi2021\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2021\/wp-json\/wp\/v2\/users\/8"}],"replies":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2021\/wp-json\/wp\/v2\/comments?post=773"}],"version-history":[{"count":9,"href":"https:\/\/summergeometry.org\/sgi2021\/wp-json\/wp\/v2\/posts\/773\/revisions"}],"predecessor-version":[{"id":973,"href":"https:\/\/summergeometry.org\/sgi2021\/wp-json\/wp\/v2\/posts\/773\/revisions\/973"}],"wp:attachment":[{"href":"https:\/\/summergeometry.org\/sgi2021\/wp-json\/wp\/v2\/media?parent=773"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2021\/wp-json\/wp\/v2\/categories?post=773"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2021\/wp-json\/wp\/v2\/tags?post=773"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}