trouver des maisons dans un rayon

Lors d'une interview, on m'a demandé ce qui suit: Une application immobilière qui répertorie toutes les maisons qui sont actuellement sur le marché (c'est-à-dire à vendre) à une distance donnée (par exemple, l'utilisateur souhaite trouver toutes les maisons à moins de 30 km), comment concevriez-vous votre application (structure de données et alogirithme) pour construire ce type de service?

Des idées? Comment le mettriez-vous en œuvre? Je lui ai dit que je ne savais pas parce que je n'avais jamais fait de trucs liés à la géo auparavant.

Ils sont probablement après une réponse mentionnant l'indexation spatiale , très probablement en sélectionnant une base de données qui fournit une indexation spatiale prête à l'emploi , mais vous pouvez également obtenir quelques points en mentionnant qu'elle peut être implémentée dans l'application elle-même si nécessaire, par exemple en implémentant un R -Arbre (peut être utile si la sélection de base de données est fixée pour d'autres raisons? Mais montre également que vous savez comment fonctionnent les bases de données spatiales). L'indexation spatiale vous permettra d'obtenir rapidement un sous-ensemble d'emplacements qui s'inscrivent dans une boîte de recherche, vous pouvez affiner cela en calculant la distance réelle (si nécessaire, le rectangle seul peut être assez bon bien sûr) pour chacun pour donner une vraie recherche cercle / ellipse

Étant donné que les distances sont probablement de 20 m ou moins, vous êtes probablement d'accord en supposant une terre plate pour calculer la distance bien que vous commencerez à voir des erreurs notables vers l'extrémité de 20 m, si des plages beaucoup plus grandes sont nécessaires avec précision, vous devrez également commencer à chercher de meilleurs modèles de distance pour le globe, par exemple la distance Haversine

il y a aussi bien sûr une myriade d'autres détails qui pourraient être discutés, par exemple la conception de l'interface utilisateur, le schéma de base de données qui pourraient être des sujets entiers à part entière

Chaque fois que vous êtes confronté à une question comme celle-ci et que vous n'avez tout simplement pas d'expertise dans le domaine problématique, il est bon de faire quelques choses.

Tout d'abord, reconnaissez que vous n'avez pas d'expertise spécifique dans ce domaine problématique.

Deuxièmement , expliquez comment vous pourriez résoudre le problème.

Bien que je n'aie pas d'expérience spécifique en matière de recherche géographique, je suis convaincu qu'il existe des algorithmes bien documentés et des technologies existantes pour résoudre le problème. Je les explorerais pour acquérir des connaissances sur les solutions communes à ma disposition et faire un choix de mise en œuvre en fonction des exigences du projet.

Troisièmement , réduisez toujours les problèmes comme celui-ci jusqu'aux composants de base. Vous savez que les emplacements sur une carte sont distribués en deux dimensions. Vous savez que si vous obtenez des coordonnées arbitraires x, y, la distance à chaque coordonnée d'une autre coordonnée est calculée en formant un triangle et en résolvant la longueur inconnue. Nous espérons également que si l'on vous demande de trouver toutes les coordonnées dans une boîte englobante, vous pouvez le faire simplement en calculant l'étendue de la boîte que vous souhaitez rechercher et en utilisant une logique supérieure à, inférieure à la logique le long des deux axes.

Enfin , je n'ai jamais embauché un développeur qui semblait abandonner les questions. Si je pose une question et que la personne dit "je ne sais pas" et n'essaie même pas d'y réfléchir verbalement, cela me donne l'impression qu'elle ne contribuera pas aux séances de remue-méninges - ce qui est essentiel dans les organisations qui écrivent des logiciels .

Cela est probablement évident, mais pour de nombreuses applications, la solution lente du pauvre peut convenir.

Avoir une table dans une base de données relationnelle qui stocke la latitude et la longitude. Recherchez tous les emplacements qui ont une latitude à moins de 20 miles et une longitude à moins de 20 miles. Cela vous donne un rectangle englobant de la taille du plus petit rectangle englobant qui contient le rayon que vous voulez vraiment rechercher (et ignore également la courbure de la terre).

Ensuite, vous prenez l'ensemble renvoyé (par une requête à l'aide d'index) et le filtrez en utilisant un calcul précis de la distance.

Donc, pas de performances efficaces, mais très efficaces à temps pour se développer. Pour de nombreuses applications, cela pourrait être un meilleur choix.

La façon la plus simple est probablement d'utiliser un arbre quadruple pour stocker les emplacements de vos maisons, en supposant qu'ils soient répartis dans un paysage 2D. La recherche doit être assez simple.

Si vous utilisez un SGBDR compatible SIG pour stocker vos données, vous n'avez vraiment pas à vous en soucier. Voir cette question pour quelques informations sur les performances des joueurs principaux.