StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Let's deal with only one chain first. We want to check whether <code>(qx, qy)</code> is above a convex chain of line segments.</p> <p>The expensive part is is binary searching on a list of <code>x</code> coordinates to find the biggest one less than your query point. All you need for this is an array of the points of the chain sorted in <code>x</code> order. Then it's a simple "point above line?" test.</p> <p>Now we want to see whether a point is in a convex polygon. If you represent the edges of that convex polygon as an upper chain and a lower chain, then it's the intersection of the stuff below the upper chain with the stuff above the lower chain. So it's two binary searches.</p> <p>(Even if you've just got the points in clockwise sorted order or something, you can find the smallest and largest <code>x</code> coordinates in the polygon in logarithmic time using binary search or four-point search. So you don't even have to precompute the upper and lower chains if you don't want to.)</p> <p><strong>EDIT</strong>: I see that your question can also be parsed as "what do point location data structures look ilke?" rather than "how do I store the convex hull to permit efficient inside/outside testing?"</p> <p>It is natural to study point location in a slightly more general context than inside-outside testing. There is a </p> <p><a href="http://www.cgal.org" rel="nofollow">CGAL</a> can do point location in a couple of different ways. It's written by smart people with a good understanding of the algorithms they're implementing and the computers the algorithms are going to use. You probably won't be able to find anything too much faster that still works correctly.</p> <p>With that said, Haran and Halperin <a href="http://www.math.tau.ac.il/~danha/papers/landmarks.pdf" rel="nofollow">compared</a> the performance of CGAL's various algorithms. They used a modern computer as of 2008 and they made up a lot of test data and tried CGAL's different point location strategies on each test case. Among other things, they have a case of about 1.4 million randomly-placed edges where their best data structure only needs about 190 microseconds to answer a point location query.</p> <p>This is very fast considering the complexity of typical point location algorithms --- I couldn't do that myself. And the theory tells us that it grows like O(log n). However, that O(log n) is several orders of magnitude slower than the O(log n) time it takes to search a sorted array. Bear that in mind when you do computational geometry; the constants matter and they're often not very small.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload