This is a pre-production deployment of Warehouse, however changes made here WILL affect the production instance of PyPI.
Latest Version Dependencies status unknown Test status unknown Test coverage unknown
Project Description

A module that provides the CellTree data structure as described by Garth and Joy in their 2010 paper

This implementation is 2D specific and includes some additions useful to answering one question:
_"What is the index of the polygon that contains this point?"_

Algorithm Notes

There are two major benefits to this algorithm over other types of BVHs. First is that overlaps in volumes
bounded by nodes do not create duplicates, decreasing the memory footprint. Secondly, the tree is balanced
by splitting a node along the plane that minimizes a cost function that 'weighs' each half. The result is
a tree with no duplicates and that becomes increasingly balanced as the number of buckets used when building
the tree increases (though this linearly increases build time).

This is a 2D version of the algorithm that is oriented towards maximum lookup speed and immediate answer
checking. The basic CellTree does not hold enough information to give conclusive point-in-polygon answers;
the best it can do is provide the (short) list of cells that contain the point. Since a point can be within
the bounds of two different leaves, and it is very possible both children of a parent node will need to be
searched, implementing immediate point-in-polygon checks on each cell as they are encountered is highly
beneficial, as an early success will avoid all further tree traversal.

Usage Notes

The tree needs certain information to be built:
1. 'verts' - A 2xV numpy array containing x/y coordinates of the V vertices
2. 'faces' - A PxN numpy array containing N arrays of P indices of vertices that describe one 'face' or polygon of degree P
3. 'num_buckets' - The # of buckets desired. Must be >= 2 The default is 4. Values higher than 8 begin to provide diminishing returns.
4. 'cells\_per\_leaf' - The # of polygons per leaf node. The default is 2. Using 1 is possible, but doubles memory footprint for only slightly.
faster lookup. If memory is a concern, this value can be increased, but lookup performance will quickly be impacted

IMPORTANT: 'verts' and 'faces' MUST describe a _properly formed_ unstructed grid. Assume that degenerate (0 area) or
overlapping polygons WILL cause a build failure. If the construction of the tree causes a segfault, this is probably
the cause.
Release History

Release History


This version

History Node

TODO: Figure out how to actually get changelog content.

Changelog content for this version goes here.

Donec et mollis dolor. Praesent et diam eget libero egestas mattis sit amet vitae augue. Nam tincidunt congue enim, ut porta lorem lacinia consectetur. Donec ut libero sed arcu vehicula ultricies a non tortor. Lorem ipsum dolor sit amet, consectetur adipiscing elit.

Show More

Download Files

Download Files

TODO: Brief introduction on what you do with files - including link to relevant help section.

File Name & Checksum SHA256 Checksum Help Version File Type Upload Date (124.0 kB) Copy SHA256 Checksum SHA256 Source Feb 26, 2016

Supported By

WebFaction WebFaction Technical Writing Elastic Elastic Search Pingdom Pingdom Monitoring Dyn Dyn DNS Sentry Sentry Error Logging CloudAMQP CloudAMQP RabbitMQ Heroku Heroku PaaS Kabu Creative Kabu Creative UX & Design Fastly Fastly CDN DigiCert DigiCert EV Certificate Rackspace Rackspace Cloud Servers DreamHost DreamHost Log Hosting