Click on "VISUALIZE" to visualize the simplicial depth of each region. The depth is represented by height in the z-axis
Click on "TOPVIEW" to see the point set from the top after VISUALIZE
Click on "RESET" to input a new set of points.
Options
GRID - toggles the grid
DETAIL - toggles mouse tip
Overview
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.
Algorithm
The Algorithm is broken down into steps
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)
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)
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)
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
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
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
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
