The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.
 / 
Math-Vector-BestRotation-0.007
River stage zero No dependents
/ Math::Vector::BestRotation

NAME

Math::Vector::BestRotation - best rotation to match two vector sets

VERSION

Version 0.007

SYNOPSIS

    use Math::Vector::BestRotation;

    my $best = Math::Vector::BestRotation->new();

    $best->add_pair([1, 2, 3], [4, 5, 6]);
    $best->add_pair([0, -1, 5], [-3, 6, 0]);
    .
    .
    .
    $best->add_pair([3, -1, 5], [0.1, -0.7, 4]);

    my $ortho = $best->best_orthogonal;
    my $rot   = $best->best_rotation;
    my $flip  = $best->best_flipped_rotation;

    # start over
    $best->clear;

DESCRIPTION

Assume that you have a list of vectors v_1, v_2, v_3, ..., v_n and an equally sized list of vectors w_1, w_2, ..., w_n. A way to quantify how similar these lists are to each other is to compute the sum of the squared distances between the vectors: sum((w_1 - v_1)**2 + ... + (w_n - v_n)**2). In the literature, this sum is sometimes divided by 2 or divided by n or divided by n and the square root is taken ("root mean square" or RMS deviation).

In some situations, one data set can be arbitrarily rotated with respect to the other one. In this case, one of them has to be rotated in order to calculate the RMS deviation in a meaningful way. Math::Vector::BestRotation solves this problem. It calculates the best orthogonal map U between the v_i and w_i. "Best" means here that the RMS deviation between Uv and w as calculated above is minimized.

An orthogonal map can be a rotation or a rotation combined with a reflection (I call that a flipped rotation). This module enables you to find the best orthogonal map, the best rotation, or the best flipped rotation between two given vector sets.

The algorithm implemented here is based on two research papers listed in the ACKNOLEDGEMENT section. It works for higher dimensional vector spaces as well, but the current implementation supports only three-dimensional vectors. This limitation is going to be remedied in a future version of this module.

The two data sets could not only rotated with respect to each other, but also translated. This translation can be removed prior to the determination of the rotation by aligning the centers of masses of the two vector sets. However, this procedure is not offered by Math::Vector::BestRotation and possibly will never be, because this would require to store the full data sets in memory which is not necessary now.

INTERFACE

Constructors

new

  Usage   : Math::Vector::BestRotation->new(%args)
  Function: creates a new Math::Vector::BestRotation object
  Returns : a Math::Vector::BestRotation object
  Args    : initial attribute values as named parameters

Creates a new Math::Vector::BestRotation object and calls init(%args). If you subclass Math::Vector::BestRotation overload init, not new.

init

  Usage   : only called by new
  Function: initializes attributes
  Returns : nothing
  Args    : initial attribute values as named parameters

If you overload init, your method should also call this one. It provides the following functions:

  • For each given argument (which has not been deleted by the previous actions) it calls the accessor with the same name to initialize the attribute. If such an accessor does not exist a warning is printed and the argument is ignored.

Public Attributes

matrix_r

This attributes holds a matrix built from the pairs of vectors and used to compute the desired orthogonal map. It is called R in the documentation and the underlying Research papers. The accessor is readonly. At startup, matrix_r is initialized with zeros.

Note that the matrix is stored internally as an array to speed up data acquisition. When you call the accessor a Math::MatrixReal object is created. This implies that such an object is not updated as you add more vector pairs. You have to call the accessor again to get a new object. Accordingly, changing of your retrieved matrix does not alter the underlying matrix stored in the Math::Vector::BestRotation object.

Methods for Users

add_pair

  Usage   : $obj->add_pair([1, 2, 3], [0, 7, 5])
  Function: updates matrix_r
  Returns : nothing
  Args    : a pair of vectors, each as an ARRAY reference

The orthogonal map computed by this module will try to map the first vector of each pair onto the corresponding second vector. This method uses the new vector pair to update the matrix R which is later used to compute the best map. The vectors are discarded afterwards and can therefore not be removed once they have been added.

