{ "info": { "author": "Xavier Olive", "author_email": "xavier@xoolive.org", "bugtrack_url": null, "classifiers": [], "description": "Quadtrees iterating on pairs of neighbouring items\n==================================================\n\nA quadtree is a tree data structure in which each node has exactly four\nchildren. It is a particularly efficient way to store elements when you\nneed to quickly find them according to their x-y coordinates.\n\nA common problem with elements in quadtrees is to detect pairs of\nelements which are closer than a definite threshold.\n\nThe proposed implementation efficiently addresses this problem.\n\n.. code:: python\n\n from smartquadtree import Quadtree\n\nCreation & insertion of elements\n--------------------------------\n\nAs you instantiate your quadtree, you must specify the center of your\nspace then the height and width.\n\n.. code:: python\n\n q = Quadtree(0, 0, 10, 10)\n\nThe output of a quadtree on the console is pretty explicit. (You can\nrefer to next section for the meaning of \"No mask set\")\n\n.. code:: python\n\n q\n\n\n\n\n.. parsed-literal::\n\n \n Total number of elements: 0\n No mask set\n\n\n\nYou can easily insert elements from which you can naturally infer x-y\ncoordinates (e.g. tuples or lists)\n\n.. code:: python\n\n q.insert((1, 2))\n q.insert((-3, 4))\n q\n\n\n\n\n.. parsed-literal::\n\n \n Total number of elements: 2\n No mask set\n First elements:\n (1, 2),\n (-3, 4),\n \n\n\n\nNo error is raised if the element you are trying to insert is outside\nthe scope of the quadtree. But it won't be stored anyway!\n\n.. code:: python\n\n q.insert((-20, 0))\n q\n\n\n\n\n.. parsed-literal::\n\n \n Total number of elements: 2\n No mask set\n First elements:\n (1, 2),\n (-3, 4),\n \n\n\n\nIf you want to insert other Python objects, be sure to provide\n``get_x()`` and ``get_y()`` methods to your class!\n\n.. code:: python\n\n class Point(object):\n \n def __init__(self, x, y, color):\n self.x = x\n self.y = y\n self.color = color\n \n def __repr__(self):\n return \"(%.2f, %.2f) %s\" % (self.x, self.y, self.color)\n \n def get_x(self):\n return self.x\n \n def get_y(self):\n return self.y\n\n\nYou cannot insert elements of a different type from the first element\ninserted.\n\n.. code:: python\n\n q.insert(Point(2, -7, \"red\"))\n\nBut feel free to create a new one and play with it:\n\n.. code:: python\n\n point_quadtree = Quadtree(5, 5, 5, 5)\n point_quadtree.insert(Point(2, 7, \"red\"))\n point_quadtree\n\n\n\n\n.. parsed-literal::\n\n \n Total number of elements: 1\n No mask set\n First elements:\n (2.00, 7.00) red,\n \n\n\n\nSimple iteration\n----------------\n\n.. code:: python\n\n from random import random\n q = Quadtree(0, 0, 10, 10, 16)\n for a in range(50):\n q.insert([random()*20-10, random()*20-10])\n\nThe ``print`` function does not display all elements and uses the\n``__repr__()`` method of each element.\n\n.. code:: python\n\n print(q)\n\n\n.. parsed-literal::\n\n \n Total number of elements: 50\n No mask set\n First elements:\n [5.576253335483335, 2.9926458306078647],\n [2.956289387002718, 3.792134207741281],\n [3.9903269308895766, 5.492168007874362],\n ...\n\n\nWe can write our own iterator and print each element we encounter the\nway we like.\n\n.. code:: python\n\n from __future__ import print_function\n for p in q.elements():\n print (\"[%.2f, %.2f]\" % (p[0], p[1]), end=\" \")\n\n\n.. parsed-literal::\n\n [5.58, 2.99] [2.96, 3.79] [3.99, 5.49] [3.43, 1.10] [7.73, 4.09] [9.67, 6.81] [2.95, 4.12] [0.14, 5.80] [2.77, 7.87] [0.05, 1.61] [-8.74, 7.64] [-1.22, 1.90] [-0.95, 3.91] [-3.17, 1.09] [-7.41, 4.26] [-8.25, 6.47] [-6.91, 3.80] [-3.73, 3.10] [-5.74, 8.80] [8.50, -9.31] [2.49, -9.10] [6.64, -8.61] [0.40, -2.93] [7.99, -4.08] [4.71, -6.75] [0.12, -1.84] [0.72, -2.94] [9.62, -9.90] [0.15, -9.75] [8.67, -7.19] [2.44, -3.60] [5.08, -8.63] [8.86, -1.87] [1.07, -9.43] [-7.96, -5.53] [-2.53, -5.75] [-1.31, -5.81] [-7.24, -3.55] [-8.76, -9.37] [-8.48, -1.33] [-1.28, -0.69] [-6.60, -4.65] [-4.28, -0.89] [-7.56, -7.31] [-4.72, -7.02] [-1.98, -2.33] [-3.43, -5.74] [-3.71, -1.13] [-1.01, -7.29] [-2.04, -5.90] \n\nIt is easy to filter the iteration process and apply the function only\non elements inside a given polygon. Use the ``set_mask()`` method and\npass a list of x-y coordinates. The polygon will be automatically\nclosed.\n\n.. code:: python\n\n q.set_mask([(-3, -7), (-3, 7), (3, 7), (3, -7)])\n print(q)\n\n\n.. parsed-literal::\n\n \n Total number of elements: 50\n Total number of elements inside mask: 15\n First elements inside the mask:\n [2.956289387002718, 3.792134207741281],\n [2.945472950394006, 4.1166899654293765],\n [0.14379102547949074, 5.797490949080599],\n ...\n\n\nThe same approach can be used to count the number of elements inside the\nquadtree.\n\n.. code:: python\n\n print (sum (1 for x in q.elements()))\n print (sum (1 for x in q.elements(ignore_mask=True)))\n\n\n\n.. parsed-literal::\n\n 15\n 50\n\n\nAs a mask is set on the quadtree, we only counted the elements inside\nthe mask. You can use the ``size()`` method to count elements and ignore\nthe mask by default. Disabling the mask with ``set_mask(None)`` is also\na possibility.\n\n.. code:: python\n\n print (\"%d elements (size method)\" % q.size())\n print (\"%d elements (don't ignore the mask)\" % q.size(False))\n \n q.set_mask(None)\n print (\"%d elements (disable the mask)\" % q.size())\n\n\n.. parsed-literal::\n\n 50 elements (size method)\n 15 elements (don't ignore the mask)\n 50 elements (disable the mask)\n\n\nPlaying with plots\n------------------\n\n.. code:: python\n\n %matplotlib inline\n from matplotlib import pyplot as plt\n \n q = Quadtree(5, 5, 5, 5, 10)\n \n for a in range(200):\n q.insert([random()*10, random()*10])\n \n fig = plt.figure()\n plt.axis([0, 10, 0, 10])\n \n q.set_mask(None)\n for p in q.elements():\n plt.plot([p[0]], [p[1]], 'o', color='lightgrey')\n \n q.set_mask([(3, 3), (3, 7), (7, 7), (7, 3)])\n \n for p in q.elements():\n plt.plot([p[0]], [p[1]], 'ro')\n \n _ = plt.plot([3, 3, 7, 7, 3], [3, 7, 7, 3, 3], 'r')\n\n\n\n\n.. image:: https://raw.githubusercontent.com/xoolive/quadtree/master/tutorial_files/tutorial_31_0.png\n\n\nIteration on pairs of neighbouring elements\n-------------------------------------------\n\nIterating on pairs of neighbouring elements is possible through the\n``neighbour_elements()`` function. It works as a generator and yields\npair of elements, the first one being inside the mask (if specified),\nthe second one being in the same cell or in any neighbouring cell, also\nin the mask.\n\nNote that if ``(a, b)`` is yielded by ``neighbour_elements()``,\n``(b, a)`` will be omitted from future yields.\n\n.. code:: python\n\n # Let's start with a new quadtree because we need\n q = Quadtree(5, 5, 5, 5, 10)\n q.set_limitation(2) # do not create a new subdivision if one side of the cell is below 2\n \n for a in range(200):\n q.insert([random()*10, random()*10])\n \n fig = plt.figure()\n plt.axis([0, 10, 0, 10])\n \n for p in q.elements():\n plt.plot([p[0]], [p[1]], 'o', color='lightgrey')\n \n q.set_mask([(1, 1), (4, 1), (5, 4), (2, 5), (1, 1)])\n \n for p in q.elements():\n plt.plot([p[0]], [p[1]], 'o', color='green')\n \n for p1, p2 in q.neighbour_elements():\n if ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2 < 1):\n plt.plot([p1[0]], [p1[1]], 'o', color='red')\n plt.plot([p2[0]], [p2[1]], 'o', color='red')\n plt.plot([p1[0], p2[0]], [p1[1], p2[1]], 'red')\n \n _ = plt.plot([1, 4, 5, 2, 1], [1, 1, 4, 5, 1], 'r')\n\n\n\n\n.. image:: https://raw.githubusercontent.com/xoolive/quadtree/master/tutorial_files/tutorial_34_0.png", "description_content_type": null, "docs_url": null, "download_url": "UNKNOWN", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "https://github.com/xoolive/quadtree", "keywords": null, "license": "MIT", "maintainer": null, "maintainer_email": null, "name": "smartquadtree", "package_url": "https://pypi.org/project/smartquadtree/", "platform": "UNKNOWN", "project_url": "https://pypi.org/project/smartquadtree/", "project_urls": { "Download": "UNKNOWN", "Homepage": "https://github.com/xoolive/quadtree" }, "release_url": "https://pypi.org/project/smartquadtree/1.0/", "requires_dist": null, "requires_python": null, "summary": "Implementation of quadtrees for moving objects", "version": "1.0" }, "last_serial": 2462727, "releases": { "0.2": [], "1.0": [ { "comment_text": "", "digests": { "md5": "4f0dc70513751504b328dd05a3c09284", "sha256": "bd24dc01ca7bb523ba6cd49e16eaf2773cb95bf47f6fed1e793508ed68b87273" }, "downloads": -1, "filename": "smartquadtree-1.0-cp27-none-macosx_10_10_intel.whl", "has_sig": false, "md5_digest": "4f0dc70513751504b328dd05a3c09284", "packagetype": "bdist_wheel", "python_version": "2.7", "requires_python": null, "size": 49406, "upload_time": "2015-10-26T22:20:51", "url": "https://files.pythonhosted.org/packages/54/49/2a996f7660fdad7fca569938de8a7cda8e69c6a5278a4c6ce95438c0f33f/smartquadtree-1.0-cp27-none-macosx_10_10_intel.whl" }, { "comment_text": "", "digests": { "md5": "4d48694b3e54448a3c742cad614fc0f9", "sha256": "0ba10cdb6665569c91b49b5cb71a0fc5b848bbd1da7414ad280a0cd16dbc5c5b" }, "downloads": -1, "filename": "smartquadtree-1.0-cp27-none-win32.whl", "has_sig": false, "md5_digest": "4d48694b3e54448a3c742cad614fc0f9", "packagetype": "bdist_wheel", "python_version": "2.7", "requires_python": null, "size": 56821, "upload_time": "2015-10-27T09:07:11", "url": "https://files.pythonhosted.org/packages/c6/c4/5fd12b751ddb024c32d79aa33b8932c84c6ba58d9e75f7f2eaca2003c3d6/smartquadtree-1.0-cp27-none-win32.whl" }, { "comment_text": "", "digests": { "md5": "50a5adba639383ed365bf7f282d5e3c6", "sha256": "730cf7c3db8f7812b707462415428da63e022a21d9a2e4d9aa372f8b9b18c28a" }, "downloads": -1, "filename": "smartquadtree-1.0-cp34-cp34m-macosx_10_10_x86_64.whl", "has_sig": false, "md5_digest": "50a5adba639383ed365bf7f282d5e3c6", "packagetype": "bdist_wheel", "python_version": "3.4", "requires_python": null, "size": 51626, "upload_time": "2015-10-26T22:19:54", "url": "https://files.pythonhosted.org/packages/b6/67/20d7c96fda52783a88fc7708583c2aa6991598cd083ca55a4957b8601952/smartquadtree-1.0-cp34-cp34m-macosx_10_10_x86_64.whl" }, { "comment_text": "", "digests": { "md5": "26bcb755ee19e235ce86f09236b75689", "sha256": "f996f12e6c977dd54f29168d529ed7b4822c74a0545f49f084f33a8bdae4d2dd" }, "downloads": -1, "filename": "smartquadtree-1.0-cp34-none-win32.whl", "has_sig": false, "md5_digest": "26bcb755ee19e235ce86f09236b75689", "packagetype": "bdist_wheel", "python_version": "3.4", "requires_python": null, "size": 56782, "upload_time": "2015-10-27T09:07:31", "url": "https://files.pythonhosted.org/packages/95/79/4a5edf5170ffe7f8fb13ab2e27bc7173a8abff742b83b9c391cb4428505a/smartquadtree-1.0-cp34-none-win32.whl" }, { "comment_text": "", "digests": { "md5": "867dd86e3267a58302c85c6f65f5a9ee", "sha256": "74590db19105e3ce67fd6dbb16e4fb6c048ac451b303324111c0c49664fd43cd" }, "downloads": -1, "filename": "smartquadtree-1.0-py2.7-macosx-10.10-intel.egg", "has_sig": false, "md5_digest": "867dd86e3267a58302c85c6f65f5a9ee", "packagetype": "bdist_egg", "python_version": "2.7", "requires_python": null, "size": 46745, "upload_time": "2015-10-26T22:20:27", "url": "https://files.pythonhosted.org/packages/cd/dc/9ea4f87d756fb9a56ce57ba68ddc0a2968b4606a919cfb5c8c6e5a86bfb6/smartquadtree-1.0-py2.7-macosx-10.10-intel.egg" }, { "comment_text": "", "digests": { "md5": "08e84396995f29100dea1ed19d5a024f", "sha256": "a0db58312f606909e2f673e204277b343b087d4e7672401ff8acb1ab39fd4eaf" }, "downloads": -1, "filename": "smartquadtree-1.0-py2.7-win32.egg", "has_sig": false, "md5_digest": "08e84396995f29100dea1ed19d5a024f", "packagetype": "bdist_egg", "python_version": "2.7", "requires_python": null, "size": 54143, "upload_time": "2015-10-27T09:07:45", "url": "https://files.pythonhosted.org/packages/f7/74/e752e457517cb1d1dbb5991d7ec0b1371e597c9117fc1447b42671068190/smartquadtree-1.0-py2.7-win32.egg" }, { "comment_text": "", "digests": { "md5": "2eda1cb6123bff3146df07277f47cafd", "sha256": "c92515ec7385e0b1d4110a2b11c3279a6638ff754ed88d6306a9cc11cef6adf3" }, "downloads": -1, "filename": "smartquadtree-1.0-py3.4-macosx-10.10-x86_64.egg", "has_sig": false, "md5_digest": "2eda1cb6123bff3146df07277f47cafd", "packagetype": "bdist_egg", "python_version": "3.4", "requires_python": null, "size": 49019, "upload_time": "2015-10-26T22:20:05", "url": "https://files.pythonhosted.org/packages/9f/c2/b847e1110364c777bdb7bb167fffbde719beb2334cb6904bd59819bd053f/smartquadtree-1.0-py3.4-macosx-10.10-x86_64.egg" }, { "comment_text": "", "digests": { "md5": "58c077e82e2f29552e66816bfe2f730d", "sha256": "637a3ad1404c91ef06f8ed517f98f2a7b055b8e54b88287eb37e819051cbd235" }, "downloads": -1, "filename": "smartquadtree-1.0-py3.4-win32.egg", "has_sig": false, "md5_digest": "58c077e82e2f29552e66816bfe2f730d", "packagetype": "bdist_wheel", "python_version": "3.4", "requires_python": null, "size": 54193, "upload_time": "2015-10-27T09:08:01", "url": "https://files.pythonhosted.org/packages/99/bb/3d991eee58e5a684bd342e32a560593a7d6ee44e2aacb3eb52c6db3ca7b1/smartquadtree-1.0-py3.4-win32.egg" }, { "comment_text": "", "digests": { "md5": "48e1b8e3f0ebd5fd81d6eb7c0273bbc6", "sha256": "42ab10e8a0079f4be9babbffdf2becdb41cfea62d57e1b9982f88e5e85092733" }, "downloads": -1, "filename": "smartquadtree-1.0-py3.5-win32.egg", "has_sig": false, "md5_digest": "48e1b8e3f0ebd5fd81d6eb7c0273bbc6", "packagetype": "bdist_egg", "python_version": "3.5", "requires_python": null, "size": 39477, "upload_time": "2016-11-15T21:27:41", "url": "https://files.pythonhosted.org/packages/df/9f/4c118e8b81445b7b2faa3cfbcce1f042f57364b36981344cf06a2fc88dd2/smartquadtree-1.0-py3.5-win32.egg" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "4f0dc70513751504b328dd05a3c09284", "sha256": "bd24dc01ca7bb523ba6cd49e16eaf2773cb95bf47f6fed1e793508ed68b87273" }, "downloads": -1, "filename": "smartquadtree-1.0-cp27-none-macosx_10_10_intel.whl", "has_sig": false, "md5_digest": "4f0dc70513751504b328dd05a3c09284", "packagetype": "bdist_wheel", "python_version": "2.7", "requires_python": null, "size": 49406, "upload_time": "2015-10-26T22:20:51", "url": "https://files.pythonhosted.org/packages/54/49/2a996f7660fdad7fca569938de8a7cda8e69c6a5278a4c6ce95438c0f33f/smartquadtree-1.0-cp27-none-macosx_10_10_intel.whl" }, { "comment_text": "", "digests": { "md5": "4d48694b3e54448a3c742cad614fc0f9", "sha256": "0ba10cdb6665569c91b49b5cb71a0fc5b848bbd1da7414ad280a0cd16dbc5c5b" }, "downloads": -1, "filename": "smartquadtree-1.0-cp27-none-win32.whl", "has_sig": false, "md5_digest": "4d48694b3e54448a3c742cad614fc0f9", "packagetype": "bdist_wheel", "python_version": "2.7", "requires_python": null, "size": 56821, "upload_time": "2015-10-27T09:07:11", "url": "https://files.pythonhosted.org/packages/c6/c4/5fd12b751ddb024c32d79aa33b8932c84c6ba58d9e75f7f2eaca2003c3d6/smartquadtree-1.0-cp27-none-win32.whl" }, { "comment_text": "", "digests": { "md5": "50a5adba639383ed365bf7f282d5e3c6", "sha256": "730cf7c3db8f7812b707462415428da63e022a21d9a2e4d9aa372f8b9b18c28a" }, "downloads": -1, "filename": "smartquadtree-1.0-cp34-cp34m-macosx_10_10_x86_64.whl", "has_sig": false, "md5_digest": "50a5adba639383ed365bf7f282d5e3c6", "packagetype": "bdist_wheel", "python_version": "3.4", "requires_python": null, "size": 51626, "upload_time": "2015-10-26T22:19:54", "url": "https://files.pythonhosted.org/packages/b6/67/20d7c96fda52783a88fc7708583c2aa6991598cd083ca55a4957b8601952/smartquadtree-1.0-cp34-cp34m-macosx_10_10_x86_64.whl" }, { "comment_text": "", "digests": { "md5": "26bcb755ee19e235ce86f09236b75689", "sha256": "f996f12e6c977dd54f29168d529ed7b4822c74a0545f49f084f33a8bdae4d2dd" }, "downloads": -1, "filename": "smartquadtree-1.0-cp34-none-win32.whl", "has_sig": false, "md5_digest": "26bcb755ee19e235ce86f09236b75689", "packagetype": "bdist_wheel", "python_version": "3.4", "requires_python": null, "size": 56782, "upload_time": "2015-10-27T09:07:31", "url": "https://files.pythonhosted.org/packages/95/79/4a5edf5170ffe7f8fb13ab2e27bc7173a8abff742b83b9c391cb4428505a/smartquadtree-1.0-cp34-none-win32.whl" }, { "comment_text": "", "digests": { "md5": "867dd86e3267a58302c85c6f65f5a9ee", "sha256": "74590db19105e3ce67fd6dbb16e4fb6c048ac451b303324111c0c49664fd43cd" }, "downloads": -1, "filename": "smartquadtree-1.0-py2.7-macosx-10.10-intel.egg", "has_sig": false, "md5_digest": "867dd86e3267a58302c85c6f65f5a9ee", "packagetype": "bdist_egg", "python_version": "2.7", "requires_python": null, "size": 46745, "upload_time": "2015-10-26T22:20:27", "url": "https://files.pythonhosted.org/packages/cd/dc/9ea4f87d756fb9a56ce57ba68ddc0a2968b4606a919cfb5c8c6e5a86bfb6/smartquadtree-1.0-py2.7-macosx-10.10-intel.egg" }, { "comment_text": "", "digests": { "md5": "08e84396995f29100dea1ed19d5a024f", "sha256": "a0db58312f606909e2f673e204277b343b087d4e7672401ff8acb1ab39fd4eaf" }, "downloads": -1, "filename": "smartquadtree-1.0-py2.7-win32.egg", "has_sig": false, "md5_digest": "08e84396995f29100dea1ed19d5a024f", "packagetype": "bdist_egg", "python_version": "2.7", "requires_python": null, "size": 54143, "upload_time": "2015-10-27T09:07:45", "url": "https://files.pythonhosted.org/packages/f7/74/e752e457517cb1d1dbb5991d7ec0b1371e597c9117fc1447b42671068190/smartquadtree-1.0-py2.7-win32.egg" }, { "comment_text": "", "digests": { "md5": "2eda1cb6123bff3146df07277f47cafd", "sha256": "c92515ec7385e0b1d4110a2b11c3279a6638ff754ed88d6306a9cc11cef6adf3" }, "downloads": -1, "filename": "smartquadtree-1.0-py3.4-macosx-10.10-x86_64.egg", "has_sig": false, "md5_digest": "2eda1cb6123bff3146df07277f47cafd", "packagetype": "bdist_egg", "python_version": "3.4", "requires_python": null, "size": 49019, "upload_time": "2015-10-26T22:20:05", "url": "https://files.pythonhosted.org/packages/9f/c2/b847e1110364c777bdb7bb167fffbde719beb2334cb6904bd59819bd053f/smartquadtree-1.0-py3.4-macosx-10.10-x86_64.egg" }, { "comment_text": "", "digests": { "md5": "58c077e82e2f29552e66816bfe2f730d", "sha256": "637a3ad1404c91ef06f8ed517f98f2a7b055b8e54b88287eb37e819051cbd235" }, "downloads": -1, "filename": "smartquadtree-1.0-py3.4-win32.egg", "has_sig": false, "md5_digest": "58c077e82e2f29552e66816bfe2f730d", "packagetype": "bdist_wheel", "python_version": "3.4", "requires_python": null, "size": 54193, "upload_time": "2015-10-27T09:08:01", "url": "https://files.pythonhosted.org/packages/99/bb/3d991eee58e5a684bd342e32a560593a7d6ee44e2aacb3eb52c6db3ca7b1/smartquadtree-1.0-py3.4-win32.egg" }, { "comment_text": "", "digests": { "md5": "48e1b8e3f0ebd5fd81d6eb7c0273bbc6", "sha256": "42ab10e8a0079f4be9babbffdf2becdb41cfea62d57e1b9982f88e5e85092733" }, "downloads": -1, "filename": "smartquadtree-1.0-py3.5-win32.egg", "has_sig": false, "md5_digest": "48e1b8e3f0ebd5fd81d6eb7c0273bbc6", "packagetype": "bdist_egg", "python_version": "3.5", "requires_python": null, "size": 39477, "upload_time": "2016-11-15T21:27:41", "url": "https://files.pythonhosted.org/packages/df/9f/4c118e8b81445b7b2faa3cfbcce1f042f57364b36981344cf06a2fc88dd2/smartquadtree-1.0-py3.5-win32.egg" } ] }