{
    "info": {
        "author": "",
        "author_email": "",
        "bugtrack_url": null,
        "classifiers": [],
        "description": "# pyzorder\n\nPython implementation of z-order curve (a.k.a. Morton order)\n\nz-order curve maps multidimensional data to one dimension.\n\nUsing z-order curve, you can implement multidimensional sort key for DynamoDB, which allows only 1 sort key at once.\npyzorder helps to implement ranging indexing with z-order curved data.\n\n(\u65e5\u672c\u8a9e\u30c9\u30ad\u30e5\u30e1\u30f3\u30c8\u306f\u3001\u82f1\u8a9e\u7248\u306e\u5f8c\u308d\u306b\u3042\u308a\u307e\u3059)\n\n## What is \"z-order curve\"? \n\n\"z-order curve\" maps multidimensional data to one dimension while preserving locality of the data points.\nThe z value is calculated by interleaving input values.\n\n![](https://upload.wikimedia.org/wikipedia/commons/thumb/3/30/Z-curve.svg/400px-Z-curve.svg.png)\n(cited from [Z\\-order curve \\- Wikipedia](https://en.wikipedia.org/wiki/Z-order_curve))\n\nTypical usage is for DynamoDB, which allows only 1 sort key at once.\nFor example, if you want to indexing the data with both x-axis and y-axis,\nyou can map x and y with z-order curve, and put the z-ordered data in the DynamoDB table as Sort Key.\nHowever, you have to care about \"unnecessary region.\"\n\n![](https://upload.wikimedia.org/wikipedia/commons/thumb/0/02/BIGMIN.svg/400px-BIGMIN.svg.png)  \n(cited again from [Z\\-order curve \\- Wikipedia](https://en.wikipedia.org/wiki/Z-order_curve))\n\nIf you want to access (x = 2, ..., 3, y = 2, ..., 6), the corresponding region is dotted lines square.\nWhen accessing z-order curve sequentially, the next value of \"15\" should be \"36\".\nThe region \"16\" to \"35\" is \"unnecessary region.\"\nSo, you need to treat with such \"unnecessary region\" efficiently.\n\n**`pyzorder` implements `next_zorder_index` which returns next valid z-order value**\nYou can easily implement regional indexing access with z-order curved data.\n\n`next_zorder_index` is re-implementaion of Tropf, H.; Herzog, H. (1981), [\"Multidimensional Range Search in Dynamically Balanced Trees\"](http://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf) in Python.\n`next_zorder_index` is shown as `BIGMIN` in the paper.\n\n## Usage\n\n```python\nfrom pyzorder import ZOrderIndexer\n\nzi = ZOrderIndexer((2, 3), (2, 6))\n\nz_2_2 = zi.zindex(2, 2)\n# z_2_2 = 12\n\nzi.next_zorder_index(z_2_2)\n# return 13\n\nzi.next_zorder_index(15)\n# return 36\n```\n\n## Reference\n\n- [trevorprater/pymorton: A lightweight and efficient Python Morton encoder with support for geo\\-hashing](https://github.com/trevorprater/pymorton)\n- [Z\\-order curve \\- Wikipedia](https://en.wikipedia.org/wiki/Z-order_curve)\n- [Z\\-Order Indexing for Multifaceted Queries in Amazon DynamoDB: Part 1 \\| AWS Database Blog](https://aws.amazon.com/jp/blogs/database/z-order-indexing-for-multifaceted-queries-in-amazon-dynamodb-part-1/)\n- [Z\\-order indexing for multifaceted queries in Amazon DynamoDB: Part 2 \\| AWS Database Blog](https://aws.amazon.com/jp/blogs/database/z-order-indexing-for-multifaceted-queries-in-amazon-dynamodb-part-2/)\n- Tropf, H.; Herzog, H. (1981), [\"Multidimensional Range Search in Dynamically Balanced Trees\"](http://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf)\n\n# pyzorder\uff08\u65e5\u672c\u8a9e\u30c9\u30ad\u30e5\u30e1\u30f3\u30c8\uff09\n\nz-order curve (a.k.a. Morton order) \u306e Python \u5b9f\u88c5\n\nz-order curve \u306f\u591a\u6b21\u5143\u30c7\u30fc\u30bf\u3092 1 \u6b21\u5143\u306b\u96c6\u7d04\u3057\u307e\u3059\u3002\n\npyzorder \u3092\u4f7f\u3046\u3053\u3068\u3067\u3001DynamoDB \u306e\u3088\u3046\u306a\u30bd\u30fc\u30c8\u30ad\u30fc\u3092 1 \u3064\u3060\u3051\u6301\u3066\u308b DB \u306b\u3064\u3044\u3066\u3001\u591a\u6b21\u5143\u306e\u9818\u57df\u30a4\u30f3\u30c7\u30c3\u30af\u30b9\u3092\u53ef\u80fd\u306b\u3057\u307e\u3059\u3002\n\n## \"z-order curve\" \u3068\u306f?\n\nz-order curve \u306f\u3001\u591a\u6b21\u5143\u306e\u30c7\u30fc\u30bf\u30921\u6b21\u5143\u3067\u8868\u3059\u305f\u3081\u306e\u624b\u6cd5\u3067\u3059\u3002\n\u3053\u306e\u3068\u304d\u3001x1 < x2 \u306a\u3089 zorder2(x1, y) < zorder2(x2, y) \u3068\u3044\u3046\u95a2\u4fc2\u304c\u5e38\u306b\u4fdd\u305f\u308c\u308b\u3088\u3046\u306a\u5909\u63db\u306b\u306a\u3063\u3066\u3044\u307e\u3059\u3002\n\u4ed6\u306e\u6b21\u5143\u306b\u3064\u3044\u3066\u3082\u540c\u69d8\u3067\u3059\u3002\n\nz-order curve \u3067\u306f\u3001\u5404\u30d3\u30c3\u30c8\u3092\u30a4\u30f3\u30bf\u30fc\u30ea\u30fc\u30d6\u3059\u308b\u3053\u3068\u3067\u3001\u305d\u306e\u3088\u3046\u306a\u30de\u30c3\u30d4\u30f3\u30b0\u3092\u5b9f\u73fe\u3057\u3066\u3044\u307e\u3059\u3002\n\n![](https://upload.wikimedia.org/wikipedia/commons/thumb/3/30/Z-curve.svg/400px-Z-curve.svg.png)  \n(cited from [Z\\-order curve \\- Wikipedia](https://en.wikipedia.org/wiki/Z-order_curve))\n\n\u5229\u7528\u7528\u9014\u3068\u3057\u3066\u3001DynamoDB \u306e\u3088\u3046\u306b\u30bd\u30fc\u30c8\u7528\u30a4\u30f3\u30c7\u30c3\u30af\u30b9\u3092 1 \u3064\u3060\u3051\u6301\u3066\u308b\u3088\u3046\u306a\u30c7\u30fc\u30bf\u30d9\u30fc\u30b9\u306b\u5bfe\u3057\u3066\u3001\n\u8907\u6570\u306e\u30ab\u30e9\u30e0\u3067\u306e\u30a4\u30f3\u30c7\u30c3\u30af\u30b9\u3092\u5b9f\u73fe\u3057\u305f\u3044\u5834\u5408\u306b\u4f7f\u3048\u307e\u3059\u3002\n\u4f8b\u3048\u3070\u3001x \u5ea7\u6a19, y \u5ea7\u6a19\u306e\u4e21\u65b9\u3067\u30a4\u30f3\u30c7\u30c3\u30af\u30b9\u3092\u3057\u305f\u3044\u5834\u5408\u306a\u3069\u3067\u3059\u3002\nz-order curve \u3067\u30a4\u30f3\u30bf\u30fc\u30ea\u30fc\u30d6\u3057\u305f\u5024\u3092\u683c\u7d0d\u3057\u3066\u304a\u304d\u3001\u305d\u306e\u5024\u3092\u30bd\u30fc\u30c8\u30ad\u30fc\u306b\u3059\u308c\u3070\u30012\u6b21\u5143\u30c7\u30fc\u30bf\u306b\u5bfe\u3059\u308b\u30a4\u30f3\u30c7\u30c3\u30af\u30b9\u304c\u53ef\u80fd\u306b\u306a\u308a\u307e\u3059\u3002\n\u305f\u3060\u3057\u3001\u3053\u306e\u3068\u304d 1 \u3064\u6ce8\u610f\u3059\u3079\u304d\u70b9\u304c\u3042\u308a\u307e\u3059\u3002\n\n![](https://upload.wikimedia.org/wikipedia/commons/thumb/0/02/BIGMIN.svg/400px-BIGMIN.svg.png)  \n(cited again from [Z\\-order curve \\- Wikipedia](https://en.wikipedia.org/wiki/Z-order_curve))\n\n(x = 2, ..., 3, y = 2, ..., 6) \u306e\u7bc4\u56f2\u3092\u30a2\u30af\u30bb\u30b9\u3057\u305f\u3044\u5834\u5408\u3001\u3053\u306e\u56f3\u3067\u306f\u70b9\u7dda\u3067\u56f2\u307e\u308c\u305f\u9818\u57df\u304c\u8a72\u5f53\u3057\u307e\u3059\u3002\n\u3053\u306e\u3068\u304d\u3001z-order \u306e\u5024\u3092\u9806\u756a\u306b\u305f\u3069\u308b\u3068 z-order \"15\" \u306e\u6b21\u306b\u7bc4\u56f2\u5185\u3068\u306a\u308b z-order \u306f \"36\" \u3068\u306a\u3063\u3066\u3044\u307e\u3059\u3002\n\u3064\u307e\u308a\u3001\u3053\u306e\u3088\u3046\u306a 2 \u6b21\u5143\u9818\u57df\u3078\u30a2\u30af\u30bb\u30b9\u3059\u308b\u5834\u5408\u306f\u3001\u5358\u7d14\u306b z-order \u306e\u5024\u3092\u305f\u3069\u308b\u306e\u3067\u306f\u306a\u304f\u3001\u3053\u306e\u3088\u3046\u306a \"\u98db\u3073\u5730\" \u3092\u52b9\u7387\u3088\u304f\u51e6\u7406\u3059\u308b\u5fc5\u8981\u304c\u3042\u308a\u307e\u3059\u3002\n\n**`pyzorder` \u306f\u3001\"15\" \u306e\u6b21\u306e\u6709\u52b9\u306a z-order \u3067\u3042\u308b \"36\" \u3092\u6c42\u3081\u308b `next_zorder_index` \u3092\u5b9f\u88c5\u3057\u3066\u3044\u307e\u3059\u3002**\n\u3053\u308c\u306b\u3088\u308a\u3001z-order curve \u3067\u8868\u73fe\u3055\u308c\u305f\u30c7\u30fc\u30bf\u304b\u3089\u3001\u4efb\u610f\u306e2\u6b21\u5143\u9818\u57df\u3078\u306e\u30a2\u30af\u30bb\u30b9\u3092\u5b9f\u73fe\u3067\u304d\u307e\u3059\u3002\n\n\u306a\u304a\u3001`next_zorder_index` \u3092\u6c42\u3081\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f Tropf, H.; Herzog, H. (1981), [\"Multidimensional Range Search in Dynamically Balanced Trees\"](http://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf)\n\u3067\u63d0\u6848\u3055\u308c\u305f\u3082\u306e\u3092 Python \u3067\u5b9f\u88c5\u3059\u308b\u3053\u3068\u3067\u5b9f\u73fe\u3057\u3066\u3044\u307e\u3059\u3002\uff08\u8ad6\u6587\u4e2d\u306e `BIGMIN` \u3068\u3044\u3046\u95a2\u6570\u304c\u8a72\u5f53\u3057\u307e\u3059\uff09\n\n## \u4f7f\u3044\u65b9\n\n```python\nfrom pyzorder import ZOrderIndexer\n\nzi = ZOrderIndexer((2, 3), (2, 6))\n\nz_2_2 = zi.zindex(2, 2)\n# z_2_2 = 12\n\nzi.next_zorder_index(z_2_2)\n# return 13\n\nzi.next_zorder_index(15)\n# return 36\n```\n\n## \u53c2\u8003\n\n- [trevorprater/pymorton: A lightweight and efficient Python Morton encoder with support for geo\\-hashing](https://github.com/trevorprater/pymorton)\n- Tropf, H.; Herzog, H. (1981), [\"Multidimensional Range Search in Dynamically Balanced Trees\"](http://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf)\n- [Z\\-order curve \\- Wikipedia](https://en.wikipedia.org/wiki/Z-order_curve)\n- [Z\\-Order Indexing for Multifaceted Queries in Amazon DynamoDB: Part 1 \\| AWS Database Blog](https://aws.amazon.com/jp/blogs/database/z-order-indexing-for-multifaceted-queries-in-amazon-dynamodb-part-1/)\n- [Z\\-order indexing for multifaceted queries in Amazon DynamoDB: Part 2 \\| AWS Database Blog](https://aws.amazon.com/jp/blogs/database/z-order-indexing-for-multifaceted-queries-in-amazon-dynamodb-part-2/)",
        "description_content_type": "text/markdown",
        "docs_url": null,
        "download_url": "",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/smatsumoto78/pyzorder",
        "keywords": "",
        "license": "MIT",
        "maintainer": "",
        "maintainer_email": "",
        "name": "pyzorder",
        "package_url": "https://pypi.org/project/pyzorder/",
        "platform": "",
        "project_url": "https://pypi.org/project/pyzorder/",
        "project_urls": {
            "Homepage": "https://github.com/smatsumoto78/pyzorder"
        },
        "release_url": "https://pypi.org/project/pyzorder/0.0.1/",
        "requires_dist": null,
        "requires_python": "",
        "summary": "z-order curve (a.k.a. Morton order) implementation in Python",
        "version": "0.0.1"
    },
    "last_serial": 5627537,
    "releases": {
        "0.0.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "04e0afe9399d66b4c6b0472d85965ac7",
                    "sha256": "fcd3b9cdd7bb04d755c44995e10a86e41ea6527f1833d83671c35db677ad0e15"
                },
                "downloads": -1,
                "filename": "pyzorder-0.0.1.tar.gz",
                "has_sig": false,
                "md5_digest": "04e0afe9399d66b4c6b0472d85965ac7",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 6126,
                "upload_time": "2019-08-03T08:15:35",
                "url": "https://files.pythonhosted.org/packages/7a/3c/cecb4e4c412ee3240e8f67e0dbada90aaf73a127a9ecab1c731d4bbd1896/pyzorder-0.0.1.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "04e0afe9399d66b4c6b0472d85965ac7",
                "sha256": "fcd3b9cdd7bb04d755c44995e10a86e41ea6527f1833d83671c35db677ad0e15"
            },
            "downloads": -1,
            "filename": "pyzorder-0.0.1.tar.gz",
            "has_sig": false,
            "md5_digest": "04e0afe9399d66b4c6b0472d85965ac7",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 6126,
            "upload_time": "2019-08-03T08:15:35",
            "url": "https://files.pythonhosted.org/packages/7a/3c/cecb4e4c412ee3240e8f67e0dbada90aaf73a127a9ecab1c731d4bbd1896/pyzorder-0.0.1.tar.gz"
        }
    ]
}