أقرب مربع الشبكة إلى نقطة في الإحداثيات الكروية

Question

أنا برمجة خوارزمية حيث كنت قد تفككت سطح المجال في نقاط الشبكة (على البساطة لدي شبكة خطوط متوازية عمودية على خطوط الطول).نظرا النقطة ، أود أن تكون قادرة على كفاءة اتخاذ أي شبكة "مربع" و تحديد نقطة ب في مربع مع أقل كروية تنسيق المسافة AB.في تتدهور الحالة "الساحات" هي في الواقع "مثلثات".

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

• قررت أن ترسل هذا السؤال الرياضيات تجاوز: https://mathoverflow.net/questions/854/closest-grid-square-to-a-point-in-spherical-coordinates.مزيد من التقدم قد أحرز هنا

Answer 1

انظر تجاوز الرياضيات: https://mathoverflow.net/questions/854/closest-grid-square-to-a-point-in-spherical-coordinates. حل دقيق

Answer 2

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

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

Answer 3

بضع نقاط من أجل الوضوح.

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

السؤال يتحدث عن [الكمال] المجال.الأمور سوف تكون مختلفة إلى حد ما إذا كنا ننظر في الأرض (أو الكواكب الأخرى) مع بالارض القطبين.

التالي هو "خوارزمية" التي من شأنها أن تناسب مشروع القانون ، أشك في ذلك هو الأمثل ، ولكن يمكن أن توفر أساسا جيدا. تحرير:انظر Tom10 اقتراح للعمل مع عادي 3D المسافة بين نقطة بدلا من المقابلة رائعة cirle المسافة (أيأن الحبل بدلا من قوس) ، كما أن هذا سوف يقلل كثيرا من تعقيد الصيغ.

Problem layout:  (A, B and Sq as defined in the OP's question)
 A  : a given point the the surface of the sphere
 Sq : a given "square" from the grid 
 B  : solution to problem : point located within Sq which has the shortest 
      distance to A.
 C  : point at the center of Sq

Tentative algorithm:
Using the formulas associated with [Great Circle][1], we can:
 - find the equation of the  circle that includes A and C
 - find the distance between A and C. See the [formula here][2] (kindly lifted
    from Tom10's reply).
 - find the intersect of the Great Circle arc between these points, with the
   arcs  of parallel or meridian defining the Sq.
   There should be only one such point, unless this finds a "corner" of Sq, 
   or -a rarer case- if the two points are on the same diameter (see 
   'antipodes' below).
Then comes the more algorithmic part of this procedure (so far formulas...):
 - find, by dichotomy, the point on Sq's arc/seqment which is the closest from
   point A.  We're at B! QED.

Optimization:  
 It is probably possible make a good "guess" as to the location
 of B, based on the relative position of A and C, hence cutting the number of
 iterations for the binary search.
 Also, if the distance A and C is past a certain threshold the intersection
 of the cicles' arcs is probably a good enough estimate of B.  Only when A
 and C are relatively close will B be found a bit further on the median or
 parallel arc in these cases, projection errors between A and C (or B) are
 smaller and it may be ok to work with orthogonal coordinates and their 
 simpler formulas.

Another approach is to calculate the distance between A and each of the 4 
corners of the square and to work the dichotomic search from two of these
points (not quite sure which; could be on the meridian or parallel...)

( * ) *Antipodes case*:  When points A and C happen to be diametrically 
opposite to one another, all great circle lines between A and C have the same
 length, that of 1/2 the circonference of the sphere, which is the maximum any
 two points on the surface of a sphere may be.  In this case, the point B will
 be the "square"'s corner that is the furthest from C. 

آمل أن يساعد هذا...

Answer 4

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