0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You will first have to identify your regions by changing the plane equations to inequalities. Then for each point just check which set of inequalities it satisfies. Also, this question is more suitable for math.stackexchange.com $\endgroup$ – Abhishek Bansal Sep 18 '14 at 13:07
  • $\begingroup$ Could you elaborate more on that? I'm not seeing how this inequalities would help me. I thought this would be the best place since this question was proposed in the last programming contest here in Brazil, so I supposed it would have an algorithm for this. $\endgroup$ – Danimar Ribeiro Sep 18 '14 at 13:18
  • 1
    $\begingroup$ It will be easier if you visualise the problem in 2-D. Say you have 10 lines randomly placed and oriented in space. Then those lines shall form polygons (some closed, some open). Each polygon shall be defined by a set of in-equalities. Then pick up each point and check which set of inequalities that point satisfies. I suggested you to post this on math.stackexchange because IMO you have a better chance of getting good answers for this question there. $\endgroup$ – Abhishek Bansal Sep 18 '14 at 13:23
  • $\begingroup$ I'll check about the inequalities, despite I'm studying physics I'm still not confortable with some math problems. I posted there math.stackexchange.com/questions/936502/… $\endgroup$ – Danimar Ribeiro Sep 18 '14 at 13:48
  • $\begingroup$ Maybe convex-hull algorithms can help? $\endgroup$ – Raphael Sep 18 '14 at 14:00
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What's the complexity of this? denoting m planes and n points, this would give O(mn) ? $\endgroup$ – Danimar Ribeiro Sep 20 '14 at 3:07
  • $\begingroup$ Added a note on the running time. See updated answer. $\endgroup$ – A.Schulz Sep 21 '14 at 7:55
2
$\begingroup$

A plane divides the 3D space in two regions. A good method to discern is to apply the plane equation to the point and see if it yields negative or positive result:

$$Ax + By + Cz + D = 0$$

is the equation of a plane in 3D. So if you put the point coordinates you'll get a positive, zero or negative number. (If zero, the point belongs to the plane and so, it's neither in either side of the plane.)

The question asks to count the points that belong to each of the delimited regions for each plane. Well, you have n planes each dividing the space in two halves (so you have $2^n$ regions at most, except in case you have paralell planes, but this procedure is applicable also in that case ---you'll get regions not accounted for as no point can lie in them), just consider each point and apply it to each plane. Then construct a number X, making bit $i$ (for plane $i$) of X a 1 in case applying plane to it gives a positive number and 0 in case applying it gives a negative one (in case it returns 0 you have to decide what side to count it ---what value you select for bit $i$--- for (if any) as this is a point that belongs to the plane) then with that number as a key for region X, increment counter of region X selected, so in one pass over all points you'll get all counters actualized with how many points belong to each region. Each key X, so constructed, identifies each of the possible regions you have divided the space into, so you must cope with $2^n$ regions (and counters) for $n$ planes.

$\endgroup$
  • $\begingroup$ Sorry, I didn't get the last part. I don't see how to use the key to identify the region. $\endgroup$ – Danimar Ribeiro Sep 20 '14 at 20:43
  • $\begingroup$ you need a table, indexed by a number of n bits, with a counter in each entry. Suppose you have three planes A, B and C. You associate each plane one bit in a number... so key [000] is the region of space in which all points satisfy the plane eq with negative values, [001] is the region of space that satisfies all the planes but the last with negative values, and so on. $\endgroup$ – Luis Colorado Sep 21 '14 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.