Fork me on GitHub

Visualizing Simplicial Depth

by Hui Han Chin, Junjie Liang
Overview / Algorithm / Download


  1. Click on grid to add points.
  2. Click on a point to remove it.
  3. Click on "VISUALIZE" to visualize the simplicial depth of each region. The depth is represented by height in the z-axis
  4. Click on "TOPVIEW" to see the point set from the top after VISUALIZE
  5. Click on "RESET" to input a new set of points.


  • GRID - toggles the grid
  • DETAIL - toggles mouse tip


Given a set of points P,a nd a query point Q, the simplicial depth of Q with respect to P is the number of simplices formed by P that contains Q. In the 2-D case, the simplex would be a triangle and the simplicial depth of a point would be the number of triangles that contained that point. Simplicial depth give raise to a notation of "deepness" of a point in a point set.


The Algorithm is broken down into steps

  1. Given a point set P of size n, compute all possible lines segments that can be formed. This can be done in O(n^2)
  2. Compute the convex hull of P. Any point that lies outside the convex hull has depth 0. This can be done using Graham Scan in O(n log n)
  3. Compute every intersection of any pair of lines and we pertube the point of interesection slightly to get a new set of point that lies in some small distance from the original distance. These points would be used to represent the regions that has the intersection point as a vertex and the lines as edges. This can be done in O(n log n)
  4. For each of the "pertubed" points we compute the "color" of the point,a number which represents the number of lines where the point is infront of. We can check this using CCW
  5. Next we compute the simplicial depth of the points and any point that is in a face that has such a pertubed point will have the same simplicial depth as that point
  6. For every point in the convex hull we "color" the point and obtain its simplicial depth by looking the pertubed points which shares the same color
  7. The depth of each point is then visualized as the height in the Z-axis. The deeper a point, the higher it is in the Z-axis


$ git clone git://

get the source code on GitHub : hchin/15456-Project-1