查找计划最近的交叉点 [英] Find the Closest intersection point in plan

问题描述

有人问我在采访中以下问题最近：

I was asked following question in interview recently:

让假设你有，以下电网笛卡尔坐标系（象限I）上。

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）方法是kd树，但你知不知道任何其他解决方案？

1) Approach is k-d tree, but do you know any other solution ?

谢谢， Bmis13

Thanks, Bmis13

更新：谢谢大家的回答这个问题，我凑近了很多......谢谢大家，祝大家新年快乐!!所有

Update: Thank you all for answering this question I leaned a lot... Thank you all and Happy New Year to All !!

推荐答案

如果问题要求最小化曼哈顿距离（也就是人们只能步行平行于轴线），那么问题就那么pretty的琐碎。首先，选择的 X 的坐标和的是的坐标是独立的问题。

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.

然后，对于每个坐标，只需找到沿轴线人民的立场的中间值。对于人许多配置，可以有一个以上的点最小化所有的人的步行距离的总和。 （只是考虑2人由以上2块x中，并在同一y坐标分开;二者之间的任何交叉点都需要相同的总行走由两个人）

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.)

如果该问题需要最小的欧几里德距离，则目标是要找到2-可变的L1中位数。这是一个标准的问题，但它是远离微不足道。 （见这里，例如。）有唯一的答案。鉴于这是一个面试问题，我怀疑这并不适用。

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.

这篇关于查找计划最近的交叉点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！