Is there a way to tell FindShortestTour to avoid backtracking when connecting points to form a closed, but possiblely non-convex, curve?

Question

Among a set of points, I want to find a closed curve.

It is not required for the curve to go through all the points, only that the curve goes through as many points as possible. These points are expected form a closed curve, but it may be a non-convex closed curve, as shown in the picture below.

While FindShortestTour can help me find such a curve, it ends up backtracking in many places.

Is there a way to tell FindShortestTour to avoid backtracking as much as possible, such that if it detects backtracking, it will incur a penalty.

I guess this is similar to how the built-in examples of FindShortestTour in the documentation penalize crossing a river?

Below is my code.

Thanks :)

Remove["Global`*"] // Quiet;

{dist, order} = 
  FindShortestTour[datDirty, PerformanceGoal :> "Quality", 
   DirectedEdges -> False];
dat = Part[datDirty, order];


Animate[
 Show[
  (*ListPlot[dat,PlotStyle->Gray,ImageSize->500],*)
  ListLinePlot[dat[[1 ;; i]], PlotStyle -> Blue],
  ListPlot[{dat[[i]]}, PlotStyle -> {Thin, Red}, 
   PlotMarkers -> {Automatic, 10}]
  ], {i, 1, Length@dat, 1}]

datDirty = {{-303.509891512444`, -207.272727272727`}, \
{-302.999361837907`, -214.545454545455`}, {-301.978302488832`, \
-243.636363636364`}, {-301.467772814295`, -250.909090909091`}, \
{-297.894065092533`, -338.181818181818`}, {-296.362476068921`, \
-345.454545454545`}, {-293.809827696235`, -349.090909090909`}, \
{-293.299298021697`, -356.363636363636`}, {-291.767708998085`, 
    330.909090909091`}, {-290.746649649011`, -392.727272727273`}, \
{-288.704530950862`, 
    341.818181818182`}, {-286.662412252712`, -392.727272727273`}, \
{-284.620293554563`, 
    374.545454545455`}, {-283.088704530951`, -410.909090909091`}, \
{-282.067645181876`, 374.545454545455`}, {-281.046585832801`, 
    370.909090909091`}, {-279.514996809189`, 
    378.181818181818`}, {-277.983407785578`, -418.181818181818`}, \
{-275.941289087428`, -425.454545454545`}, {-274.920229738353`, 
    396.363636363636`}, {-273.899170389279`, -447.272727272727`}, \
{-272.878111040204`, 407.272727272727`}, {-272.367581365667`, 
    392.727272727273`}, {-270.325462667518`, -454.545454545455`}, \
{-268.793873643905`, -450.909090909091`}, {-267.262284620294`, 
    410.909090909091`}, {-266.241225271219`, 
    410.909090909091`}, {-265.220165922144`, -461.818181818182`}, \
{-263.688576898532`, 
    429.090909090909`}, {-261.646458200383`, -461.818181818182`}, \
{-260.625398851308`, 418.181818181818`}, {-259.604339502234`, 
    429.090909090909`}, {-258.072750478622`, 
    440.`}, {-256.54116145501`, 
    425.454545454545`}, {-255.009572431398`, 
    443.636363636364`}, {-253.477983407786`, 
    429.090909090909`}, {-252.456924058711`, 
    432.727272727273`}, {-251.435864709636`, 
    443.636363636364`}, {-249.904275686024`, -480.`}, \
{-248.372686662412`, 454.545454545455`}, {-246.8410976388`, 
    436.363636363636`}, {-245.309508615188`, 
    454.545454545455`}, {-243.777919591576`, 
    465.454545454545`}, {-241.22527121889`, -480.`}, \
{-239.693682195278`, 
    454.545454545455`}, {-237.141033822591`, -494.545454545455`}, \
{-235.098915124442`, -490.909090909091`}, {-233.056796426292`, \
-512.727272727273`}, {-231.014677728143`, -498.181818181818`}, \
{-229.993618379068`, 
    461.818181818182`}, {-227.951499680919`, -498.181818181818`}, \
{-226.419910657307`, -512.727272727273`}, {-224.888321633695`, 
    476.363636363636`}, {-222.846202935546`, -501.818181818182`}, \
{-220.804084237396`, -516.363636363636`}, {-218.761965539247`, 
    465.454545454545`}, {-217.740906190172`, 
    487.272727272727`}, {-216.20931716656`, -516.363636363636`}, \
{-214.677728142948`, -509.090909090909`}, {-212.635609444799`, \
-512.727272727273`}, {-211.104020421187`, 
    472.727272727273`}, {-209.572431397575`, 
    476.363636363636`}, {-207.530312699426`, 
    483.636363636364`}, {-204.977664326739`, 
    480.`}, {-203.956604977664`, 
    480.`}, {-201.403956604978`, -534.545454545455`}, \
{-199.872367581366`, -527.272727272727`}, {-197.830248883216`, 
    483.636363636364`}, {-196.298659859604`, 
    501.818181818182`}, {-194.767070835992`, 
    483.636363636364`}, {-192.724952137843`, 
    501.818181818182`}, {-191.193363114231`, 
    501.818181818182`}, {-189.661774090619`, 
    483.636363636364`}, {-188.130185067007`, 
    509.090909090909`}, {-186.598596043395`, -538.181818181818`}, \
{-184.556477345246`, 512.727272727273`}, {-182.003828972559`, 
    501.818181818182`}, {-179.451180599872`, -523.636363636364`}, \
{-176.898532227186`, 501.818181818182`}, {-174.345883854499`, 
    501.818181818182`}, {-171.793235481812`, 
    505.454545454545`}, {-169.240587109126`, 
    498.181818181818`}, {-167.708998085514`, 
    516.363636363636`}, {-165.156349712827`, 
    512.727272727273`}, {-162.60370134014`, 
    509.090909090909`}, {-160.051052967454`, -552.727272727273`}, \
{-157.498404594767`, 
    509.090909090909`}, {-155.456285896618`, -552.727272727273`}, \
{-153.924696873006`, -549.090909090909`}, {-152.393107849394`, 
    505.454545454545`}, {-150.350989151244`, 
    520.`}, {-148.819400127632`, 
    523.636363636364`}, {-147.28781110402`, 
    505.454545454545`}, {-145.245692405871`, -541.818181818182`}, \
{-144.224633056796`, 
    530.909090909091`}, {-142.182514358647`, -538.181818181818`}, \
{-139.62986598596`, -541.818181818182`}, {-137.077217613274`, 
    527.272727272727`}, {-134.524569240587`, 
    523.636363636364`}, {-129.419272495214`, 
    520.`}, {-127.887683471602`, 
    523.636363636364`}, {-126.35609444799`, 
    516.363636363636`}, {-125.335035098915`, 
    530.909090909091`}, {-123.292916400766`, -563.636363636364`}, \
{-121.761327377154`, 
    527.272727272727`}, {-120.229738353542`, -560.`}, \
{-118.187619655392`, -563.636363636364`}, {-116.65603063178`, \
-549.090909090909`}, {-115.124441608168`, -563.636363636364`}, \
{-112.571793235482`, 
    520.`}, {-110.019144862795`, -560.`}, {-108.99808551372`, \
-549.090909090909`}, {-106.955966815571`, -556.363636363636`}, \
{-105.424377791959`, -563.636363636364`}, {-103.892788768347`, 
    523.636363636364`}, {-101.850670070198`, -567.272727272727`}, \
{-100.319081046586`, -570.909090909091`}, {-98.7874920229738`, \
-560.`}, {-96.7453733248245`, -560.`}, {-95.2137843012125`, 
    527.272727272727`}, {-93.6821952776005`, -560.`}, \
{-91.6400765794511`, -563.636363636364`}, {-90.1084875558392`, 
    534.545454545455`}, {-88.5768985322272`, 
    527.272727272727`}, {-86.5347798340778`, 
    523.636363636364`}, {-85.0031908104659`, -567.272727272727`}, \
{-83.4716017868539`, -563.636363636364`}, {-81.9400127632418`, 
    530.909090909091`}, {-79.8978940650925`, -570.909090909091`}, \
{-78.3663050414805`, -560.`}, {-76.8347160178685`, 
    538.181818181818`}, {-74.7925973197192`, -556.363636363636`}, \
{-73.2610082961072`, -556.363636363636`}, {-71.7294192724952`, \
-556.363636363636`}, {-69.6873005743459`, 
    545.454545454545`}, {-68.1557115507339`, -574.545454545455`}, \
{-66.6241225271219`, -574.545454545455`}, {-64.5820038289726`, \
-563.636363636364`}, {-63.0504148053606`, -570.909090909091`}, \
{-61.5188257817485`, 
    534.545454545455`}, {-59.4767070835992`, -560.`}, \
{-57.9451180599872`, -563.636363636364`}, {-56.4135290363752`, 
    549.090909090909`}, {-54.8819400127632`, -563.636363636364`}, \
{-53.8608806636886`, 534.545454545455`}, {-52.3292916400766`, 
    549.090909090909`}, {-51.3082322910019`, -556.363636363636`}, \
{-49.7766432673899`, -563.636363636364`}, {-48.7555839183152`, 
    534.545454545455`}, {-47.2239948947032`, -560.`}, \
{-45.6924058710913`, -556.363636363636`}, {-43.6502871729419`, 
    545.454545454545`}, {-42.1186981493299`, -567.272727272727`}, \
{-40.5871091257179`, -560.`}, {-38.5449904275686`, 
    549.090909090909`}, {-37.0134014039565`, -560.`}, \
{-35.4818123803446`, -563.636363636364`}, {-33.9502233567326`, \
-556.363636363636`}, {-32.4186343331206`, -560.`}, \
{-31.3975749840459`, 
    545.454545454545`}, {-29.8659859604339`, -567.272727272727`}, \
{-28.8449266113593`, -560.`}, {-27.3133375877472`, -560.`}, \
{-25.7817485641352`, -556.363636363636`}, {-24.2501595405233`, \
-563.636363636364`}, {-22.7185705169113`, 
    552.727272727273`}, {-21.6975111678366`, 
    560.`}, {-20.1659221442246`, -578.181818181818`}, \
{-19.1448627951499`, -574.545454545455`}, {-18.1238034460753`, 
    556.363636363636`}, {-16.5922144224633`, -574.545454545455`}, \
{-15.5711550733886`, -570.909090909091`}, {-14.0395660497767`, \
-560.`}, {-11.9974473516273`, -560.`}, {-10.9763880025527`, \
-556.363636363636`}, {-9.44479897894064`, -560.`}, \
{-8.42373962986596`, 552.727272727273`}, {-7.40268028079129`, 
    552.727272727273`}, {-5.87109125717927`, 
    560.`}, {-4.8500319081046`, 
    563.636363636364`}, {-3.82897255903003`, -563.636363636364`}, \
{-2.29738353541802`, -563.636363636364`}, {-1.27632418634334`, 
    560.`}, {0.255264837268669`, 
    545.454545454545`}, {1.27632418634334`, -556.363636363636`}, \
{2.29738353541802`, 
    545.454545454545`}, {2.80791320995536`, -567.272727272727`}, \
{4.33950223356737`, 
    563.636363636364`}, {5.36056158264205`, -560.`}, \
{6.89215060625395`, 
    556.363636363636`}, {7.91320995532863`, -560.`}, \
{9.44479897894064`, -567.272727272727`}, {10.4658583280153`, \
-574.545454545455`}, {11.48691767709`, 
    552.727272727273`}, {13.018506700702`, -563.636363636364`}, \
{14.550095724314`, 556.363636363636`}, {16.5922144224633`, 
    556.363636363636`}, {18.1238034460753`, -556.363636363636`}, \
{19.6553924696873`, -563.636363636364`}, {21.6975111678366`, \
-563.636363636364`}, {23.2291001914487`, -574.545454545455`}, \
{24.7606892150607`, -560.`}, {26.2922782386727`, -556.363636363636`}, \
{28.3343969368219`, 
    560.`}, {29.8659859604339`, -570.909090909091`}, \
{31.3975749840459`, -556.363636363636`}, {33.4396936821953`, 
    556.363636363636`}, {34.9712827058073`, 
    556.363636363636`}, {36.5028717294193`, 
    552.727272727273`}, {38.5449904275686`, -556.363636363636`}, \
{40.0765794511806`, -556.363636363636`}, {41.6081684747926`, \
-556.363636363636`}, {43.6502871729419`, -556.363636363636`}, \
{45.181876196554`, -560.`}, {46.713465220166`, -556.363636363636`}, \
{48.7555839183152`, -570.909090909091`}, {50.2871729419272`, \
-570.909090909091`}, {51.8187619655392`, -556.363636363636`}, \
{53.8608806636886`, -560.`}, {55.3924696873006`, -560.`}, \
{56.9240587109126`, -556.363636363636`}, {58.9661774090619`, 
    563.636363636364`}, {60.4977664326739`, -556.363636363636`}, \
{62.0293554562859`, -560.`}, {64.0714741544352`, 
    560.`}, {65.6030631780473`, 
    556.363636363636`}, {67.1346522016593`, -556.363636363636`}, \
{69.1767708998085`, -560.`}, {70.7083599234205`, -556.363636363636`}, \
{72.2399489470325`, -560.`}, {74.2820676451819`, -556.363636363636`}, \
{75.8136566687939`, -560.`}, {77.3452456924059`, -556.363636363636`}, \
{79.3873643905551`, -560.`}, {80.9189534141672`, 
    552.727272727273`}, {82.4505424377792`, -570.909090909091`}, \
{84.4926611359285`, -570.909090909091`}, {86.0242501595405`, 
    552.727272727273`}, {87.5558391831526`, -560.`}, \
{89.5979578813019`, 
    570.909090909091`}, {91.1295469049138`, -563.636363636364`}, \
{92.6611359285258`, 552.727272727273`}, {94.7032546266752`, 
    560.`}, {96.2348436502872`, 
    563.636363636364`}, {97.7664326738992`, -567.272727272727`}, \
{100.319081046586`, -563.636363636364`}, {102.871729419272`, 
    570.909090909091`}, {105.424377791959`, 
    556.363636363636`}, {107.977026164646`, -570.909090909091`}, \
{110.529674537332`, -560.`}, {113.082322910019`, -567.272727272727`}, \
{115.634971282706`, 560.`}, {118.187619655392`, 
    552.727272727273`}, {120.740268028079`, 
    552.727272727273`}, {123.292916400766`, -556.363636363636`}, \
{125.335035098915`, -560.`}, {127.887683471602`, 
    560.`}, {130.440331844288`, -560.`}, {132.992980216975`, \
-563.636363636364`}, {135.545628589662`, -563.636363636364`}, \
{138.098276962348`, 
    560.`}, {140.650925335035`, -567.272727272727`}, \
{143.203573707722`, 
    567.272727272727`}, {145.245692405871`, -563.636363636364`}, \
{147.798340778558`, -563.636363636364`}, {150.350989151244`, \
-549.090909090909`}, {153.414167198468`, -574.545454545455`}, \
{155.456285896618`, -563.636363636364`}, {156.98787492023`, 
    563.636363636364`}, {159.029993618379`, -541.818181818182`}, \
{160.561582641991`, -552.727272727273`}, {161.582641991066`, -560.`}, \
{163.114231014678`, -556.363636363636`}, {164.135290363752`, \
-545.454545454545`}, {165.666879387364`, -556.363636363636`}, \
{166.687938736439`, -560.`}, {168.219527760051`, -549.090909090909`}, \
{169.240587109126`, 560.`}, {170.772176132738`, 
    560.`}, {172.814294830887`, -552.727272727273`}, \
{174.345883854499`, -545.454545454545`}, {175.877472878111`, \
-552.727272727273`}, {177.91959157626`, -545.454545454545`}, \
{179.451180599872`, -549.090909090909`}, {180.982769623484`, \
-549.090909090909`}, {183.024888321634`, -552.727272727273`}, \
{184.556477345246`, -552.727272727273`}, {186.088066368858`, \
-541.818181818182`}, {188.130185067007`, -549.090909090909`}, \
{189.661774090619`, -545.454545454545`}, {191.193363114231`, 
    541.818181818182`}, {192.724952137843`, -552.727272727273`}, \
{193.746011486918`, 
    549.090909090909`}, {195.27760051053`, -545.454545454545`}, \
{196.298659859604`, -538.181818181818`}, {197.830248883216`, \
-538.181818181818`}, {198.851308232291`, -534.545454545455`}, \
{199.872367581366`, 549.090909090909`}, {201.403956604978`, 
    549.090909090909`}, {202.425015954052`, -538.181818181818`}, \
{203.956604977664`, 545.454545454545`}, {204.977664326739`, 
    545.454545454545`}, {206.509253350351`, -530.909090909091`}, \
{207.530312699426`, -527.272727272727`}, {209.061901723038`, 
    545.454545454545`}, {210.082961072112`, 
    549.090909090909`}, {211.614550095724`, 
    545.454545454545`}, {213.146139119336`, -523.636363636364`}, \
{214.677728142948`, 
    541.818181818182`}, {216.20931716656`, -538.181818181818`}, \
{218.25143586471`, 545.454545454545`}, {219.783024888322`, 
    534.545454545455`}, {221.314613911934`, -520.`}, \
{222.846202935546`, 534.545454545455`}, {224.377791959158`, 
    530.909090909091`}, {226.419910657307`, -530.909090909091`}, \
{227.440970006382`, 534.545454545455`}, {228.462029355456`, 
    520.`}, {228.972559029994`, 520.`}, {230.504148053606`, 
    509.090909090909`}, {233.056796426292`, 
    516.363636363636`}, {235.609444798979`, -527.272727272727`}, \
{239.18315252074`, 
    516.363636363636`}, {243.777919591576`, -501.818181818182`}, \
{246.330567964263`, -498.181818181818`}, {248.88321633695`, 
    501.818181818182`}, {251.435864709636`, -505.454545454545`}, \
{253.477983407786`, 
    494.545454545455`}, {254.49904275686`, -494.545454545455`}, \
{257.051691129547`, 
    501.818181818182`}, {259.093809827696`, -509.090909090909`}, \
{259.604339502234`, 
    498.181818181818`}, {261.135928525846`, -498.181818181818`}, \
{261.646458200383`, -487.272727272727`}, {262.667517549458`, \
-490.909090909091`}, {264.709636247607`, 
    465.454545454545`}, {265.730695596682`, -487.272727272727`}, \
{266.751754945756`, -469.090909090909`}, {267.262284620294`, 
    458.181818181818`}, {268.283343969368`, -469.090909090909`}, \
{269.304403318443`, -469.090909090909`}, {270.835992342055`, \
-483.636363636364`}, {272.367581365667`, -483.636363636364`}, \
{273.899170389279`, -476.363636363636`}, {274.920229738354`, \
-465.454545454545`}, {276.451818761966`, -472.727272727273`}, \
{277.983407785577`, -469.090909090909`}, {279.514996809189`, 
    447.272727272727`}, {281.557115507339`, 
    440.`}, {283.599234205488`, -447.272727272727`}, {285.1308232291`,
     425.454545454545`}, {286.151882578175`, -447.272727272727`}, \
{288.194001276324`, 
    414.545454545455`}, {289.725590299936`, -410.909090909091`}, \
{291.257179323548`, -400.`}, {292.278238672623`, 
    381.818181818182`}, {293.299298021697`, -385.454545454545`}, \
{295.341416719847`, 356.363636363636`}, {296.873005743459`, 
    349.090909090909`}, {297.894065092534`, 
    349.090909090909`}, {299.425654116145`, 
    320.`}, {301.978302488832`, 
    290.909090909091`}, {302.488832163369`, 
    258.181818181818`}, {302.999361837907`, 
    221.818181818182`}, {304.020421186981`, 
    170.909090909091`}, {304.530950861519`, 181.818181818182`}};

