Comment puis-je utiliser ArcGIS 10.1 pour trouver un point équidistant géodésique défini par trois points?

12

Par exemple, j'ai des coordonnées pour trois points de base sur un littoral et j'ai besoin de trouver les coordonnées du point au large de la côte qui est équidistant des trois. C'est un simple exercice de géométrie, mais toutes les mesures doivent tenir compte de la géodésie.

Si j'approchais cela d'une manière euclidienne, je pourrais mesurer les chemins géodésiques reliant les points de base, trouver les points médians des côtés du triangle résultant et créer des orthodromes perpendiculaires à chacun de ces chemins. Les trois loxodromes convergeraient vraisemblablement au point équidistant. Si c'est la bonne méthode, il doit y avoir un moyen plus simple de le faire dans Arc.

Je dois trouver O

Graisse
la source
Existe-t-il des contraintes sur les positions relatives des 3 points? Image côte est, le point médian est le plus à l'est. Votre solution ne fonctionnerait pas car les perpendiculaires ne convergeraient pas au large. Je suis sûr que nous pouvons trouver d'autres mauvais cas!
mkennedy
Je me demande si vous pourriez utiliser une projection préservant la distance et exécuter le calcul à partir de là? progonos.com/furuti/MapProj/Normal/CartProp/DistPres/… Pas sûr de l'algorithme pour le faire, il doit y en avoir un ... peut-être que c'est le barycentre: en.wikipedia.org/wiki/Barycentric_coordinate_system
Alex Leith
Pour trouver des solutions à un problème étroitement lié, recherchez sur notre site la "trilatération" . En outre, gis.stackexchange.com/questions/10332/… est un doublon mais n'a pas de réponses adéquates (probablement parce que la question a été posée de manière confuse).
whuber
@mkennedy Il n'y a, en principe, aucun mauvais cas, seulement des cas numériquement instables. Ceux-ci se produisent lorsque les trois points de base sont colinéaires; les deux solutions (sur un modèle sphérique) se produisent aux deux pôles de la géodésique commune; dans un modèle ellipsoïdal, ils se produisent près de l'endroit où ces pôles seraient attendus.
whuber
L'utilisation de loxodromes ici ne serait pas correcte: ce ne sont pas les bissectrices perpendiculaires. Sur la sphère, ces lignes feront partie de grands cercles (géodésiques), mais sur l'ellipsoïde, elles s'écarteront légèrement de la géodésique.
whuber

Réponses:

10

Cette réponse est divisée en plusieurs sections:

  • Analyse et réduction du problème , montrant comment trouver le point souhaité avec des routines "en conserve".

  • Illustration: un prototype fonctionnel , donnant un code de travail.

  • Exemple , montrant des exemples de solutions.

  • Pièges , discuter des problèmes potentiels et comment y faire face.

  • Implémentation d'ArcGIS , commentaires sur la création d'un outil ArcGIS personnalisé et où obtenir les routines nécessaires.


Analyse et réduction du problème

Commençons par observer que dans le modèle sphérique (parfaitement rond), il y aura toujours une solution - en fait, exactement deux solutions. Étant donné les points de base A, B et C, chaque paire détermine sa "bissectrice perpendiculaire", qui est l'ensemble des points équidistants des deux points donnés. Cette bissectrice est une géodésique (grand cercle). La géométrie sphérique est elliptique : deux géodésiques quelconques se croisent (en deux points uniques). Ainsi, les points d'intersection de la bissectrice AB et de la bissectrice BC sont - par définition - équidistants de A, B et C, résolvant ainsi le problème. (Voir la première figure ci-dessous.)

Les choses semblent plus compliquées sur un ellipsoïde, mais comme il s'agit d'une petite perturbation de la sphère, on peut s'attendre à un comportement similaire. (L'analyse de cela nous mènerait trop loin.) Les formules compliquées utilisées (en interne dans un SIG) pour calculer des distances précises sur un ellipsoïde ne sont cependant pas une complication conceptuelle: le problème est fondamentalement le même. Pour voir à quel point le problème est simple, énonçons-le de manière un peu abstraite. Dans cette déclaration, "d (U, V)" fait référence à la distance vraie et entièrement précise entre les points U et V.

Étant donné trois points A, B, C (en tant que paires lat-lon) sur un ellipsoïde, trouvez un point X pour lequel (1) d (X, A) = d (X, B) = d (X, C) et ( 2) cette distance commune est la plus petite possible.

Ces trois distances dépendent toutes du X inconnu . Ainsi, les différences de distances u (X) = d (X, A) - d (X, B) et v (X) = d (X, B) - d (X, C) sont des fonctions à valeur réelle de X. Encore une fois, de façon quelque peu abstraite, nous pouvons assembler ces différences en une paire ordonnée. Nous utiliserons également (lat, lon) comme coordonnées pour X, ce qui nous permettra de le considérer également comme une paire ordonnée, disons X = (phi, lambda). Dans cette configuration, la fonction

F (phi, lambda) = (u (X), v (X))

est une fonction d'une partie d'un espace à deux dimensions prenant des valeurs dans un espace à deux dimensions et notre problème se réduit à

Trouver tous les possibles (phi, lambda) pour lesquels F (phi, lambda) = (0,0).

