I have for example 10 planes with their equation: Ax + By + Cz = D and a list of 3D points.Those plane can make regions, some of them closed, and others not, the task is to count the number of points in each region.I just need some ideas about how to solve, or if there is an algorithm for that.
Count points enclosed by several planes in 3D space
algorithms;computational geometry
Each of the plane can be considered as a constraint which might hold with =, <, or >. A point lies either on the plane or on one of the sides. This can be decoded by a +, - and 0. Say the string +++++----- decodes the cell for which the first 5 constraints hold with >, and the last 5 with <.You can now go through all the possibilities. Start with the first plane and filter the points with respect to this plane. You will get three sets. Then use recursion to subdivide the sets further. If the recursion stops (that is you processed the 10th plane), you count the remaining set.Regarding the running time. If you have $n$ points and $m$ planes then$$ T(n,m)= T(n_1,m-1)+T(n_2,m-1)+T(n_3,m-1) + O(n)$$for $n_1+n_2+n_3=n$. This solves to $O(nm)$. You can use induction on $m$ to prove this.