Answer 1

Maybe use MovingAverage or Partition+Mean to smoothing the dat after FindShortestTour.

Clear[k, data2];
k = 6;
data2 = Append[#, First@#] &@(Mean /@ Partition[dat, k, 1, -1]);
ListLinePlot[{dat, data2}, PlotStyle -> {Opacity[.6], Red}]

Answer 2

Not (yet) an answer, only a solution idea.

To solve your problem we have to redefine FindShortestTour in such a way , that the distance function includes points and angle of lineelements.

dist[p_  ] := 
 Block[{tag = 1 , n = Length[p], 
   pn = Join[ p[[-2 ;; -1]] , p, p[[1 ;; 2]] ] , 
   angle = Function[{a, b}, 
     If[a . b == 0 && Det[{a, b}] == 0, 0, 
      ArcTan[a . b, Det[{a, b}]]]]  (*signed vectorangle between a,
   b*)
    (*,angle=Function[{a,b},ArcTan[a.b,Det[{a,b}]]]*)
   , faktor = 1/2 + tag Boole[#^2 > (Pi/2)^2]  (#^2 - (Pi/2)^2)^2 & 
    },
    Sum[ (faktor[
         angle[pn[[ i + 1]] - pn[[i ]], pn[[i ]] - pn[[i - 1 ]]]] + 
        faktor[angle[pn[[ i ]] - pn[[i - 1 ]], 
          pn[[i - 1 ]] - pn[[i - 2 ]]]])  Sqrt[# . #] &[
    pn[[i]] - pn[[i - 1]]] , {i, 3, n + 2}]
  ]

If the angle of neighboring lineelements is much greater than 0 dist returns a norm much greater than the length of the line element.

Simple Redefinition of FindShortetsTour

findSmoothTour = 
 Function[p, Block[{n = Length[p ],  pn, n1, n2, distp, distpn},
   distp = dist[p ];
   {n1, n2} = RandomSample[Range[1, Length[p]], 2] ;
   If[n1 < n2,
    pn = Join[p[[;; n1 - 1]], Reverse[p[[n1 ;; n2]]], p[[n2 + 1 ;;]]],
    pn = Join[p[[;; n2 - 1]], Reverse[p[[n2 ;; n1]]], p[[n1 + 1 ;;]]]
    ];
   distpn = dist[pn ];
   If[distpn < distp, pn, p]
   ] ]

Currently this approach isn't fast, though we reduce size of tourdata

datDirtyn=RandomSample[DatDirty, 200]  ;
{dist, order} = FindShortestTour[datDirtyn ];
dat = Part[datDirty, order];

test

datG = Nest[findSmoothTour, dat    , 5000  ];
{ dist[dat], dist[datG]} (* {7528.7, 6463.85} *)

Approach gives an improvement of dist but tour doesn't look much better.

Any ideas how to improve this approach?

Answer 3

Not sure how you define "backtracking". It appears that you define it as the requirement to go to ever-increasing polar angles which may in cases contradict the requirement for "shortest" tour I think. If that's the case, then a simple polar transform, sort by angle and then inverse polar transform should give you what you need (but note, there is absolutely no element of shortness in this path):

transformed = (datDirty /. {a_, b_} :> AbsArg[a + I  b] // 
     SortBy[Last]) /. {c_, d_} :> c {Cos[d], Sin[d]};
ListLinePlot@transformed

Answer 4

If I correctly understand your aim, the following does the job.

Region[RegionBoundary[ConvexHullRegion[datDirty]]]