C'est là que l'abstraction est payante: il existe de nombreux excellents logiciels pour résoudre ce problème (de recherche de racine multidimensionnelle purement numérique). La façon dont cela fonctionne est que vous écrivez une routine pour calculer F , puis vous la transmettez au logiciel avec toute information sur les restrictions de son entrée ( phi doit se situer entre -90 et 90 degrés et lambda doit se situer entre -180 et 180 degrés). Il démarre pendant une fraction de seconde et retourne (généralement) une seule valeur de ( phi , lambda ), s'il en trouve une.

Il y a des détails à gérer, car il y a un art à cela: il existe différentes méthodes de solution à choisir, selon la façon dont F "se comporte"; il permet de "piloter" le logiciel en lui donnant un point de départ raisonnable pour sa recherche (c'est une façon d'obtenir la solution la plus proche , plutôt que toute autre); et vous devez généralement spécifier à quel point vous souhaitez que la solution soit précise (afin qu'elle sache quand arrêter la recherche). (Pour en savoir plus sur ce que les analystes SIG doivent savoir à propos de ces détails, qui surviennent souvent dans les problèmes SIG, veuillez consulter la rubrique Recommandations à inclure dans un cours d'informatique pour les technologies géospatiales et consultez la section "Divers" vers la fin. )


Illustration: un prototype fonctionnel

L'analyse montre que nous devons programmer deux choses: une estimation initiale brute de la solution et le calcul de F lui-même.

L'estimation initiale peut être faite par une "moyenne sphérique" des trois points de base. Ceci est obtenu en les représentant en coordonnées géocentriques cartésiennes (x, y, z), en faisant la moyenne de ces coordonnées et en projetant cette moyenne dans la sphère et en la ré-exprimant en latitude et longitude. La taille de la sphère est sans importance et les calculs sont donc simples: parce que ce n'est qu'un point de départ, nous n'avons pas besoin de calculs ellipsoïdaux.

Pour ce prototype fonctionnel, j'ai utilisé Mathematica 8.

sphericalMean[points_] := Module[{sToC, cToS, cMean},
  sToC[{f_, l_}] := {Cos[f] Cos[l], Cos[f] Sin[l], Sin[f]};
  cToS[{x_, y_, z_}] := {ArcTan[x, y], ArcTan[Norm[{x, y}], z]};
  cMean = Mean[sToC /@ (points Degree)];
  If[Norm[Most@cMean] < 10^(-8), Mean[points], cToS[cMean]] / Degree
  ]

(La Ifcondition finale teste si la moyenne peut ne pas indiquer clairement une longitude; dans l'affirmative, elle revient à une moyenne arithmétique droite des latitudes et longitudes de son entrée - peut-être pas un excellent choix, mais au moins une valeur valide. Pour ceux qui utilisent ce code comme guide d'implémentation, notez que les arguments de Mathematica ArcTan sont inversés par rapport à la plupart des autres implémentations: son premier argument est la coordonnée x, son second est la coordonnée y et il renvoie l'angle fait par le vecteur ( x, y).)

En ce qui concerne la deuxième partie, car Mathematica - comme ArcGIS et presque tous les autres SIG - contient du code pour calculer des distances précises sur l'ellipsoïde, il n'y a presque rien à écrire. Nous appelons simplement la routine de recherche de racine:

tri[a_, b_, c_] := Block[{d = sphericalMean[{a, b, c}], sol, f, q},
   sol = FindRoot[{GeoDistance[{Mod[f, 180, -90], Mod[q, 360, -180]}, a] == 
                   GeoDistance[{Mod[f, 180, -90], Mod[q, 360, -180]}, b] ==
                   GeoDistance[{Mod[f, 180, -90], Mod[q, 360, -180]}, c]}, 
           {{f, d[[1]]}, {q, d[[2]]}}, 
           MaxIterations -> 1000, AccuracyGoal -> Infinity, PrecisionGoal -> 8];
   {Mod[f, 180, -90], Mod[q, 360, -180]} /. sol
   ];

L'aspect le plus remarquable de cette implémentation est la façon dont elle évite la nécessité de contraindre la latitude ( f) et la longitude ( q) en les calculant toujours modulo à 180 et 360 degrés, respectivement. Cela évite d'avoir à contraindre le problème (ce qui crée souvent des complications). Les paramètres de contrôle, MaxIterationsetc. sont modifiés pour que ce code offre la plus grande précision possible.

Pour le voir en action, appliquons-le aux trois points de base donnés dans une question connexe :

sol = tri @@ (bases = {{-6.28530175, 106.9004975375}, {-6.28955287, 106.89573839}, {-6.28388865789474, 106.908087643421}})

{-6.29692, 106.907}

Les distances calculées entre cette solution et les trois points sont

{1450.23206979, 1450.23206979, 1450.23206978}

(ce sont des mètres). Ils s'accordent au onzième chiffre significatif (ce qui est trop précis, en fait, car les distances sont rarement précises à mieux qu'un millimètre environ). Voici une image de ces trois points (noir), de leurs trois bissectrices mutuelles et de la solution (rouge):

Figure 1


Exemple

