Accepting request 972546 from devel:languages:perl:autoupdate
- updated to 0.2 see /usr/share/doc/packages/perl-Algorithm-QuadTree/Changes 0.2 [New features] - New method: ->clear - Method ->add now treats shape as circular when passed four arguments - Method ->getEnclosedObjects now treats shape as circular when passed three arguments - Object references are now correctly handled and can be used instead of IDs [Bug fixes] - fix ->delete method - RT#55747 [Other changes] - Performance optimization - Added test suite - Added github repository and bugtracker - Maintenance-related changes OBS-URL: https://build.opensuse.org/request/show/972546 OBS-URL: https://build.opensuse.org/package/show/devel:languages:perl/perl-Algorithm-QuadTree?expand=0&rev=6
This commit is contained in:
Stephan Kulow
committed by
Git OBS Bridge
Git OBS Bridge
parent
f78a99c46c
commit
75c1af5b26
@@ -1,7 +1,7 @@
|
||||
#
|
||||
# spec file for package perl-Algorithm-QuadTree
|
||||
#
|
||||
# Copyright (c) 2011 SUSE LINUX Products GmbH, Nuernberg, Germany.
|
||||
# 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
|
||||
@@ -12,65 +12,106 @@
|
||||
# license that conforms to the Open Source Definition (Version 1.9)
|
||||
# published by the Open Source Initiative.
|
||||
|
||||
# Please submit bugfixes or comments via http://bugs.opensuse.org/
|
||||
# Please submit bugfixes or comments via https://bugs.opensuse.org/
|
||||
#
|
||||
|
||||
|
||||
|
||||
%define cpan_name Algorithm-QuadTree
|
||||
Name: perl-Algorithm-QuadTree
|
||||
Version: 0.1
|
||||
Release: 1
|
||||
AutoReqProv: on
|
||||
Group: Development/Libraries/Perl
|
||||
License: Perl
|
||||
Url: http://search.cpan.org/dist/Algorithm-QuadTree/
|
||||
Summary: A QuadTree Algorithm class in pure Perl
|
||||
Source: Algorithm-QuadTree-%{version}.tar.gz
|
||||
BuildRoot: %{_tmppath}/%{name}-%{version}-build
|
||||
%{perl_requires}
|
||||
Version: 0.2
|
||||
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.
|
||||
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.
|
||||
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
|
||||
%setup -q -n QuadTree
|
||||
%autosetup -n %{cpan_name}-%{version}
|
||||
|
||||
%build
|
||||
perl Makefile.PL OPTIMIZE="$RPM_OPT_FLAGS -Wall"
|
||||
make
|
||||
perl Makefile.PL INSTALLDIRS=vendor
|
||||
%make_build
|
||||
|
||||
%check
|
||||
make test
|
||||
|
||||
%install
|
||||
make DESTDIR=$RPM_BUILD_ROOT install_vendor
|
||||
%perl_make_install
|
||||
%perl_process_packlist
|
||||
%perl_gen_filelist
|
||||
|
||||
%clean
|
||||
rm -rf $RPM_BUILD_ROOT
|
||||
|
||||
%files
|
||||
%defattr(-,root,root)
|
||||
%doc README Changes
|
||||
%doc %{_mandir}/man3/*
|
||||
%{perl_vendorlib}/Algorithm
|
||||
#%{perl_vendorarch}/auto/Algorithm
|
||||
%files -f %{name}.files
|
||||
%doc Changes README.md
|
||||
|
||||
%changelog
|
||||
|
||||
Reference in New Issue
Block a user