Solution.md

Identically Connected Colored Components

Question

Find identically-colored connected components in a triangle mesh with Open3D.

Implement a function to return a list of identically-colored connected components. An identically-colored connected component consists of spatially connected vertices with the same color. In this question, a connected component is represented by a list of vertex indices.

Example Triangle Mesh

Algorithm Used:

• Read the mesh.
• Calculate Triangle clusters using ClusterConnectedTriangles() function. Vertices in triangles having same cluster index are connected to each other.
• Find unique cluster indexes form above calculated clusters. Find unique colors of vertices colors.
• Initialize a 2D array of variable vectors, where no. of rows = size of unique cluster indexes and no. of coloumns = size of unique colors.
• Loop over the vertex indexs of triangles belonging to same cluster and check if the vertex color is identical to current unique color.
  • If True, then check if the vertex is already present in the vector, if present, add the vertex index to the vector.
  • Else, continue.
• Sort the vectors ascendingly based on their length.

How to Build

• The C++ function IdenticallyColoredConnectedComponents() with unit test and its Python Binding is integrated with source code and Open3D build system.
• Follow the instructions to build as documented at http://www.open3d.org/docs/release/compilation.html.

Run Unit Test

Run unit tests by running the following command at open3d/build/bin/:

$ ./unitTests

Run C++ Example solution.cpp and Python Example solution.py

• C++ Example solution.cpp is compiled while building Open3D.

  It can be run at open3d/build/bin/examples/ using:

  $ ./solution ../../../examples/TestData/test_mesh.ply 

  results.txt will be generated with formatted results.

• Python Example solution.py at open3d/examples/Python/Basic can be run using:

  $ python3 solution.py 

  results.txt will be generated with formatted results.