Given a list of coordinates representing points in a 3D object, how can I split those points into 4 quadrants? The quadrants are defined by planes across the two diagonals when looking at the x-y plane from above.
A visual description is given here.
Context:
I have a set of data points representing points in space inside some object. Typically this object has a rectangular cross section with some hole through the middle (containing no points). Think of these points as nodes in a finite element analysis or positions in a finite difference analysis.
Purely from this set of data points I am interested in dividing the points into 4 quadrants defined by two planes through the opposite diagonals – lets say the diagonals in the x-y plane, extending through the object for all of Z.
Attempt:
I believe my starting point is to locate the corners of the object along the planes I am interested in. This gives me 4 data points for each of my two planes.
The next step seems to be defining a normal vector to the plane and performing a cross product of the difference between a specific point, A a point in the plane B and the normal vector i.e dot(A-B,N). I believe the resulting sign would describe which side of the plane point B is located at.
This would allow me to split the data in half along the diagonal and sort the points into two halves. In principle the next step would be to repeat this process along the other diagonal.
However, when performing this task computationally, the initial division leaves only two guaranteed points for the second plane which isn't enough to define the subsequent plane.
I am unsure how to find the normal vector for my plane or how to divide the points into the quadrants I'm interested in.
It would also be useful to be able to find points which lie exactly on the plane however I think that is achievable using Boolean logic once I have a mathematical description of my plane.
I have searched extensively but the related threads I managed to find weren't helpful.
Best Answer
Though the exact geometry of your problem is unclear, you can probably proceed as follows: to find the "corners", determine the points with largest $x+y+z$, $x+y-z$, $-x-y+z$ and $-x-y-z$, which define a first plane, and largest $x-y+z$, $x-y-z$, $-x+y+z$ and $-x+y-z$ for the second. If the corners do not achieve the extreme $z$, you can instead find the extreme $\pm x\pm y$ and then the $(x,y,z)$ points that achieve these values most closely.
Four points are too much to define a plane, and you can discard one for each plane. Then the equation of a plane by three points is
$$\begin{vmatrix}x&y&z&1\\x_a&y_a&z_a&1\\x_b&y_b&z_b&1\\x_c&y_c&z_c&1\\\end{vmatrix}=0,$$ also written $$\begin{vmatrix}x-x_a&y-y_a&z-z_a\\x_b-x_a&y_b-y_a&z_b-z_a\\x_c-x_a&y_c-y_a&z_c-z_a\\\end{vmatrix}=0,$$ and this determinant is positive or negative on either side of the plane.
To split your point set, it suffices to classify according to the signs of the two determinants defined by the two planes. The handling of the zero cases (if any) is up to you.