为它的位置相对于凸包在日志测试点（n）的 [英] Test point for its position relative to the convex hull in log(n)
问题描述
我有2D点的集合取值，我需要测试一个输入点①是内部还是凸包取值之外。
因为它是关于一个二进制的决定，我想我可以在理论上达到 O（日志（N））用决策树。
不过，我不知道如何来组织数据和算法如何将看起来像真正得到答案 O（日志（N））。
虽然有这种想法的研究，我发现这样的：
如何才能更快地找到这两种情况？二进制搜索。只是 在点的两条链的第一个坐标搜索对于x。如果 它是在链中，你已经发现，通过一个顶点交叉（和 你不必尽可能小心地告诉什么样的道口， 其一）。一个顶点如果x不是在链中的坐标，两个 最近的值，它告诉你哪个段从（X，Y）的射线可能 交叉。因此，我们可以测试点是否在一个凸多边形时刻 O（log n）的
事实证明，有数据结构可以测试是否 点是在一个任意的多边形（或哪几个多边形它 中）在同一个 O（log n）的的约束时间。但他们更复杂，所以 我没有时间在这里形容他们。我会谈论他们在一些 点ICS 164。
（<一href="http://www.ics.uci.edu/~eppstein/161/960307.html">http://www.ics.uci.edu/~eppstein/161/960307.html)
那么，你有什么想法：
- 如何将数据结构应该像把它倒在
O（日志（N））？ - 如何算法应该是什么样子？
让我们只处理一条链第一。我们要检查是否（QX，QY）高于线段的凸链。
昂贵的部分是名单上的二分法查找X 坐标找到比你的查询点的最大一个都不能少。所有你需要的是连锁排序 X 秩序的点组成的数组。那么这是一个简单的点线之上？试验。
现在，我们希望看到一个点是否在凸多边形。如果重新present该凸多边形作为上链和下链的边缘，那么它的上部链与下链上面的东西下方的东西的交集。因此，这两个二进制搜索。
（即使你拿到顺时针积分排序顺序什么的，你可以找到的最小和最大 X 坐标的多边形数时间使用二进制搜索或四点搜索，所以你甚至不必为precompute上下链，如果你不想。）
修改：？什么点位数据结构看ILKE我看你的问题，也可以解析为而不是我怎么存储的凸包，允许有效的内部/外部测试？
这是很自然的学习比内外线测试一个稍微大背景下点位置。有一个
CGAL 可以在几个不同的方式做点位置。它写的聪明人，他们正在实施的算法和算法将要使用的计算机有很好的理解。你可能无法找到任何更快过多仍然正常工作。
随着中说，哈兰和霍尔珀林相比的对CGAL的各种算法的性能。他们利用现代计算机在2008年，他们做了很多的测试数据，并试图对每个测试用例CGAL的不同点位置的策略。除其他事项外，它们具有约140万随机放置的边缘的情况下它们的最佳的数据结构只需要约190微秒回答一个点位置询问
这是非常快的考虑的典型点定位算法的复杂性---我不能这样做我自己。而理论告诉我们，它变得像O（log n）的。然而，O（log n）的是几个数量级比O（log n）的需要到搜索排序的数组时慢。记住这一点，当你计算几何;常量重要，它们常常不是非常小的。
I have a collection of 2D points S and I need to test if an input point q is inside or outside the convex hull of S.
Since it's about a binary decision, I was thinking I could theoretically achieve O(log(N)) by using a decision tree.
However I have no idea how to organize the data and how the algorithm would look like to really get an answer in O(log(N)).
While researching with this idea in mind, I've found this:
How can we find these two cases more quickly? Binary search. Just search for x in the first coordinates of points in the two chains. If it is in the chain, you have found a crossing through a vertex (and you don't have to be as careful to tell what kind of crossing, either). If x is not the coordinate of a vertex in the chain, the two nearest values to it tell you which segment the ray from (x,y) might cross. So we can test whether a point is in a convex polygon in time O(log n).
It turns out that there are data structures that can test whether a point is in an arbitrary polygon (or which of several polygons it's in) in the same O(log n) time bound. But they're more complicated, so I don't have time to describe them here; I'll talk about them at some point in ICS 164.
(http://www.ics.uci.edu/~eppstein/161/960307.html)
So do you have any ideas:
- How the data structure should look like to get it down in
O(log(N))? - How the algorithm should look like?
Let's deal with only one chain first. We want to check whether (qx, qy) is above a convex chain of line segments.
The expensive part is is binary searching on a list of x 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 x order. Then it's a simple "point above line?" test.
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.
(Even if you've just got the points in clockwise sorted order or something, you can find the smallest and largest x 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.)
EDIT: 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?"
It is natural to study point location in a slightly more general context than inside-outside testing. There is a
CGAL 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.
With that said, Haran and Halperin compared 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.
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.
这篇关于为它的位置相对于凸包在日志测试点（n）的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
