---------- Forwarded message ----------
From: Arcadie Cracan <acracan@gmail.com>
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
Inkscape-devel mailing list