---------- Forwarded message ----------

From:

Date: Dec 31, 2009 11:36 AM

Subject: Re: [Inkscape-devel] Re : Exchange position of two objects

To: Krzysztof Kosiński <tweenk.pl@gmail.com>

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@gmail.com> wrote:

2009/12/30 bulia byak <buliabyak@gmail.com>:

> 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