найти дома в радиусе

Во время собеседования меня спросили, учитывая следующее: приложение для недвижимости, в котором перечислены все дома, которые в настоящее время находятся на рынке (например, продаются) на заданном расстоянии (например, пользователь хочет найти все дома в пределах 20 миль), Как бы вы разработали свое приложение (как структуру данных, так и логарифм) для создания этого типа сервиса?

Любые идеи? Как бы вы это реализовали? Я сказал ему, что не знаю, потому что раньше никогда не занимался гео-делами.

Они, вероятно, после ответа упоминают пространственную индексацию , скорее всего, выбирая базу данных, которая обеспечивает пространственную индексацию из коробки , но вы также можете получить несколько баллов, упомянув, что это может быть реализовано в самом приложении, если это необходимо, например, путем реализации R -Дерево (может быть удобно, если выбор БД фиксирован по другим причинам? Но также демонстрирует, как вы знаете, как работают пространственные базы данных). Пространственная индексация позволит вам быстро получить подмножество местоположений, которые помещаются в поле поиска, вы можете уточнить это далее, рассчитав фактическое расстояние (при необходимости, один прямоугольник может быть достаточно хорошим, конечно) для каждого, чтобы дать истинный поиск круг / эллипс

Принимая во внимание, что расстояния, вероятно, составляют 20 м или менее, вы, вероятно, в порядке, предполагая, что для расчета расстояния используется плоская земля, хотя вы начнете видеть заметные ошибки к концу 20 м. Если точно требуются гораздо большие диапазоны, вам также нужно будет начать смотреть на модели лучшего расстояния. для земного шара, например, расстояние Хаверсайн

Есть также, конечно, множество других деталей, которые можно обсудить, например, дизайн пользовательского интерфейса, схема БД, которые могут быть целыми темами сами по себе.

Всякий раз, когда вы сталкиваетесь с таким вопросом и у вас просто нет опыта в проблемной области, полезно сделать пару вещей.

Сначала подтвердите, что у вас нет специальных знаний в этой проблемной области.

Во-вторых , объясните, как вы решите проблему.

Хотя у меня нет особого опыта работы с географическим поиском, я уверен, что есть хорошо документированные алгоритмы и существующие технологии для решения проблемы. Я хотел бы изучить их, чтобы узнать общие решения, доступные для меня, и сделать выбор в отношении реализации, основываясь на требованиях проекта.

В-третьих , всегда сводите подобные проблемы к их основным компонентам. Вы знаете, что местоположения на карте распределены в двух измерениях. Вы знаете, что если вам заданы произвольные координаты x, y, расстояние до каждой координаты из другой координаты рассчитывается путем формирования треугольника и решения для неизвестной длины. Надеемся, вы также знаете, что если вас попросят найти все координаты внутри ограничительной рамки, вы можете сделать это, просто вычислив экстенты поля, которое вы хотите найти, и используя простую логику больше, меньше, чем по обеим осям.

Наконец , я никогда не нанимал разработчика, который, казалось, отказывался от вопросов. Если я задаю вопрос, а человек говорит: «Я не знаю» и даже не пытается обдумать его устно, у меня создается впечатление, что они не будут участвовать в мозговых штурмах, что очень важно в организациях, которые пишут программное обеспечение. ,

Это, вероятно, очевидно, но для многих приложений медленное решение бедного человека может быть хорошим.

Имейте таблицу в реляционной базе данных, которая хранит широту и долготу. Запросите все местоположения, которые имеют широту в пределах 20 миль и долготу в пределах 20 миль. Это дает вам ограничивающий прямоугольник размером с наименьший ограничивающий прямоугольник, который содержит радиус, который вы действительно хотите найти (и игнорирует также кривизну Земли).

Затем вы берете набор, который возвращается (по запросу с использованием индексов), и фильтруете его, используя точный расчет расстояния.

Таким образом, не эффективная производительность, но очень эффективная во времени, чтобы развиваться. Для многих приложений это может быть лучшим выбором.

Вероятно, самый простой способ - использовать квадри для хранения местоположений ваших домов, предполагая, что они распределены в 2D-ландшафте. Поиск должен быть довольно простым.

Если для хранения ваших вещей вы используете СУБД с поддержкой ГИС, вам не нужно об этом беспокоиться. Посмотрите этот вопрос для получения дополнительной информации о производительности ведущих игроков.