Hi, Let's implement the following exciting task.  First have a understanding of the following information : ## K-D Trees

A k-d tree is a binary tree where each node represents a k-dimensional point, and every non-leaf node defines a hyperplane that splits the space into two parts. The hyperplane is perpendicular to one of the k dimensions, and points to the left and right of the hyperplane are represented by the left and right subtrees, respectively. The direction of the hyperplane is chosen based on the dimension associated with the current node. The hyperplane is defined by the value of the associated dimension of the node, and its normal is the unit vector along that dimension's axis.
You are required to build a K-D Tree from your point cloud. You can use SciPy for this.

## Distance Filter Algorithm

The distance filer algorithm is a naive method for downsampling point clouds. It calculates the distance of one point from every other point in the point cloud. If you find any point within distance $d$ of the point under consideration then the point under consideration is removed. To clarify, we remove the point if it falls within the defined neighborhood otherwise we keep the point. 
Do NOT use loops for a brute force search. You are required to use KD-Trees.


## K-Means Clustering

The K-means algorithm identifies a certain number of centroids within a data set, a centroid being the arithmetic mean of all the data points belonging to a particular cluster. The algorithm then allocates every data point to the nearest cluster as it attempts to keep the clusters as small as possible (the ‘means’ in K-means refers to the task of averaging the data or finding the centroid). At the same time, K-means attempts to keep the other clusters as different as possible.  The Folder structure is as follows : lab5
├── data
│   └── SfM_Images
│   |   └── B21.jpg
│   |   └── B22.jpg
│   |   └── B23.jpg
│   |   └── B24.jpg
│   |   └── B25.jpg
│   └── Captured_Images (Images captured by you)
│   |   └── <images in jpg>
│   └── pc(X).ply
├── src
└──  └── <Your_python_scripts>

### Task 2 → 

- Task 2 A → 
Write a python script `cluster.py` that inputs the `pc.ply` pointcloud and clusters it into `N` clusters using the K-means clustering algorithm. If we `cd` into your package and run your code (`python3 src/cluster.py`), it should work.
Implement a  K-means by yourself and not use an in-built implementation, feel free to use numpy for basic operations.
 Once you have your clusters, you need to color the clusters (Fig on right) using Open3D’s paint pointcloud.
 Time your clustering algorithm (you can use timeit or other libraries)
  Add screenshots of your clustering output and time taken to your report-                                                                                                                                                                                                                                                                            
  Task 2 B → (30 points → 25 for downsample + 5 for timing)
    - Write a python script `downsample.py` that inputs a pointcloud and distance thresold `e` and downsamples the pointcloud using the distance filter algorithm explained above.
    - You **MUST** use KDtrees for downsample, you can use the implementation from `scipy`
    - Answer the following questions in your report :
        1. What are KD Trees? 
        2. Why do we use them for pointcloud operations?
        3. What is the time complexity of KD Tree search?
    - Save your downsampled pointcloud as `pc_downsampled.ply`
    - Time your downsampling algorithm (you can use timit or other libraries)
    - Add screenshots of the original point cloud and the downsampled point cloud in your report along with the time taken to downsample