Pour tester cette implémentation et mieux comprendre le comportement du problème, voici un tracé de contour de l'écart quadratique moyen des distances pour trois points de base largement espacés. (L'écart RMS est obtenu en calculant les trois différences d (X, A) -d (X, B), d (X, B) -d (X, C) et d (X, C) -d (X , A), en faisant la moyenne de leurs carrés et en prenant la racine carrée. Il est égal à zéro lorsque X résout le problème et augmente à mesure que X s'éloigne d'une solution, et mesure ainsi à quel point nous sommes «proches» d'être une solution à n'importe quel endroit. )

Figure 2

Les points de base (60, -120), (10, -40) et (45,10) sont représentés en rouge dans cette projection Plate Carree; la solution (49.2644488, -49.9052992) - qui a nécessité 0,03 seconde pour calculer - est en jaune. Son écart RMS est inférieur à trois nanomètres , bien que toutes les distances pertinentes soient des milliers de kilomètres. Les zones sombres montrent de petites valeurs de RMS et les zones claires montrent des valeurs élevées.

Cette carte montre clairement qu'une autre solution se trouve à proximité (-49.2018206, 130.0297177) (calculée à un RMS de deux nanomètres en définissant la valeur de recherche initiale diamétralement opposée à la première solution.)


Pièges

Instabilité numérique

Lorsque les points de base sont presque colinéaires et rapprochés, toutes les solutions seront à près d'un demi-monde et extrêmement difficiles à cerner avec précision. La raison en est que de petits changements dans un emplacement à travers le globe - le déplacer vers ou loin des points de base - n'induiront que des changements incroyablement minuscules dans les différences de distances. Il n'y a tout simplement pas assez d'exactitude et de précision intégrées dans le calcul habituel des distances géodésiques pour déterminer le résultat.

Par exemple, en commençant par les points de base à (45.001, 0), (45, 0) et (44.999,0), qui sont séparés le long du méridien principal de seulement 111 mètres entre chaque paire, triobtient la solution (11.8213, 77.745 ). Les distances de celui-ci aux points de base sont de 8 127 964,998 77; 8 127 964,998 41; et 8 127 964,998 65 mètres, respectivement. Ils s'entendent au millimètre près! Je ne suis pas sûr de la précision de ce résultat, mais je ne serais pas du tout surpris si d'autres implémentations renvoyaient des emplacements loin de celui-ci, montrant une égalité presque aussi bonne des trois distances.

Temps de calcul

Ces calculs, car ils impliquent une recherche considérable à l'aide de calculs de distance compliqués, ne sont pas rapides, nécessitant généralement une fraction notable de seconde. Les applications en temps réel doivent en être conscientes.


Implémentation d'ArcGIS

Python est l'environnement de script préféré pour ArcGIS (à partir de la version 9). Le paquet scipy.optimize a un rootfinder multivarié rootqui devrait faire ce qui FindRootfait dans le code Mathematica . Bien sûr, ArcGIS lui-même propose des calculs précis de distance ellipsoïdale. Le reste, alors, ce sont tous les détails d'implémentation: décidez comment les coordonnées du point de base seront obtenues (à partir d'un calque? Tapé par l'utilisateur? À partir d'un fichier texte? De la souris?) Et comment la sortie sera présentée (sous forme de coordonnées affiché à l'écran? comme un point graphique? comme un nouvel objet ponctuel dans un calque?), écrivez cette interface, portez le code Mathematica montré ici (simple), et vous serez prêt.

