I'm trying to come up with a generalised algorithm for detecting whether a point lies within or on the boundary of a m-dimensional hyperrectangle defined using intervals.
For a 2D-case it is straight-forward and one can if point lies within a polygon using techniques such as ray-casting. However, how would one check for an m-dimensional hyperrectangle? Is there a way of say equation such a hyperrectangle and checking whether point lies within or on the boundary?
I'm trying to implement this in C++, are there any known libraries that may help?
Thanks! Help much appreciated!
If you have the hyperrectangle (HR) stored as a combination of intervals (i.e. center coordinate + extent or beginning + end) and rotations, you can transform the query point into the coordinate system of the HR (through appropriate rotation, translation and scaling). Then you only have to do 2*m
bound checks.
Your suggested alternative of using a polyhedron is potentially a performance hog because an m-dimensional HR has 2^m
corner points.
(This is of course assuming you are not restricting yourself to axis-aligned boxes, in which case the answer is of course trivial)