在 2D 中查找远程点
我在无限（好吧，双精度）二维平面上有一组点。
给定该集合的凸包，如何找到凸包内部距离输入集合中所有点相对较远的一些点？
在下图中，黑色点是原始集合的一部分，阴影区域表示如果我们以半径 R“增长”它们，则所有点所占据的空间。
橙色点是我想要得到的示例。它们具体在哪里并不重要，只要它们距离所有黑点相对较远即可。
最远点搜索 http://en.wiki.mcneel.com/content /upload/images/point_far_search.png
更新：使用 delaunay 算法查找大的空三角形似乎是一个很好的方法： Delaunay 解决方案 http://en.wiki.mcneel.com/content/上传/图片/DelaunaySolutionToInternalFurthestPoints.png
I have a set of points on the infinite (well, double precision) 2D plane.
Given the convex hull for this set, how can find some points on the inside of the convex hull that are relatively far away from all the points in the input set?
In the image below, the black points are part of the original set and the hatched area represents the space taken up by all the points if we "grow" them with radius R.
The orange points are examples of what I'd like to get. It doesn't really matter where exactly they are, as long as they are relatively far away from all the black points.
Furthest Point Search http://en.wiki.mcneel.com/content/upload/images/point_far_search.png
Update: Using a delaunay algorithm to find large empty triangles seems to be a great approach for this:
Delaunay Solution http://en.wiki.mcneel.com/content/upload/images/DelaunaySolutionToInternalFurthestPoints.png
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这是一个可以使用 KD-Trees 解决问题的一个很好的例子。数值食谱第三次添加中有一些很好的注释。
如果您试图找到相对孤立的点位置......也许最大四边形元素的中心将是一个不错的候选者。
创建 KD 树的复杂度为 O(n log^2 n)...而创建四边形大小的排序列表将为 O(n Log n)。即使对于大量点来说似乎也是合理的（当然，这取决于您的要求）。
This is a good example of a problem that may be solved using KD-Trees... there are some good notes in Numerical Recipes 3rd Addition.
If you are trying to find point locations that are relatively isolated... maybe the center of the largest quad elements would be a good candidate.
The complexity would be O(n log^2 n) for creating the KD-Tree... and creating a sorted list of quad sizes would be O(n Log n). Seems reasonable for even a large number of points (of course, depending on your requirements).
这是一个简单的算法：
对于 (2)，将其视为半径搜索仍然意味着您最终会计算每个点到其他点的距离，因为查找一个点是否位于另一个点的给定半径内与查找距离是一样的点之间。
为了优化搜索，您可以将空间划分为网格，并将每个点分配给一个网格位置。然后，您对上述 (2) 的搜索将首先检查同一个方格内的和周围的 8 个方格。如果到另一个点的最小距离在同一个方块内，则返回该值。如果它来自 8 之一，并且距离使得 9 之外的点可能更近，则必须检查这 9 之外的网格位置的下一个轮廓，是否有比 9 内发现的更近的点。冲洗/重复。
This is a naive algorithm:
For (2), thinking of this as a radius search still means you end up calculating the distance from each point to each other point, because finding out whether a point lies within a given radius of another point is the same thing as finding the distance between the points.
To optimize the search, you can divide the space into a grid, and assign each point to a grid location. Then, your search for (2) above would first check within the same square and the surrounding 8 squares. If the minimum distance to another point is within the same square, return that value. If it is from one of the 8 and the distance is such that a point outside the 9 could be closer, you have to then check the next outline of grid locations outside those 9 for any closer than those found within the 9. Rinse/repeat.