minBoundingBox

A minimum bounding box solver employing principal component analysis (PCA). I coded all the math from scratch including building up a matrix library, and necessary statistical analysis functions for computation of eigenvalues and eigenvectors for 2x2 and 3x3 matrices. The 3X3 eigenvalues are computed using the Faddeev–LeVerrier algorithm, and the Cardano's equation. The 3X3 eigenvectors are computed using Gaussian Elimination. Works with both 2D and 3D point clouds, and meshes! This is an exercise in mathematical curiosity!

#statistics #linear-algebra #unsupervised learning #ML #applied-maths #3d #geometry

Highlights

• No external libraries such as numpy/scipy are used.
• The solution is completely in Python, with no library calls.
• The algorithm is integrated inside Rhino 3d, using the Rhinocommon API.

Intent

• I'm curious about learning how algorithms work!
• Hence, this exploration employing matrices, and linear algebra!
• Rhino v7 doesnot support scientific computing libraries natively, as it runs IronPython. So i wrote a matrices and statistical library, and implemented eigenvalue and eigenvector solvers to emable computation of 2x2 and 3x3 matrices!

Pseudocode

• Math
  • Construct a 2D Data Matrix.
  • Compute the Covariance Matrix.
  • The current implementation considers a sample population, so all computations as (N-1).
  • Solve the Linear Equation System obtained by subtracting the Lambda from the variances in the Covariance Matrix (across the diagonal of the matrix). Solve the linear equation system to obtain the eigenValues.
  • Now, compute the eigenVectors.
  • The eigenvectors are the principal components of the 2D data. They span across the directions of minimum and maximum variance in the dataset.
• Geometry
  • The extents of the dataset along the two principal components is derived by associatively sorting the Projections of the dataset with the projection formula on the respective PC vectors, and their respective projections (dot products).
  • Finally, some simple Rhinocommon gymnastics to compute bounding box geometry from the obtained information above.
  • Done!

References

• Websites
  • The Mathematics Behind Principal Component Analysis
  • What is the purpose of subtracting the mean from data when standardizing?
• Videos (YouTube)
  • ultra-cool
    • Principal Component Analysis- YouTube Playlist by Victor Lavrenko | 2014
    • COVARIANCE AND VARIANCE - YouTube Playlist by Michel van Biezen | 2021
  • cool
    • StatQuest: Principal Component Analysis (PCA), Step-by-Step by Josh Starmer | 2018
    • StatQuest: PCA main ideas in only 5 minutes!!! by Josh Starmer | 2017
    • Principal Component Analysis (PCA) by Luis Serrano | 2019
    • The applications of eigenvectors and eigenvalues- That thing you heard in Endgame has other uses by Zach Star | 2019
    • The Applications of Matrices | What I wish my teachers told me way earlier by Zach Star | 2019
    • Eigenvectors and eigenvalues | Chapter 14, Essence of linear algebra by 3Blue1Brown | 2016
  • also cool
    • Principal Component Analysis (PCA) by Steve Brunton | 2020
    • Principal Components Analysis - Georgia Tech - Machine Learning by Udacity | 2015
    • Principal Component Analysis (PCA) by Visually Explained | 2021
    • PCA : the basics - simply explained by TileStats | 2021
• Concept Basics
  • Specific Searches
    • Google: eigenvector computation by hand
      • Eigenvector - Definition, Equations, and Examples | ByJus
      • ❖ Finding Eigenvalues and Eigenvectors : 2 x 2 Matrix Example ❖ by patrickJMT | 2014
      • lecture14.pdf | Introduction to Numerical Methods and Matlab Programming for Engineers | Department of Mathematics at Ohio University | 2023
  • Books
    • A Sampler of Useful Computational Tools for Applied Geometry, Computer Graphics, and Image Processing by Daniel Cohen-Or, Chen Greif, Tao Ju, Niloy J. Mitra, Ariel Shamir, Olga Sorkine-Hornung, Hao (Richard) Zhang | 2015
    • Linear Algebra for Everyone by Gilbert Strang | 2020
    • Geometry for Programmers by Oleksandr Kaleniuk | 2023
    • Coding The Matrix: Linear Algebra Through Computer Science Applications by Philip Klein | 2013

---

2D BOUNDING BOXES!


GIF 1
2D bounding boxes: on shape point clouds

GIF 2
2D bounding boxes: on point clouds

---

3D BOUNDING BOXES on Point Clouds!


IMG A
3D bounding boxes: on point clouds: principal symmetry planes!

GIF A
3D bounding boxes: on point clouds: principal symmetry planes!


GIF B
3D bounding boxes: on point clouds: bounding boxes on kettle geometries



IMGs B,C,D
3D bounding boxes: on point clouds: bounding boxes on kettle geometries

---

3D BOUNDING BOXES on Meshes!


IMG E
3D bounding boxes: on Meshes: bounding boxes on kettle geometries

IMG F
Screenshot from Rhino3D with the PCA integrated with Rhinocommon to report & augment geometries

---

Note
[1] GIFs scaled for viewing on a mobile phone.
[2] 3d meshes sourced from here .

---

Favourite Book Covers!