---------- Forwarded message ---------- From: Arcadie Cracan <acracan@...400...> Date: Dec 31, 2009 11:36 AM Subject: Re: [Inkscape-devel] Re : Exchange position of two objects To: Krzysztof Kosiński <tweenk.pl@...400...>
Actually the center might be the center of mass ( http://en.wikipedia.org/wiki/Center_of_mass), and, as Krzysztof said, a sort around this center is the way to go. But there is a better approach than using atan2 function. It is described in the Chapter 33 - Computational Geometry in Introduction to algorithms by T. Cormen. It does compare 2 vectors' angle by computing their cross product. As I can see, the angle_sort() function already exists in 2geom (see convex-cover.cpp and convex-cover.h) and it seems that it used to use the atan2() function for angle comparison, but now computes some kind of matrix determinants (that lead to vector slopes I guess). The use of cross products avoids the division operation, so it is faster.
On 12/31/09, Krzysztof Kosiński <tweenk.pl@...400...> wrote:
2009/12/30 bulia byak <buliabyak@...400...>:
But a still better and more useful approach is to dedect a clockwise order, as I wrote before. This may not be always easy, but it's an interesting mathematical challenge. For example: calculate a center point of objects and rotate clockwise a ray from this center, and process objects in the order in which this ray crosses their bbox centers.
This is actually rather simple. Compute the center (this may require learning some not-perfectly-clear API); for each object calculate the vector from the center to that object's center (let's call it relpos) and sort on Geom::atan2(relpos), for example by inserting the SPItem*s into a std::map<double, SPItem*> and then iterating over it. I'm not sure whether it will produce a clockwise or a counterclockwise ordering, because I never remember which one (desktop / document) is the mathematical one :)
Regards, Krzysztof
This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel