Pathfinding di wilayah 2D

Question

Bagaimana saya bisa menemukan rute terpendek atau mendekati optimal antara dua titik di mana rute dibatasi dalam wilayah 2D?

Pertama, pertimbangkan bundel baris berikut:

SeedRandom[1];
points = RandomPoint[Disk[], 70];
nf = Nearest[points];
lines = Line /@ Partition[points, 2];
start = First[nf[{0, -1}]];
end = First[nf[{0, 1}]];
Graphics[{lines, Blue, PointSize[Large], Point[start], Red, Point[end]}]

Untuk mengatasi hal ini bisa membuat grafik dimana perpotongannya adalah simpul. Namun, bagaimana jika kita memiliki kombinasi kawasan yang lebih rumit seperti berikut:

SeedRandom[1];
numdisks = 60;
numpolys = 40;

disks = MapThread[
   Disk[#1, #2] &, {RandomPoint[Disk[], numdisks], 
    RandomReal[1/5, numdisks]}];

polygons = MapThread[
   Translate[#1, #2] &, {RandomPolygon[8, numpolys, 
     DataRange -> {-.15, .15}], RandomPoint[Disk[], numpolys]}];

Graphics[{
  disks, polygons, PointSize[Large], Cyan, Point[{-.4, .9}], Magenta, 
  Point[{-.8, -.6}]
}]

Harus ada beberapa jalur yang terdiri dari segmen garis yang membawa kita dari titik cyan ke titik magenta. Saya ingin menyelesaikan contoh khusus ini dalam pengertian agnostik tanpa mempertimbangkan properti khusus apa pun dari primitif yang mendasarinya. Dengan kata lain, kami hanya diberi satu wilayah suka ImageMesh[ColorNegate[Graphics[{polygons, disks}]]]dan tidak ada cara untuk memecahnya lebih jauh.

Answer 1

Berikut adalah pendekatan yang akan menghasilkan solusi optimal secara global (kode di bawah):

Setelah beberapa pra-pemrosesan, kinerjanya mampu secara real-time seperti yang ditunjukkan dalam gif. Pemrosesan awal perlu dijalankan sekali untuk setiap wilayah, tetapi membutuhkan waktu kurang dari 3 detik di komputer saya untuk wilayah yang dimaksud.

Idenya adalah bahwa setiap jalur terpendek pada dasarnya terdiri dari garis lurus antar titik pada batas wilayah (dan tentu saja titik awal dan akhir). Untuk melihat ini, bayangkan berada di sebuah ruangan dengan bentuk wilayah, dan jalur terpendek kandidat Anda ditandai dengan string: Jika sekarang Anda menarik tali (untuk meminimalkan panjang jalur yang diambil oleh string), string akan tertangkap oleh beberapa sudut ruangan, tetapi akan berada di garis lurus di antaranya. Pada titik ini kami juga mencatat bahwa hanya sudut yang mengarah ke dalam yang perlu dipertimbangkan: Tidak ada jalur terpendek yang akan pergi ke sudut yang menghadap ke luar dari wilayah tersebut, seperti yang dapat dilihat lagi dari analogi dengan string.

Implementasi memilih semua sudut penunjuk ke dalam pointData(yang juga berisi data untuk fungsi yang insideQdijelaskan di bawah) dan menghasilkan daftar semua kemungkinan baris antara titik-titik tersebut, dan kemudian memilih yang ada di dalam wilayah (ini adalah langkah yang akan mengambil sementara, karena ada ~ 25000 jalur untuk memeriksa wilayah di atas). Untuk mendapatkan jalur sebenarnya dari awal hingga akhir, kita perlu menambahkan semua garis dari dua titik tersebut ke titik batas penunjuk ke dalam, tetapi daftar itu jauh lebih pendek dan dengan demikian dapat dihitung secara real time.

Hal yang sulit adalah mendapatkan fungsi yang dapat dengan cepat memeriksa apakah suatu garis ada di dalam wilayah atau tidak - sayangnya, fungsi wilayah bawaan terlalu lambat (dan bermasalah), jadi kami memerlukan solusi khusus.

Ini dilakukan oleh fungsi lineWithinQ, intersectingQdan insideQ:

• insideQmemeriksa apakah garis yang diuji menunjuk ke dalam dari tepi batas dengan secara esensial menghitung hasil kali tiga dari dua vektor tepi yang bersebelahan dan garis yang dimaksud. Kami juga menyusun fungsi untuk kinerja maksimal.

• intersectingQmemeriksa apakah garis yang diuji berpotongan dengan salah satu garis batas (menyentuh garis tidak dihitung). Fungsi tersebut secara efektif menyelesaikan perpotongan dua garis (berdasarkan titik ujungnya) dan memverifikasi bahwa perpotongan tersebut memang berada di antara titik-titik akhir. Untuk performa maksimal, fungsi ini dikompilasi dan dibatalkan segera setelah persimpangan ditemukan

• Terakhir, lineWithinQperiksa apakah garis ada di dalam wilayah dalam dua langkah:

  • Pertama, periksa apakah garis mengarah ke wilayah tersebut dengan insideQ
  • Kedua, periksa apakah garis melintasi batas pada titik mana pun dengan intersectingQ(ingat bahwa sentuhan tidak dihitung)

Karena fungsi hanya berfungsi untuk garis antar titik di perbatasan, menambahkan titik awal dan akhir dilakukan sedikit berbeda (seperti yang terlihat dengan penanganan startdan enddi dalam kode di RegionShortestPathFunctionbawah): Pertama-tama kita memfilter garis dari titik batas mana pun ke awal / end using lineWithinQ, karena fungsinya masih berfungsi selama titik pertama ada di batas ( insideQperiksa apakah titik garis mengarah ke wilayah hanya melihat dari titik awal garis). Untuk memeriksa apakah garis lurus dari awal sampai akhir valid, kita cukup memeriksa apakah garis tersebut memotong batas sama sekali.

Module[
 {cond, l, i},
 cond = Unevaluated@FullSimplify[0 < t < 1 && 0 < u < 1] /. 
   First@Solve[{t, 1 - t}.{{x1, y1}, {x2, y2}} == {u, 
        1 - u}.{{x3, y3}, {x4, y4}}, {t, u}];
 cond = cond /. 
   Thread[{x1, y1, x2, y2} -> Table[Indexed[l, {i, j}], {j, 4}]];
 cond = cond /. Thread[{x3, y3} -> Table[Indexed[p1, i], {i, 2}]];
 cond = cond /. Thread[{x4, y4} -> Table[Indexed[p2, i], {i, 2}]];
 With[
  {cond = cond},
  intersectingQ = Compile @@ Hold[
     {{l, _Real, 2}, {p1, _Real, 1}, {p2, _Real, 1}},
     Module[{ret = False}, 
      Do[If[cond, ret = True; Break[]], {i, Length@l}]; ret],
     CompilationTarget -> "C", RuntimeAttributes -> {Listable}, 
     Parallelization -> True
     ]
  ]
 ]

Module[
 {cond, x1, y1, z1, x2, y2, v1, v2},
 cond = {x1, y1, z1}.Append[Normalize@{x2, y2}, 1] > 0 /. 
    Abs -> RealAbs // FullSimplify[#, x2^2 + y2^2 > 0] &;
 cond = cond /. Thread[{x1, y1, z1} -> Table[Indexed[v1, i], {i, 3}]];
 cond = cond /. Thread[{x2, y2} -> Table[Indexed[v2, i], {i, 2}]];
 insideQ = Compile @@ {
    {{v1, _Real, 1}, {v2, _Real, 1}},
    cond,
    CompilationTarget -> "C", RuntimeAttributes -> {Listable}, 
    Parallelization -> True
    }
 ]

lineWithinQ[lineData_, {{p1_, v1_}, {p2_, _}}] :=
 insideQ[v1, p2 - p1] && ! intersectingQ[lineData, p1, p2]

Options[RegionFindShortestPath] = {"MonitorProgress" -> True};

RegionFindShortestPath[region_?MeshRegionQ, start : {_, _}, end : {_, _}, opts : OptionsPattern[]] :=
 RegionFindShortestPath[region, start, opts][end]
RegionFindShortestPath[region_?MeshRegionQ, start : {_, _}, opts : OptionsPattern[]] :=
 RegionFindShortestPath[region, opts][start]

RegionFindShortestPath[region_?MeshRegionQ, OptionsPattern[]] :=
 Module[
  {lines, lineData, pointData, pathData},
  lines = MeshPrimitives[RegionBoundary@region, 1][[All, 1]];
  lineData = Catenate /@ lines;
  pointData = Cases[(* select inwards pointing corners *)
     {p_, {__, z_} /; z > 0, c_} :> {p, c}
     ]@Catenate[
     Transpose@{
         #[[All, 2]],
         Sequence @@ Table[
           Cross[#, {-1, -1, 1} #2] & @@@
            Partition[
             Append[z]@*Normalize /@ Subtract @@@ #,
             2, 1, {1, 1}
             ],
           {z, 0, 1}
           ]
         } & /@
      FindCycle[Graph[UndirectedEdge @@@ lines], \[Infinity], All]
     ];
  pathData = With[
    {expr := 
      Select[lineWithinQ[lineData, #] &]@Subsets[pointData, {2}]},
    If[OptionValue["MonitorProgress"],
      ResourceFunction["MonitorProgress"][expr, 
       "CurrentDisplayFunction" -> None],
      expr
      ][[All, All, 1]]
    ];
  RegionShortestPathFunction[pointData, lineData, 
   Join[pathData, lines]]
  ]

RegionShortestPathFunction[data__][start : {_, _}, end : {_, _}] :=
 RegionShortestPathFunction[data][start][end]
RegionShortestPathFunction[pointData_, lineData_, pathData_][start : {_, _}] :=
 RegionShortestPathFunction[pointData, lineData, Join[
   pathData,
   Select[lineWithinQ[lineData, #] &][{#, {start, {}}} & /@ 
      pointData][[All, All, 1]]
   ], start]

RegionShortestPathFunction[pointData_, lineData_, pathData_, start_][end : {_, _}] :=
 With[
  {allLines = Join[
     pathData,
     Select[lineWithinQ[lineData, #] &][{#, {end, {}}} & /@ 
        pointData][[All, All, 1]],
     If[! intersectingQ[lineData, start, end], {{start, end}}, {}]
     ]},
  Quiet@
   Check[
    FindShortestPath[
     Graph[UndirectedEdge @@@ allLines, 
      EdgeWeight -> EuclideanDistance @@@ allLines], start, end],
    {}
    ]
  ]

summaryBoxIcon = Graphics[
  {{[email protected], 
    Polygon@{{0, 0}, {0, 1}, {1, 1}, {1, -1}, {-2, -1}, {-2, 
       1.5}, {-1, 1.5}, {-1, 0}}}, {Red, 
    Line@{{0.5, 0.5}, {0, 0}, {-1, 0}, {-1.5, 1}}}, 
   AbsolutePointSize@4, Point[{0.5, 0.5}], {Point[{-1.5, 1}]}}, 
  Background -> GrayLevel[0.93], PlotRangePadding -> Scaled[0.1], 
  FrameStyle -> Directive[Thickness[Tiny], [email protected]], 
  ElisionsDump`commonGraphicsOptions
  ]

MakeBoxes[
  f : RegionShortestPathFunction[pointData_, lineData_, pathData_, 
    start_ | PatternSequence[]], fmt_] ^:=
 BoxForm`ArrangeSummaryBox[
  RegionShortestPathFunction,
  f,
  summaryBoxIcon,
  {
   BoxForm`SummaryItem@{"Corner points: ", Length@lineData},
   BoxForm`SummaryItem@{"Start set: ", Length@{start} > 0}
   },
  {
   BoxForm`SummaryItem@{"Possible segments: ", Length@pathData}
   },
  fmt
  ]

SeedRandom[1];
numdisks = 60;
numpolys = 40;

disks = MapThread[
   Disk[#1, #2] &, {RandomPoint[Disk[], numdisks], 
    RandomReal[1/5, numdisks]}];
translatePoly[poly_, pos_] := 
  Polygon[# + pos & /@ poly[[1]], poly[[2]]];
polygons = 
  MapThread[
   translatePoly[#1, #2] &, {RandomPolygon[8, numpolys, 
     DataRange -> {-.15, .15}], RandomPoint[Disk[], numpolys]}];
start = {-.4, .9};
end = {-.8, -.6};
Graphics[{disks, polygons, PointSize[Large], Cyan, Point[start], 
  Magenta, Point[end]}]
mesh = DiscretizeRegion[RegionUnion[Join[polygons, disks]]];

spf = RegionFindShortestPath[mesh]

Manipulate[
 Show[
   mesh,
   Graphics[{Thick, Red, Dynamic@Line@spf[p1, p2]}]
  ],
 {p1, Locator},
 {p2, Locator}
 ]

Seperti yang ditunjukkan, fungsi dapat digunakan sebagai RegionFindShortestPath[mesh][start,end](di mana RegionFindShortestPath[mesh]memberi a RegionShortestPathFunctiondengan informasi yang dihitung sebelumnya yang disimpan di cache). Semua kombinasi seperti RegionFindShortestPath[mesh,start,end]dan RegionFindShortestPath[mesh,start][end]berfungsi dengan baik, dengan informasi sebanyak mungkin disimpan dalam cache.

Answer 2

Saya datang dengan solusi yang tidak konvensional dan tidak efisien yang mungkin rentan terhadap masalah meshing dan sensitif terhadap ukuran sel mesh, tetapi saya yakin ini menghasilkan jalur pendek yang cukup baik. Mungkin orang lain dapat memperbaiki ini atau menyarankan solusi alternatif:

SeedRandom[1];
numdisks = 60;
numpolys = 40;

disks = MapThread[
   Disk[#1, #2] &, {RandomPoint[Disk[], numdisks], 
    RandomReal[1/5, numdisks]}];
translatePoly[poly_, pos_] := 
  Polygon[# + pos & /@ poly[[1]], poly[[2]]];
polygons = 
  MapThread[
   translatePoly[#1, #2] &, {RandomPolygon[8, numpolys, 
     DataRange -> {-.15, .15}], RandomPoint[Disk[], numpolys]}];
start = {-.4, .9};
end = {-.8, -.6};
Graphics[{disks, polygons, PointSize[Large], Cyan, Point[start], 
  Magenta, Point[end]}]
mesh = DiscretizeRegion[RegionUnion[Join[polygons, disks]]];

cells = MeshCells[mesh, 2][[All, 1]];
prims = MeshPrimitives[mesh, 2];
meshcentroids = RegionCentroid /@ prims;
nprim = Nearest[meshcentroids -> "Index"];
startcell = cells[[First[nprim[start]]]];
endcell = cells[[First[nprim[end]]]];
connectedCells[cells1_, cells2_] := 
 Length[Intersection[cells1, cells2]] == 2
cellGr = RelationGraph[connectedCells[#1, #2] &, cells, 
   VertexCoordinates -> meshcentroids];
path = FindShortestPath[cellGr, startcell, endcell];

Show[Graphics[
  {EdgeForm[LightRed], FaceForm[LightYellow], mesh, PointSize[Large], 
   Cyan, Point[start], Magenta, Point[end]}
  ], HighlightGraph[cellGr, PathGraph[path]]
 ]

Kode di atas menemukan jalur dalam grafik konektivitas mesh. Itu adalah grafik segitiga yang berdekatan (berbagi tepi) di jala terpisah. Jalur ini jelas sangat berlekuk-lekuk, jadi kode berikut mencoba menemukan 'lompatan' terpanjang di sepanjang jalur yang dapat melewati simpul tetapi tetap berada di dalam kawasan:

(** from the currentPoint, try to draw a line that to the furthest 
  possible point on the path that stays within the region **)
getcoords[cell_] := AnnotationValue[{cellGr, cell}, VertexCoordinates]
pathcoords = Join[{start},getcoords /@ path, {end}];
maxiline[currentPoint_, coords_] := 
 SelectFirst[Reverse[coords], 
  Quiet[Check[RegionWithin[mesh, Line[{currentPoint, #}]], False]] &]
lpath = NestWhileList[maxiline[#, pathcoords] &, start, # != end &];
Graphics[{mesh, Red, Line[lpath], PointSize[Large], Cyan, 
  Point[start], Magenta, Point[end]}]

Answer 3

ini percobaan pertama. Ini dapat ditingkatkan, tetapi seseorang harus memulai dari suatu tempat. Program berikut mengambil wilayah, titik awal dan akhir, serta ukuran langkah. Itu membuat plot jalur (merah) dan titik-titik yang dicoba (hijau). Tapi ambillah mobil, karena tidak ada prasyarat untuk dieksploitasi, dibutuhkan banyak langkah. Ini adalah program rekursif, oleh karena itu kita perlu memperbesar "$ RecursionLimit". Berhati-hatilah dengan "stepsize", buatlah sebesar yang masuk akal, jika tidak, jumlah langkah akan meledak. Selanjutnya, perbedaan koordinat x dan y antara titik awal dan akhir harus merupakan kelipatan ukuran langkah. Jika tidak, akhir tidak akan pernah ditemukan. Dan untuk kesederhanaan, titik awal harus dipilih di atas titik akhir. Perhatikan juga bahwa jalurnya bisa sangat besar, jadi tidak masuk akal untuk mencetaknya. Idenya adalah, Anda akan melakukan sesuatu dengannya selain mencetak. Selanjutnya, Anda akan memerlukan beberapa wilayah nyata, bukan poligon terjemahan, yang akan bekerja dengan "RegionMember". Ini programnya, bersenang-senanglah:

getPath[region_, start_, end_, stepsize_] := 
  Module[{path = {pos = start}, step = stepsize, wrong = {}, remem, 
    search},
   If[Mod[(end - start)/step, 1] != {0, 0}, 
    Print["Difference between end and start must be a multiple of \
stepsize."]; Return[]];
   remem = RegionMember[region];
   search[pos_] := Module[{},
     If[ Norm[pos - end] < 0.001, Return[{}]];
     Which[
      tp = 
       pos + {0, -1} step;  ( ! MemberQ[path, tp]) && ( ! 
         MemberQ[wrong, tp]) && remem[tp], AppendTo[path, tp]; 
      search[tp],
      tp = 
       pos + {1, 0} step ;  ( ! MemberQ[path, tp]) && ( ! 
         MemberQ[wrong, tp]) && remem[tp], AppendTo[path, tp]; 
      search[tp],
      tp = 
       pos + {-1, 0} step; ( ! MemberQ[path, tp]) && ( ! 
         MemberQ[wrong, tp]) && remem[tp], AppendTo[path, tp];  
      search[tp],
      True, AppendTo[wrong, path[[-1]]];  path = Delete[path, -1]; 
      If[path == {}, Return[{}]]; search[path[[-1]]];
      ]];
   search[start];
   Show[Region[region], 
     Graphics[{Green, Point[wrong], Thick, Red, Line[path], Black, 
       PointSize[0.03], Point[end] , Point[start]}], 
     PlotRange -> {{-1, 4}, {-1, 5}}, Axes -> True] // Print;
   path
   ];

Kami membuat beberapa wilayah sewenang-wenang, memilih titik awal dan akhir dan membiarkan program mencari jalur.

region = RegionUnion[Disk[{0, 3.2}], Disk[{0.9, 2.2}, 0.5], 
   Disk[{1.9, 3.}, 0.8], Disk[{2.5, 1.8}, 0.6], Disk[{1.8, .6}, .9], 
   Disk[{0, 0}]];
start = {0., 3.2};
end = {0, 0};
stepsize = 1/10;
$RecursionLimit = 10^4;
path = getPath[region, start, end, stepsize];

Answer 4

Mulailah dengan ini:

RegionUnion[Disk[{0, 0}, 2], Disk[{3, 0}, 2]];

Region[%]

Untuk lingkaran sederhana dan satu titik:

RegionDistance[Disk[{0, 0}, 2], {3, 0}]

1

Graphics[{Disk[{0, 0}, 2], Point[{3, 0}], Red, 
  Line[{{0, 0}, {3, 0}}]}]

Jika niat utama tetap bekerja dengan Random-fungsi, ide dari @flinty tidak buruk untuk melihat apakah ini terhubung dan ada jalur.

Ini adalah pendekatan yang dihasilkan untuk susunan geometris bidang Circledan Polygon. Untuk masing-masing pusat diketahui dan satu Sortatau lainnya mudah dilakukan.

Proses ini harus diulangi dengan hati-hati untuk setiap set kecil yang berfungsi.

Berurusan dengan Transformgagal untuk BooleanRegion.

ℜpolygon = 
 Region@RegionUnion[
   Table[Polygon[
     Plus[cent[[i]], #] & /@ RandomReal[{-0.15, 0.15}, {8, 2}]], {i, 
     30}]]
ℜcircle = 
 Region@RegionUnion[
   MapThread[
    Disk[#1, #2] &, {RandomPoint[Disk[], numdisks], 
     RandomReal[1/5, numdisks]}]]

ℜcomp = 
 Region@RegionUnion[ℜpolygon, ℜcircle]

Namun RegionNearest dan RegionDistance tidak berfungsi, tidak ditentukan untuk BooleanRegion.

RegionDistance[
 Region@RegionUnion[{Disk[{0, 0}, 2], Disk[{1, 1}, 2], 
    Disk[{1, -1}, 2]}], {3, 0}]

Graphics[{Disk[{0, 0}, 2], Disk[{1, 1}, 2], Disk[{1, -1}, 2], 
  Point[{3, 0}], Red, 
  Line[{{Sqrt[(3/2 + 1/10 (-5 - 4 Sqrt[5]))^2 + (-3 + 
        1/5 (5 + 4 Sqrt[5]))^2], 0}, {3, 0}}]}]

Ini juga harus menjadi BooleanRegion.

Mathematica V12 memiliki built-in RandomInstancedanGeometricScene

RandomInstance[GeometricScene[{a, b, c, d, g, e, f}, {
   a == {-1/2, 0}, b == {1/2, 0}, Line[{f, a, b, e}],
   p0 == Polygon[{e, g, f}],
   p1 == Style[Polygon[{a, c, b}], Yellow],
   p2 == Style[Polygon[{b, d, c}], Magenta],
   p3 == Style[Polygon[{d, c, g}], Green],
   p4 == Style[Polygon[{g, c, a}], Blue],
   p5 == Style[Polygon[{e, b, d}], Purple],
   p6 == Style[Polygon[{g, a, f}], Orange],
   GeometricAssertion[{p0, p1, p2, p3, p4, p5, p6}, "Similar"]}], 
 RandomSeeding -> 4]

Ini memiliki built-in GeometricAssertiondengan menawarkan proses generatif untuk membangun jalur bersama dengan objek. Dan ini memungkinkan poligon acak yang lebih bagus dan lebih realistis. Dan itu memberikan deskripsi jalur di bidang dan menangani lebih banyak hubungan geometris yaitu SimplePolygonQ.

Sambungan mungkin diperkenalkan kembali pada V12.1 dan yang lebih baru. Saya dapat ditemukan di jawaban lain atas pertanyaan di komunitas ini. Urutan @@ gaya lama.

AnnotationValuetidak ada dalam dokumentasi saya tentang Mathematica V12.0.0. Tetapi AnnotationValuebekerja di V12.0.0. Jadi ini adalah bawaan tanpa nilai dalam pertanyaan ini: Gagal.

Jadi sisanya tidak berfungsi.

Ini berfungsi di V12.0.0 dan serupa:

Show[Graphics[{mesh, PointSize[Large], Cyan, Point[start], Magenta, 
   Point[end]}], Subgraph[cellGr, PathGraph[path]]]

Menggunakan

connectedCells[cells1_, cells2_] := 
 Length[Intersection[cells1, cells2]] == 1

dalam kode penggunaan di atas memberikan:

Show[Graphics[{mesh, PointSize[Large], Cyan, Point[start], Magenta, 
   Point[end]}], 
 Subgraph[cellGr, PathGraph[path], EdgeStyle -> {Thick, Green}]]

Ini lebih cepat, tetapi masih memiliki masalah di bagian kiri bawah DiscretizeRegion.

mesh = DiscretizeRegion [RegionUnion [Gabung [poligon, disk]], MaxCellMeasure -> 1]

mesh = DiscretizeRegion[RegionUnion[Join[polygons, disks]], 
   MaxCellMeasure -> {"Length" -> 1/15}, PrecisionGoal -> None];
cells = MeshCells[mesh, 2][[All, 1]];
prims = MeshPrimitives[mesh, 2];
meshcentroids = RegionCentroid /@ prims;
nprim = Nearest[meshcentroids -> "Index"];
startcell = cells[[First[nprim[start]]]];
endcell = cells[[First[nprim[end]]]];
connectedCells[cells1_, cells2_] := 
 Length[Intersection[cells1, cells2]] == 1
cellGr = RelationGraph[connectedCells[#1, #2] &, cells, 
   VertexCoordinates -> meshcentroids];
path = FindShortestPath[cellGr, startcell, endcell];

Show[Graphics[{mesh, PointSize[Large], Cyan, Point[start], Magenta, 
   Point[end]}], Subgraph[cellGr, PathGraph[path]]]

Hal ini menunjukkan bahwa meshing adaptif harus diganti dengan mesh yang halus dengan kepadatan reguler untuk mendapatkan jalur yang paling optimal jika menggunakan triangularisasi. Setiap sudut, setiap pelanggaran yang lebih kecil, setiap ekstensi yang mengarah ke dalam atau ke luar menarik jaring triangulasi, dan di sana menyebabkan osilasi di jalur terpendek.

Reguler memang menyebabkan osilasi selama ukuran selnya tinggi. Untuk yang lebih kecil setelah berhenti terpendek dari berosilasi dan langsung dan tetap berada di dalam gumpalan bertautan. Jika batasnya akan diperhitungkan dengan lebih baik, yang terpendek mungkin lebih banyak berada di wilayah pusat gumpalan.

Ini adalah kompromi antara waktu dan arah seberapa pendek jalan terpendek itu.