Add discretization type for sample object

[smattis]

I am finally having time to work on my side of version 2, and I was thinking that for sample objects we should have a discretization type. Right now, we are kind of assuming all sample objects are Voronoi tesselations. Especially for defining output probabilities sample objects we don't always want to deal with Voronoi tesselations. I would propose we add at least 2 more:

• Cartesian grids (where the inputs are the same as for meshgrid in Numpy
• Balls (there is a radius and norm type for each value)
  We also probably should have the modified Voronoi tesselations not based on the 2-norm like we were discussing as well. Then, I propose having a "query" function for the sample object. For Voronoi it will query the kdtree, and for balls and grids we can calculate with cell(s) a point is in very quickly.

This will basically let us get rid of voronoiHistogram altogether. Thoughts? @lcgraham

[lcgraham]

Would you propose a sample_set base class from which cartesian_sample_set, voronoi_sample_set, and ball_sample_set all inherit? We would then add an additional method called query(x, p) for the sample_set object, where x is a numpy array and 0<p<=infinity. In this configuration voronoi_sample_set would have still get/set methods for kdtree, but there would also be a query(x, p) method. Currently, all the **_ptr methods in bet.sample.discretization can handle Voronoi tesselations for any p-norm, but the norm is specified in the method call (issue #157 ).

I would suggest that we add p (int indicating a p-norm) as an attribute to discretization objects regardless of the type of sample_set objects that input and output are. This is the p what will be used in the **_ptr methods. Otherwise, the user should be able to specify any p.

Is the ball_sample_set the discretization discussed in issue #160 ? These would be the ones defined by a radius in addition to a p-norm.

Technically, grid could/should inherit from ball_sample_set since they are regularly spaced balls with the infinity p-norm that are closely packed. If either input or output are grid_sample_set objects then p should be automatically set to infinity.

I think we will still need some form of voronoiHistogram because we still want to be able to exactly calculate volumes for orthogonal grids which are not regularly spaced (like [http://geo.mff.cuni.cz/~io/con96/con9601.gif].) However, if the grids were bounded then we wouldn't need a good deal of the code in voronoiHistogram which places extra points around the interior grid to bound the voronoi cells that they generate. Thoughts?

[smattis]

Yes, I think we have a sample_set base class that they all inherit from. I like your idea for the query function. I will work on doing that.

ball_sample_set is kind of like that in issue #160, and yes, it would be defined with a radius and a norm. We could also add an ability to scale different dimensions.

Yes, I agree that topologically a cartesian grid is just a bunch of balls, but I don't think we should use inheritance here. The way we would do query for them would be completely different, so there is no algorithmic reason to do that.

[lcgraham]

I agree that grid_sample_set should not inherit from ball_sample_set since query would be completely different. Sounds like a good plan.

[lcgraham]

I think the "distance_upper_bound" KDTree.query(x, k=1, eps=0, p=2, distance_upper_bound=inf) option is an already implemented version of what we are looking for in ball_sample_set. This is were we would supply the radius.

[lcgraham]

This might also be useful http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Rectangle.html#scipy.spatial.Rectangle

[smattis]

In the next few days, I will be doing another pull request to v2_master adding new types of sample sets.