Consider 3 dimensional space which has been partitioned by at least two planes which go through the origin. If there are n
planes then the number of distinct pyramidal regions this creates is exactly 2 - n + n^2
as long as they are in "general position", a term I make specific below.
The challenge is write code that will return one point per pyramidal region. That is to return
2 - n + n^2
points in 3d space, each of which is in a different pyramidal region.
Notice that a plane through the origin can be defined by a single vector starting at the origin which is orthogonal to the plane.
Your code should take a list of planes in as input, each plane being described by a vector from the origin which is orthogonal to it. The vector itself is just represented as a space separated list of three numbers. Your should output a list of 2 - n + n^2
points. You can assume the planes are in general position, that is that no three of the vectors defining the planes are coplanar.
I will verify that the points are really all in different pyramidal regions using the following code.
Let us assume the variable planes
contains an array of vectors, each one of which defines the plane. For example, let n = 4, the planes
could equal
[[ 0.44060338 -0.55711491 -0.70391167]
[ 0.15640806 0.89972402 0.40747172]
[-0.48916566 0.86280671 0.12759912]
[ 0.25920378 -0.94828262 0.18323068]]
We can then choose a number of points and put them in a 2d array called testpoints
. To determine if they are all in distinct pyramidal regions we can call the following Python function which just looks to see which side of each plane the points are on and checks that each point is on at least one different side from every other point.
def all_in_distinct_pyramidal_regions(testpoints, planes):
signs = np.sign(np.inner(testpoints, hyperplanes))
return (len(set(map(tuple,signs)))==len(signs))
You can create some random test planes by first sampling points on a sphere and then using those points to define the hyperplanes. Here is a Python function that does this sampling.
import numpy as np
def points_on_sphere(N, norm=np.random.normal):
"""
http://en.wikipedia.org/wiki/N-sphere#Generating_random_points
"""
normal_deviates = norm(size=(N, 3))
radius = np.sqrt((normal_deviates ** 2).sum(axis=0))
points = normal_deviates / radius
return points
You can use any language you choose for which there is a free and easy way to run the code in Linux. You can use any standard libraries of that language. I will however want to test your code so please give full instructions for how to run it.
Code to produce 10 random points on a sphere can be run using http://ideone.com/cuaHy5 .
Here is a picture of the 4 planes described above along with 2 - 4 + 16 = 14 points, one in each of the pyramidal regions created by the planes.
A valid output for this instance would therefore be the 14 points.
0.96716439 0.21970818 0.12775507
-0.84226594 -0.37162037 -0.39049504
0.60145419 0.58557551 -0.54346497
-0.4850864 0.26433373 -0.83355796
-0.69380885 -0.62124759 0.36425364
0.09880807 -0.09275638 0.99077405
0.19131628 -0.97946254 -0.06364919
-0.98100047 0.17593773 -0.08175574
-0.76331009 0.63554838 -0.11591362
0.89104146 0.34728895 0.29229352
-0.61696755 -0.26411912 0.74134482
0.18382632 -0.03398322 -0.98237112
-0.44983933 -0.18244731 0.87427545
0.8391045 0.18244157 -0.51246338
6 faces + 8 corners + 12 edges = 26 infinite regions
) which don't match your formula (2-6+36=32
) so the only thing I could guess you might mean seems wrong. Please clarify. \$\endgroup\$