Problem 45261. Query every vertices neighbor indices

Created by Nicolas Douillet

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Input T is a</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://fr.mathworks.com/help/matlab/ref/triangulation.html\"><w:r><w:t>triangulation</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The purpose of this function is to query at once the cell array N of all vertex neighbor indices... of every vertices, nothing less (!)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output N must be a cell array since of course each vertex may have a different number of neighbors.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For example, for an input filled octahedron whom triangulation is</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[T = [1, 2, 3;...\n 1, 3, 4;...\n 1, 4, 5;...\n 1, 2, 5;...\n 2, 3, 6;...\n 3, 4, 6;...\n 4, 5, 6;...\n 2, 5, 6;...\n 2, 3, 4;...\n 2, 4, 5;...\n 1, 2, 4;...\n 2, 4, 6],]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>then the output N is a 6x1 cell array of integers row vectors, such that :</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[N(1,1) = {[2, 3, 4, 5]};\nN(2,1) = {[1, 3, 4, 5, 6]};\nN(3,1) = {[1, 2, 4, 6]};\nN(4,1) = {[1, 2, 3, 5, 6]};\nN(5,1) = {[1, 2, 4, 6]};\nN(6,1) = {[2, 3, 4, 5]};]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Indeed vertex #2 is part of triangles [1, 2, 3], [1, 2, 5], [2, 3, 6], [2, 5, 6], [2, 3, 4], [2, 4, 5], [1, 2, 4], and [2, 4, 6], it then admit all the other vertices as neighbors ([1, 3, 4, 5, 6]).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Hypothesis / conditions :</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>a</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>vertex is the neighbor of another</w:t></w:r><w:r><w:t> if they are linked with an edge</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>in at least one same triangle</w:t></w:r><w:r><w:t>. A vertex is not neighbor of itself.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output N row order is crucial</w:t></w:r><w:r><w:t> since</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>row number actually corresponds to the vertex id / index.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Output N cells content order doesn't matter, but it doesn't admit any duplicated index / value.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Tip :</w:t></w:r><w:r><w:t> solving</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://fr.mathworks.com/matlabcentral/cody/players/8668631-nicolas-douillet/created\"><w:r><w:t>my previous problems</w:t></w:r></w:hyperlink><w:r><w:t>, and especially</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://fr.mathworks.com/matlabcentral/cody/problems/45256-query-a-vertex-neighbors\"><w:r><w:t>query_vertex_neighbors</w:t></w:r></w:hyperlink><w:r><w:t> will help you to fully understand and solve this one.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>NB : the question of unreferenced vertices is not tacled here. We just supposed there are not.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Good work Matlab-bro ! :)</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Input T is a <a href = "https://fr.mathworks.com/help/matlab/ref/triangulation.html">triangulation</a>.The purpose of this function is to query at once the cell array N of all vertex neighbor indices... of every vertices, nothing less (!)Output N must be a cell array since of course each vertex may have a different number of neighbors.For example, for an input filled octahedron whom triangulation is<pre class="language-matlab">T = [1, 2, 3;...
 1, 3, 4;...
 1, 4, 5;...
 1, 2, 5;...
 2, 3, 6;...
 3, 4, 6;...
 4, 5, 6;...
 2, 5, 6;...
 2, 3, 4;...
 2, 4, 5;...
 1, 2, 4;...
 2, 4, 6],
</pre>then the output N is a 6x1 cell array of integers row vectors, such that :<pre class="language-matlab">N(1,1) = {[2, 3, 4, 5]};
N(2,1) = {[1, 3, 4, 5, 6]};
N(3,1) = {[1, 2, 4, 6]};
N(4,1) = {[1, 2, 3, 5, 6]};
N(5,1) = {[1, 2, 4, 6]};
N(6,1) = {[2, 3, 4, 5]};
</pre>Indeed vertex #2 is part of triangles [1, 2, 3], [1, 2, 5], [2, 3, 6], [2, 5, 6], [2, 3, 4], [2, 4, 5], [1, 2, 4], and [2, 4, 6], it then admit all the other vertices as neighbors ([1, 3, 4, 5, 6]).Hypothesis / conditions :<ul><li>a vertex is the neighbor of another if they are linked with an edge in at least one same triangle. A vertex is not neighbor of itself.</li></ul><ul><li>Output N row order is crucial since row number actually corresponds to the vertex id / index.</li></ul><ul><li>Output N cells content order doesn't matter, but it doesn't admit any duplicated index / value.</li></ul>Tip : solving <a href = "https://fr.mathworks.com/matlabcentral/cody/players/8668631-nicolas-douillet/created">my previous problems</a>, and especially <a href = "https://fr.mathworks.com/matlabcentral/cody/problems/45256-query-a-vertex-neighbors">query_vertex_neighbors</a> will help you to fully understand and solve this one.NB : the question of unreferenced vertices is not tacled here. We just supposed there are not.Good work Matlab-bro ! :)

Solve

Solution Stats

11 Solutions
9 Solvers

Last Solution submitted on Sep 18, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Nicolas Douillet on 10 Jan 2020

Pedagogic solution is available in position 2 (commented, same as solution 1 but more explicit thus suboptimal).

Problem Recent Solvers9

Problem Tags

3d edge face facet find geometry index indices list mathematics mesh mesh processing surface triangle triangulation trimesh triplet vertex vertices

Problem 45261. Query every vertices neighbor indices

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers9

Suggested Problems

More from this Author9

Problem Tags

Problem 45261. Query every vertices neighbor indices

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers9

Suggested Problems

More from this Author9

Problem Tags

Players