خوارزمية لإيجاد مكان قريب النقاط ؟

Question

بالنظر إلى مجموعة من عدة ملايين من النقاط x,y إحداثيات, ما هو خوارزمية خيار بسرعة العثور على أعلى 1000 أقرب نقطة من موقع ؟ "بسرعة" يعني هنا عن 100ms على كمبيوتر المنزل.

القوة الغاشمة يعني به الملايين من الضرب ومن ثم فرزها.في حين حتى الثعبان بسيط التطبيق يمكن أن تفعل ذلك في أقل من دقيقة ، فإنه لا يزال طويلا من أجل تطبيق تفاعلي.

المربع المحيط على النقاط التي سوف تكون معروفة ، لذلك تقسيم المساحة إلى شبكة بسيطة من الممكن.ومع ذلك النقاط يتم توزيعها بشكل غير متساو إلى حد ما, لذلك أظن معظم الساحات الشبكة ستكون فارغة ثم فجأة بعض منها تحتوي على نسبة كبيرة من النقاط.

تحرير:لا يجب أن تكون دقيقة, في الواقع يمكن أن تكون دقيقة تماما.لن تكون صفقة كبيرة إذا كان أعلى 1000 هي في الواقع مجرد بعض النقاط العشوائية من أعلى 2000 على سبيل المثال.

تحرير:مجموعة من النقاط نادرا ما يتغير.

Answer 1

وماذا عن استخدام quadtree ؟

ويمكنك تقسيم المنطقة إلى مستطيلات، وإذا كان المجال ديها كثافة منخفضة من النقاط، مستطيلات كبيرة، وإذا كان المجال ديها كثافة عالية من النقاط، والمستطيلات تكون صغيرة. كنت متكرر تقسيم كل مستطيل إلى أربعة مستطيلات الفرعية حتى مستطيلات صغيرة بما فيه الكفاية أو تحتوي على عدد قليل من ما يكفي من النقاط.

ويمكنك البدء ثم النظر في النقاط في المستطيلات بالقرب من الموقع، ونقل إلى الخارج حتى كنت قد وجدت لديك 1000 نقطة.

ورمز لهذا يمكن الحصول على معقد إلى حد ما، لذلك ربما عليك أن تحاول أولا مع شبكة بسيطة ومعرفة ما اذا كان سريع بما فيه الكفاية.

Answer 2

وQuadtrees لطيفة، ولكن الأشجار BSP مضمونة للتشغيل في O (تسجيل ن) وقت . أعتقد quadtrees تتطلب حجم المحيط محدود، ووهناك بعض الحالات المنحطة حيث تفشل فشلا ذريعا quadtrees، مثل عند عدد كبير من النقاط تشغل نفس المساحة الصغيرة نسبيا.

وأن يقال، Quadtrees هي أسهل القول لتنفيذ وفعالة جدا في حالات الأكثر شيوعا. وهذا ما يستخدم UPS في خوارزميات التوجيه الخاصة بها، لأنه من عيوب لا تشكل مشاكل كبيرة في الممارسة العملية، ربما لأن المدن تميل الى ان تكون موزعة على المنطقة من اهتمام.

Answer 3

وتحتاج إلى استخدام هيكل مثل شجرة رباعية، أو RTree. هذه هي الهياكل مؤشر متعددة الأبعاد.

والمفتاح هو استخدام جيد "منحنى ملء الفضاء"، وهو ما يساعد على تحديد القرب من النقاط. A ملء الفضاء منحنى بسيط هو Zorder، ولكن هل سيكون أكثر اهتماما في ما يشبه منحنى هيلبرت.

http://en.wikipedia.org/wiki/Space_filling_curve

وأنا لا أعرف من أي تطبيقات الجاهزة من هذه الاشياء. كنت مؤخرا قد نفذت بلدي RTree في 2 الأبعاد التي تدعم فقط التحميل والبحث بالجملة (عن طريق المربع المحيط المقدمة).

وعيب واحد هنا هو أن لديك ليتم احتواء النقاط الخاصة بك في منطقة محدودة. هناك نعرف أن هناك مساحة ملء المنحنيات التي تعمل من أجل المساحات التي لا محدود، ولكن أنا لا أعرف عنهم شيئا.

