125 lines
4.7 KiB
RPMSpec
125 lines
4.7 KiB
RPMSpec
#
|
|
# spec file for package perl-Algorithm-QuadTree
|
|
#
|
|
# Copyright (c) 2024 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.500.0
|
|
Release: 0
|
|
# 0.5 -> normalize -> 0.500.0
|
|
%define cpan_version 0.5
|
|
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}-%{cpan_version}.tar.gz
|
|
Source1: cpanspec.yml
|
|
Source100: README.md
|
|
BuildArch: noarch
|
|
BuildRequires: perl
|
|
BuildRequires: perl-macros
|
|
Provides: perl(Algorithm::QuadTree) = %{version}
|
|
Provides: perl(Algorithm::QuadTree::PP) = %{version}
|
|
%undefine __perllib_provides
|
|
%{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}-%{cpan_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
|