whuber
la source
3
+1 Très approfondi. Je pense que vous devrez peut-être commencer à facturer cela, @whuber.
Radar
2
@Radar Merci. J'espère que les gens achèteront mon livre quand (jamais) il finira par apparaître :-).
whuber
1
Will Bill ... Envoyez un brouillon !!!
Excellent! Pourtant, il semble qu'une solution analytique serait possible. En reformulant le problème dans l'espace cartésien 3D avec 3 points A, B, C et E où E est le centre de la terre. Trouvez ensuite deux plans Plane1 et Plane2. Le plan 1 serait le plan normal au planABE et passant par E, au milieu (A, B). De même, Plane2 serait le plan normal à planACE et passant par E, au milieu (C, E). La ligne O formée par l'intersection du plan 1 et du plan 2 représente des points équidistants des 3 points. Le plus proche des deux points à A (ou B ou C) où la ligne O coupe la sphère est le point O.
Kirk Kuykendall
Cette solution analytique, @Kirk, ne s'applique qu'à la sphère. (Les intersections des plans avec l'ellipsoïde ne sont jamais des bissectrices perpendiculaires dans la métrique de l'ellipsoïde, sauf pour quelques cas exceptionnels évidents: quand ce sont des méridiens ou l'équateur.)
Whuber
3

Comme vous le constatez, ce problème se pose lors de la détermination des frontières maritimes; il est souvent appelé le problème des «trois points» et vous pouvez le résoudre sur Google et trouver plusieurs articles sur le sujet. Un de ces papiers est de moi (!) Et je propose une solution précise et rapidement convergente. Voir la section 14 de http://arxiv.org/abs/1102.1215

La méthode comprend les étapes suivantes:

  1. devinez un O à trois points
  2. utiliser O comme centre d'une projection équidistante azimutale
  3. projet A, B, C, à cette projection
  4. trouver le tri-point dans cette projection, O '
  5. utiliser O 'comme nouveau centre de projection
  6. répéter jusqu'à ce que O 'et O coïncident

La formule nécessaire pour la solution à trois points dans la projection est donnée dans l'article. Tant que vous utilisez une projection équidistante azimutale précise, la réponse sera exacte. La convergence est quadratique, ce qui signifie que seules quelques itérations sont nécessaires. Cela surpassera presque certainement les méthodes générales de recherche de racines suggérées par @whuber.

Je ne peux pas vous aider directement avec ArcGIS. Vous pouvez récupérer mon package python pour effectuer des calculs géodésiques à partir de https://pypi.python.org/pypi/geographiclib et coder la projection en fonction de cela est simple.


Éditer

Le problème de trouver le tri-point dans le cas dégénéré de @ whuber (45 + eps, 0) (45,0) (45-eps, 0) a été examiné par Cayley dans On the geodesic lines on a oblate spheroid , Phil. Mag. (1870), http://books.google.com/books?id=4XGIOoCMYYAC&pg=PA15

Dans ce cas, le tri-point est obtenu en suivant une géodésique de (45,0) avec l'azimut 90 et en trouvant le point où l'échelle géodésique disparaît. Pour l'ellipsoïde WGS84, ce point est (-0.10690908732248, 89.89291072793167). La distance de ce point à chacun de (45,001,0), (45,0), (44,999) est de 10010287,665788943 m (dans un nanomètre environ). C'est environ 1882 km de plus que l'estimation de Whuber (ce qui montre à quel point ce cas est instable). Pour une terre sphérique, le tri-point serait (0,90) ou (0, -90), bien sûr.

ADDENDA: Voici une implémentation de la méthode équidistante azimutale utilisant Matlab

function [lat, lon] = tripoint(lat1, lon1, lat2, lon2, lat3, lon3)
% Compute point equidistant from arguments
% Requires:
%   http://www.mathworks.com/matlabcentral/fileexchange/39108
%   http://www.mathworks.com/matlabcentral/fileexchange/39366
  lats = [lat1, lat2, lat3];
  lons = [lon1, lon2, lon3];
  lat0 = lat1;  lon0 = lon1; % feeble guess for tri point
  for i = 1:6
    [x, y] = eqdazim_fwd(lat0, lon0, lats, lons);
    a = [x(1), y(1), 0];
    b = [x(2), y(2), 0];
    c = [x(3), y(3), 0];
    z = [0, 0, 1];
    % Eq. (97) of http://arxiv.org/abs/1102.1215
    o = cross((a*a') * (b - c) + (b*b') * (c - a) + (c*c') * (a - b), z) ...
        / (2 * dot(cross(a - b, b - c), z));
    [lat0, lon0] = eqdazim_inv(lat0, lon0, o(1), o(2))
  end
  % optional check
  s12 = geoddistance(lat0, lon0, lats, lons); ds12 = max(s12) - min(s12)
  lat = lat0; lon = lon0;
end

Tester cela en utilisant Octave, je reçois

octave: 1> format long
octave: 2> [lat0, lon0] = tripoint (41, -74,36,140, ​​-41,175)
lat0 = 15.4151378380375
lon0 = -162.479314381144
lat0 = 15.9969703299812
lon0 = -147.046790722192
lat0 = 16.2232960167545
lon0 = -147.157646039471
lat0 = 16.2233394851560
lon0 = -147.157748279290
lat0 = 16.2233394851809
lon0 = -147.157748279312
lat0 = 16.2233394851809
lon0 = -147.157748279312
ds12 = 3,72529029846191e-09
lat0 = 16.2233394851809
lon0 = -147.157748279312

comme point de tri pour New York, Tokyo et Wellington.

Cette méthode est inexacte pour les points colinéaires voisins, par exemple, [45.001,0], [45,0], [44.999,0]. Dans ce cas, vous devez résoudre pour M 12 = 0 sur une géodésique émanant de [45,0] à l'azimut 90. La fonction suivante fait l'affaire (en utilisant la méthode de Newton):

function [lat2,lon2] = semiconj(lat1, lon1, azi1)
% Find the point where neighboring parallel geodesics emanating from
% close to [lat1, lon1] with azimuth azi1 intersect.

  % First guess is 90 deg on aux sphere
  [lat2, lon2, ~, ~, m12, M12, M21, s12] = ...
      geodreckon(lat1, lon1, 90, azi1, defaultellipsoid(), true);
  M12
  % dM12/ds2 = - (1 - M12*M21/m12)
  for i = 1:3
    s12 = s12 - M12 / ( -(1 - M12*M21)/m12 ); % Newton
    [lat2, lon2, ~, ~, m12, M12, M21] = geodreckon(lat1, lon1, s12, azi1);
    M12
  end
end

Pour l'exemple, cela donne:

[lat2, lon2] = semiconj (45, 0, 90)
M12 = 0,00262997817649321
M12 = -6,08402492665097e-09
M12 = 4,38017677684144e-17
M12 = 4,38017677684144e-17
lat2 = -0.106909087322479
lon2 = 89.8929107279317
cffk
la source
+1. Cependant, il n'est pas clair qu'un chercheur de racine général fonctionnera moins bien: la fonction se comporte bien près de son optimum et la méthode de Newton, par exemple, convergera également quadratique. ( Mathematica prend généralement environ quatre étapes pour converger; chaque étape nécessite quatre évaluations pour estimer le jacobien.) Le véritable avantage que je vois pour votre méthode est qu'elle peut facilement être scriptée dans un SIG sans recourir à l'utilisation d'un root finder.
blanc
Je suis d'accord. Ma méthode est équivalente à Newton et donc, contrairement à la méthode de recherche de racines de Mathematica, il n'est pas nécessaire d'estimer le gradient en prenant des différences.
cffk
C'est vrai - mais vous devez faire la reprojection à chaque fois, ce qui semble être à peu près la même quantité de travail. J'apprécie cependant la simplicité et l'élégance de votre approche: il est immédiatement évident qu'elle devrait fonctionner et converger rapidement.
whuber
J'ai publié des résultats pour les mêmes points de test dans ma réponse.
Kirk Kuykendall
3

J'étais curieux de voir à quelle vitesse l'approche de @ cffk converge vers une solution, j'ai donc écrit un test à l'aide d'arcobjects, qui a produit cette sortie. Les distances sont en mètres:

0 longitude: 0 latitude: 90
    Distances: 3134.05443974188 2844.67237777542 3234.33025754997
    Diffs: 289.382061966458 -389.657879774548 -100.27581780809
1 longitude: 106.906152157596 latitude: -6.31307123035178
    Distances: 1450.23208989615 1450.23208089398 1450.23209429293
    Diffs: 9.00216559784894E-06 -1.33989510686661E-05 -4.39678547081712E-06
2 longitude: 106.906583669013 latitude: -6.29691590176649
    Distances: 1450.23206976414 1450.23206976408 1450.23206976433
    Diffs: 6.18456397205591E-11 -2.47382558882236E-10 -1.85536919161677E-10
3 longitude: 106.906583669041 latitude: -6.29691590154641
    Distances: 1450.23206976438 1450.23206976423 1450.23206976459
    Diffs: 1.47565515362658E-10 -3.61751517630182E-10 -2.14186002267525E-10
4 longitude: 106.906583669041 latitude: -6.29691590154641
    Distances: 1450.23206976438 1450.23206976423 1450.23206976459
    Diffs: 1.47565515362658E-10 -3.61751517630182E-10 -2.14186002267525E-10

Voici le code source. (Modifier) ​​Modification du FindCircleCenter pour gérer les intersections (points centraux) qui tombent du bord de la projection azimutale:

public static void Test()
{
    var t = Type.GetTypeFromProgID("esriGeometry.SpatialReferenceEnvironment");
    var srf = Activator.CreateInstance(t) as ISpatialReferenceFactory2;
    var pcs = srf.CreateProjectedCoordinateSystem((int)esriSRProjCSType.esriSRProjCS_WGS1984N_PoleAziEqui)
        as IProjectedCoordinateSystem2;

    var pntA = MakePoint(106.9004975375, -6.28530175, pcs.GeographicCoordinateSystem);
    var pntB = MakePoint(106.89573839, -6.28955287, pcs.GeographicCoordinateSystem);
    var pntC = MakePoint(106.908087643421, -6.28388865789474, pcs.GeographicCoordinateSystem);

    int maxIter = 5;
    for (int i = 0; i < maxIter; i++)
    {
        var msg = string.Format("{0} longitude: {1} latitude: {2}", i, pcs.get_CentralMeridian(true), pcs.LatitudeOfOrigin);
        Debug.Print(msg);
        var newCenter = FindCircleCenter(ProjectClone(pntA, pcs), ProjectClone(pntB, pcs), ProjectClone(pntC, pcs));
        newCenter.Project(pcs.GeographicCoordinateSystem); // unproject
        var distA = GetGeodesicDistance(newCenter, pntA);
        var distB = GetGeodesicDistance(newCenter, pntB);
        var distC = GetGeodesicDistance(newCenter, pntC);
        Debug.Print("\tDistances: {0} {1} {2}", distA, distB, distC);
        var diffAB = distA - distB;
        var diffBC = distB - distC;
        var diffAC = distA - distC;
        Debug.Print("\tDiffs: {0} {1} {2}", diffAB, diffBC, diffAC);

        pcs.set_CentralMeridian(true, newCenter.X);
        pcs.LatitudeOfOrigin = newCenter.Y;
    }
}
public static IPoint FindCircleCenter(IPoint a, IPoint b, IPoint c)
{
    // from http://blog.csharphelper.com/2011/11/08/draw-a-circle-through-three-points-in-c.aspx
    // Get the perpendicular bisector of (x1, y1) and (x2, y2).
    var x1 = (b.X + a.X) / 2;
    var y1 = (b.Y + a.Y) / 2;
    var dy1 = b.X - a.X;
    var dx1 = -(b.Y - a.Y);

    // Get the perpendicular bisector of (x2, y2) and (x3, y3).
    var x2 = (c.X + b.X) / 2;
    var y2 = (c.Y + b.Y) / 2;
    var dy2 = c.X - b.X;
    var dx2 = -(c.Y - b.Y);

    // See where the lines intersect.
    var cx = (y1 * dx1 * dx2 + x2 * dx1 * dy2 - x1 * dy1 * dx2 - y2 * dx1 * dx2)
        / (dx1 * dy2 - dy1 * dx2);
    var cy = (cx - x1) * dy1 / dx1 + y1;

    // make sure the intersection point falls
    // within the projection.
    var earthRadius = ((IProjectedCoordinateSystem)a.SpatialReference).GeographicCoordinateSystem.Datum.Spheroid.SemiMinorAxis;

    // distance is from center of projection
    var dist = Math.Sqrt((cx * cx) + (cy * cy));
    double factor = 1.0;
    if (dist > earthRadius * Math.PI)
    {
        // apply a factor so we don't fall off the edge
        // of the projection
        factor = earthRadius / dist;
    }
    var outPoint = new PointClass() as IPoint;
    outPoint.PutCoords(cx * factor, cy* factor);
    outPoint.SpatialReference = a.SpatialReference;
    return outPoint;
}

public static double GetGeodesicDistance(IPoint pnt1, IPoint pnt2)
{
    var pc = new PolylineClass() as IPointCollection;
    var gcs = pnt1.SpatialReference as IGeographicCoordinateSystem;
    if (gcs == null)
        throw new Exception("point does not have a gcs");
    ((IGeometry)pc).SpatialReference = gcs;
    pc.AddPoint(pnt1);
    pc.AddPoint(pnt2);
    var t = Type.GetTypeFromProgID("esriGeometry.SpatialReferenceEnvironment");
    var srf = Activator.CreateInstance(t) as ISpatialReferenceFactory2;
    var unit = srf.CreateUnit((int)esriSRUnitType.esriSRUnit_Meter) as ILinearUnit;
    var pcGeodetic = pc as IPolycurveGeodetic;
    return pcGeodetic.get_LengthGeodetic(esriGeodeticType.esriGeodeticTypeGeodesic, unit);
}

public static IPoint ProjectClone(IPoint pnt, ISpatialReference sr)
{
    var clone = ((IClone)pnt).Clone() as IPoint;
    clone.Project(sr);
    return clone;
}

public static IPoint MakePoint(double longitude, double latitude, ISpatialReference sr)
{
    var pnt = new PointClass() as IPoint;
    pnt.PutCoords(longitude, latitude);
    pnt.SpatialReference = sr;
    return pnt;
}

Il existe également une approche alternative dans le numéro de juin 2013 du magazine MSDN, Amoeba Method Optimization using C # .


Éditer

Le code précédemment affiché a convergé vers l'antipode dans certains cas. J'ai modifié le code pour qu'il produise cette sortie pour les points de test de @ cffk.

Voici la sortie qu'il produit maintenant:

0 0
0 longitude: 0 latitude: 0
    MaxDiff: 1859074.90170379 Distances: 13541157.6493561 11682082.7476523 11863320.2116807
1 longitude: 43.5318402621384 latitude: -17.1167429904981
    MaxDiff: 21796.9793742411 Distances: 12584188.7592282 12588146.4851222 12566349.505748
2 longitude: 32.8331167578493 latitude: -16.2707976739314
    MaxDiff: 6.05585224926472 Distances: 12577536.3369782 12577541.3560203 12577542.3928305
3 longitude: 32.8623898057665 latitude: -16.1374156408507
    MaxDiff: 5.58793544769287E-07 Distances: 12577539.6118671 12577539.6118666 12577539.6118669
4 longitude: -147.137582018133 latitude: 16.1374288796667
    MaxDiff: 1.12284109462053 Distances: 7441375.08265703 7441376.12671342 7441376.20549812
5 longitude: -147.157742373074 latitude: 16.2233413614432
    MaxDiff: 7.45058059692383E-09 Distances: 7441375.70752843 7441375.70752842 7441375.70752842
5 longitude: -147.157742373074 latitude: 16.2233413614432 Distance 7441375.70752843
iterations: 5

Voici le code révisé:

class Program
{
    private static LicenseInitializer m_AOLicenseInitializer = new tripoint.LicenseInitializer();

    [STAThread()]
    static void Main(string[] args)
    {
        //ESRI License Initializer generated code.
        m_AOLicenseInitializer.InitializeApplication(new esriLicenseProductCode[] { esriLicenseProductCode.esriLicenseProductCodeStandard },
        new esriLicenseExtensionCode[] { });
        try
        {
            var t = Type.GetTypeFromProgID("esriGeometry.SpatialReferenceEnvironment");
            var srf = Activator.CreateInstance(t) as ISpatialReferenceFactory2;
            var pcs = srf.CreateProjectedCoordinateSystem((int)esriSRProjCSType.esriSRProjCS_World_AzimuthalEquidistant)
                as IProjectedCoordinateSystem2;
            Debug.Print("{0} {1}", pcs.get_CentralMeridian(true), pcs.LatitudeOfOrigin);
            int max = int.MinValue;
            for (int i = 0; i < 1; i++)
            {
                var iterations = Test(pcs);
                max = Math.Max(max, iterations);
                Debug.Print("iterations: {0}", iterations);
            }
            Debug.Print("max number of iterations: {0}", max);
        }
        catch (Exception ex)
        {
            Debug.Print(ex.Message);
            Debug.Print(ex.StackTrace);
        }
        //ESRI License Initializer generated code.
        //Do not make any call to ArcObjects after ShutDownApplication()
        m_AOLicenseInitializer.ShutdownApplication();
    }
    public static int Test(IProjectedCoordinateSystem2 pcs)
    {
        var pntA = MakePoint(-74.0, 41.0, pcs.GeographicCoordinateSystem);
        var pntB = MakePoint(140.0, 36.0, pcs.GeographicCoordinateSystem);
        var pntC = MakePoint(175.0, -41.0, pcs.GeographicCoordinateSystem);


        //var r = new Random();
        //var pntA = MakeRandomPoint(r, pcs.GeographicCoordinateSystem);
        //var pntB = MakeRandomPoint(r, pcs.GeographicCoordinateSystem);
        //var pntC = MakeRandomPoint(r, pcs.GeographicCoordinateSystem);

        int maxIterations = 100;
        for (int i = 0; i < maxIterations; i++)
        {
            var msg = string.Format("{0} longitude: {1} latitude: {2}", i, pcs.get_CentralMeridian(true), pcs.LatitudeOfOrigin);
            Debug.Print(msg);
            var newCenter = FindCircleCenter(ProjectClone(pntA, pcs), ProjectClone(pntB, pcs), ProjectClone(pntC, pcs));
            var c = ((IClone)newCenter).Clone() as IPoint;
            newCenter.Project(pcs.GeographicCoordinateSystem); // unproject
            //newCenter = MakePoint(-147.1577482, 16.2233394, pcs.GeographicCoordinateSystem);
            var distA = GetGeodesicDistance(newCenter, pntA);
            var distB = GetGeodesicDistance(newCenter, pntB);
            var distC = GetGeodesicDistance(newCenter, pntC);
            var diffAB = Math.Abs(distA - distB);
            var diffBC = Math.Abs(distB - distC);
            var diffAC = Math.Abs(distA - distC);
            var maxDiff = GetMax(new double[] {diffAB,diffAC,diffBC});
            Debug.Print("\tMaxDiff: {0} Distances: {1} {2} {3}",maxDiff, distA, distB, distC);
            if (maxDiff < 0.000001)
            {
                var earthRadius = pcs.GeographicCoordinateSystem.Datum.Spheroid.SemiMinorAxis;
                if (distA > earthRadius * Math.PI / 2.0)
                {
                    newCenter = AntiPode(newCenter);
                }
                else
                {
                    Debug.Print("{0} longitude: {1} latitude: {2} Distance {3}", i, pcs.get_CentralMeridian(true), pcs.LatitudeOfOrigin, distA);
                    return i;
                }
            }
            //Debug.Print("\tDiffs: {0} {1} {2}", diffAB, diffBC, diffAC);

            pcs.set_CentralMeridian(true, newCenter.X);
            pcs.LatitudeOfOrigin = newCenter.Y;
        }
        return maxIterations;
    }

    public static IPoint FindCircleCenter(IPoint a, IPoint b, IPoint c)
    {
        // from http://blog.csharphelper.com/2011/11/08/draw-a-circle-through-three-points-in-c.aspx
        // Get the perpendicular bisector of (x1, y1) and (x2, y2).
        var x1 = (b.X + a.X) / 2;
        var y1 = (b.Y + a.Y) / 2;
        var dy1 = b.X - a.X;
        var dx1 = -(b.Y - a.Y);

        // Get the perpendicular bisector of (x2, y2) and (x3, y3).
        var x2 = (c.X + b.X) / 2;
        var y2 = (c.Y + b.Y) / 2;
        var dy2 = c.X - b.X;
        var dx2 = -(c.Y - b.Y);

        // See where the lines intersect.
        var cx = (y1 * dx1 * dx2 + x2 * dx1 * dy2 - x1 * dy1 * dx2 - y2 * dx1 * dx2)
            / (dx1 * dy2 - dy1 * dx2);
        var cy = (cx - x1) * dy1 / dx1 + y1;

        // make sure the intersection point falls
        // within the projection.
        var earthRadius = ((IProjectedCoordinateSystem)a.SpatialReference).GeographicCoordinateSystem.Datum.Spheroid.SemiMinorAxis;

        // distance is from center of projection
        var dist = Math.Sqrt((cx * cx) + (cy * cy));
        double factor = 1.0;
        if (dist > earthRadius * Math.PI)
        {
            // apply a factor so we don't fall off the edge
            // of the projection
            factor = earthRadius / dist;
        }
        var outPoint = new PointClass() as IPoint;
        outPoint.PutCoords(cx * factor, cy* factor);
        outPoint.SpatialReference = a.SpatialReference;
        return outPoint;
    }

    public static IPoint AntiPode(IPoint pnt)
    {
        if (!(pnt.SpatialReference is IGeographicCoordinateSystem))
            throw new Exception("antipode of non-gcs projection not supported");
        var outPnt = new PointClass() as IPoint;
        outPnt.SpatialReference = pnt.SpatialReference;
        if (pnt.X < 0.0)
            outPnt.X = 180.0 + pnt.X;
        else
            outPnt.X = pnt.X - 180.0;
        outPnt.Y = -pnt.Y;
        return outPnt;
    }

    public static IPoint MakeRandomPoint(Random r, IGeographicCoordinateSystem gcs)
    {
        var latitude = (r.NextDouble() - 0.5) * 180.0;
        var longitude = (r.NextDouble() - 0.5) * 360.0;
        //Debug.Print("{0} {1}", latitude, longitude);
        return MakePoint(longitude, latitude, gcs);
    }
    public static double GetMax(double[] dbls)
    {
        var max = double.MinValue;
        foreach (var d in dbls)
        {
            if (d > max)
                max = d;
        }
        return max;
    }
    public static IPoint MakePoint(IPoint[] pnts)
    {
        double sumx = 0.0;
        double sumy = 0.0;
        foreach (var pnt in pnts)
        {
            sumx += pnt.X;
            sumy += pnt.Y;
        }
        return MakePoint(sumx / pnts.Length, sumy / pnts.Length, pnts[0].SpatialReference);
    }
    public static double GetGeodesicDistance(IPoint pnt1, IPoint pnt2)
    {
        var pc = new PolylineClass() as IPointCollection;
        var gcs = pnt1.SpatialReference as IGeographicCoordinateSystem;
        if (gcs == null)
            throw new Exception("point does not have a gcs");
        ((IGeometry)pc).SpatialReference = gcs;
        pc.AddPoint(pnt1);
        pc.AddPoint(pnt2);
        var t = Type.GetTypeFromProgID("esriGeometry.SpatialReferenceEnvironment");
        var srf = Activator.CreateInstance(t) as ISpatialReferenceFactory2;
        var unit = srf.CreateUnit((int)esriSRUnitType.esriSRUnit_Meter) as ILinearUnit;
        var pcGeodetic = pc as IPolycurveGeodetic;
        return pcGeodetic.get_LengthGeodetic(esriGeodeticType.esriGeodeticTypeGeodesic, unit);
    }

    public static IPoint ProjectClone(IPoint pnt, ISpatialReference sr)
    {
        var clone = ((IClone)pnt).Clone() as IPoint;
        clone.Project(sr);
        return clone;
    }

    public static IPoint MakePoint(double longitude, double latitude, ISpatialReference sr)
    {
        var pnt = new PointClass() as IPoint;
        pnt.PutCoords(longitude, latitude);
        pnt.SpatialReference = sr;
        return pnt;
    }
}

Éditer

Voici les résultats que j'obtiens avec esriSRProjCS_WGS1984N_PoleAziEqui

0 90
0 longitude: 0 latitude: 90
    MaxDiff: 1275775.91880553 Distances: 8003451.67666723 7797996.2370572 6727675.7578617
1 longitude: -148.003774863594 latitude: 9.20238223616225
    MaxDiff: 14487.6784785809 Distances: 7439006.46128994 7432752.45732905 7447240.13580763
2 longitude: -147.197808459106 latitude: 16.3073233548167
    MaxDiff: 2.32572609744966 Distances: 7441374.94409209 7441377.26981819 7441375.90768183
3 longitude: -147.157734641831 latitude: 16.2233338760411
    MaxDiff: 7.72997736930847E-08 Distances: 7441375.70752842 7441375.70752848 7441375.7075284
3 longitude: -147.157734641831 latitude: 16.2233338760411 Distance 7441375.70752842
Kirk Kuykendall
la source
C'est une convergence incroyablement rapide! (+1)
whuber
Vous devez utiliser une projection équidistante azimutale honnête à la bonté centrée sur newCenter. Au lieu de cela, vous utilisez la projection centrée sur le pôle N et déplacez l'origine vers newCenter. Il peut donc être accidentel que vous obteniez une solution décente dans ce cas (peut-être parce que les points sont proches les uns des autres?). Il serait bon de l'essayer avec 3 points à des milliers de kilomètres de distance. Une implémentation de la projection équidistante azimutale est donnée dans mathworks.com/matlabcentral/fileexchange/…
cffk
@cffk La seule autre façon que je vois pour créer une projection équidistante azimutale centrée sur un point particulier est d'utiliser la même méthode mais avec esriSRProjCS_World_AzimuthalEquidistant au lieu de esriSRProjCS_WGS1984N_PoleAziEqui (ou esriSRProjCS_WGS1984S_PS). La seule différence cependant, c'est qu'il est centré sur 0,0 au lieu de 0,90 (ou 0, -90). Pouvez-vous me guider dans l'exécution d'un test avec mathworks pour voir si cela produit des résultats différents à partir d'une projection "honnête à la bonté"?
Kirk Kuykendall
@KirkKuykendall: voir l'addendum à ma première réponse.
cffk
1
@KirkKuykendall Alors peut-être qu'ESRI a mis en œuvre une projection "honnête à la bonté"? La propriété clé requise pour que cet algorithme fonctionne est que les distances mesurées à partir du "point central" sont vraies. Et cette propriété est assez facile à vérifier. (La propriété azimutale par rapport au point central est secondaire et ne peut affecter que le taux de convergence.)
cffk