Answer 4

وبالإضافة إلى QuadTree وBSP اقتراحات شجرة، يجب أن ننظر حتى أقرب جار البحث . ويستند اختيار الخوارزمية على عدد المرات التي تقوم بإضافتها إلى مجموعة البيانات الأساسي الخاص بك. إذا كنت تقوم بإضافة وإزالة كثير من الأحيان، حلول شجرة متفوقة. إذا كانت البيانات أكثر ثابتة، أقرب جار البحث ويمكن أن المخططات voronoi يكون أسرع بكثير، وتحجيم أفضل.

Answer 5

وإذا كانت مجموعة من النقاط نادرا ما يتغير، هل يمكن أن تنظر أيضا في استخدام مخطط فورونوي. لست متأكدا اذا كان ذلك يساعد في العثور على الأولى نقطة أسرع، ولكن ينبغي أن تجعل من الأسهل كثيرا للعثور على 999 نقطة المقبلة.

Answer 6

وأفترض النقاط هي في قاعدة بيانات أو بعض المواقع المفهرسة للبحث؟ إذا كان الأمر كذلك فإنه يجب أن تكون سريعة جدا. من نقطة معينة يمكن أن يكون لديك مجموعة على سين وصاد محور والحصول على جميع المواقع داخل هذا النطاق (أي تحديد أعلى يقم معظم الزاوية العاشر (أ) و y (ب) وأسفل الأكثر الصحيح الزاوية س (ج) و y (د)).

وثم القيام الاستعلام حيث للحصول على نقاط حيث ص => ب و ص <= D و س> = A و س <= ج. هذا سوف تكون سريعة على افتراض لديك الفهارس على x و y ينسق seperatly. (على افتراض الأصل هو 0،0 في أعلى اليسار).

ويمكنك بعد ذلك زيادة (أو نقصان إذا النتيجة هي ضخمة) هذا النطاق من قبل ض حتى عدد من النقاط ضمن مجموعة نتائج> = 1000. ومن خلال بعض محاكمة يدير يجب أن تكون قادرة على الخروج مع انحراف معياري وغيرها الأرقام الإحصائية التي من شأنها أن تساعدك على تحديد حجم المستطيل لتبدأ. البرنامج يمكن أيضا ضبط النفس من أجل هذا بناء على النتائج التي يحصل.

وبعد الانتهاء من إعداد البيانات الخام الرياضيات لها بسيطة جدا للعمل على المسافة بين كل نقطة والنقطة المصدر.

Answer 7

وأنا أعلم به قال لا يجري أسرع إذا كنت تريد حقا حقا نتائج سريعة من خلال رؤية لقد وجدت هذا المنصب من جوجل فكرت في إضافة my SQL الحل الذي اعتدت منذ فترة في شكل تخزينها proc.فإنه يبحث عن مواقع قريبة من coord و يعود لهم من خلال المسافة.

وآمل أن يساعد شخص ما :)

CREATE PROCEDURE [dbo].[getstores] @lat float,  @lng float AS
DECLARE @radius float, @DegToRad float
SET @DegToRad = 57.29577951
SET @radius = 25000
SELECT TOP 10
    name
    ,sto_lat
    ,sto_lng
    ,postcode
    ,ROUND((ACOS((SIN(@lat/57.2958) * SIN(sto_lat/@DegToRad)) +(COS(@lat/@DegToRad) * COS(sto_lat/@DegToRad) *COS(sto_lng/@DegToRad - @lng/@DegToRad))))* 6387.7, 2) AS distance
FROM store
WHERE (sto_lat >= @lat - (@radius/111))
And (sto_lat <= @lat + (@radius/111))
AND (sto_lng >= @lng - (@radius/111))
AND (sto_lng <= @lng + (@radius/111))
AND (
     ISNUMERIC(sto_lat) = 1
    AND
    ISNUMERIC(sto_lat) = 1
)
ORDER BY distance

ملاحظة:لقد سبق أن ذكرت أن هذا هو أفضل حل هذا السؤال ببساطة ربما لشخص وجدت هذا على جوجل مثلي