<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Josh Baker on Medium]]></title>
        <description><![CDATA[Stories by Josh Baker on Medium]]></description>
        <link>https://medium.com/@tidwall?source=rss-2ee4c13b361a------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*zWLSnQj9W0obtEJsNCHwqQ.png</url>
            <title>Stories by Josh Baker on Medium</title>
            <link>https://medium.com/@tidwall?source=rss-2ee4c13b361a------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 23:05:06 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@tidwall/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Faster geospatial queries in Tile38]]></title>
            <link>https://medium.com/@tidwall/faster-geospatial-queries-in-tile38-f771e2f6b1bd?source=rss-2ee4c13b361a------2</link>
            <guid isPermaLink="false">https://medium.com/p/f771e2f6b1bd</guid>
            <category><![CDATA[geospatial]]></category>
            <category><![CDATA[database]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Josh Baker]]></dc:creator>
            <pubDate>Mon, 15 Oct 2018 15:46:29 GMT</pubDate>
            <atom:updated>2018-10-16T16:37:35.126Z</atom:updated>
            <content:encoded><![CDATA[<h3>Faster spatial queries in Tile38</h3><h4>Search complex geospatial data in an instant</h4><p>The most common request from <a href="https://tile38.com/">Tile38</a> users is for faster spatial queries. Specifically the point-in-polygon operation.</p><p>I pushed an <a href="https://github.com/tidwall/tile38/commit/6257ddba788c37f93458b3a65a7ab94c6d27e933">update</a> to the master branch over the weekend that includes faster point-in-polygon and geometry intersect operations. The performance increase comes from indexing complex polygon segments into discrete <a href="https://github.com/tidwall/boxtree">R-trees</a> and ray casting the point as a rect with infinite X extents.</p><p>Here’s an example of the performance increase.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hqsUDZanh2tP1Xueg-uv5Q.png" /></figure><h3>Indexing the segments</h3><p>First take all of the polygon’s segments and bulk load them into an R-tree. This makes searching for segments very fast.</p><p><em>For simple polygons, less than 64 points, there’s no need to index.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9tTJNhPoI2s7KQf4wWDnWw.png" /></figure><h3>Search for segment candidates</h3><p>With an indexed polygon, finding the segments for ray casting is super fast. You just make a rectangle with the min-y and max-y coordinates equal to the target point and the min-x and max-x equal to -infinity and +infinity. Then search for the r-tree for overlapping rectangles.</p><p>From there you perform the <a href="https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm">Ray casting algorithm</a> on the segments.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sFwpWZ2Eoirvy_RZ4X-4Vw.gif" /></figure><p>You can find this update in <a href="https://github.com/tidwall/tile38">Tile38’s master branch</a> today.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f771e2f6b1bd" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>