File perl-Algorithm-QuadTree.spec of Package perl-Algorithm-QuadTree

Overview Repositories Revisions Requests Users Attributes Meta

File perl-Algorithm-QuadTree.spec of Package perl-Algorithm-QuadTree

#
# spec file for package perl-Algorithm-QuadTree
#
# Copyright (c) 2022 SUSE LLC
#
# All modifications and additions to the file contributed by third parties
# remain the property of their copyright owners, unless otherwise agreed
# upon. The license for this file, and modifications and additions to the
# file, is the same license as for the pristine package itself (unless the
# license for the pristine package is not an Open Source License, in which
# case the license is the MIT License). An "Open Source License" is a
# license that conforms to the Open Source Definition (Version 1.9)
# published by the Open Source Initiative.

# Please submit bugfixes or comments via https://bugs.opensuse.org/
#

%define cpan_name Algorithm-QuadTree
Name:           perl-Algorithm-QuadTree
Version:        0.5
Release:        0
License:        Artistic-1.0 OR GPL-1.0-or-later
Summary:        QuadTree Algorithm class in pure Perl
URL:            https://metacpan.org/release/%{cpan_name}
Source0:        https://cpan.metacpan.org/authors/id/B/BR/BRTASTIC/%{cpan_name}-%{version}.tar.gz
Source1:        cpanspec.yml
BuildArch:      noarch
BuildRequires:  perl
BuildRequires:  perl-macros
%{perl_requires}

%description
Algorithm::QuadTree implements a quadtree algorithm (QTA) in pure Perl.
Essentially, a _QTA_ is used to access a particular area of a map very
quickly. This is especially useful in finding objects enclosed in a given
region, or in detecting intersection among objects. In fact, I wrote this
module to rapidly search through objects in a Tk::Canvas widget, but have
since used it in other non-Tk programs successfully. It is a classic
memory/speed trade-off.

Lots of information about QTAs can be found on the web. But, very briefly,
a quadtree is a hierarchical data model that recursively decomposes a map
into smaller regions. Each node in the tree has 4 children nodes, each of
which represents one quarter of the area that the parent represents. So,
the root node represents the complete map. This map is then split into 4
equal quarters, each of which is represented by one child node. Each of
these children is now treated as a parent, and its area is recursively
split up into 4 equal areas, and so on up to a desired depth.

Here is a somewhat crude diagram:

------------------------------
                  |AAA|AAB|       |              |
                  |___AA__|  AB   |              |
                  |AAC|AAD|       |              |
                  |___|___A_______|      B       |
                  |       |       |              |
                  |       |       |              |
                  |   AC  |   AD  |              |
                  |       |       |              |
                   -------------ROOT-------------
                  |               |              |
                  |               |              |
                  |               |              |
                  |      C        |      D       |
                  |               |              |
                  |               |              |
                  |               |              |
                   ------------------------------

Which corresponds to the following quadtree:

__ROOT_
                       /  / \  \
                      /  /   \  \
                _____A_  B   C   D
               /  / \  \
              /  /   \  \
        _____AA  AB  AC  AD
       /  / \  \
      /  /   \  \
    AAA AAB AAC AAD

In the above diagrams I show only the nodes through the first branch of
each level. The same structure exists under each node. This quadtree has a
depth of 4.

Each object in the map is assigned to the nodes that it intersects. For
example, if we have an object that overlaps regions _AAA_ and _AAC_, it
will be assigned to the nodes _ROOT_, _A_, _AA_, _AAA_ and _AAC_. Now,
suppose we want to find all the objects that intersect a given area.
Instead of checking all objects, we check to see which children of the ROOT
node intersect the area. For each of those nodes, we recursively check
_their_ children nodes, and so on until we reach the leaves of the tree.
Finally, we find all the objects that are assigned to those leaf nodes and
check them for overlap with the initial area.

%prep
%autosetup  -n %{cpan_name}-%{version}

%build
perl Makefile.PL INSTALLDIRS=vendor
%make_build

%check
make test

%install
%perl_make_install
%perl_process_packlist
%perl_gen_filelist

%files -f %{name}.files
%doc Changes README.md
%license LICENSE

%changelog

Places

File perl-Algorithm-QuadTree.spec of Package perl-Algorithm-QuadTree

Places