Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #5006

Re: "Traveling salesman on a hemisphere" problem

From Olaf <olaf.rogalsky@googlemail.com>
Newsgroups comp.soft-sys.math.mathematica
Subject Re: "Traveling salesman on a hemisphere" problem
Date 2011-09-16 09:55 +0000
Organization Steven M. Christensen and Associates, Inc and MathTensor, Inc.
Message-ID <j4v6f2$c97$1@smc.vnet.net> (permalink)
References <j4see5$sp4$1@smc.vnet.net>

Show all headers | View raw


Hi Peter,

with the arclen from http://en.wikipedia.org/wiki/Great-circle_distance,
the following code will give you the shortest route.

stars = {
   {"M51", {21, 44.7}},
   {"NGC2721", {4, -17}},
   {"a funny comet", {57.3, 7}},
   {"absolutely must see", {23, -176.3}}};

arclen[{_, {F1_, L1_}}, {_, {F2_, L2_}}] :=
 Module[{f1 = F1 Degree, l1 = L1 Degree, f2 = F2 Degree, l2 = L2
Degree, dl = (L1 - L2) Degree},
  ArcTan[Sin[f1] Sin[f2] + Cos[f1] Cos[f2] Cos[dl],
             Sqrt[(Cos[f2] Sin[dl])^2 + (Cos[f1] Sin[f2] - Sin[f1]
Cos[f2] Cos[dl])^2]]]

tour = FindShortestTour[stars, DistanceFunction -> arclen]

sortedStars = starlist[[tour[[2]]]]


And here some eye-candy:


p2c[{_, {f_, l_}}] := {Cos[f Degree] Cos[l Degree],
  Sin[f Degree] Cos[l Degree], Sin[l Degree]}
greatCircleArc[{q_, p_}] :=
 Module[{u = p2c[q], v = p2c[p], a}, a = VectorAngle[u, v];
  Table[Evaluate[RotationTransform[t, {u, v}][u]], {t, 0, a,
    a/Ceiling[10 a]}]]

Graphics3D[
 {Sphere[{0, 0, 0}, 0.97],
  {Black, Thick, Arrow[{{0, 0, -1.3}, {0, 0, 1.3}}]},
  {Red, PointSize[Medium], Point[Map[p2c, sortedStars]]},
  {Blue, Thick,
   Map[Line, Map[greatCircleArc, Partition[sortedStars, 2, 1]]]}
  }, SphericalRegion -> True]

Regards, Olaf

Back to comp.soft-sys.math.mathematica | Previous | Next — Previous in thread | Find similar | Unroll thread


Thread

"Traveling salesman on a hemisphere" problem Peter Sisak <p-kun80@hotmail.com> - 2011-09-15 08:53 +0000
  Re: "Traveling salesman on a hemisphere" problem Olaf <olaf.rogalsky@googlemail.com> - 2011-09-16 09:55 +0000

csiph-web