<?xml version="1.0" encoding="ascii"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<title>Bio.KDTree.KDTree.KDTree</title>
<link rel="stylesheet" href="epydoc.css" type="text/css" />
<script type="text/javascript" src="epydoc.js"></script>
</head>
<body bgcolor="white" text="black" link="blue" vlink="#204080"
alink="#204080">
<!-- ==================== NAVIGATION BAR ==================== -->
<table class="navbar" border="0" width="100%" cellpadding="0"
bgcolor="#a0c0ff" cellspacing="0">
<tr valign="middle">
<!-- Tree link -->
<th> <a
href="module-tree.html">Trees</a> </th>
<!-- Index link -->
<th> <a
href="identifier-index.html">Indices</a> </th>
<!-- Help link -->
<th> <a
href="help.html">Help</a> </th>
<th class="navbar" width="100%"></th>
</tr>
</table>
<table width="100%" cellpadding="0" cellspacing="0">
<tr valign="top">
<td width="100%">
<span class="breadcrumbs">
Bio ::
KDTree ::
KDTree ::
KDTree ::
Class KDTree
</span>
</td>
<td>
<table cellpadding="0" cellspacing="0">
<!-- hide/show private -->
<tr><td align="right"><span class="options">[<a href="javascript:void(0);" class="privatelink"
onclick="toggle_private();">hide private</a>]</span></td></tr>
<tr><td align="right"><span class="options"
>[<a href="frames.html" target="_top">frames</a
>] | <a href="Bio.KDTree.KDTree.KDTree-class.html"
target="_top">no frames</a>]</span></td></tr>
</table>
</td>
</tr>
</table>
<!-- ==================== CLASS DESCRIPTION ==================== -->
<h1 class="epydoc">Class KDTree</h1><p class="nomargin-top"><span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree">source code</a></span></p>
<pre class="base-tree">
object --+
|
<strong class="uidshort">KDTree</strong>
</pre>
<hr />
<p>KD tree implementation (C++, SWIG python wrapper)</p>
<p>The KD tree data structure can be used for all kinds of searches that
involve N-dimensional vectors, e.g. neighbor searches (find all points
within a radius of a given point) or finding all point pairs in a set
that are within a certain radius of each other.</p>
<p>Reference:</p>
<p>Computational Geometry: Algorithms and Applications Second Edition
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf
published by Springer-Verlag 2nd rev. ed. 2000. ISBN: 3-540-65620-0</p>
<p>The KD tree data structure is described in chapter 5, pg. 99.</p>
<p>The following article made clear to me that the nodes should contain
more than one point (this leads to dramatic speed improvements for the
"all fixed radius neighbor search", see below):</p>
<p>JL Bentley, "Kd trees for semidynamic point sets," in Sixth
Annual ACM Symposium on Computational Geometry, vol. 91. San Francisco,
1990</p>
<p>This KD implementation also performs a "all fixed radius neighbor
search", i.e. it can find all point pairs in a set that are within a
certain radius of each other. As far as I know the algorithm has not been
published.</p>
<!-- ==================== INSTANCE METHODS ==================== -->
<a name="section-InstanceMethods"></a>
<table class="summary" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
<td colspan="2" class="table-header">
<table border="0" cellpadding="0" cellspacing="0" width="100%">
<tr valign="top">
<td align="left"><span class="table-header">Instance Methods</span></td>
<td align="right" valign="top"
><span class="options">[<a href="#section-InstanceMethods"
class="privatelink" onclick="toggle_private();"
>hide private</a>]</span></td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a href="Bio.KDTree.KDTree.KDTree-class.html#__init__" class="summary-sig-name">__init__</a>(<span class="summary-sig-arg">self</span>,
<span class="summary-sig-arg">dim</span>,
<span class="summary-sig-arg">bucket_size</span>=<span class="summary-sig-default">1</span>)</span><br />
x.__init__(...) initializes x; see help(type(x)) for signature</td>
<td align="right" valign="top">
<span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.__init__">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a href="Bio.KDTree.KDTree.KDTree-class.html#set_coords" class="summary-sig-name">set_coords</a>(<span class="summary-sig-arg">self</span>,
<span class="summary-sig-arg">coords</span>)</span><br />
Add the coordinates of the points.</td>
<td align="right" valign="top">
<span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.set_coords">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a href="Bio.KDTree.KDTree.KDTree-class.html#search" class="summary-sig-name">search</a>(<span class="summary-sig-arg">self</span>,
<span class="summary-sig-arg">center</span>,
<span class="summary-sig-arg">radius</span>)</span><br />
Search all points within radius of center.</td>
<td align="right" valign="top">
<span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.search">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a href="Bio.KDTree.KDTree.KDTree-class.html#get_radii" class="summary-sig-name">get_radii</a>(<span class="summary-sig-arg">self</span>)</span><br />
Return radii.</td>
<td align="right" valign="top">
<span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.get_radii">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a href="Bio.KDTree.KDTree.KDTree-class.html#get_indices" class="summary-sig-name">get_indices</a>(<span class="summary-sig-arg">self</span>)</span><br />
Return the list of indices.</td>
<td align="right" valign="top">
<span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.get_indices">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a href="Bio.KDTree.KDTree.KDTree-class.html#all_search" class="summary-sig-name">all_search</a>(<span class="summary-sig-arg">self</span>,
<span class="summary-sig-arg">radius</span>)</span><br />
All fixed neighbor search.</td>
<td align="right" valign="top">
<span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.all_search">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a href="Bio.KDTree.KDTree.KDTree-class.html#all_get_indices" class="summary-sig-name">all_get_indices</a>(<span class="summary-sig-arg">self</span>)</span><br />
Return All Fixed Neighbor Search results.</td>
<td align="right" valign="top">
<span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.all_get_indices">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a href="Bio.KDTree.KDTree.KDTree-class.html#all_get_radii" class="summary-sig-name">all_get_radii</a>(<span class="summary-sig-arg">self</span>)</span><br />
Return All Fixed Neighbor Search results.</td>
<td align="right" valign="top">
<span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.all_get_radii">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td colspan="2" class="summary">
<p class="indent-wrapped-lines"><b>Inherited from <code>object</code></b>:
<code>__delattr__</code>,
<code>__format__</code>,
<code>__getattribute__</code>,
<code>__hash__</code>,
<code>__new__</code>,
<code>__reduce__</code>,
<code>__reduce_ex__</code>,
<code>__repr__</code>,
<code>__setattr__</code>,
<code>__sizeof__</code>,
<code>__str__</code>,
<code>__subclasshook__</code>
</p>
</td>
</tr>
</table>
<!-- ==================== PROPERTIES ==================== -->
<a name="section-Properties"></a>
<table class="summary" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
<td colspan="2" class="table-header">
<table border="0" cellpadding="0" cellspacing="0" width="100%">
<tr valign="top">
<td align="left"><span class="table-header">Properties</span></td>
<td align="right" valign="top"
><span class="options">[<a href="#section-Properties"
class="privatelink" onclick="toggle_private();"
>hide private</a>]</span></td>
</tr>
</table>
</td>
</tr>
<tr>
<td colspan="2" class="summary">
<p class="indent-wrapped-lines"><b>Inherited from <code>object</code></b>:
<code>__class__</code>
</p>
</td>
</tr>
</table>
<!-- ==================== METHOD DETAILS ==================== -->
<a name="section-MethodDetails"></a>
<table class="details" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
<td colspan="2" class="table-header">
<table border="0" cellpadding="0" cellspacing="0" width="100%">
<tr valign="top">
<td align="left"><span class="table-header">Method Details</span></td>
<td align="right" valign="top"
><span class="options">[<a href="#section-MethodDetails"
class="privatelink" onclick="toggle_private();"
>hide private</a>]</span></td>
</tr>
</table>
</td>
</tr>
</table>
<a name="__init__"></a>
<div>
<table class="details" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr><td>
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr valign="top"><td>
<h3 class="epydoc"><span class="sig"><span class="sig-name">__init__</span>(<span class="sig-arg">self</span>,
<span class="sig-arg">dim</span>,
<span class="sig-arg">bucket_size</span>=<span class="sig-default">1</span>)</span>
<br /><em class="fname">(Constructor)</em>
</h3>
</td><td align="right" valign="top"
><span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.__init__">source code</a></span>
</td>
</tr></table>
<p>x.__init__(...) initializes x; see help(type(x)) for signature</p>
<dl class="fields">
<dt>Overrides:
object.__init__
<dd><em class="note">(inherited documentation)</em></dd>
</dt>
</dl>
</td></tr></table>
</div>
<a name="set_coords"></a>
<div>
<table class="details" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr><td>
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr valign="top"><td>
<h3 class="epydoc"><span class="sig"><span class="sig-name">set_coords</span>(<span class="sig-arg">self</span>,
<span class="sig-arg">coords</span>)</span>
</h3>
</td><td align="right" valign="top"
><span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.set_coords">source code</a></span>
</td>
</tr></table>
<p>Add the coordinates of the points.</p>
<p>o coords - two dimensional NumPy array. E.g. if the points have
dimensionality D and there are N points, the coords array should be NxD
dimensional.</p>
<dl class="fields">
</dl>
</td></tr></table>
</div>
<a name="search"></a>
<div>
<table class="details" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr><td>
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr valign="top"><td>
<h3 class="epydoc"><span class="sig"><span class="sig-name">search</span>(<span class="sig-arg">self</span>,
<span class="sig-arg">center</span>,
<span class="sig-arg">radius</span>)</span>
</h3>
</td><td align="right" valign="top"
><span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.search">source code</a></span>
</td>
</tr></table>
<p>Search all points within radius of center.</p>
<p>o center - one dimensional NumPy array. E.g. if the points have
dimensionality D, the center array should be D dimensional. o radius -
float>0</p>
<dl class="fields">
</dl>
</td></tr></table>
</div>
<a name="get_radii"></a>
<div>
<table class="details" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr><td>
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr valign="top"><td>
<h3 class="epydoc"><span class="sig"><span class="sig-name">get_radii</span>(<span class="sig-arg">self</span>)</span>
</h3>
</td><td align="right" valign="top"
><span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.get_radii">source code</a></span>
</td>
</tr></table>
<p>Return radii.</p>
<p>Return the list of distances from center after a neighbor search.</p>
<dl class="fields">
</dl>
</td></tr></table>
</div>
<a name="get_indices"></a>
<div>
<table class="details" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr><td>
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr valign="top"><td>
<h3 class="epydoc"><span class="sig"><span class="sig-name">get_indices</span>(<span class="sig-arg">self</span>)</span>
</h3>
</td><td align="right" valign="top"
><span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.get_indices">source code</a></span>
</td>
</tr></table>
<p>Return the list of indices.</p>
<p>Return the list of indices after a neighbor search. The indices refer
to the original coords NumPy array. The coordinates with these indices
were within radius of center.</p>
<p>For an index pair, the first index<second index.</p>
<dl class="fields">
</dl>
</td></tr></table>
</div>
<a name="all_search"></a>
<div>
<table class="details" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr><td>
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr valign="top"><td>
<h3 class="epydoc"><span class="sig"><span class="sig-name">all_search</span>(<span class="sig-arg">self</span>,
<span class="sig-arg">radius</span>)</span>
</h3>
</td><td align="right" valign="top"
><span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.all_search">source code</a></span>
</td>
</tr></table>
<p>All fixed neighbor search.</p>
<p>Search all point pairs that are within radius.</p>
<p>o radius - float (>0)</p>
<dl class="fields">
</dl>
</td></tr></table>
</div>
<a name="all_get_indices"></a>
<div>
<table class="details" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr><td>
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr valign="top"><td>
<h3 class="epydoc"><span class="sig"><span class="sig-name">all_get_indices</span>(<span class="sig-arg">self</span>)</span>
</h3>
</td><td align="right" valign="top"
><span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.all_get_indices">source code</a></span>
</td>
</tr></table>
<p>Return All Fixed Neighbor Search results.</p>
<p>Return a Nx2 dim NumPy array containing the indices of the point
pairs, where N is the number of neighbor pairs.</p>
<dl class="fields">
</dl>
</td></tr></table>
</div>
<a name="all_get_radii"></a>
<div>
<table class="details" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr><td>
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr valign="top"><td>
<h3 class="epydoc"><span class="sig"><span class="sig-name">all_get_radii</span>(<span class="sig-arg">self</span>)</span>
</h3>
</td><td align="right" valign="top"
><span class="codelink"><a href="Bio.KDTree.KDTree-pysrc.html#KDTree.all_get_radii">source code</a></span>
</td>
</tr></table>
<p>Return All Fixed Neighbor Search results.</p>
<p>Return an N-dim array containing the distances of all the point pairs,
where N is the number of neighbor pairs..</p>
<dl class="fields">
</dl>
</td></tr></table>
</div>
<br />
<!-- ==================== NAVIGATION BAR ==================== -->
<table class="navbar" border="0" width="100%" cellpadding="0"
bgcolor="#a0c0ff" cellspacing="0">
<tr valign="middle">
<!-- Tree link -->
<th> <a
href="module-tree.html">Trees</a> </th>
<!-- Index link -->
<th> <a
href="identifier-index.html">Indices</a> </th>
<!-- Help link -->
<th> <a
href="help.html">Help</a> </th>
<th class="navbar" width="100%"></th>
</tr>
</table>
<table border="0" cellpadding="0" cellspacing="0" width="100%%">
<tr>
<td align="left" class="footer">
Generated by Epydoc 3.0.1 on Thu Aug 18 18:19:26 2011
</td>
<td align="right" class="footer">
<a target="mainFrame" href="http://epydoc.sourceforge.net"
>http://epydoc.sourceforge.net</a>
</td>
</tr>
</table>
<script type="text/javascript">
<!--
// Private objects are initially displayed (because if
// javascript is turned off then we want them to be
// visible); but by default, we want to hide them. So hide
// them unless we have a cookie that says to show them.
checkCookie();
// -->
</script>
</body>
</html>
