Re : Exchange position of two objects
---------- 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
On Dec 31, 2009, at 1:37 AM, Arcadie Cracan wrote:
---------- 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
So, we hit the fun for "center" vs. "centroid", etc.
:-)
W dniu 31 grudnia 2009 10:37 użytkownik Arcadie Cracan <acracan@...400...> napisał:
The use of cross products avoids the division operation, so it is faster.
This is an interactive action that most likely won't be used in batch mode thousands of times, so as long as it takes less than 50ms, it is practically instantaneous to the user. In such a situation, performance should take a back seat to clarity and maintainability.
For example, I used a trivial pairwise nearest neighbor algorithm in the node tool, which is O(n^3), to determine which pairs of nodes should be joined. It's just very unlikely someone is going to regularly join 10,000 nodes in one step. On the other hand, when using a more involved algorithm it is easier to create a non-obvious bug; and other developers will want to read, bugfix or modify my code, so all else equal it makes sense to make life easier for them.
I expect centroid computations to take much more time than the order computation. So all in all, I think the immediate clarity of the atan2 approach is preferable to using less obvious optimized approaches that will not result in any tangible performance gain.
Of course in the end, the implementor decides :)
Regards, Krzysztof
On Dec 31, 2009, at 2:18 AM, Krzysztof Kosiński wrote:
This is an interactive action that most likely won't be used in batch mode thousands of times, so as long as it takes less than 50ms, it is practically instantaneous to the user. In such a situation, performance should take a back seat to clarity and maintainability.
Actually, it's even better than that.
Standard usability holds that 100ms is the threshold for users noticing an operation.
For scripting that might also hold to at least as good. That is, if we have it so fast that a user won't notice, then running in a script will probably be acceptable as well. Of course, for that we really need data on ranges of complexity, power of machine, etc. that might be encountered.
participants (3)
-
Arcadie Cracan -
Jon Cruz -
Krzysztof Kosiński