找到计划中最近的交点
最近在采访中我被问到以下问题：
假设您有笛卡尔坐标系（象限 I）上的网格。
o - x - x - x - o
| | | | |
x - x - x - o - x
| | | | |
x - o - o - x - x
where, o => person at intersection and x => no person at intersection
class Point {
int x;
int y;
boolean hasPerson;
}
Point findNearestPointWhereAllPeopleCanMeet(Point[] people) {
}
实现一个例程，其中给定人员位置（点）列表，找到距离所有给定点最近的点的位置（点）。
你会如何解决这个问题？
1）方法是kd树，但是你知道其他解决方案吗？
I was asked following question in interview recently:
Let suppose you have, following grid on Cartesian coordinate system ( Quadrant I).
o - x - x - x - o
| | | | |
x - x - x - o - x
| | | | |
x - o - o - x - x
where, o => person at intersection and x => no person at intersection
class Point {
int x;
int y;
boolean hasPerson;
}
Point findNearestPointWhereAllPeopleCanMeet(Point[] people) {
}
Implement a routine where given a list of people location (points), find a location(point) such that is closest point to all given point.
How would you solve this problem ?
1) Approach is k-d tree, but do you know any other solution ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果问题需要最小化曼哈顿距离（也就是说，人们只平行于轴线行走） ，那么问题就相当微不足道了。首先，选择x坐标和y坐标是独立的问题。
然后，对于每个坐标，只需找到人沿该轴的位置的中值即可。对于许多人的配置，可以有多个点来最小化所有人的步行距离之和。 （只需考虑 2 个人在 x 方向上相距超过 2 个块且位于相同的 y 坐标；两者之间的任何交叉点都将需要两个人的总步行量相同。）
如果问题要求最小化欧几里得距离，那么目标是找到 2 变量 L1 中位数。这是一个标准问题，但绝非微不足道。 （例如，参见此处。）独特的答案。鉴于这是一个面试问题，我怀疑这并不适用。
If the problem calls for minimizing the Manhattan distance (that is, people only walk parallel to the axes), then the problem is then pretty trivial. First, selecting the x coordinate and the y coordinate are independent problems.
Then, for the each coordinate, simply find the median value of the position of the people along that axis. For many configurations of people, there can be more than one point that minimizes the sum of the walking distances of all people. (Just consider 2 people separated by more than 2 blocks in x and at the same y coordinate; any intersection in between will require the same total walking by the two people.)
If the problem calls for minimizing the Euclidean distance, then the goal is to find the 2-variable L1 median. This is a standard problem, but it is far from trivial. (See here, for instance.) There is a unique answer. Given that this was an interview question, I suspect that this does not apply.
在研究 kd 树之前，我想到了以下一些想法：
取具有最低 MAX_distance E.G. 。给定点(0,0)：
(0,0) 的 MAX_distance 为 6。根据您的输入，最低 MAX_distance 应为 3，并且有许多点具有该值，例如 (2,1)。
应该有办法让这个算法更高效。也许可以使用 kd 树 :p 或其他调整，例如检查总人数、他们的相对位置/距离、任何迭代的 MAX_distance 值等。
Before going to study k-d trees these are some thoughts that came to my mind:
E.G. Given Point(0,0):
The MAX_distance for (0,0) is 6. Given your input the lowest MAX_distance should be 3 and there are many Points with that value like (2,1) for instance.
There should be ways to make this algorithm more efficient.. Maybe with k-d trees :p or with other tweaks like checking the total number of people, their relative location/distance, the MAX_distance value at any iteration, etc..
这可能会为您提供比正确答案更多的近似答案。
但也许你可以尝试某种聚类（参见医学图像处理）
如果将所有点投影到 Y 轴上：
然后投影到 X 轴上：
图例： 3* 表示轴上的该坐标有 3 个人
现在找到中位数还使用权重（权重@位置=轴上该位置有多少人）
如果您找到两个轴的中位数，那么您可以将交汇点视为（medianX，medianY）。
如果在计算一个轴上的中值时，还确保通过计算另一轴的中值来最小化距离，则可以获得正确的最近点。后一种情况更难。
This will probably give you more of an approximate than the correct answer.
But maybe you can try some sort of clustering (see medical image processing)
What if you project all points onto the Y axis:
Then project onto the X axis:
Legend: 3* means 3 people at this coordinate on the axis
Now find the median also using the weights (weight @location = how many people at that location on axis)
If you find the median for both axis then you could take the meeting points as (medianX, medianY).
You could get the correct closest point if when you calculate median on one axis, you also make sure to minimize distance by calculating the median of the other axis. This latter case is harder.