I need to store a 6d set of double points on a torus and query the nearest neighbors. I believe the distance algorithm isn't too hard to implement by simply using the angle difference on each axis:
However, I'm not sure if r-tree could handle that or how to set it up. Could you provide advice? Would I need to implement an entirely new distance strategy? I believe the basics should work with boost geometry model points because I should only be storing, querying, and taking the distance between points which if I recall correctly are among the basics implemented for higher dimensions. Thanks for your help. Andrew Hundt _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Hi Andrew.
On 02/04/2015 06:51 πμ, Andrew Hundt
wrote:
I would like to understand better what you have in mind: are you going to be using the first two coordinates of these points for the distance computation? The remaining 4 coordinates are just some other data?
I will leave it up to Adam to talk about the r-tree in detail, but let me add 2c about this. the r-rtree does not work properly right now for points on the spherical coordinate system. The reason is that the current implementation of boxes does not take into account the periodicity of the underlying space (I mean the sphere here parametrized through longitude latitude).
Well this is almost true (see also my question above). In order to use the r-tree for nearest neighbor queries you need to be able to compute the envelope of (subsets of) your points, and be able to compute the distance of a point (the query point) to both another point and a box. as I mention above the problem is with respect to the computation of the envelope (box) of a set of points. Some "good" news: I am currently working on implementing envelope calculation for points on a sphere. On the other hand, defining what a box is on the sphere is not as straightforward as in the Cartesian case, so this is another issue to be taken care of. I meant to, and will, send an email to the list about this, and everybody on the list will have the chance to comment on it. Best, - m.
_______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Hi Andrew, Menelaos,
Menelaos Karavelas wrote: Hi Andrew. I think it's a 3d position with 3d orientation but I'm not sure what does Andrew have in mind by saying that the points are on a torus. In general case of points on some 3D surface (let's consider a sphere) the points can be stored in cartesian 3D or the coordinates could be mapped into the 2D surface, e.g. lat/lon for a sphere/spheroid. And AFAIS (http://en.wikipedia.org/wiki/Toroidal_coordinates) in the case of a torus one could also use 3d toroidal coordinates. If you have 3d points I'm assuming they're already in 3D cartesian or toroidal so you could just store them in the rtree as 3D cartesian points (since we doesn't have toroidal CS). An alternative would be to map them to the surface of a torus using some projection and then store them as 2d points in the rtree. In case you had points defined in toroidal CS, you could consider adding this CS to the Boost.Geometry, implementing all of the required algorithms/strategies for this CS, etc.
This shouldn't be a problem. The points would be stored in the different parts of the tree but if the predicates like distance/intersection/etc. was calculated properly (so taking the periodicity into account) the result would be correct. I'm talking about spherical CS. I think that for 3d toroidal it could also apply but I should think more about it. Now, I'm guessing the problem is the distance calculation, because it must be the shortest distance on the surface of a torus, not in 3D cartesian space. Do I get it right? In case if the distance could be the simple 3D cartesian distance it should work out of the box. As you probably know the rtree stores the points and bounding boxes. If the points was 3d cartesian points then the boxes would be 3d cartesian boxes. If the points was mapped into the 2d surface then the boxes would also lie on this surface (as spherical lon/lat or 3d cartesian). During the nearest query the rtree checks shortest distances to bounding boxes and values (points) stored in the rtree. So if you wanted to find the closest points to some point the rtree would need to call both: bg::comparable_distance(query_point, bounding_box) bg::comparable_distance(query_point, value_point). So you could just overload both of those functions for e.g. some specific type of query_point and do the math there.
AFAIU the points are on a surface of a torus, not a sphere? But the cases are similar indeed. Since we doesn't have a torus coordinate system you could use cartesian and store the points either in 3d or 2d. They'd be indexed as cartesian points without taking into account the periodicity. Then you could use some "special" query point type and pass it into the nearest predicate. Then force the rtree to calculate the distances the way you like by overloading bg::comparable_distance(). Or you could consider contributing the support for another coordinate system. Regards, Adam _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Adam Wulkiewicz wrote:
Those 2d coordinates could be phi (toroidal angle) and theta (poloidal angle) (http://fusionwiki.ciemat.es/wiki/Toroidal_coordinates). They could be stored in the rtree as 2d cartesian points but you'd still have to implement your own distance function (see below). On a torus those angles would probably both be in range [-pi, pi] and both would have periodical nature (like longitude in spherical and geographical coordinate systems). Now it depends, how precise must the distance be. You could calculate a simple cartesian distance of those coordinates (treating them as cartesian) but taking the periodicity into account. This however wouldn't be the "true"/shortest distance between points or between a point and a box on the surface of a torus, defined by geodesics. For this you'd probably have to approximate it somehow through integral expression, newton's method, taylor series, etc. The results of a quick search for the definition of geodesics on torus: http://www.rdrop.com/~half/math/torus/torus.geodesics.pdf http://www34.homepage.villanova.edu/robert.jantzen/notes/torus/torusgeos.pdf Regards, Adam
_______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
On Thu, Apr 2, 2015 at 9:43 AM, Adam Wulkiewicz <[hidden email]> wrote:
I'm using a 2 arms, one 6 degree of freedom and the other 7 dof with revolute (rotating) joints. The position of the arm can be accurately represented as an n-d point representing the angle of each joint, with no need for orientation/pose on the surface of a torus, with 1 dimension for each joint. Here is a simple image explaining the 2d case: Therefore I don't need to worry about orientation but probably just the envelope/box which I believe is used for the data structure and the points themselves.
As detailed above, this means in my current use case I can skip theta.
I may be mistaken, but I believe the distance can be calculated by taking the angular distance separately in each dimension as linked previously, and listing them as a single tor_dist_vec, then take the sqrt(element_sum(tor_dist_vec)). Since all the distances will always be between [0,pi] I believe this will work correctly.
Thanks, these look like good links. Right now I only plan to use the coordinates to find the k nearest neighbors in cartesian space, but the information is useful to have.
I might be interested in doing this eventually. Are the instructions you have in that github repository under your account sufficiently up to date for me to follow in getting set up? https://github.com/awulkiew/temp-contributing Thanks! Andrew Hundt _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Andrew Hundt wrote:
<snip>
Ok, if I understand you correctly you would like to represent a configuration of an arm (N angles) as a point (N coordinates), store those points in the rtree and then use it to search for the closest known configuration. If representing the configuration in 6d cartesian space is enough for you (which AFAIU is the case) then you just may store tham in the rtree as they are. Now the question is, can the joints rotate infinitely or not (because of some mechanical limitations)? I.e. can a joint go from angle 0 to 2pi and then further so again jump to 0 and go to 2pi, etc.? If the answer is no and the joint must go back then cartesian representation is all you need. But if the answer is yes then the cartesan representation is not really correct, since the angles may wrap around the edges 0 <-> 2pi or -pi <-> pi and you should be able to find the closest distance if it was on the other side of the range. So indeed we have a torus, for 2 joints -> 2DoF -> 3D torus, so I'm guessing that 6 joints -> 6Dof -> 7D torus. In this case simple cartesian distance won't be sufficient because in any of those dimensions the coordinates can wrap around the edge, so you must take it into account. Which means that for each coordinate that can wrap you need to calculate a normalized signed difference in a range [-pi, pi] and calculate a distance using this value. For non-wrapping coordinate you just need a regular, not-normalized difference. Furthermore this can be a cartesian comparable_distance, so there is no need to calcualte the sqrt(). A sum of elements probably won't do the trick, you need a dot product so a sum of squares. This'd look like this in pseudo-code: dot = 0; foreach ( D ) // you need to use a recursive template for this { diff = get<D>(p2) - get<D>(p1); if ( is_wrapping ) normalize(diff); // to range [-pi, pi] dot += diff * diff; } return dot; // comparable_distance Now, the above is for point-point distance. Note that this may not be the "correct" distance on a torus' surfce just like a cartesian distance of angular coordinates is not the "correct" distance on a sphere. I put the word "correct" in the quotes because what's correct depends on the case I guess. But let's back to the subject. You also need similar implementation for point-box, so for each dimension first check if a point is closer to min, max or between them and then use the diff (min<D> - p<D>), (p<D> - max<D>), or 0 respectively. Again normalizing if the coordinates can be wrapped. In the case of cartesian points stored in the rtree, nodes' bounding boxes will also be cartesian so exactly in the same range [0, 2pi] with min <= max. So there shouldn't be any additional problems with wrapping (this is true only for points stored in the rtree!). But if needed, normalize the box and point before checking if the point is between min and max, they must be represented somehow uniformly. If some joints could be rotated e.g. only N times I'm guessing you could represent them by having the coordinates in the range [0, N*2pi] without wrapping. Putting all of this together: // define a separate point for this specific arm in order to calculate the distance specifically for it. struct arm_6dof_pos { /*...*/ }; // register the above as 6D cartesian point namespace boost { namespace geometry { double comparable_distance(arm_6dof_pos const& p1, arm_6dof_pos const& p2) { // calculate the point/point distance (above) } template <typename Box> double comparable_distance(arm_6dof_pos const& p, Box const& b) { // calculate the point/box distance } }} // namespace /*...*/ rtree<arm_6dof_pos, ...> tree; /*fill the rtree*/ arm_6dof_pos query_pos(/*...*/); tree.query(nearest(query_pos, 1), out); I hope that I understand your problem correctly and that the above is clear enough. Please let me know about the outcome, it's very interesting!
Yes, those are the instructions about the worflow we use at Boost.Geometry, how to work with modularized Boost, GitHub, etc. As states on this page, the more recent version can be found in the Boost.Geometry wiki: https://github.com/boostorg/geometry/wiki/Contribution-Tutorial Regards, Adam _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Adam Wulkiewicz <[hidden email]> wrote: <snip>
Thanks for the starter explanation! I'm trying to instantiate things as you described, but I'm running into an issue with NOT_IMPLEMENTED_FOR_THIS_POINT_TYPE. I'm basically mixing the geometry graph example with some of the rtree examples and your description. The rtree is accelerating my graph creation process so I can eventually do a shortest path search on it. All the important details and the compiler error are in this gist: // use boost::array as the type we will adapt #include <boost/geometry/geometries/adapted/boost_array.hpp> // ... // I instantiated the torus comparisons: // perhaps these aren't overload correctly or the boost_array include causes conflicts? namespace boost { namespace geometry { double comparable_distance(ArmPos const& p1, ArmPos const& p2 ) ; template<typename Box> double comparable_distance(ArmPos const& armpos, Box const& box ); }} // I define types for the vertex and edge properties (see gist) // I define all the types necessary to create the rtree and graph //typedef bg::model::point<double, 3, bg::cs::cartesian> point; typedef boost::array<double,6> ArmPos; typedef ArmPos point_type; typedef bg::model::box<point_type> box; typedef bg::model::referring_segment<point_type> line_type; //typedef bg::model::polygon<point, false, false> polygon; // ccw, open polygon typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS , bg_vertex_property<point_type> // bundled , bg_edge_property<line_type> > graph_type; typedef boost::graph_traits<graph_type>::vertex_descriptor vertex_type; // I expected that the point_type of the pair would be seen as implemented // I also expected that the vertex_type would simply be data not utilized, // which I believe is true in the case of a simple <point,int> like in the quick start typedef std::pair<point_type, vertex_type> rtree_value; typedef boost::geometry::index::rtree<rtree_value,bgi::rstar<16, 4> > knn_rtree_type; // I instantiate the rtree + graph and get a compiler error void instantiate_rtree_and_graph(){ // comment these two lines to "fix" compiler error graph_type graph; knn_rtree_type rtree; } The key line of the error I got, which I didn't expect was:
I expected it to work like one of the examples of default value types where the first item is indexed and the second is data such as: boost::tuple<geometry::model::point<...>, int, float> Any help you might be able to provide with getting the templates to resolve correctly would be appreciated! I also appreciate that you find my use case interesting :-) Cheers! Andrew Hundt _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
2015-04-05 5:58 GMT+02:00 Andrew Hundt <[hidden email]>:
<snip>
You probably didn't adapt ArmPos to Point concept properly. You should call e.g.: BOOST_GEOMETRY_REGISTER_BOOST_ARRAY_CS(cs::cartesian) see: http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/reference/adapted/boost_array.html or use: model::point<double, 6, cs::cartesian> instead. Regards, Adam _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Free forum by Nabble | Edit this page |