In some applications, very many vector pairs will be added making this the rate limiting step of the calculation. Therefore, no convenience functionality is offered. For example, the method strictly requires ARRAY references. If your vectors are stored e.g. as Math::VectorReal objects you have to turn them into ARRAY references yourself. Furthermore, no error checking whatsoever is performed. The method expects you to provide valid data. See also add_many_pairs.

add_many_pairs

  Usage   : $obj->add_many_pairs([[1, 2, 3], [3, 0, 6]],
                                 [[0, 7, 5], [-2, 1, -1]])
  Function: updates matrix_r
  Returns : nothing
  Args    : a pair of vectors, each as an ARRAY reference

An alternative to add_pair. It expects two lists of vectors. The first one contains the first vector of each pair, the second one contains the second vector of each pair (see add_pair. If you have many vector pairs to add it is probably faster to build these lists and then use this method since it saves you a lot of method calls.

For perfomance reasons, no checks are performed not even if the two lists have equal sizes. You are expected to provide valid data.

best_orthogonal

  Usage   : $matrix = $obj->best_orthogonal
  Function: computes the best orthogonal map between the vector sets
  Returns : a Math::MatrixReal object
  Args    : none

Computes the best orthogonal map between the two vector sets, i.e. the orthogonal map that minimizes the sum of the squared distances between the image of the first vector of each pair and the corresponding second vector. This map can be either a rotation or a rotation followed by a reflection.

The representing matrix of the found map is returned in form of a Math::MatrixReal object.

best_rotation

  Usage   : $matrix = $obj->best_rotation
  Function: computes the best rotation between the vector sets
  Returns : a Math::MatrixReal object
  Args    : none

This is identical to best_orthogonal except that it finds the best special orthogonal map (this means that the determinant is +1, i.e. the map is a true rotation).

The method computes the best rotation between the two vector sets, i.e. the rotation that minimizes the sum of the squared distances between the image of the first vector of each pair and the corresponding second vector.

The representing matrix of the found map is returned in form of a Math::MatrixReal object.

best_flipped_rotation

  Usage   : $matrix = $obj->best_flipped_rotation
  Function: computes the best rotation combined with a reflection
  Returns : a Math::MatrixReal object
  Args    : none

This is identical to best_orthogonal except that it finds the best orthogonal map with determinant is -1. I do not know why one would want that, but the method is included for completeness.

The representing matrix of the found map is returned in form of a Math::MatrixReal object.

clear

  Usage   : $obj->clear
  Function: resets the object
  Returns : nothing
  Args    : none

This method resets matrix_r to the null matrix (all entries equal zero). This enables you to start from scratch with two new vector sets without destroying the object.

DIAGNOSTICS

Exceptions

Sorry, not documented, yet.

Warnings

Sorry, not documented, yet.

BUGS AND LIMITATIONS

Bugs

No bugs have been reported, but the code should be considered as beta quality.

Please report any bugs or feature requests to bug-math-vector-bestrotation at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Math-Vector-BestRotation. I will be notified, and then you will automatically be notified of progress on your bug as I make changes.

Limitations

See DESCRIPTION.

AUTHOR

Lutz Gehlen, <perl at lutzgehlen.de>

ACKNOWLEDGEMENTS

The algorithm implemented here is based on two research papers by Wolfgang Kabsch, Max-Planck-Institut für Medizinische Forschung, Heidelberg, Germany:

[1] Kabsch, W. (1976). A solution for the best rotation to relate two sets of vectors. Acta Cryst., A32, 922
[2] Kabsch, W. (1978). A discussion of the solution for the best rotation to relate two sets of vectors. Acta Cryst., A34, 827-828

LICENSE AND COPYRIGHT

Copyright 2010 Lutz Gehlen.

This program is free software; you can redistribute it and/or modify it under the terms of either: the GNU General Public License as published by the Free Software Foundation; or the Artistic License.

See http://dev.perl.org/licenses/ for more information.

1 POD Error

The following errors were encountered while parsing the POD:

Around line 517:

Non-ASCII character seen before =encoding in 'für'. Assuming UTF-8