The mountain is described by the height function
$$ h(x,y)=\Bigl(5000-0.005(x^2+y^2+xy)+12.5(x+y)\Bigr)e^{-\left|10^{-6}(x^2+y^2)-0.0015(x+y)+0.7\right|}. $$
We must travel from
$$ A=(200,200)\qquad\text{to}\qquad B=(1400,1400) $$
while obeying the rule that the route may never rise above the smallest possible pass height. Among all such valid routes, we want the shortest one.
The implementation therefore solves two problems in sequence:
1. find the minimum feasible ceiling height,
2. under that ceiling, find the shortest route.
For any continuous path \(\gamma\) from \(A\) to \(B\), define its ceiling cost by
$$ C(\gamma)=\max_{p\in\gamma} h(p). $$
The smallest mountain pass height is then
$$ f_*=\min_{\gamma:A\to B} C(\gamma). $$
This is not yet a shortest-path problem in the Euclidean sense. It is a bottleneck problem: we minimize the highest altitude touched by the route.
Only after \(f_*\) is known does the actual geometric shortest-path problem begin.
The code samples the square
$$ [0,1600]\times[0,1600] $$
on a regular grid with spacing grid-step. With the default setting grid-step = 1.0, this gives
$$ n=1601 $$
grid points on each axis.
At each grid point \((i\Delta,j\Delta)\), the program stores the sampled height
$$ h(i\Delta,j\Delta). $$
This replaces the continuous terrain by a finite graph whose vertices are grid samples and whose edges connect the four axis-adjacent neighbors.
The four-neighbor choice matters because the code is using the grid only to estimate topological connectivity under a height ceiling; diagonal moves are not needed for the minimax search itself.
For a grid path
$$ v_0,v_1,\dots,v_t, $$
the discrete bottleneck cost is
$$ \max\bigl(h(v_0),h(v_1),\dots,h(v_t)\bigr). $$
If the current best ceiling at a vertex is \(c\), and we step to a neighbor \(u\), the new ceiling becomes
$$ c'=\max(c,h(u)). $$
This update is monotone: extending a path never lowers its ceiling. That is exactly the property Dijkstra needs. Once a vertex leaves the priority queue with the smallest currently known ceiling, no later path can improve it.
So the routine minimax_height is a correct Dijkstra-style solver for the minimax problem, with relaxation rule
$$ \text{best}[u]\leftarrow \min\bigl(\text{best}[u], \max(\text{best}[v],h(u))\bigr). $$
The returned value is a grid approximation of the true continuous pass height \(f_*\).
Once \(f_*\) is known, define the forbidden set
$$ \Omega=\{(x,y): h(x,y)>f_*\}. $$
The allowed set is its complement
$$ F=\{(x,y): h(x,y)\le f_*\}. $$
Any valid route must lie entirely in \(F\). Therefore the shortest valid route is simply the shortest Euclidean path from \(A\) to \(B\) in the plane with the obstacle region \(\Omega\) removed.
The critical boundary is the contour
$$ \partial\Omega=\{(x,y): h(x,y)=f_*\}. $$
The whole second phase of the algorithm is about approximating this contour and then solving a shortest-path problem around it.
For a fixed obstacle with smooth or polygonal boundary, a shortest path in the free plane has a standard structure:
1. whenever the path is strictly inside free space, it is a straight line segment,
2. if it cannot remain straight because the obstacle blocks it, it touches the obstacle boundary,
3. while constrained by the obstacle, it follows the boundary, then leaves it along another straight visible segment.
So once the relevant contour loop is known, the shortest valid route must be one of these forms:
1. the direct segment \(AB\), if it stays below \(f_*\),
2. \(A\to P_i\), then an arc of the contour, then \(P_j\to B\), where \(P_i\) and \(P_j\) are visible contour points.
This is the geometric reason the code only scans visible contour-point pairs instead of searching arbitrary curved paths in the plane.
The grid already tells us which sampled vertices are above the ceiling and which are below it. The code marks a sample as inside the forbidden region when
$$ h(i\Delta,j\Delta)>f_*. $$
Each grid cell has four corners, so there are \(2^4=16\) possible above/below patterns. The arrays kCaseCount and kCaseEdges are the usual marching-squares lookup tables for those 16 cases.
If an edge crosses the contour \(h=f_*\), the crossing point is approximated by linear interpolation. If an edge endpoint heights are \(h_1\) and \(h_2\), then the crossing fraction is
$$ t=\frac{f_*-h_1}{h_2-h_1}, $$
and the point is
$$ P(t)=P_1+t(P_2-P_1). $$
Cells of ambiguous type produce two contour segments; ordinary crossing cells produce one. Running over all cells produces a polygonal approximation of the level set \(h=f_*\).
The interpolated segment endpoints are floating-point numbers. Two segments that should meet can differ by tiny roundoff noise, so the code quantizes each point with scale
$$ 10^6. $$
That means nearly coincident points are snapped to the same integer key.
The program then builds an adjacency map from these quantized keys. In an ideal simple contour, every contour vertex has degree 2. The code checks exactly that.
Next it walks the adjacency graph to recover closed loops. If several loops appear, the implementation keeps the loop with largest perimeter.
This is an implementation-level robustness choice: numerically extracted contours can split into several pieces, but the outer main obstacle loop is the one relevant for the shortest route around the mountain.
Once a single contour loop
$$ P_0,P_1,\dots,P_{m-1} $$
has been recovered, the code computes prefix arc lengths
$$ S_0=0,\qquad S_{i+1}=S_i+|P_iP_{i+1}|, $$
with indices taken cyclically. The total contour perimeter is
$$ L=S_m. $$
For two contour vertices \(P_i\) and \(P_j\), one arc has length
$$ s_{ij}=|S_j-S_i|, $$
and the opposite arc has length
$$ L-s_{ij}. $$
The shorter one is the relevant boundary-travel cost for that pair.
A contour point \(P_i\) is usable from \(A\) only if the straight segment \(AP_i\) stays under the ceiling. Since the code does not solve the exact intersection analytically, it checks visibility by sampling points along the segment with step size vis-step.
If any sampled point satisfies
$$ h(x,y)>f_*+10^{-10}, $$
then the segment is rejected.
This produces two visible-index sets:
$$ V_A=\{i: A\text{ can see }P_i\},\qquad V_B=\{j: B\text{ can see }P_j\}. $$
Only pairs from \(V_A\times V_B\) need to be examined.
For each visible pair \((i,j)\), the candidate route length is
$$ |AP_i|+\min\bigl(s_{ij},\,L-s_{ij}\bigr)+|P_jB|. $$
The code also checks the direct segment \(AB\) first. If it is visible under \(f_*\), then no bent route can beat it, because a straight segment is the shortest Euclidean connection between two points.
Otherwise, the minimum over all visible contour pairs is the program's approximation to the true shortest valid route.
The program validates several necessary conditions:
1. \(f_*\) cannot be below the heights of \(A\) or \(B\),
2. the contour must not be empty,
3. every contour node must have degree 2,
4. the final route cannot be shorter than the direct distance \(|AB|\).
With the default parameters, the endpoint heights are approximately
$$ h(A)\approx 7851.540,\qquad h(B)\approx 6964.696. $$
The straight segment from \(A\) to \(B\) reaches heights above
$$ 13275, $$
so it is not feasible at the optimal ceiling.
When run with --verbose, the program reports
$$ f_*\approx 10396.458664, $$
and with default discretization it prints the route length
$$ 2531.205. $$
These are code-level numerical outputs, not symbolic closed forms.
compute_heights samples the height field on the grid, optionally in parallel. minimax_height then runs the priority-queue minimax search and returns the discrete pass height.
After that, the code marks grid vertices with height above \(f_*\), extracts contour segments cell by cell with marching squares, quantizes segment endpoints, builds an adjacency graph, walks it into loops, chooses the largest loop, and computes prefix arc lengths around that loop.
Next, it evaluates which contour points are visible from \(A\) and \(B\), checks the direct segment \(AB\), and finally scans all visible pairs with the formula
$$ |AP_i|+\min\bigl(s_{ij},L-s_{ij}\bigr)+|P_jB|. $$
The minimum of those candidates is printed to three decimal places.
If the grid has \(n\) points on each axis, then height sampling costs \(O(n^2)\), the minimax Dijkstra pass costs \(O(n^2\log n)\), contour extraction costs \(O(n^2)\), and visibility checks cost
$$ O(|V_A|+|V_B|)\times\text{sampling work} $$
plus the final pair scan
$$ O(|V_A||V_B|). $$
Memory usage is \(O(n^2)\) because the sampled height field dominates storage.
The important tradeoff is numerical: smaller grid-step and vis-step improve the approximation to the continuous problem, but they increase runtime and memory consumption.
Das Gebirge wird durch die Höhenfunktion
$$ h(x,y)=\Bigl(5000-0.005(x^2+y^2+xy)+12.5(x+y)\Bigr)e^{-\left|10^{-6}(x^2+y^2)-0.0015(x+y)+0.7\right|}. $$
beschrieben. Gesucht ist der kürzeste zulässige Weg von
$$ A=(200,200)\qquad\text{nach}\qquad B=(1400,1400), $$
wobei „zulässig“ bedeutet, dass der Weg niemals über die kleinstmögliche Passhöhe ansteigt. Unter allen solchen Wegen soll die kürzeste Route gefunden werden.
Der Solver behandelt deshalb zwei Teilprobleme nacheinander:
1. Bestimme die minimale erreichbare Maximalhöhe,
2. finde unter dieser Schranke den kürzesten Weg.
Für einen beliebigen Pfad \(\gamma\) von \(A\) nach \(B\) definieren wir die Höhenkosten durch
$$ C(\gamma)=\max_{p\in\gamma}h(p). $$
Die gesuchte kleinste Passhöhe ist
$$ f_*=\min_{\gamma:A\to B} C(\gamma). $$
Das ist zunächst kein euklidisches Kürzeste-Wege-Problem, sondern ein Bottleneck-Problem: minimiert wird die größte berührte Höhe.
Erst nach Bestimmung von \(f_*\) kann man über die eigentliche Weglänge sprechen.
Der Code diskretisiert das Quadrat
$$ [0,1600]\times[0,1600] $$
auf einem regulären Raster mit Schrittweite grid-step. Standardmäßig ist grid-step = 1.0, also gibt es
$$ n=1601 $$
Gitterpunkte pro Achse.
An jedem Rasterpunkt \((i\Delta,j\Delta)\) wird die Höhe
$$ h(i\Delta,j\Delta) $$
berechnet. So wird aus dem kontinuierlichen Gebirge ein endlicher Graph, dessen Knoten Rasterpunkte und dessen Kanten die vier achsenparallelen Nachbarn verbinden.
Für einen Gitterpfad
$$ v_0,v_1,\dots,v_t $$
ist die diskrete Passkostenfunktion
$$ \max\bigl(h(v_0),h(v_1),\dots,h(v_t)\bigr). $$
Hat ein Knoten aktuell die beste bekannte Schranke \(c\), dann erzeugt ein Schritt zu Nachbar \(u\) die neue Schranke
$$ c'=\max(c,h(u)). $$
Diese Aktualisierung ist monoton: eine Pfadverlängerung kann die benötigte Deckenhöhe nie senken. Genau deshalb bleibt das Dijkstra-Prinzip gültig. Sobald ein Knoten mit kleinster aktueller Schranke aus der Prioritätswarteschlange entfernt wird, ist diese Schranke optimal.
Die Relaxierung im Code lautet also
$$ \text{best}[u]\leftarrow \min\bigl(\text{best}[u], \max(\text{best}[v],h(u))\bigr), $$
und minimax_height liefert eine Gitterapproximation von \(f_*\).
Ist \(f_*\) bekannt, so definiert man die verbotene Menge
$$ \Omega=\{(x,y):h(x,y)>f_*\} $$
und die erlaubte Menge
$$ F=\{(x,y):h(x,y)\le f_*\}. $$
Jeder zulässige Weg muss ganz in \(F\) liegen. Der Rand der verbotenen Menge ist die kritische Niveaulinie
$$ \partial\Omega=\{(x,y):h(x,y)=f_*\}. $$
Damit reduziert sich die zweite Phase auf einen euklidischen Kürzeste-Wege-Fall im freien Gebiet außerhalb des Hindernisses \(\Omega\).
Für ein fixes Hindernis besitzt der kürzeste Weg in der Ebene eine bekannte Struktur:
1. fern vom Hindernis verläuft er geradlinig,
2. wenn die direkte Verbindung blockiert ist, berührt er den Rand,
3. entlang des Hindernisses folgt er dem Rand, bevor er wieder geradlinig weiterläuft.
Deshalb genügt es, nach Wegen der Form zu suchen:
1. direkte Strecke \(AB\), falls zulässig,
2. \(A\to P_i\), dann ein Konturbogen, dann \(P_j\to B\), wobei \(P_i\) und \(P_j\) sichtbare Konturpunkte sind.
Genau diese Reduktion verwendet der Code.
Nachdem für jeden Rasterpunkt bekannt ist, ob er oberhalb oder unterhalb von \(f_*\) liegt, betrachtet der Code jede Rasterzelle mit ihren vier Ecken. Daraus entsteht eine 4-Bit-Maske; insgesamt gibt es also \(16\) Fälle.
Die Tabellen kCaseCount und kCaseEdges kodieren diese \(16\) Marching-Squares-Konfigurationen. Schneidet die Niveaukurve eine Zellkante, wird der Schnittpunkt linear interpoliert:
$$ t=\frac{f_*-h_1}{h_2-h_1},\qquad P(t)=P_1+t(P_2-P_1). $$
Mehrdeutige Zellmuster erzeugen zwei Segmente, gewöhnliche Muster ein Segment. Über alle Zellen hinweg ergibt das eine polygonale Approximation der Kontur \(h=f_*\).
Da interpolierte Punkte Gleitkommazahlen sind, können eigentlich identische Konturpunkte durch Rundungsfehler leicht voneinander abweichen. Der Code quantisiert daher jeden Punkt mit Maßstab
$$ 10^6, $$
sodass numerisch sehr nahe Punkte auf denselben ganzzahligen Schlüssel abgebildet werden.
Danach wird ein Adjazenzgraph der Segmentenden aufgebaut. Für eine saubere geschlossene Kontur muss jeder Knoten Grad \(2\) besitzen; genau das wird geprüft.
Anschließend durchläuft der Code den Graphen und rekonstruiert geschlossene Schleifen. Falls mehrere Schleifen entstehen, wird die mit dem größten Umfang gewählt. Das ist eine numerische Robustheitsentscheidung: die relevante Außenkontur des Bergmassivs soll erhalten bleiben.
Sei die gewählte Kontur
$$ P_0,P_1,\dots,P_{m-1}. $$
Dann definiert der Code Präfixlängen
$$ S_0=0,\qquad S_{i+1}=S_i+|P_iP_{i+1}|, $$
zyklisch verstanden. Der Gesamtumfang ist
$$ L=S_m. $$
Für zwei Punkte \(P_i\) und \(P_j\) gibt es zwei mögliche Umlaufrichtungen; ihre Längen sind
$$ s_{ij}=|S_j-S_i| $$
und
$$ L-s_{ij}. $$
Ein Konturpunkt \(P_i\) ist von \(A\) aus benutzbar, wenn die Gerade \(AP_i\) vollständig unterhalb der Deckenhöhe bleibt. Statt einer exakten analytischen Schnittrechnung prüft der Code dies durch Abtasten des Segments mit Schrittweite vis-step.
Wird an einem Stichpunkt
$$ h(x,y)>f_*+10^{-10} $$
festgestellt, ist die Sichtverbindung unzulässig.
So entstehen die beiden Indexmengen
$$ V_A=\{i:A\text{ sieht }P_i\},\qquad V_B=\{j:B\text{ sieht }P_j\}. $$
Für jedes sichtbare Paar \((i,j)\in V_A\times V_B\) berechnet der Code
$$ |AP_i|+\min\bigl(s_{ij},L-s_{ij}\bigr)+|P_jB|. $$
Zuvor wird zusätzlich die direkte Strecke \(AB\) getestet. Ist sie unterhalb von \(f_*\) sichtbar, kann kein gebrochener Weg kürzer sein, weil die Gerade in der Ebene die minimale euklidische Verbindung ist.
Andernfalls liefert das Minimum über alle sichtbaren Konturpaare die numerische Lösung.
Der Code validiert mehrere notwendige Bedingungen:
1. \(f_*\) darf nicht unter den Endpunkthöhen liegen,
2. die Kontur darf nicht leer sein,
3. jeder Konturknoten muss Grad \(2\) haben,
4. der gefundene Weg darf nicht kürzer als \(|AB|\) sein.
Mit den Standardparametern erhält man ungefähr
$$ h(A)\approx 7851.540,\qquad h(B)\approx 6964.696. $$
Die direkte Strecke \(AB\) steigt auf Werte über
$$ 13275 $$
an und ist daher unterhalb des optimalen Passniveaus nicht zulässig. Mit --verbose meldet das Programm
$$ f_*\approx 10396.458664, $$
und bei Standarddiskretisierung die Weglänge
$$ 2531.205. $$
compute_heights berechnet das Höhenfeld auf dem Raster, optional parallel. Danach bestimmt minimax_height per Prioritätswarteschlange die diskrete Passhöhe \(f_*\).
Anschließend markiert der Code die verbotenen Rasterpunkte, extrahiert mit Marching Squares die Niveaukontur, quantisiert die Segmentenden, baut einen Adjazenzgraphen, verfolgt daraus geschlossene Schleifen, wählt die größte Schleife und erzeugt Präfix-Bogenlängen.
Dann werden die von \(A\) und \(B\) aus sichtbaren Konturpunkte bestimmt, die direkte Verbindung \(AB\) getestet und schließlich alle sichtbaren Paare mit der Formel
$$ |AP_i|+\min\bigl(s_{ij},L-s_{ij}\bigr)+|P_jB| $$
durchmustert. Das Minimum wird mit drei Dezimalstellen ausgegeben.
Bei \(n\) Rasterpunkten pro Achse kostet die Höhenberechnung \(O(n^2)\), die Minimax-Dijkstra-Phase \(O(n^2\log n)\), die Konturextraktion \(O(n^2)\) und die Sichtbarkeits-/Paarprüfung
$$ O(|V_A||V_B|) $$
zuzüglich Abtastkosten entlang der Sichtsegmente.
Der Speicherverbrauch ist \(O(n^2)\), da das Höhenfeld den Hauptspeicher dominiert.
Der zentrale Trade-off ist numerisch: kleinere Werte für grid-step und vis-step verbessern die Kontinuumsapproximation, machen das Verfahren aber teurer.
Dağlık arazi şu yükseklik fonksiyonu ile verilir:
$$ h(x,y)=\Bigl(5000-0.005(x^2+y^2+xy)+12.5(x+y)\Bigr)e^{-\left|10^{-6}(x^2+y^2)-0.0015(x+y)+0.7\right|}. $$
Amacımız
$$ A=(200,200)\qquad\text{noktasından}\qquad B=(1400,1400) $$
noktasına gitmektir. Ancak yol “mümkün olan en düşük geçit yüksekliği”nin üstüne hiç çıkmamalıdır. Bu koşulu sağlayan yollar arasında en kısa olan istenir.
Dolayısıyla kod iki ayrı problemi peş peşe çözer:
1. önce gerekli en küçük tavan yüksekliğini bulur,
2. sonra bu tavan altında en kısa yolu hesaplar.
\(A\)'dan \(B\)'ye giden herhangi bir sürekli yol \(\gamma\) için yolun tavan maliyetini
$$ C(\gamma)=\max_{p\in\gamma} h(p) $$
diye tanımlayalım.
Aranan en küçük geçit yüksekliği
$$ f_*=\min_{\gamma:A\to B} C(\gamma) $$
olur.
Bu henüz “en kısa yol” problemi değildir. Bu bir bottleneck / minimax problemdir: yolun çıktığı en yüksek yer küçültülür.
Gerçek geometrik kısa yol hesabı ancak \(f_*\) bulunduktan sonra başlar.
Kod,
$$ [0,1600]\times[0,1600] $$
karesini düzenli bir grid ile örnekler. Adım uzunluğu grid-step'tir. Varsayılan ayarda grid-step = 1.0 olduğu için bir eksende
$$ n=1601 $$
adet grid noktası vardır.
Her \((i\Delta,j\Delta)\) noktasında
$$ h(i\Delta,j\Delta) $$
hesaplanır.
Böylece sürekli yüzey, düğümleri grid örnekleri ve kenarları dört eksensel komşuluk olan sonlu bir grafa dönüştürülür.
Buradaki 4-komşuluk seçimi önemlidir: kod bu grafiği gerçek yol uzunluğunu değil, belirli bir tavan altında bağlanabilirliği yaklaşık hesaplamak için kullanır.
Bir grid yolunun
$$ v_0,v_1,\dots,v_t $$
maliyeti, yol üzerindeki en büyük yükseklik olarak alınır:
$$ \max\bigl(h(v_0),h(v_1),\dots,h(v_t)\bigr). $$
Eğer bir düğümde mevcut en iyi tavan \(c\) ise ve komşu \(u\)'ya geçiyorsak yeni tavan
$$ c'=\max(c,h(u)) $$
olur.
Bu güncelleme monotondur; bir yolu uzatmak tavanı azaltamaz. Dijkstra’nın çalışması için gereken şey de tam olarak budur. Bir düğüm öncelik kuyruğundan en küçük mevcut tavan ile çıktığında, artık daha iyi bir tavan bulunamaz.
Dolayısıyla minimax_height fonksiyonu şu gevşetme kuralıyla çalışan doğru bir minimax-Dijkstra çözümüdür:
$$ \text{best}[u]\leftarrow \min\bigl(\text{best}[u], \max(\text{best}[v],h(u))\bigr). $$
Döndürülen değer, gerçek sürekli \(f_*\)'ün grid tabanlı yaklaşımıdır.
\(f_*\) bulunduktan sonra yasak bölge
$$ \Omega=\{(x,y):h(x,y)>f_*\} $$
olarak tanımlanır.
İzinli bölge ise
$$ F=\{(x,y):h(x,y)\le f_*\} $$
olur.
Geçerli herhangi bir rota tamamen \(F\) içinde kalmak zorundadır. Bu nedenle ikinci faz, aslında düzlemde \(\Omega\) engel bölgesi etrafındaki euklidyen kısa yol problemidir.
Kritik sınır,
$$ \partial\Omega=\{(x,y):h(x,y)=f_*\} $$
seviye eğrisidir.
Sabit bir engel etrafındaki en kısa yolun temel geometrisi şudur:
1. yol serbest bölgede kaldığı sürece düz gider,
2. düz gitmek engel yüzünden mümkün değilse sınırı temas eder,
3. engel tarafından zorlandığı kısımda sınır boyunca ilerler, sonra tekrar düz bir parça ile ayrılır.
Bu yüzden final arama şu iki biçime indirgenebilir:
1. eğer uygunsa doğrudan \(AB\) doğrusu,
2. \(A\to P_i\), sonra kontur üzerinde bir yay, sonra \(P_j\to B\), burada \(P_i\) ve \(P_j\) görünür kontur noktalarıdır.
Kodun tüm görünür nokta çiftlerini taraması işte bu geometrik gerekçeye dayanır.
Grid üzerinde her örnek noktanın \(f_*\)'ün üstünde mi altında mı olduğu artık bilinir. Kod,
$$ h(i\Delta,j\Delta)>f_* $$
ise noktayı yasak bölgenin içinde sayar.
Her hücrenin dört köşesi olduğundan toplam \(2^4=16\) olası üst/alt deseni vardır. kCaseCount ve kCaseEdges tabloları, bu 16 marching-squares durumunu uygular.
Bir hücre kenarı seviye eğrisiyle kesişiyorsa kesişim noktası doğrusal enterpolasyonla bulunur:
$$ t=\frac{f_*-h_1}{h_2-h_1},\qquad P(t)=P_1+t(P_2-P_1). $$
Bazı belirsiz hücre tipleri iki segment üretir, sıradan tipler bir segment üretir. Tüm hücreler dolaşıldığında \(h=f_*\) eğrisinin poligonal bir yaklaşımı elde edilir.
Enterpolasyon noktaları kayan noktalıdır. Aslında birleşmesi gereken iki uç nokta, küçük sayısal hatalar yüzünden tam aynı çıkmayabilir. Bu yüzden kod her noktayı
$$ 10^6 $$
ölçeğinde kuantize eder ve yakındaki noktaları aynı tamsayı anahtara yapıştırır.
Sonra bu anahtarlar üzerinden bir komşuluk grafiği kurulur. İdeal kapalı konturda her düğümün derecesi \(2\) olmalıdır; kod bunu açıkça doğrular.
Daha sonra bu graf üzerinde yürüyerek kapalı döngüler oluşturulur. Eğer birden fazla döngü çıkarsa, çözüm en büyük çevreye sahip döngüyü seçer. Bu, kodun sayısal kararlılık tercihidir: esas engel sınırı büyük dış döngüdür.
Seçilen tek döngü
$$ P_0,P_1,\dots,P_{m-1} $$
olsun.
Kod prefix uzunluklarını
$$ S_0=0,\qquad S_{i+1}=S_i+|P_iP_{i+1}| $$
olarak kurar. Buradan toplam çevre
$$ L=S_m $$
elde edilir.
İki kontur noktası \(P_i\) ile \(P_j\) arasında bir yöndeki yay uzunluğu
$$ s_{ij}=|S_j-S_i| $$
iken, diğer yöndeki yay
$$ L-s_{ij} $$
uzunluğundadır.
Bir kontur noktası \(P_i\), ancak \(AP_i\) doğru parçası tavanın altında kalıyorsa \(A\) tarafından kullanılabilir. Kod bunu analitik kesişim çözerek değil, doğru parça üzerinde örnekleme yaparak test eder.
Örneklerden biri bile
$$ h(x,y)>f_*+10^{-10} $$
ise doğru parça reddedilir.
Böylece iki görünürlük kümesi oluşur:
$$ V_A=\{i:A\text{ noktasından }P_i\text{ görülebiliyor}\}, $$
$$ V_B=\{j:B\text{ noktasından }P_j\text{ görülebiliyor}\}. $$
Yalnızca \(V_A\times V_B\) içindeki çiftlerin denenmesi yeterlidir.
Her görünür \((i,j)\) çifti için aday uzunluk
$$ |AP_i|+\min\bigl(s_{ij},L-s_{ij}\bigr)+|P_jB| $$
şeklindedir.
Kod ayrıca en başta \(AB\) doğru parçasını da test eder. Eğer \(AB\), \(f_*\) altında görünürse hiçbir kırıklı yol onu yenemez; çünkü iki nokta arasındaki en kısa euklidyen yol düz parçadır.
Aksi durumda bütün görünür kontur çifti adayları arasında minimum alınır.
Program birkaç zorunlu koşulu doğrular:
1. \(f_*\), uç nokta yüksekliklerinden küçük olamaz,
2. kontur boş olamaz,
3. her kontur düğümünün derecesi \(2\) olmalıdır,
4. bulunan yol \(|AB|\)'den kısa olamaz.
Varsayılan parametrelerle uç nokta yükseklikleri yaklaşık olarak
$$ h(A)\approx 7851.540,\qquad h(B)\approx 6964.696 $$
çıkar.
\(AB\) doğru parçası ise
$$ 13275 $$
seviyesinin üzerine kadar çıktığı için optimal tavanda geçerli değildir.
Program --verbose ile çalıştırıldığında
$$ f_*\approx 10396.458664 $$
raporlanır; varsayılan ayrıklaştırmada yazdırdığı rota uzunluğu ise
$$ 2531.205 $$
olur. Bunlar kapalı form değil, kodun sayısal çıktılarıdır.
compute_heights yükseklik alanını grid üzerinde örnekler; uygun olursa paralel çalışır. Ardından minimax_height öncelik kuyruğu tabanlı minimax aramayı yapar ve ayrık geçit yüksekliğini verir.
Sonra kod, \(f_*\)'ün üstündeki noktaları yasak bölge olarak işaretler, marching squares ile kontur segmentlerini çıkarır, uçları kuantize eder, bir komşuluk grafiği kurar, buradan kapalı döngüler yürür, en büyük döngüyü seçer ve yay uzunluğu prefix toplamlarını hesaplar.
Daha sonra \(A\) ve \(B\)'den görülebilen kontur noktalarını bulur, doğrudan \(AB\)'yi dener ve son olarak bütün görünür çiftler için
$$ |AP_i|+\min\bigl(s_{ij},L-s_{ij}\bigr)+|P_jB| $$
formülünü tarar. Minimum değer üç ondalıkla yazdırılır.
Bir eksende \(n\) adet grid noktası varsa yükseklik örnekleme \(O(n^2)\), minimax Dijkstra \(O(n^2\log n)\), kontur çıkarımı \(O(n^2)\) maliyetlidir.
Görünürlük ve son tarama maliyeti ise
$$ O(|V_A||V_B|) $$
artı doğru parçalar üzerindeki örnekleme işidir.
Bellek kullanımı esas olarak örneklenmiş yükseklik alanından gelir ve \(O(n^2)\)'dir.
Esas değiş tokuş numeriktir: grid-step ve vis-step küçüldükçe sürekli probleme yaklaşım iyileşir, fakat zaman ve bellek maliyeti artar.
La montaña está dada por la función de altura
$$ h(x,y)=\Bigl(5000-0.005(x^2+y^2+xy)+12.5(x+y)\Bigr)e^{-\left|10^{-6}(x^2+y^2)-0.0015(x+y)+0.7\right|}. $$
Debemos ir desde
$$ A=(200,200)\qquad\text{hasta}\qquad B=(1400,1400) $$
sin superar nunca la menor altura de paso posible. Entre todas las rutas que respetan ese techo, queremos la más corta.
El programa, por tanto, resuelve dos tareas:
1. hallar la altura mínima de paso,
2. bajo ese techo, hallar la ruta más corta.
Para cualquier ruta continua \(\gamma\) de \(A\) a \(B\), definimos
$$ C(\gamma)=\max_{p\in\gamma}h(p). $$
La menor altura de paso es entonces
$$ f_*=\min_{\gamma:A\to B} C(\gamma). $$
Esto no minimiza todavía la longitud euclídea; minimiza solo la altura máxima tocada por la ruta.
El código muestrea el cuadrado
$$ [0,1600]\times[0,1600] $$
con paso grid-step. Con el valor por defecto grid-step = 1.0, hay
$$ n=1601 $$
puntos por eje.
En cada punto \((i\Delta,j\Delta)\) se evalúa
$$ h(i\Delta,j\Delta). $$
Así, el relieve continuo se sustituye por un grafo finito con vecindad de cuatro direcciones.
Para un camino de malla
$$ v_0,v_1,\dots,v_t, $$
el coste es
$$ \max\bigl(h(v_0),h(v_1),\dots,h(v_t)\bigr). $$
Si el mejor techo actual en un vértice es \(c\), entonces al extender hacia un vecino \(u\) el nuevo techo es
$$ c'=\max(c,h(u)). $$
Como esta actualización es monótona, la lógica de Dijkstra sigue funcionando: al extraer un vértice con el menor techo conocido, ese techo ya es óptimo.
La relajación implementada es
$$ \text{best}[u]\leftarrow \min\bigl(\text{best}[u],\max(\text{best}[v],h(u))\bigr). $$
Una vez hallado \(f_*\), se define la región prohibida
$$ \Omega=\{(x,y):h(x,y)>f_*\} $$
y la región permitida
$$ F=\{(x,y):h(x,y)\le f_*\}. $$
Toda ruta válida debe quedarse en \(F\). La frontera crítica es
$$ \partial\Omega=\{(x,y):h(x,y)=f_*\}. $$
En el plano euclídeo con un obstáculo, una ruta mínima tiene estructura estándar:
1. en la zona libre va recta,
2. si el obstáculo bloquea la recta, la ruta toca la frontera,
3. mientras está forzada, sigue la frontera, y luego vuelve a salir en línea recta.
Por eso basta considerar:
1. el segmento directo \(AB\), si es admisible,
2. un segmento \(A\to P_i\), luego un arco del contorno, luego un segmento \(P_j\to B\).
El programa marca cada muestra de la malla como interior de la región prohibida cuando
$$ h(i\Delta,j\Delta)>f_*. $$
Cada celda tiene cuatro esquinas, así que hay \(16\) patrones posibles. Las tablas kCaseCount y kCaseEdges codifican esos \(16\) casos de marching squares.
Si una arista de la celda cruza el nivel, el punto de intersección se aproxima por interpolación lineal:
$$ t=\frac{f_*-h_1}{h_2-h_1},\qquad P(t)=P_1+t(P_2-P_1). $$
Los extremos interpolados están en coma flotante, así que el código los cuantiza con escala
$$ 10^6 $$
para fusionar puntos casi coincidentes.
Luego construye un grafo de adyacencia. En un contorno cerrado ideal, cada nodo debe tener grado \(2\), y el programa lo comprueba explícitamente.
Después recorre ese grafo para reconstruir lazos cerrados. Si aparecen varios, conserva el de perímetro mayor, como aproximación al contorno exterior principal.
Si el lazo elegido es
$$ P_0,P_1,\dots,P_{m-1}, $$
el código construye sumas prefijas
$$ S_0=0,\qquad S_{i+1}=S_i+|P_iP_{i+1}|. $$
El perímetro total es
$$ L=S_m. $$
Para dos vértices \(P_i\) y \(P_j\), las dos longitudes posibles a lo largo del contorno son
$$ s_{ij}=|S_j-S_i| $$
y
$$ L-s_{ij}. $$
Un punto del contorno \(P_i\) solo sirve si el segmento recto desde \(A\) hasta \(P_i\) permanece bajo el techo \(f_*\). La función visible lo decide por muestreo a lo largo del segmento con paso vis-step.
Si aparece una muestra con
$$ h(x,y)>f_*+10^{-10}, $$
la visibilidad se rechaza.
Para cada par visible \((P_i,P_j)\), la longitud candidata es
$$ |AP_i|+\min\bigl(s_{ij},L-s_{ij}\bigr)+|P_jB|. $$
El segmento directo \(AB\) también se prueba primero. Si es visible bajo \(f_*\), entonces ya es óptimo, porque ninguna otra curva puede ser más corta que la recta entre dos puntos.
El código verifica que:
1. \(f_*\) no quede por debajo de las alturas de \(A\) o \(B\),
2. el contorno no sea vacío,
3. cada nodo del contorno tenga grado \(2\),
4. la ruta final no sea más corta que la distancia recta \(|AB|\).
Con los parámetros por defecto se obtiene aproximadamente
$$ h(A)\approx 7851.540,\qquad h(B)\approx 6964.696, $$
mientras que la recta \(AB\) sube por encima de
$$ 13275. $$
Con --verbose, el programa informa
$$ f_*\approx 10396.458664, $$
y con la discretización por defecto imprime
$$ 2531.205. $$
compute_heights evalúa la superficie en la malla. Después, minimax_height ejecuta la búsqueda minimax con cola de prioridad.
Luego el programa marca el interior prohibido, extrae el contorno con marching squares, cuantiza los extremos de segmento, forma un grafo de adyacencia, recupera lazos cerrados, elige el mayor y construye longitudes prefijas de arco.
Por último prueba la visibilidad desde \(A\) y \(B\), evalúa el segmento directo \(AB\) y recorre todos los pares visibles con la fórmula
$$ |AP_i|+\min\bigl(s_{ij},L-s_{ij}\bigr)+|P_jB|. $$
Si la malla tiene \(n\) puntos por eje, el muestreo de alturas cuesta \(O(n^2)\), el Dijkstra minimax cuesta \(O(n^2\log n)\), la extracción del contorno cuesta \(O(n^2)\) y el barrido final cuesta \(O(|V_A||V_B|)\), más el coste del muestreo de visibilidad.
La memoria es \(O(n^2)\), dominada por el campo de alturas muestreado.
山体由高度函数
$$ h(x,y)=\Bigl(5000-0.005(x^2+y^2+xy)+12.5(x+y)\Bigr)e^{-\left|10^{-6}(x^2+y^2)-0.0015(x+y)+0.7\right|}. $$
给出。我们要从
$$ A=(200,200)\qquad\text{到}\qquad B=(1400,1400) $$
找到一条合法路线。所谓合法，是指整条路线都不能超过“能通过的最低山口高度”。在所有满足这个高度上限的路线里，再取最短的一条。
所以程序实际上分两步：
1. 先求最小可行高度上限，
2. 再在这个上限下求最短路径。
对任意从 \(A\) 到 \(B\) 的连续路径 \(\gamma\)，定义它的高度代价
$$ C(\gamma)=\max_{p\in\gamma}h(p). $$
最小山口高度就是
$$ f_*=\min_{\gamma:A\to B} C(\gamma). $$
这一步不是在最小化欧氏长度，而是在最小化路径碰到的最高海拔，也就是一个 bottleneck / minimax 路径问题。
代码把区域
$$ [0,1600]\times[0,1600] $$
按步长 grid-step 采样。默认 grid-step = 1.0 时，每条轴上共有
$$ n=1601 $$
个网格点。
在每个采样点 \((i\Delta,j\Delta)\) 上，程序计算
$$ h(i\Delta,j\Delta). $$
这样连续地形就变成了一个有限图：顶点是网格点，边只连接四个轴向邻居。
对于网格路径
$$ v_0,v_1,\dots,v_t, $$
离散代价定义为
$$ \max\bigl(h(v_0),h(v_1),\dots,h(v_t)\bigr). $$
如果当前某点的最好上限是 \(c\)，再走到相邻点 \(u\) 时，新上限就是
$$ c'=\max(c,h(u)). $$
这个更新是单调的：路径延长后，所需高度上限只会不变或变大，不可能变小。因此 Dijkstra 的“最先弹出的最优”逻辑仍然成立。
代码中的松弛规则就是
$$ \text{best}[u]\leftarrow \min\bigl(\text{best}[u],\max(\text{best}[v],h(u))\bigr). $$
得到 \(f_*\) 之后，定义禁区
$$ \Omega=\{(x,y):h(x,y)>f_*\}, $$
可行区域则是
$$ F=\{(x,y):h(x,y)\le f_*\}. $$
所有合法路径都必须完全位于 \(F\) 内，因此第二阶段其实是在平面上绕开障碍 \(\Omega\) 的最短路问题。其关键边界就是
$$ \partial\Omega=\{(x,y):h(x,y)=f_*\}. $$
平面上绕开单个障碍的最短路具有标准结构：
1. 在自由区域内部，路径应当是直线段，
2. 如果直线被障碍挡住，路径就会接触障碍边界，
3. 被障碍约束的部分沿边界走，然后再离开边界继续走直线。
因此只需要考虑两类候选：
1. 直接线段 \(AB\)，如果它在高度上可行，
2. 从 \(A\) 到某个可见边界点 \(P_i\)，沿边界走一段弧，再从另一个可见边界点 \(P_j\) 到 \(B\)。
网格点一旦知道是高于还是低于 \(f_*\)，每个网格小方格就对应 4 个角的上下模式，共有 \(16\) 种情况。kCaseCount 与 kCaseEdges 两张表正是 marching squares 的 \(16\) 种查表规则。
若某条边跨过等高线，则交点用线性插值近似：
$$ t=\frac{f_*-h_1}{h_2-h_1},\qquad P(t)=P_1+t(P_2-P_1). $$
把所有单元格扫过后，就得到 \(h=f_*\) 的折线近似。
插值端点是浮点数，本来应该相连的点可能因为舍入误差而略有偏差。为了解决这个问题，代码用尺度
$$ 10^6 $$
把点量化成整数键，从而把几乎相同的点并在一起。
随后程序建立邻接表。理想的闭合轮廓中，每个节点都应有度 \(2\)，代码也明确检查这一点。
接着它沿邻接图走出闭环。如果由于数值原因出现多个环，就保留周长最大的那一个，把它视为主要障碍边界。
设选中的环为
$$ P_0,P_1,\dots,P_{m-1}. $$
代码建立前缀长度
$$ S_0=0,\qquad S_{i+1}=S_i+|P_iP_{i+1}|. $$
总周长就是
$$ L=S_m. $$
两个点 \(P_i,P_j\) 之间顺时针/逆时针两条弧的长度分别是
$$ s_{ij}=|S_j-S_i| $$
和
$$ L-s_{ij}. $$
轮廓点 \(P_i\) 只有在直线段 \(AP_i\) 全程不超过 \(f_*\) 时，才对 \(A\) 可见。代码并不解析求交，而是在该线段上按 vis-step 进行采样。
只要某个采样点满足
$$ h(x,y)>f_*+10^{-10}, $$
这条可见性线段就被拒绝。
对每个可见点对 \((P_i,P_j)\)，候选路径长度为
$$ |AP_i|+\min\bigl(s_{ij},L-s_{ij}\bigr)+|P_jB|. $$
代码还会先检查直线 \(AB\)。如果 \(AB\) 在高度上可见，那么它必然最优，因为两点间欧氏最短就是直线。
程序会验证：
1. \(f_*\) 不能低于 \(A\) 或 \(B\) 的高度，
2. 轮廓不能为空，
3. 每个轮廓节点的度必须为 \(2\)，
4. 最终路径不能短于 \(|AB|\)。
默认参数下，端点高度大约是
$$ h(A)\approx 7851.540,\qquad h(B)\approx 6964.696. $$
直线 \(AB\) 会升到
$$ 13275 $$
以上，因此在最优上限下不可行。程序在 --verbose 模式下给出
$$ f_*\approx 10396.458664, $$
默认离散参数下最终长度输出为
$$ 2531.205. $$
compute_heights 先在网格上计算高度场；minimax_height 再用优先队列完成 minimax 搜索，得到离散山口高度 \(f_*\)。
之后程序标记禁区，用 marching squares 提取轮廓，量化端点并建立邻接图，恢复闭环，选择最大环，建立前缀弧长，再检查从 \(A\)、\(B\) 可见的轮廓点，并用
$$ |AP_i|+\min\bigl(s_{ij},L-s_{ij}\bigr)+|P_jB| $$
扫描所有候选。
若每条轴上有 \(n\) 个网格点，则高度采样是 \(O(n^2)\)，minimax Dijkstra 是 \(O(n^2\log n)\)，轮廓提取是 \(O(n^2)\)，最后的可见点对扫描是 \(O(|V_A||V_B|)\)，外加线段采样的成本。
内存主要由高度场占据，因此是 \(O(n^2)\)。
Рельеф задается функцией высоты
$$ h(x,y)=\Bigl(5000-0.005(x^2+y^2+xy)+12.5(x+y)\Bigr)e^{-\left|10^{-6}(x^2+y^2)-0.0015(x+y)+0.7\right|}. $$
Нужно пройти из
$$ A=(200,200)\qquad\text{в}\qquad B=(1400,1400), $$
никогда не поднимаясь выше минимально возможной высоты перевала. Среди всех маршрутов, удовлетворяющих этому ограничению, требуется самый короткий.
Поэтому программа решает две задачи:
1. находит минимальный допустимый потолок по высоте,
2. при этом потолке находит кратчайший маршрут.
Для любого непрерывного пути \(\gamma\) от \(A\) к \(B\) введем стоимость
$$ C(\gamma)=\max_{p\in\gamma} h(p). $$
Тогда минимально возможная высота перевала равна
$$ f_*=\min_{\gamma:A\to B} C(\gamma). $$
Это еще не кратчайший путь в евклидовом смысле, а bottleneck / minimax-задача: минимизируется максимальная достигнутая высота.
Код семплирует квадрат
$$ [0,1600]\times[0,1600] $$
регулярной сеткой с шагом grid-step. При стандартном значении grid-step = 1.0 это дает
$$ n=1601 $$
узлов по каждой оси.
В каждом узле \((i\Delta,j\Delta)\) вычисляется
$$ h(i\Delta,j\Delta). $$
Так непрерывная поверхность превращается в конечный граф с четырехсоседней связностью.
Для сеточного пути
$$ v_0,v_1,\dots,v_t $$
стоимость определяется как
$$ \max\bigl(h(v_0),h(v_1),\dots,h(v_t)\bigr). $$
Если текущий лучший потолок в вершине равен \(c\), то при переходе к соседу \(u\) новый потолок равен
$$ c'=\max(c,h(u)). $$
Это монотонное обновление: продолжение пути не может уменьшить требуемую высоту. Поэтому аргумент корректности Dijkstra сохраняется.
В коде используется релаксация
$$ \text{best}[u]\leftarrow \min\bigl(\text{best}[u],\max(\text{best}[v],h(u))\bigr). $$
После нахождения \(f_*\) определяется запрещенная область
$$ \Omega=\{(x,y):h(x,y)>f_*\}, $$
а разрешенная область равна
$$ F=\{(x,y):h(x,y)\le f_*\}. $$
Любой допустимый маршрут должен целиком лежать в \(F\). Следовательно, вторая часть задачи — это кратчайший евклидов путь в плоскости вне препятствия \(\Omega\). Граница препятствия — уровень
$$ \partial\Omega=\{(x,y):h(x,y)=f_*\}. $$
Кратчайший путь в плоскости при наличии препятствия имеет стандартную структуру:
1. в свободной области он идет по прямой,
2. если прямая заблокирована, путь касается границы препятствия,
3. вдоль препятствия он идет по границе, а затем снова выходит на прямой участок.
Поэтому достаточно рассматривать:
1. прямой отрезок \(AB\), если он допустим,
2. отрезок \(A\to P_i\), затем дугу контура, затем отрезок \(P_j\to B\).
Каждая вершина сетки помечается как внутренняя точка запрещенной области, если
$$ h(i\Delta,j\Delta)>f_*. $$
У каждой ячейки четыре угла, значит существует \(16\) возможных масок. Таблицы kCaseCount и kCaseEdges реализуют эти \(16\) случаев marching squares.
Точка пересечения с уровнем на ребре находится линейной интерполяцией:
$$ t=\frac{f_*-h_1}{h_2-h_1},\qquad P(t)=P_1+t(P_2-P_1). $$
Поскольку концы сегментов получаются вещественными числами, код квантует их с масштабом
$$ 10^6, $$
чтобы почти совпадающие точки слипались в один целочисленный ключ.
Затем строится граф смежности. Для корректного замкнутого контура каждая вершина должна иметь степень \(2\); программа это проверяет.
Далее граф обходится для восстановления замкнутых циклов. Если циклов несколько, выбирается цикл с наибольшим периметром как основная внешняя граница препятствия.
Пусть выбранный цикл равен
$$ P_0,P_1,\dots,P_{m-1}. $$
Код строит префиксные суммы
$$ S_0=0,\qquad S_{i+1}=S_i+|P_iP_{i+1}|. $$
Тогда полный периметр равен
$$ L=S_m. $$
Для двух точек \(P_i,P_j\) длины двух направлений по контуру равны
$$ s_{ij}=|S_j-S_i| $$
и
$$ L-s_{ij}. $$
Точка контура \(P_i\) пригодна для \(A\), только если отрезок \(AP_i\) не поднимается выше потолка \(f_*\). Это проверяется дискретным семплированием отрезка с шагом vis-step.
Если в некоторой пробной точке
$$ h(x,y)>f_*+10^{-10}, $$
отрезок считается невидимым.
Для каждого видимого пары \((P_i,P_j)\) программа вычисляет
$$ |AP_i|+\min\bigl(s_{ij},L-s_{ij}\bigr)+|P_jB|. $$
Прямой отрезок \(AB\) также проверяется отдельно. Если он допустим при высоте \(f_*\), то никакой ломаный маршрут не может быть короче.
Код проверяет, что:
1. \(f_*\) не ниже высот концов,
2. контур не пуст,
3. каждая вершина контура имеет степень \(2\),
4. найденный путь не короче \(|AB|\).
При параметрах по умолчанию получаем приблизительно
$$ h(A)\approx 7851.540,\qquad h(B)\approx 6964.696. $$
Прямой отрезок \(AB\) поднимается выше
$$ 13275, $$
поэтому на оптимальном потолке он недопустим. В режиме --verbose программа сообщает
$$ f_*\approx 10396.458664, $$
а при стандартной дискретизации печатает длину
$$ 2531.205. $$
compute_heights вычисляет поле высот на сетке, затем minimax_height выполняет minimax-поиск с приоритетной очередью и возвращает дискретную высоту перевала.
После этого программа маркирует запрещенную область, извлекает контур через marching squares, квантует концы сегментов, строит граф смежности, восстанавливает циклы, выбирает крупнейший цикл, считает префиксные длины дуг, проверяет видимость точек контура из \(A\) и \(B\) и сканирует все допустимые пары по формуле
$$ |AP_i|+\min\bigl(s_{ij},L-s_{ij}\bigr)+|P_jB|. $$
Если на каждой оси \(n\) узлов, то вычисление высот стоит \(O(n^2)\), minimax Dijkstra — \(O(n^2\log n)\), извлечение контура — \(O(n^2)\), а финальный перебор пар — \(O(|V_A||V_B|)\) плюс стоимость семплирования видимости.
Память равна \(O(n^2)\), так как доминирует таблица высот.
يوصف الجبل بدالة الارتفاع
$$ h(x,y)=\Bigl(5000-0.005(x^2+y^2+xy)+12.5(x+y)\Bigr)e^{-\left|10^{-6}(x^2+y^2)-0.0015(x+y)+0.7\right|}. $$
ونريد الانتقال من \(A=(200,200)\) إلى \(B=(1400,1400)\).
بحيث لا يرتفع المسار أبدًا فوق أصغر ارتفاع ممر ممكن. ومن بين جميع المسارات التي تحترم هذا السقف، نريد الأقصر.
لذلك يعالج البرنامج مسألتين متتاليتين:
1. إيجاد أصغر سقف ارتفاع يسمح بالعبور،
2. ثم إيجاد أقصر مسار تحت هذا السقف.
لكل مسار مستمر \(\gamma\) من \(A\) إلى \(B\)، نعرف كلفة الارتفاع بـ
$$ C(\gamma)=\max_{p\in\gamma}h(p). $$
وعندئذ يكون أصغر ارتفاع ممر ممكن هو
$$ f_*=\min_{\gamma:A\to B} C(\gamma). $$
هذه ليست بعدُ مسألة أقصر مسار إقليدي، بل هي مسألة bottleneck / minimax: نقلل أعلى نقطة يلامسها المسار.
يأخذ الكود المربع
$$ [0,1600]\times[0,1600] $$
ويعينه على شبكة منتظمة بخطوة grid-step. ومع القيمة الافتراضية grid-step = 1.0 نحصل على
$$ n=1601 $$
نقطة على كل محور.
وعند كل نقطة \((i\Delta,j\Delta)\) يحسب البرنامج
$$ h(i\Delta,j\Delta). $$
وهكذا يتحول السطح المستمر إلى مخطط منتهٍ بعلاقات جوار رباعية.
إذا كان لدينا مسار شبكي
$$ v_0,v_1,\dots,v_t, $$
فإن كلفته هي
$$ \max\bigl(h(v_0),h(v_1),\dots,h(v_t)\bigr). $$
إذا كانت أفضل قيمة حالية لعقدة ما هي \(c\)، فإن الانتقال إلى جار \(u\) يعطي
$$ c'=\max(c,h(u)). $$
وهذا تحديث أحادي: توسيع المسار لا يمكن أن يخفض السقف المطلوب. ولهذا تبقى حجة Dijkstra صالحة.
فقاعدة الترخية في الكود هي
$$ \text{best}[u]\leftarrow \min\bigl(\text{best}[u],\max(\text{best}[v],h(u))\bigr). $$
بعد إيجاد \(f_*\)، تُعرّف المنطقة الممنوعة بأنها
$$ \Omega=\{(x,y):h(x,y)>f_*\}, $$
بينما المنطقة المسموحة هي
$$ F=\{(x,y):h(x,y)\le f_*\}. $$
كل مسار صحيح يجب أن يبقى داخل \(F\). إذن المرحلة الثانية هي في الحقيقة مسألة أقصر مسار في المستوى خارج العائق \(\Omega\)، وحد هذا العائق هو منحنى المستوى
$$ \partial\Omega=\{(x,y):h(x,y)=f_*\}. $$
أقصر مسار حول عائق واحد في المستوى يملك بنية معروفة:
1. في المنطقة الحرة يكون مستقيمًا،
2. إذا منع العائق المستقيم المباشر فإنه يلامس الحد،
3. ثم يسير على الحد فترة، وبعدها يغادره بقطعة مستقيمة أخرى.
لذلك يكفي فحص نوعين من المرشحين:
1. القطعة المباشرة \(AB\)، إذا كانت ممكنة،
2. \(A\to P_i\)، ثم قوس على الحد، ثم \(P_j\to B\).
بمجرد معرفة ما إذا كانت كل نقطة شبكية أعلى من \(f_*\) أو أدنى منه، يصبح لكل خلية رباعية \(16\) حالة ممكنة. الجدولان kCaseCount وkCaseEdges يطبقان هذه الحالات الست عشرة لطريقة marching squares.
إذا قطع المنحنى أحد أضلاع الخلية، فإن نقطة القطع تقرب بالاستيفاء الخطي:
$$ t=\frac{f_*-h_1}{h_2-h_1},\qquad P(t)=P_1+t(P_2-P_1). $$
نهايات القطع الناتجة أعداد عائمة، ولمنع الضجيج العددي من تفكيك النقاط المتساوية تقريبًا، يقوم الكود بتكميمها بمقياس
$$ 10^6. $$
بعد ذلك يبني خريطة تجاور. وفي الكونتور المغلق المثالي يجب أن تكون درجة كل عقدة مساوية لـ \(2\)، والكود يتحقق من ذلك صراحة.
ثم يجتاز الرسم الناتج ليعيد بناء الحلقات المغلقة. وإذا ظهرت عدة حلقات بسبب أخطاء عددية، يحتفظ بالحلقة ذات أكبر محيط بوصفها الحد الخارجي الرئيسي.
إذا كانت الحلقة المختارة هي
$$ P_0,P_1,\dots,P_{m-1}, $$
فإن البرنامج يبني مجاميع بادئة
$$ S_0=0,\qquad S_{i+1}=S_i+|P_iP_{i+1}|. $$
ومنها يكون المحيط الكلي
$$ L=S_m. $$
ولأي نقطتين \(P_i,P_j\)، فإن طولي القوسين الممكنين هما
$$ s_{ij}=|S_j-S_i| $$
و
$$ L-s_{ij}. $$
تكون النقطة \(P_i\) صالحة من جهة \(A\) فقط إذا بقيت القطعة المستقيمة \(AP_i\) تحت السقف \(f_*\). لا يحل الكود هذا الشرط تحليليًا، بل يختبره بأخذ عينات على طول القطعة بخطوة vis-step.
إذا ظهرت عينة تحقق
$$ h(x,y)>f_*+10^{-10}, $$
فإن القطعة ترفض.
لكل زوج مرئي \((P_i,P_j)\) يحسب البرنامج
$$ |AP_i|+\min\bigl(s_{ij},L-s_{ij}\bigr)+|P_jB|. $$
كما يفحص القطعة المباشرة \(AB\) أولًا. فإذا كانت مرئية تحت السقف \(f_*\)، فهي بالضرورة الأمثل لأن المستقيم هو أقصر وصلة إقليدية بين نقطتين.
يتحقق الكود من أن:
1. \(f_*\) ليس أدنى من ارتفاعي الطرفين،
2. الكونتور غير فارغ،
3. درجة كل عقدة على الكونتور تساوي \(2\)،
4. المسار النهائي ليس أقصر من \(|AB|\).
وبالقيم الافتراضية نحصل تقريبًا على
$$ h(A)\approx 7851.540,\qquad h(B)\approx 6964.696. $$
أما القطعة \(AB\) نفسها فترتفع إلى ما يزيد على
$$ 13275, $$
ولذلك فهي غير ممكنة عند السقف الأمثل. وفي وضع --verbose يطبع البرنامج
$$ f_*\approx 10396.458664, $$
ومع الإعدادات الافتراضية يعطي طولًا نهائيًا
$$ 2531.205. $$
تحسب compute_heights قيم الارتفاع على الشبكة، ثم تنفذ minimax_height بحث minimax باستعمال طابور أولوية.
بعد ذلك يحدد البرنامج المنطقة الممنوعة، ويستخرج الكونتور بطريقة marching squares، ويكمم نهايات القطع، ويبني مخطط التجاور، ويستعيد الحلقات، ويختار أكبرها، ويحسب الأطوال البادئة للأقواس، ثم يختبر الرؤية من \(A\) و\(B\)، وأخيرًا يمسح جميع الأزواج المرئية وفق الصيغة
$$ |AP_i|+\min\bigl(s_{ij},L-s_{ij}\bigr)+|P_jB|. $$
إذا كان على كل محور \(n\) نقطة شبكية، فإن حساب الارتفاعات يكلف \(O(n^2)\)، بينما يكلف minimax Dijkstra مقدار \(O(n^2\log n)\)، واستخراج الكونتور يكلف \(O(n^2)\)، أما المسح النهائي للأزواج المرئية فيكلف \(O(|V_A||V_B|)\) بالإضافة إلى كلفة أخذ العينات لاختبار الرؤية.
الذاكرة من الرتبة \(O(n^2)\) لأن حقل الارتفاعات هو البنية المسيطرة.