Cross-referencing in lists with slightly different coordinates
<p>I want to do something very similar to the question asked here:</p>

<p><a href="http://stackoverflow.com/questions/28393071/comparing-two-lists-of-coordinates-in-python-and-using-coordinate-values-to-assi">Comparing two lists of coordinates in python and using coordinate values to assign values</a></p>

<p>That is, I have two lists of coordinates (say, x and y), and I want to extract a quantity from list 2 if the (x,y) coordinates match the (x,y) coordinates in list 1.</p>

<p>Now, the answers in the question linked above do nicely for this, as long as the coordinates match <strong>exactly</strong></p>

<p>However, I want to account for possibly slight variations. So, suppose there is a small deviation dx or dy in either coordinates. And suppose I say, "for <code>dx&lt;R</code>, I consider these coordinates the same." How would I go about putting that into code - keeping in mind the solution already given in the link above (or another creative solution, of course).</p>

<p>Note: for the quick and dirty solution (a double for-loop) this is relatively easy. It is more tricky with the O(n) solution given in the accepted answer, which is what I'm looking for.</p>

<p>This is definitely a computational geometry algorithm. You can reformulate it as follows: given a set of points in a plane, find for all points <code>P</code> the set of all points at a distance <code>&lt;= R</code> (with respect to the <a href="https://en.wikipedia.org/wiki/Chebyshev_distance" rel="nofollow">Chebyshev distance</a>, provided that the conditions <code>dx &lt;= R</code> and <code>dy &lt;= R</code> must happen).</p>

<p>The solution in quadratic time is easy: you just have to check if a point lie in a given square. Nevertheless, I don't think the method based on hash table (which runs in <em>average</em> linear time) can be adapted easily.</p>

<p>A solution in <code>O(n log n)</code> is conceivable, however (though it may be dominated by the number of points in each square: I assume <code>R</code> is very small, so that there is only a constant amount of points in a given square in average).</p>

<p>For this you can adapt a <a href="https://en.wikipedia.org/wiki/Sweep_line_algorithm" rel="nofollow">sweep-line algorithm</a>. First you can "discretize" coordinates by considering only <code>x</code> an <code>y</code> corresponding to a given point in the input (this is used to make requests on <em>coordinates</em> rather than on <em>points</em>, while keeping a complexity only based on the number of points in the input).</p>

<p>After that, you can sort your points e.g. according to their <code>x</code> coordinate. In fact it would be better to add also the "events" at <code>x+r</code> and <code>x-r</code> (you can put an event on <code>x</code> too, in order to consider each point rather than sweeping in a distinct data structure) for each point, corresponding to the left and to the right corner of the square. Sweep through these events, adding points when a left corner is encountered in a binary search tree ordered by <code>y</code> coordinate (*) and removing them when you read a right corner event. </p>

<p>Thus, at a given time, your tree contains exactly the points <code>(x, y)</code> with <code>|x-xcurrent| &lt;= R</code> with respect to the current event. When you get a point, you just have to find all points in the set <code>(x, y)</code> verifying <code>|y-ycurrent| &lt;= R</code> with respect to the current event.</p>

<p>(*) In fact, it might be possible to use data structures such as <a href="https://en.wikipedia.org/wiki/Fenwick_tree" rel="nofollow">Fenwick trees</a> which are easier to code "from scratch" and resulting in lower constants than complex data structures such as binary search trees.</p>

python algorithm list