We study equilateral pentagons with side length \(1\) that must move through a right-angled corridor of width \(W\). For such a pentagon let \(A\) be its area, and let \(W\) be the smallest corridor width that still allows a continuous motion from one straight branch of the corridor to the other.
The objective is to maximize
$$\frac{A}{W^2}.$$
This ratio is scale invariant: scaling the pentagon by a factor \(\lambda\) multiplies the area by \(\lambda^2\) and the required corridor width by \(\lambda\). So it is enough to work with unit-edge pentagons and optimize a normalized shape parameter.
The implementation solves the problem numerically but the geometry is highly structured. First it restricts to a symmetric one-parameter family of equilateral pentagons, then it computes the minimal corridor width for each candidate by sampling all orientations and testing whether those orientations form a continuous feasible passage around the corner.
Symmetry about the perpendicular bisector of the first edge lets us place the first four visible vertices as
$$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1+\cos a,\sin a),\qquad v_4=(-\cos a,\sin a).$$
This already guarantees
$$|v_1-v_0|=|v_2-v_1|=|v_0-v_4|=1.$$
The only missing point is \(v_3\), which must satisfy
$$|v_3-v_2|=|v_3-v_4|=1.$$
So the entire symmetric equilateral pentagon is controlled by the single angle parameter \(a\).
The distance between the two circle centers is
$$d=|v_2-v_4|=1+2\cos a.$$
For the two unit circles to intersect we need \(d\le 2\), hence this construction requires
$$a\ge \frac{\pi}{3}.$$
The midpoint of \(v_2v_4\) is \(\left(\frac12,\sin a\right)\), so the two possible intersection points are
$$v_3=\left(\frac12,\sin a \pm \sqrt{1-\frac{d^2}{4}}\right).$$
These are the two mirror candidates examined by the implementation. For each candidate, the area is computed with the shoelace formula
$$A=\frac12\left|\sum_{i=0}^{4}\left(x_i y_{i+1}-x_{i+1} y_i\right)\right|,$$
with indices taken cyclically.
Fix an orientation angle \(\theta\), rotate the pentagon by \(\theta\), and then translate the rotated coordinates so that the minimum \(x\)-coordinate and minimum \(y\)-coordinate are both \(0\). For the translated polygon \(P_\theta\), define
$$w_x(\theta)=x_{\max}-x_{\min},\qquad w_y(\theta)=y_{\max}-y_{\min}.$$
These are the widths needed for the pentagon to fit inside a straight vertical corridor and a straight horizontal corridor of width \(W\), respectively.
The corner constraint is different. In the translated picture, a right-angled corridor of width \(W\) occupies the union of the strips \(x\le W\) and \(y\le W\), so the forbidden region is the upper-right square where both coordinates exceed \(W\). Therefore the pentagon fits at the corner exactly when
$$\max_{p\in P_\theta}\min(p_x,p_y)\le W.$$
This motivates the corner-width functional
$$w(\theta)=\max_{p\in P_\theta}\min(p_x,p_y).$$
Along any edge segment of the polygon, the function \(\min(x,y)\) is piecewise linear. Away from the diagonal \(x=y\), it is simply one coordinate or the other. The only place where the active branch can switch is where the edge crosses the diagonal.
So the maximum value of \(\min(x,y)\) on the polygon boundary is attained either at a vertex or at a point where an edge meets the diagonal \(x=y\).
The implementation uses exactly that fact: for every sampled orientation it checks all shifted vertices and all edge-diagonal intersections, and the largest such value becomes \(w(\theta)\).
For a fixed corridor width \(W\), let
$$S_W=\{\theta\in[0,2\pi): w(\theta)\le W\}.$$
These are the orientations that can be placed at the corner. A continuous passage around the bend requires more than isolated feasible orientations. We need one connected arc of \(S_W\) that contains
an orientation with \(w_y(\theta)\le W\), so the pentagon can lie inside a straight horizontal branch, and
an orientation with \(w_x(\theta)\le W\), so it can lie inside a straight vertical branch.
Because orientation is periodic, the angle domain is a circle. The implementation samples that circle densely, sorts the samples by increasing \(w(\theta)\), activates them in threshold order, and merges neighboring active samples. Each connected component stores the smallest observed \(w_x\) and \(w_y\). The first threshold whose component satisfies both minima is the required motion width for that pentagon.
Take
$$a=\frac{\pi}{2}.$$
Then
$$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1,1),\qquad v_4=(0,1),$$
and the two circle intersections are
$$v_3=\left(\frac12,1\pm\frac{\sqrt3}{2}\right).$$
Using the upper intersection gives a simple pentagon with area
$$A=1+\frac{\sqrt3}{4}\approx 1.4330127.$$
At orientation \(\theta=0\), the polygon is already translated with \(x_{\min}=y_{\min}=0\), so
$$w_x(0)=1,\qquad w_y(0)=1+\frac{\sqrt3}{2},\qquad w(0)=1.$$
This means the pentagon can sit at the corner of a width-\(1\) corridor, because no point has both coordinates larger than \(1\). But it does not fit completely inside a straight horizontal branch of width \(1\), since its vertical span exceeds \(1\). This is exactly why the algorithm tracks all three profiles \(w\), \(w_x\), and \(w_y\).
For each admissible \(a\), the implementation evaluates both mirror candidates, computes the corresponding minimal corridor width \(W(a)\), and keeps the larger value of
$$F(a)=\frac{A(a)}{W(a)^2}.$$
The search is one-dimensional, and within the narrow region containing the best symmetric pentagon the numerical profile is handled efficiently by a golden-section search.
The C++ implementation precomputes a dense table of trigonometric values for equally spaced orientations around the full circle. For each candidate pentagon it rotates the five vertices at every sampled angle, shifts the pose so the lower-left touching position is normalized, and records the three geometric profiles \(w\), \(w_x\), and \(w_y\).
It then sorts the sampled orientations by the corner-width profile \(w\). As the threshold rises, neighboring active samples on the cyclic angle grid are merged with a disjoint-set structure. Each connected component remembers the smallest straight-corridor widths seen so far, so the first component with both \(w_x\le W\) and \(w_y\le W\) determines the motion width.
At the outer level, the implementation performs a golden-section search over the single angle parameter and evaluates both circle-intersection branches at each step. The final candidate is checked numerically to confirm that all five edges still have unit length and that the pentagon is simple. The Python and Java implementations delegate to the same compiled numerical core and return the parsed numeric result.
Let \(N_\theta\) be the number of sampled orientations. For one pentagon, computing all rotated poses and the three width profiles costs \(O(N_\theta)\) geometric work because the polygon has only five vertices and five edges. Sorting the orientations by \(w\) costs
$$O(N_\theta\log N_\theta),$$
and the connectivity sweep with a disjoint-set structure is effectively linear, \(O(N_\theta \alpha(N_\theta))\).
So one motion-width evaluation is dominated by \(O(N_\theta\log N_\theta)\) time and \(O(N_\theta)\) memory. If the outer search uses \(T\) objective evaluations, the total cost is
$$O(T\,N_\theta\log N_\theta).$$
The C++ version parallelizes the per-angle geometry across hardware threads, which improves wall-clock time but does not change the asymptotic bound.
Betrachtet werden gleichseitige Fünfecke mit Seitenlänge \(1\), die durch einen rechtwinkligen Korridor der Breite \(W\) bewegt werden müssen. Für ein solches Fünfeck sei \(A\) seine Fläche und \(W\) die kleinste Korridorbreite, die noch eine stetige Bewegung von einem geraden Korridorarm in den anderen erlaubt.
Zu maximieren ist
$$\frac{A}{W^2}.$$
Dieser Quotient ist skaleninvariant: Bei einer Skalierung mit Faktor \(\lambda\) wächst die Fläche mit \(\lambda^2\), die notwendige Korridorbreite aber nur mit \(\lambda\). Daher genügt es, Einheitskanten anzunehmen und nur eine normierte Form zu optimieren.
Die Lösung ist numerisch, aber die zugrunde liegende Geometrie ist stark strukturiert. Zuerst wird das Problem auf eine symmetrische einparametrige Familie gleichseitiger Fünfecke reduziert. Danach wird für jedes Kandidatenfünfeck die minimale Korridorbreite über alle Rotationen bestimmt.
Durch Symmetrie bezüglich der Mittelsenkrechten der ersten Kante können wir die ersten sichtbaren Eckpunkte so wählen:
$$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1+\cos a,\sin a),\qquad v_4=(-\cos a,\sin a).$$
Damit gilt bereits
$$|v_1-v_0|=|v_2-v_1|=|v_0-v_4|=1.$$
Es fehlt nur noch \(v_3\), und dieser Punkt muss die Bedingungen
$$|v_3-v_2|=|v_3-v_4|=1$$
erfüllen. Somit wird das gesamte symmetrische gleichseitige Fünfeck durch einen einzigen Winkel \(a\) beschrieben.
Der Abstand der Kreismittelpunkte ist
$$d=|v_2-v_4|=1+2\cos a.$$
Damit sich zwei Einheitskreise schneiden, muss \(d\le 2\) gelten, also
$$a\ge \frac{\pi}{3}.$$
Der Mittelpunkt von \(v_2v_4\) ist \(\left(\frac12,\sin a\right)\), daher lauten die beiden möglichen Schnittpunkte
$$v_3=\left(\frac12,\sin a \pm \sqrt{1-\frac{d^2}{4}}\right).$$
Genau diese beiden Spiegelkandidaten testet die Implementierung. Für jeden Kandidaten wird die Fläche mit der Shoelace-Formel berechnet:
$$A=\frac12\left|\sum_{i=0}^{4}\left(x_i y_{i+1}-x_{i+1} y_i\right)\right|,$$
wobei zyklisch indiziert wird.
Fixiere einen Rotationswinkel \(\theta\), rotiere das Fünfeck und verschiebe die rotierten Koordinaten anschließend so, dass das kleinste \(x\) und das kleinste \(y\) beide gleich \(0\) sind. Für das so normierte Polygon \(P_\theta\) definieren wir
$$w_x(\theta)=x_{\max}-x_{\min},\qquad w_y(\theta)=y_{\max}-y_{\min}.$$
Diese beiden Größen sind genau die Breiten, die das Fünfeck benötigt, um vollständig in einen geraden vertikalen beziehungsweise horizontalen Korridorarm der Breite \(W\) zu passen.
Die Eckensituation ist subtiler. Im normierten Bild belegt ein rechtwinkliger Korridor der Breite \(W\) die Vereinigung der beiden Halbstreifen \(x\le W\) und \(y\le W\). Verboten ist also nur das obere rechte Quadrat, in dem beide Koordinaten größer als \(W\) sind. Deshalb passt das Fünfeck genau dann um die Ecke, wenn
$$\max_{p\in P_\theta}\min(p_x,p_y)\le W.$$
Dies motiviert die Eckbreitenfunktion
$$w(\theta)=\max_{p\in P_\theta}\min(p_x,p_y).$$
Entlang einer Polygonkante ist die Funktion \(\min(x,y)\) stückweise linear. Abseits der Diagonale \(x=y\) ist sie einfach eine der beiden Koordinaten. Nur beim Schnitt mit der Diagonale kann sich der aktive Zweig ändern.
Daher wird das Maximum von \(\min(x,y)\) auf dem Rand entweder an einem Eckpunkt oder an einem Schnittpunkt einer Kante mit der Diagonalen \(x=y\) angenommen.
angenommen. Genau das nutzt die Implementierung: Für jede abgetastete Orientierung werden alle verschobenen Eckpunkte und alle Diagonalschnitte der Kanten geprüft, und das größte gefundene Ergebnis ist \(w(\theta)\).
Für eine feste Korridorbreite \(W\) sei
$$S_W=\{\theta\in[0,2\pi): w(\theta)\le W\}.$$
Das sind die Orientierungen, die an der Ecke überhaupt möglich sind. Für eine stetige Passage reicht es aber nicht, einzelne zulässige Winkel zu haben. Benötigt wird ein zusammenhängender Bogen in \(S_W\), der sowohl
eine Orientierung mit \(w_y(\theta)\le W\) enthält, sodass das Fünfeck vollständig in einem horizontalen Korridorarm liegen kann, als auch
eine Orientierung mit \(w_x(\theta)\le W\), sodass es vollständig in einem vertikalen Korridorarm liegen kann.
Da Orientierungen periodisch sind, ist der Winkelraum ein Kreis. Die Implementierung tastet ihn dicht ab, sortiert die Stichproben nach wachsendem \(w(\theta)\), aktiviert sie in dieser Reihenfolge und vereinigt benachbarte aktive Stichproben. Zu jeder Zusammenhangskomponente werden das kleinste beobachtete \(w_x\) und \(w_y\) gespeichert. Der erste Schwellenwert, bei dem eine Komponente beide Bedingungen erfüllt, ist die gesuchte Bewegungsbreite des Fünfecks.
Setze
$$a=\frac{\pi}{2}.$$
Dann gilt
$$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1,1),\qquad v_4=(0,1),$$
und die beiden Kreisschnittpunkte sind
$$v_3=\left(\frac12,1\pm\frac{\sqrt3}{2}\right).$$
Nimmt man den oberen Schnittpunkt, erhält man ein einfaches Fünfeck mit Fläche
$$A=1+\frac{\sqrt3}{4}\approx 1.4330127.$$
Für die Orientierung \(\theta=0\) ist das Polygon bereits so platziert, dass \(x_{\min}=y_{\min}=0\) gilt. Damit erhält man
$$w_x(0)=1,\qquad w_y(0)=1+\frac{\sqrt3}{2},\qquad w(0)=1.$$
Das Fünfeck kann also an einer Ecke eines Korridors der Breite \(1\) liegen, denn kein Punkt hat gleichzeitig beide Koordinaten größer als \(1\). Es passt aber noch nicht vollständig in einen geraden horizontalen Arm der Breite \(1\), weil seine vertikale Spannweite größer als \(1\) ist. Genau deshalb braucht der Algorithmus alle drei Profile \(w\), \(w_x\) und \(w_y\).
Für jedes zulässige \(a\) werden beide Spiegelkandidaten ausgewertet, die zugehörige minimale Korridorbreite \(W(a)\) bestimmt und anschließend der größere Wert von
$$F(a)=\frac{A(a)}{W(a)^2}$$
verwendet. Da die Suche eindimensional ist und das interessante Intervall numerisch gutmütig behandelt werden kann, eignet sich eine Goldener-Schnitt-Suche sehr gut zur Verfeinerung des optimalen Winkels.
Die C++-Implementierung berechnet zunächst eine dichte Tabelle trigonometrischer Werte für gleichmäßig verteilte Orientierungen auf dem gesamten Winkelkreis. Für jedes Kandidatenfünfeck werden die fünf Eckpunkte für jeden dieser Winkel rotiert, in eine normierte Berührlage verschoben und anschließend die drei Profile \(w\), \(w_x\) und \(w_y\) gespeichert.
Danach werden die Orientierungen nach dem Eckprofil \(w\) sortiert. Wenn der Schwellenwert wächst, werden benachbarte aktive Stichproben auf dem zyklischen Winkelgitter per Disjoint-Set-Struktur zusammengeführt. Jede Zusammenhangskomponente speichert die kleinsten bisher gesehenen Geradkorridor-Breiten. Sobald eine Komponente gleichzeitig \(w_x\le W\) und \(w_y\le W\) besitzt, ist die Bewegungsbreite gefunden.
Auf der äußeren Ebene führt die Implementierung eine Goldener-Schnitt-Suche über den einen Winkelparameter aus und prüft pro Kandidatenwinkel beide Kreisschnitt-Varianten. Am Ende wird numerisch kontrolliert, dass alle fünf Kanten tatsächlich Einheitslänge haben und dass das gewählte Fünfeck einfach ist. Die Python- und Java-Implementierungen delegieren an denselben kompilierten numerischen Kern und liefern nur das geparste numerische Ergebnis zurück.
Sei \(N_\theta\) die Anzahl der abgetasteten Orientierungen. Für ein einzelnes Fünfeck kostet die Berechnung aller rotierten Lagen und der drei Breitenprofile \(O(N_\theta)\), weil das Polygon nur fünf Ecken und fünf Kanten besitzt. Das Sortieren nach \(w\) benötigt
$$O(N_\theta\log N_\theta),$$
und die Zusammenhangssuche mit der Disjoint-Set-Struktur ist praktisch linear, also \(O(N_\theta \alpha(N_\theta))\).
Damit wird eine einzelne Bewegungsbreiten-Auswertung von \(O(N_\theta\log N_\theta)\) Zeit und \(O(N_\theta)\) Speicher dominiert. Verwendet die äußere Suche \(T\) Zielfunktionsauswertungen, ergibt sich insgesamt
$$O(T\,N_\theta\log N_\theta).$$
Die C++-Version verteilt die Geometrie pro Winkel auf mehrere Hardware-Threads; das verbessert die Laufzeit in der Praxis, ändert aber nicht die asymptotische Ordnung.
Burada incelenen nesneler, kenar uzunluğu \(1\) olan eşkenar beşgenlerdir. Her beşgenin, genişliği \(W\) olan dik açılı bir koridorda bir düz koldan diğerine sürekli olarak taşınabildiğini varsayıyoruz. \(A\) beşgenin alanı, \(W\) ise bu hareketi mümkün kılan en küçük koridor genişliğidir.
Maksimize edilmek istenen nicelik
$$\frac{A}{W^2}$$
oranıdır. Bu oran ölçekten bağımsızdır: şekil \(\lambda\) kat büyütülürse alan \(\lambda^2\) ile, gerekli koridor genişliği ise \(\lambda\) ile çarpılır. Bu yüzden kenarları \(1\) kabul etmek genel çözümü daraltmaz.
Çözüm sayısal olsa da geometri oldukça düzenlidir. Önce problem, simetrik ve tek parametreli bir eşkenar beşgen ailesine indirgenir. Sonra her aday için tüm yönelimler taranarak o şeklin dönebileceği en küçük koridor genişliği hesaplanır.
İlk kenarın orta dikmesine göre simetri kullanılarak köşeler şöyle yerleştirilebilir:
$$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1+\cos a,\sin a),\qquad v_4=(-\cos a,\sin a).$$
Böylece şimdiden
$$|v_1-v_0|=|v_2-v_1|=|v_0-v_4|=1$$
elde edilir. Geriye yalnızca \(v_3\) kalır ve bu noktanın
$$|v_3-v_2|=|v_3-v_4|=1$$
koşullarını sağlaması gerekir. Dolayısıyla tüm simetrik eşkenar beşgen tek bir açı parametresi \(a\) ile kontrol edilir.
İki merkez arasındaki uzaklık
$$d=|v_2-v_4|=1+2\cos a$$
olur. İki birim çemberin kesişebilmesi için \(d\le 2\) gerektiğinden
$$a\ge \frac{\pi}{3}$$
zorunludur. \(v_2v_4\) doğru parçasının orta noktası \(\left(\frac12,\sin a\right)\) olduğundan iki olası kesişim noktası
$$v_3=\left(\frac12,\sin a \pm \sqrt{1-\frac{d^2}{4}}\right)$$
şeklindedir. Uygulama bu iki ayna adayını da dener. Her adayın alanı da shoelace formülüyle hesaplanır:
$$A=\frac12\left|\sum_{i=0}^{4}\left(x_i y_{i+1}-x_{i+1} y_i\right)\right|,$$
burada indisler çevrimsel alınır.
Sabit bir \(\theta\) yönelimi seçelim. Beşgen \(\theta\) kadar döndürülür ve sonra döndürülmüş koordinatlar, en küçük \(x\) ve en küçük \(y\) değeri \(0\) olacak şekilde ötelenir. Bu normalize edilmiş \(P_\theta\) çokgeni için
$$w_x(\theta)=x_{\max}-x_{\min},\qquad w_y(\theta)=y_{\max}-y_{\min}$$
tanımlarını yaparız. Bunlar, şeklin genişliği \(W\) olan dikey ve yatay düz koridor kollarına sığması için gereken yatay ve düşey açıklıklardır.
Köşe kısıtı farklıdır. Normalize edilmiş resimde genişliği \(W\) olan dik açılı koridor, \(x\le W\) ve \(y\le W\) şeritlerinin birleşimidir. Dolayısıyla yasak bölge, her iki koordinatın da \(W\)'den büyük olduğu sağ üst karedir. Beşgen köşeden geçebiliyorsa
$$\max_{p\in P_\theta}\min(p_x,p_y)\le W$$
olmalıdır. Bu nedenle köşe-genişliği fonksiyonunu
$$w(\theta)=\max_{p\in P_\theta}\min(p_x,p_y)$$
olarak tanımlarız.
Bir kenar üzerinde \(\min(x,y)\) fonksiyonu parçalı doğrusaldır. \(x=y\) doğrusundan uzakta bu fonksiyon yalnızca \(x\) ya da yalnızca \(y\) olur. Aktif dalın değişebileceği tek yer, kenarın bu diyagonal ile kesiştiği noktadır.
Bu yüzden \(\min(x,y)\) değerinin sınır üzerindeki maksimumu ancak bir köşede ya da bir kenarın \(x=y\) doğrusu ile kesişiminde oluşabilir.
oluşabilir. Uygulama da tam olarak bunu yapar: her örnek yönelimde tüm ötelenmiş köşeleri ve tüm diyagonal kesişimlerini kontrol eder; bulunan en büyük değer \(w(\theta)\) olur.
Sabit bir koridor genişliği \(W\) için
$$S_W=\{\theta\in[0,2\pi): w(\theta)\le W\}$$
olsun. Bunlar köşede durabilen yönelimlerdir. Ancak yalnızca tek tek uygun açılar yeterli değildir. Yatay koldan dikey kola sürekli geçiş için \(S_W\) içinde aynı bağlı yay üzerinde hem
\(w_y(\theta)\le W\) sağlayan, yani yatay düz kola sığabilen bir yönelim, hem de
\(w_x(\theta)\le W\) sağlayan, yani dikey düz kola sığabilen bir yönelim
bulunmalıdır.
Yönelim uzayı çevrimseldir; yani açı ekseni bir çemberdir. Uygulama bu çemberi çok sık örnekler, örnekleri artan \(w(\theta)\) sırasına göre aktive eder ve komşu aktif örnekleri birleştirir. Her bağlı bileşen için görülen en küçük \(w_x\) ve \(w_y\) değerleri tutulur. Bu iki minimumu aynı anda sağlayan ilk eşik, beşgenin gerekli hareket genişliğini verir.
Şimdi
$$a=\frac{\pi}{2}$$
alalım. O zaman
$$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1,1),\qquad v_4=(0,1)$$
olur ve iki kesişim noktası
$$v_3=\left(\frac12,1\pm\frac{\sqrt3}{2}\right)$$
şeklindedir. Üstteki kesişimi seçersek basit bir beşgen elde ederiz ve alan
$$A=1+\frac{\sqrt3}{4}\approx 1.4330127$$
çıkar. \(\theta=0\) yöneliminde çokgen zaten \(x_{\min}=y_{\min}=0\) olacak biçimdedir, dolayısıyla
$$w_x(0)=1,\qquad w_y(0)=1+\frac{\sqrt3}{2},\qquad w(0)=1$$
olur. Yani bu poz, genişliği \(1\) olan bir koridor köşesinde bulunabilir; çünkü hiçbir noktada hem \(x\) hem \(y\) aynı anda \(1\)'den büyük değildir. Fakat düşey boyu \(1\)'den büyük olduğu için aynı genişlikte yatay düz kola tamamen sığmaz. Bu örnek, neden yalnızca \(w\)'yi değil \(w_x\) ve \(w_y\)'yi de izlemek gerektiğini açıkça gösterir.
Her uygun \(a\) değeri için iki ayna adayı da değerlendirilir, karşılık gelen en küçük koridor genişliği \(W(a)\) bulunur ve
$$F(a)=\frac{A(a)}{W(a)^2}$$
değerlerinden büyük olanı alınır. Arama tek boyutludur ve en iyi simetrik beşgeni içeren dar aralıkta altın oran araması verimli bir sayısal rafinman sağlar.
C++ uygulaması önce tam açı çemberini sık aralıklarla örnekleyen trigonometrik bir tablo hazırlar. Her aday beşgen için beş köşe her örnek açıda döndürülür, poz alt-sol temas durumuna ötelenir ve böylece \(w\), \(w_x\) ve \(w_y\) profilleri çıkarılır.
Daha sonra örnek yönelimler köşe-genişliği profili \(w\)'ye göre sıralanır. Eşik büyürken, açısal ızgarada komşu olan aktif örnekler bir ayrık-küme yapısı ile birleştirilir. Her bağlı bileşen, şimdiye kadar görülen en küçük düz-koridor açıklıklarını saklar. Aynı bileşen hem \(w_x\le W\) hem de \(w_y\le W\) koşulunu ilk kez sağladığında, aranan hareket genişliği bulunmuş olur.
Dış döngüde uygulama, tek açı parametresi üzerinde altın oran araması yapar ve her aday açıda iki çember-kesişimi dalını da değerlendirir. Son aşamada seçilen beşgenin tüm kenarlarının gerçekten birim uzunlukta olduğu ve şeklin basit kaldığı sayısal olarak doğrulanır. Python ve Java uygulamaları ise aynı derlenmiş sayısal çekirdeğe bağlanır ve yalnızca ayrıştırılmış sayısal sonucu döndürür.
\(N_\theta\), örneklenen yönelim sayısı olsun. Tek bir beşgen için tüm döndürülmüş pozları ve üç genişlik profilini üretmek \(O(N_\theta)\) geometrik iş gerektirir; çünkü çokgenin köşe ve kenar sayısı sabit olarak \(5\)'tir. \(w\)'ye göre sıralama
$$O(N_\theta\log N_\theta)$$
zaman alır; bağlılık taraması ise ayrık-küme yapısı ile pratikte doğrusal olup \(O(N_\theta \alpha(N_\theta))\) mertebesindedir.
Bu nedenle tek bir hareket-genişliği değerlendirmesini baskın olarak \(O(N_\theta\log N_\theta)\) zaman ve \(O(N_\theta)\) bellek belirler. Dış arama \(T\) kez amaç fonksiyonunu hesaplıyorsa toplam maliyet
$$O(T\,N_\theta\log N_\theta)$$
olur. C++ sürümü açı başına geometriyi çok çekirdeğe böler; bu pratik süreyi azaltır ama asimptotik mertebeyi değiştirmez.
Se estudian pentágonos equiláteros de lado \(1\) que deben poder pasar por un corredor en ángulo recto de anchura \(W\). Para cada pentágono, \(A\) representa su área y \(W\) la menor anchura de corredor que todavía permite un movimiento continuo desde un tramo recto del pasillo hasta el otro.
La cantidad que se quiere maximizar es
$$\frac{A}{W^2}.$$
Este cociente es invariante por escala: si todas las longitudes se multiplican por \(\lambda\), el área se multiplica por \(\lambda^2\) y la anchura mínima necesaria del corredor por \(\lambda\). Por eso basta fijar el lado en \(1\) y optimizar una familia normalizada de formas.
La solución es numérica, pero la geometría subyacente tiene una estructura clara. Primero se restringe la búsqueda a una familia simétrica de pentágonos equiláteros gobernada por un solo ángulo. Después se calcula, para cada candidato, la anchura mínima del corredor analizando todas las orientaciones posibles.
La simetría respecto de la mediatriz del primer lado permite fijar cuatro vértices como
$$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1+\cos a,\sin a),\qquad v_4=(-\cos a,\sin a).$$
Con esto ya se cumple que
$$|v_1-v_0|=|v_2-v_1|=|v_0-v_4|=1.$$
Solo falta el punto \(v_3\), que debe satisfacer
$$|v_3-v_2|=|v_3-v_4|=1.$$
Así, todo el pentágono equilátero simétrico queda determinado por el parámetro angular \(a\).
La distancia entre los centros de esas circunferencias es
$$d=|v_2-v_4|=1+2\cos a.$$
Para que dos circunferencias de radio \(1\) se corten hace falta \(d\le 2\), luego la construcción exige
$$a\ge \frac{\pi}{3}.$$
El punto medio de \(v_2v_4\) es \(\left(\frac12,\sin a\right)\), por lo que las dos intersecciones posibles son
$$v_3=\left(\frac12,\sin a \pm \sqrt{1-\frac{d^2}{4}}\right).$$
Esos son exactamente los dos candidatos espejo que evalúa la implementación. Para cada uno, el área se calcula con la fórmula del zapatero:
$$A=\frac12\left|\sum_{i=0}^{4}\left(x_i y_{i+1}-x_{i+1} y_i\right)\right|,$$
tomando los índices de forma cíclica.
Fijemos una orientación \(\theta\). Se rota el pentágono y luego se traslada la figura resultante para que el mínimo \(x\) y el mínimo \(y\) sean ambos \(0\). Para el polígono trasladado \(P_\theta\), definimos
$$w_x(\theta)=x_{\max}-x_{\min},\qquad w_y(\theta)=y_{\max}-y_{\min}.$$
Estas dos cantidades miden la anchura necesaria para que el pentágono quepa, respectivamente, en un tramo recto vertical y en un tramo recto horizontal de un corredor de anchura \(W\).
La condición en la esquina es distinta. En la figura normalizada, un corredor en L de anchura \(W\) ocupa la unión de las franjas \(x\le W\) y \(y\le W\). La región prohibida es, por tanto, el cuadrado superior derecho donde ambas coordenadas superan \(W\). El pentágono cabe en la esquina exactamente cuando
$$\max_{p\in P_\theta}\min(p_x,p_y)\le W.$$
Esto sugiere definir la anchura de esquina
$$w(\theta)=\max_{p\in P_\theta}\min(p_x,p_y).$$
Sobre cada lado del polígono, la función \(\min(x,y)\) es lineal a trozos. Lejos de la diagonal \(x=y\), coincide simplemente con una coordenada o con la otra. El único lugar donde esa elección puede cambiar es en un cruce con la diagonal.
Por eso, el máximo de \(\min(x,y)\) sobre la frontera aparece necesariamente en un vértice o en una intersección de un lado con la diagonal \(x=y\).
La implementación aprovecha exactamente esa observación: en cada orientación muestreada revisa todos los vértices trasladados y todos los cortes de las aristas con la diagonal, y el mayor valor obtenido es \(w(\theta)\).
Para una anchura fija \(W\), sea
$$S_W=\{\theta\in[0,2\pi): w(\theta)\le W\}.$$
Ese conjunto contiene las orientaciones que pueden colocarse en la esquina. Pero para que exista un movimiento continuo no basta con orientaciones aisladas. Hace falta un mismo arco conexo de \(S_W\) que contenga
una orientación con \(w_y(\theta)\le W\), de modo que el pentágono pueda estar completamente dentro de un tramo horizontal recto, y
una orientación con \(w_x(\theta)\le W\), para que pueda estar completamente dentro de un tramo vertical recto.
Como las orientaciones viven en un círculo, la implementación muestrea densamente ese círculo, ordena las muestras por \(w(\theta)\), las activa en orden creciente y fusiona las muestras activas vecinas. Cada componente conexa guarda el menor \(w_x\) y el menor \(w_y\) vistos hasta ese momento. El primer umbral para el cual una componente cumple ambas desigualdades es la anchura de movimiento buscada para ese pentágono.
Tomemos
$$a=\frac{\pi}{2}.$$
Entonces
$$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1,1),\qquad v_4=(0,1),$$
y las dos intersecciones son
$$v_3=\left(\frac12,1\pm\frac{\sqrt3}{2}\right).$$
Si elegimos la intersección superior, obtenemos un pentágono simple con área
$$A=1+\frac{\sqrt3}{4}\approx 1.4330127.$$
En la orientación \(\theta=0\), el polígono ya tiene \(x_{\min}=y_{\min}=0\), así que
$$w_x(0)=1,\qquad w_y(0)=1+\frac{\sqrt3}{2},\qquad w(0)=1.$$
Eso significa que la figura puede apoyarse en la esquina de un corredor de anchura \(1\), porque ningún punto tiene simultáneamente ambas coordenadas mayores que \(1\). Sin embargo, no cabe por completo en un tramo horizontal recto de anchura \(1\), ya que su altura total es mayor que \(1\). El ejemplo muestra por qué hacen falta los tres perfiles \(w\), \(w_x\) y \(w_y\).
Para cada \(a\) admisible, la implementación evalúa los dos candidatos espejo, calcula la anchura mínima correspondiente \(W(a)\) y toma el mayor valor de
$$F(a)=\frac{A(a)}{W(a)^2}.$$
La búsqueda es unidimensional, y en el intervalo estrecho que contiene al mejor pentágono simétrico la optimización numérica se refina eficientemente mediante búsqueda por sección áurea.
La implementación en C++ precalcula una tabla densa de valores trigonométricos para orientaciones uniformemente espaciadas en todo el círculo. Para cada pentágono candidato rota los cinco vértices en cada ángulo muestreado, traslada la figura a una posición normalizada de apoyo inferior izquierdo y registra así los tres perfiles geométricos \(w\), \(w_x\) y \(w_y\).
Después ordena las orientaciones según el perfil de esquina \(w\). A medida que sube el umbral, las muestras activas vecinas en la malla angular cíclica se fusionan con una estructura de conjuntos disjuntos. Cada componente guarda las menores anchuras de tramo recto encontradas hasta ese momento. En cuanto una componente satisface simultáneamente \(w_x\le W\) y \(w_y\le W\), queda determinada la anchura de movimiento.
En el nivel exterior, la implementación realiza una búsqueda por sección áurea sobre el único parámetro angular y prueba las dos ramas procedentes de la intersección de circunferencias. El candidato final se verifica numéricamente para asegurar que los cinco lados siguen teniendo longitud \(1\) y que el pentágono es simple. Las implementaciones en Python y Java delegan en el mismo núcleo numérico compilado y solo devuelven la salida numérica ya interpretada.
Sea \(N_\theta\) el número de orientaciones muestreadas. Para un solo pentágono, calcular todas las poses rotadas y los tres perfiles de anchura cuesta \(O(N_\theta)\) trabajo geométrico, porque el polígono tiene un número constante de vértices y lados. Ordenar por \(w\) cuesta
$$O(N_\theta\log N_\theta),$$
y el barrido de conectividad con conjuntos disjuntos es esencialmente lineal, \(O(N_\theta \alpha(N_\theta))\).
Por tanto, una evaluación de la anchura de movimiento está dominada por \(O(N_\theta\log N_\theta)\) tiempo y \(O(N_\theta)\) memoria. Si la búsqueda exterior utiliza \(T\) evaluaciones del objetivo, el coste total es
$$O(T\,N_\theta\log N_\theta).$$
La versión en C++ paraleliza la geometría por orientación entre varios hilos de hardware, lo que mejora el tiempo real de ejecución sin alterar la complejidad asintótica.
这里研究的是边长为 \(1\) 的等边五边形，它必须能够通过一个宽度为 \(W\) 的直角走廊。对任意一个候选五边形，记 \(A\) 为其面积，记 \(W\) 为它从走廊的一条直线支路连续转入另一条支路所需的最小走廊宽度。
目标是最大化
$$\frac{A}{W^2}.$$
这个比值对尺度不敏感：如果把图形按比例 \(\lambda\) 放大，那么面积会乘上 \(\lambda^2\)，而所需走廊宽度只会乘上 \(\lambda\)。因此只研究单位边长五边形并不会损失一般性。
程序采用的是高精度数值方法，但几何推导本身很清楚。第一步，把搜索范围限制在一个关于中轴对称、只由一个角参数控制的等边五边形族中。第二步，对每个候选五边形采样整圈方向，判断哪些方向可以在拐角处出现，并据此求出最小可行走廊宽度。
利用第一条边的垂直平分线对称性，可以把前四个显式顶点放成
$$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1+\cos a,\sin a),\qquad v_4=(-\cos a,\sin a).$$
这样已经保证了
$$|v_1-v_0|=|v_2-v_1|=|v_0-v_4|=1.$$
还缺少的唯一顶点是 \(v_3\)，它必须满足
$$|v_3-v_2|=|v_3-v_4|=1.$$
因此整个对称等边五边形只由一个角 \(a\) 控制。
两个圆心之间的距离为
$$d=|v_2-v_4|=1+2\cos a.$$
两个半径都为 \(1\) 的圆要有交点，必须满足 \(d\le 2\)，所以需要
$$a\ge \frac{\pi}{3}.$$
\(v_2v_4\) 的中点是 \(\left(\frac12,\sin a\right)\)，因此两个可能的交点为
$$v_3=\left(\frac12,\sin a \pm \sqrt{1-\frac{d^2}{4}}\right).$$
这正是实现中检查的两个镜像候选。对每个候选，都用鞋带公式计算面积：
$$A=\frac12\left|\sum_{i=0}^{4}\left(x_i y_{i+1}-x_{i+1} y_i\right)\right|,$$
其中下标按循环方式取值。
固定一个方向角 \(\theta\)。先把五边形旋转 \(\theta\)，再把旋转后的图形平移，使最小 \(x\) 坐标和最小 \(y\) 坐标都变成 \(0\)。对平移后的多边形 \(P_\theta\)，定义
$$w_x(\theta)=x_{\max}-x_{\min},\qquad w_y(\theta)=y_{\max}-y_{\min}.$$
这两个量分别表示图形完全放进宽度为 \(W\) 的竖直直走廊和水平直走廊时所需要的水平跨度与竖直跨度。
拐角处的条件不同。经过上述平移后，宽度为 \(W\) 的 L 形走廊就是集合 \(x\le W\) 与 \(y\le W\) 的并，因此真正禁止进入的是右上角那个同时满足 \(x>W\) 且 \(y>W\) 的正方形。于是，方向 \(\theta\) 能否放在拐角处，等价于
$$\max_{p\in P_\theta}\min(p_x,p_y)\le W.$$
因此定义拐角宽度函数
$$w(\theta)=\max_{p\in P_\theta}\min(p_x,p_y).$$
在任意一条边上，函数 \(\min(x,y)\) 是分段线性的。离开对角线 \(x=y\) 时，它只是 \(x\) 或 \(y\) 中的一个；只有边穿过对角线时，取到较小值的那一支才会发生切换。
因此，\(\min(x,y)\) 在多边形边界上的最大值只能出现在顶点处，或者出现在某条边与对角线 \(x=y\) 的交点处。
实现正是利用这一点：对每个采样方向，它检查所有平移后的顶点以及所有边与对角线的交点，取其中最大的值作为 \(w(\theta)\)。
对固定走廊宽度 \(W\)，定义
$$S_W=\{\theta\in[0,2\pi): w(\theta)\le W\}.$$
这表示所有能够放在拐角处的方向。可是仅仅存在零散可行方向还不够，因为题目要求的是连续通过拐角。必须在 \(S_W\) 中找到同一个连通角区间，使它同时包含
某个满足 \(w_y(\theta)\le W\) 的方向，也就是图形可以完整待在水平直走廊中的姿态，以及
某个满足 \(w_x(\theta)\le W\) 的方向，也就是图形可以完整待在竖直直走廊中的姿态。
由于方向是模 \(2\pi\) 周期的，角度空间本身就是一个圆。实现方法是在这个圆上做高密度采样，把所有采样点按 \(w(\theta)\) 从小到大排序，按阈值逐步激活，并把相邻的激活方向合并成连通分量。每个分量维护当前见到的最小 \(w_x\) 和最小 \(w_y\)。一旦某个分量同时满足这两个最小值都不超过当前阈值，就说明找到了所需的最小通行宽度。
令
$$a=\frac{\pi}{2}.$$
这时
$$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1,1),\qquad v_4=(0,1),$$
两个交点为
$$v_3=\left(\frac12,1\pm\frac{\sqrt3}{2}\right).$$
选上方那个交点，就得到一个简单五边形，其面积为
$$A=1+\frac{\sqrt3}{4}\approx 1.4330127.$$
在方向 \(\theta=0\) 时，该图形已经满足 \(x_{\min}=y_{\min}=0\)，所以
$$w_x(0)=1,\qquad w_y(0)=1+\frac{\sqrt3}{2},\qquad w(0)=1.$$
这说明它可以放在宽度为 \(1\) 的拐角处，因为没有点同时满足 \(x>1\) 且 \(y>1\)。但是它还不能完整放进同样宽度的水平直走廊，因为竖直跨度大于 \(1\)。这个例子正好说明了为什么算法必须同时跟踪 \(w\)、\(w_x\) 和 \(w_y\) 三个量。
对每个可行的 \(a\)，实现都会评估两个镜像候选，求出对应的最小走廊宽度 \(W(a)\)，并取
$$F(a)=\frac{A(a)}{W(a)^2}$$
中较大的那个值。因为外层只剩一个实变量，在包含最优对称五边形的狭窄区间内，可以用黄金分割搜索高效地做数值优化。
C++ 实现会先为整圈均匀采样的方向预计算三角函数表。对每个候选五边形，它在每个采样角度下旋转全部五个顶点，再把姿态平移到左下接触点归零的标准位置，然后记录三个几何轮廓函数 \(w\)、\(w_x\) 和 \(w_y\)。
接着，它按照拐角宽度函数 \(w\) 对所有采样方向排序。随着阈值增加，角度圆上相邻的激活样本会通过并查集结构合并成连通分量。每个分量都维护目前见到的最小直走廊跨度。只要某个分量同时达到 \(w_x\le W\) 与 \(w_y\le W\)，该候选五边形的最小通行宽度就确定了。
在最外层，实现对唯一的角参数进行黄金分割搜索，并在每个角度上同时检查两个圆交分支。最后还会做数值校验，确认选出的五边形仍然保持五条边全为单位长度，并且没有自交。Python 和 Java 实现并不重复这些几何运算，而是调用同一个已编译的数值核心并返回解析后的数值结果。
设 \(N_\theta\) 为采样方向个数。对单个五边形而言，生成全部旋转姿态并计算三个宽度轮廓只需要 \(O(N_\theta)\) 的几何工作量，因为顶点数和边数都是常数 \(5\)。按 \(w\) 排序的代价为
$$O(N_\theta\log N_\theta),$$
随后并查集连通性扫描的代价近似线性，即 \(O(N_\theta \alpha(N_\theta))\)。
因此，一次走廊宽度评估的主导复杂度是 \(O(N_\theta\log N_\theta)\) 时间和 \(O(N_\theta)\) 空间。如果外层优化一共进行 \(T\) 次目标函数评估，那么总复杂度是
$$O(T\,N_\theta\log N_\theta).$$
C++ 版本还把每个角度上的几何计算分摊到多个硬件线程上，这会缩短实际运行时间，但不会改变渐近复杂度。
Рассматриваются равносторонние пятиугольники со стороной \(1\), которые должны проходить через коридор с прямым углом и шириной \(W\). Для каждого такого пятиугольника \(A\) обозначает площадь, а \(W\) — минимальную ширину коридора, при которой еще возможен непрерывный проход из одного прямого рукава в другой.
Нужно максимизировать величину
$$\frac{A}{W^2}.$$
Этот показатель инвариантен относительно масштаба: если увеличить фигуру в \(\lambda\) раз, площадь умножится на \(\lambda^2\), а требуемая ширина коридора — только на \(\lambda\). Поэтому можно без ограничения общности зафиксировать длину стороны равной \(1\).
Решение носит численный характер, но геометрия у него очень прозрачная. Сначала поиск ограничивается симметрическим однопараметрическим семейством равносторонних пятиугольников. Затем для каждого кандидата вычисляется минимальная допустимая ширина коридора по всем ориентациям фигуры.
Симметрия относительно серединного перпендикуляра к первой стороне позволяет задать четыре видимые вершины так:
$$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1+\cos a,\sin a),\qquad v_4=(-\cos a,\sin a).$$
Тогда уже выполняется
$$|v_1-v_0|=|v_2-v_1|=|v_0-v_4|=1.$$
Остается только вершина \(v_3\), которая должна удовлетворять условиям
$$|v_3-v_2|=|v_3-v_4|=1.$$
Итак, весь симметричный равносторонний пятиугольник задается единственным параметром \(a\).
Расстояние между центрами этих окружностей равно
$$d=|v_2-v_4|=1+2\cos a.$$
Чтобы две окружности радиуса \(1\) пересекались, необходимо \(d\le 2\), то есть
$$a\ge \frac{\pi}{3}.$$
Середина отрезка \(v_2v_4\) — это \(\left(\frac12,\sin a\right)\), поэтому два возможных пересечения имеют вид
$$v_3=\left(\frac12,\sin a \pm \sqrt{1-\frac{d^2}{4}}\right).$$
Именно эти две зеркальные ветви и проверяет реализация. Для каждой из них площадь считается по формуле Гаусса:
$$A=\frac12\left|\sum_{i=0}^{4}\left(x_i y_{i+1}-x_{i+1} y_i\right)\right|,$$
где индексы понимаются циклически.
Зафиксируем угол ориентации \(\theta\). Пятиугольник поворачивается на \(\theta\), после чего полученные координаты сдвигаются так, чтобы минимальные значения \(x\) и \(y\) стали равны \(0\). Для нормализованного многоугольника \(P_\theta\) определим
$$w_x(\theta)=x_{\max}-x_{\min},\qquad w_y(\theta)=y_{\max}-y_{\min}.$$
Это как раз те ширины, которые нужны, чтобы фигура полностью помещалась соответственно в вертикальном и горизонтальном прямом рукаве коридора ширины \(W\).
Условие в углу устроено иначе. После нормализации Г-образный коридор ширины \(W\) есть объединение полос \(x\le W\) и \(y\le W\), а запрещенной остается только правая верхняя область, где обе координаты превышают \(W\). Значит, фигура помещается в углу тогда и только тогда, когда
$$\max_{p\in P_\theta}\min(p_x,p_y)\le W.$$
Это и есть определение угловой ширины
$$w(\theta)=\max_{p\in P_\theta}\min(p_x,p_y).$$
На каждом ребре функция \(\min(x,y)\) кусочно-линейна. Вне диагонали \(x=y\) она просто совпадает либо с \(x\), либо с \(y\). Единственное место, где активная ветвь может смениться, — это пересечение ребра с диагональю.
Следовательно, максимум \(\min(x,y)\) на границе многоугольника достигается либо в вершине, либо в точке пересечения ребра с диагональю \(x=y\).
Именно этим пользуется реализация: для каждой выбранной ориентации она проверяет все сдвинутые вершины и все пересечения ребер с диагональю, а наибольшее найденное значение принимает за \(w(\theta)\).
Для фиксированной ширины коридора \(W\) введем множество
$$S_W=\{\theta\in[0,2\pi): w(\theta)\le W\}.$$
Это ориентации, которые вообще допустимы в углу. Но для непрерывного прохода мало знать, что такие ориентации существуют по отдельности. Нужна одна связная дуга множества \(S_W\), содержащая одновременно
ориентацию с \(w_y(\theta)\le W\), чтобы пятиугольник мог целиком находиться в горизонтальном прямом рукаве, и
ориентацию с \(w_x(\theta)\le W\), чтобы он мог целиком находиться в вертикальном прямом рукаве.
Так как угол поворота задается по модулю \(2\pi\), пространство ориентаций является окружностью. Реализация густо дискретизирует эту окружность, сортирует все образцы по возрастанию \(w(\theta)\), активирует их в порядке порога и объединяет соседние активные образцы. Для каждой компоненты связности хранятся минимальные значения \(w_x\) и \(w_y\), увиденные внутри нее. Первый порог, при котором одна компонента удовлетворяет обоим условиям, и есть искомая ширина прохода.
Положим
$$a=\frac{\pi}{2}.$$
Тогда
$$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1,1),\qquad v_4=(0,1),$$
а две точки пересечения равны
$$v_3=\left(\frac12,1\pm\frac{\sqrt3}{2}\right).$$
Если взять верхнюю точку, получится простой пятиугольник с площадью
$$A=1+\frac{\sqrt3}{4}\approx 1.4330127.$$
В ориентации \(\theta=0\) фигура уже имеет \(x_{\min}=y_{\min}=0\), поэтому
$$w_x(0)=1,\qquad w_y(0)=1+\frac{\sqrt3}{2},\qquad w(0)=1.$$
Это означает, что фигура может стоять в углу коридора ширины \(1\), потому что ни одна точка не имеет одновременно \(x>1\) и \(y>1\). Но целиком в горизонтальный прямой рукав той же ширины она еще не помещается, так как ее вертикальный размах больше \(1\). Именно поэтому алгоритму нужны все три профиля \(w\), \(w_x\) и \(w_y\).
Для каждого допустимого \(a\) реализация оценивает обе зеркальные ветви, вычисляет минимальную ширину коридора \(W(a)\) и берет больший из двух значений
$$F(a)=\frac{A(a)}{W(a)^2}.$$
Внешний поиск одномерен, и в узком интервале, содержащем лучший симметричный пятиугольник, его удобно и эффективно уточнять методом золотого сечения.
Реализация на C++ сначала строит плотную таблицу тригонометрических значений для равномерно распределенных ориентаций по всему кругу. Для каждого кандидата она поворачивает все пять вершин на каждый из этих углов, затем сдвигает получившуюся позу в нормализованное положение касания нижнего левого угла и записывает три профиля \(w\), \(w_x\) и \(w_y\).
После этого образцы ориентаций сортируются по угловому профилю \(w\). По мере роста порога соседние активные образцы на циклической сетке углов объединяются структурой непересекающихся множеств. Для каждой компоненты запоминаются минимальные прямолинейные ширины, встреченные до текущего момента. Как только одна компонента одновременно достигает \(w_x\le W\) и \(w_y\le W\), ширина прохода для данного пятиугольника найдена.
На внешнем уровне реализация применяет поиск золотого сечения по единственному угловому параметру и проверяет обе ветви, возникающие из пересечения окружностей. В финале проводится численная проверка: все пять сторон должны остаться единичными, а сам пятиугольник — простым, без самопересечений. Реализации на Python и Java используют тот же скомпилированный численный вычислительный блок и лишь возвращают разобранный числовой ответ.
Пусть \(N_\theta\) — число дискретизированных ориентаций. Для одного пятиугольника построение всех повернутых поз и вычисление трех профилей ширины требует \(O(N_\theta)\) геометрической работы, поскольку число вершин и ребер постоянно и равно \(5\). Сортировка по \(w\) занимает
$$O(N_\theta\log N_\theta),$$
а проход на структуре непересекающихся множеств практически линеен: \(O(N_\theta \alpha(N_\theta))\).
Следовательно, одна оценка ширины движения определяется главным образом временем \(O(N_\theta\log N_\theta)\) и памятью \(O(N_\theta)\). Если внешний поиск выполняет \(T\) оценок целевой функции, общая стоимость равна
$$O(T\,N_\theta\log N_\theta).$$
Версия на C++ дополнительно распараллеливает геометрию по углам на несколько аппаратных потоков, что ускоряет практический расчет, но не меняет асимптотику.
ندرس خماسيات متساوية الأضلاع طول ضلع كل منها \(1\)، ويجب أن تكون قادرة على المرور عبر ممر ذي زاوية قائمة وعرضه \(W\). نرمز إلى مساحة الخماسي بـ \(A\)، وإلى أصغر عرض ممر يسمح بحركة متصلة من الذراع المستقيمة الأولى إلى الذراع الأخرى بـ \(W\).
الكمية المطلوب تعظيمها هي
$$\frac{A}{W^2}.$$
هذه النسبة لا تتأثر بالمقياس: إذا كبرت جميع الأطوال بعامل \(\lambda\)، فإن المساحة تتضاعف بعامل \(\lambda^2\)، بينما يزداد عرض الممر اللازم بعامل \(\lambda\) فقط. لذلك يكفي تثبيت طول الضلع عند \(1\) والعمل على عائلة مطبّعة من الأشكال.
الحل عددي، لكن البنية الهندسية واضحة جدًا. أولًا نقيّد البحث بعائلة متناظرة من الخماسيات المتساوية الأضلاع تتحكم فيها زاوية واحدة. ثم نحسب، لكل شكل مرشح، أقل عرض للممر يمكنه أن يحقق مرورًا متصلًا حول الركن عند فحص جميع الاتجاهات الممكنة.
باستخدام التناظر حول المنصف العمودي للضلع الأول يمكن وضع أربع رؤوس على الصورة
$$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1+\cos a,\sin a),\qquad v_4=(-\cos a,\sin a).$$
وهذا يضمن مباشرة أن
$$|v_1-v_0|=|v_2-v_1|=|v_0-v_4|=1.$$
ويبقى الرأس \(v_3\) فقط، ويجب أن يحقق
$$|v_3-v_2|=|v_3-v_4|=1.$$
إذًا الخماسي المتناظر بأكمله يصبح محكومًا بالمعامل الزاوي الوحيد \(a\).
المسافة بين مركزي الدائرتين هي
$$d=|v_2-v_4|=1+2\cos a.$$
ولكي تتقاطع دائرتان نصف قطر كل منهما \(1\) يجب أن يكون \(d\le 2\)، ومن ثم لا بد من
$$a\ge \frac{\pi}{3}.$$
منتصف القطعة \(v_2v_4\) هو \(\left(\frac12,\sin a\right)\)، ولذلك تكون نقطتا التقاطع الممكنتان
$$v_3=\left(\frac12,\sin a \pm \sqrt{1-\frac{d^2}{4}}\right).$$
وهذان هما الفرعان الانعكاسيان اللذان يفحصهما التنفيذ. وبالنسبة لكل مرشح تُحسب المساحة بصيغة الحذاء:
$$A=\frac12\left|\sum_{i=0}^{4}\left(x_i y_{i+1}-x_{i+1} y_i\right)\right|,$$
مع أخذ الفهارس دوريًا.
لنثبت زاوية اتجاه \(\theta\). ندوّر الخماسي بمقدار \(\theta\)، ثم نترجم الشكل الناتج بحيث يصبح أصغر \(x\) وأصغر \(y\) مساويين للصفر. بالنسبة للمضلع المترجم \(P_\theta\)، نعرّف
$$w_x(\theta)=x_{\max}-x_{\min},\qquad w_y(\theta)=y_{\max}-y_{\min}.$$
هاتان القيمتان تمثلان العرض اللازم لكي يحتوى الشكل كاملًا داخل ذراع مستقيمة عمودية أو أفقية من الممر ذي العرض \(W\).
أما قيد الركن فله صياغة مختلفة. بعد التطبيع، يشغل الممر القائم ذو العرض \(W\) اتحاد المنطقتين \(x\le W\) و\(y\le W\)، ولذلك تكون المنطقة الممنوعة هي المربع العلوي الأيمن حيث يتجاوز كل من \(x\) و\(y\) القيمة \(W\). ومن ثم فإن وضعية الزاوية \(\theta\) تكون ممكنة إذا وفقط إذا
$$\max_{p\in P_\theta}\min(p_x,p_y)\le W.$$
ولهذا نعرّف دالة عرض الركن بـ
$$w(\theta)=\max_{p\in P_\theta}\min(p_x,p_y).$$
على أي ضلع من أضلاع المضلع تكون الدالة \(\min(x,y)\) خطية على أجزاء. بعيدًا عن القطر \(x=y\) فهي تساوي أحد الإحداثيين فقط، ولا يمكن أن يتبدل الفرع الفعال إلا عند نقطة عبور للقطر.
لذلك فإن القيمة العظمى لـ \(\min(x,y)\) على حدود المضلع لا بد أن تتحقق إما عند رأس، أو عند نقطة تقاطع ضلع مع القطر \(x=y\).
وهذا بالضبط ما يفعله التنفيذ: في كل اتجاه مأخوذ بالعينة يفحص جميع الرؤوس بعد الإزاحة وجميع تقاطعات الأضلاع مع القطر، ويأخذ أكبر قيمة بينها لتكون \(w(\theta)\).
لثابت \(W\)، لنعرّف
$$S_W=\{\theta\in[0,2\pi): w(\theta)\le W\}.$$
هذه هي الاتجاهات التي يمكن أن يوجد فيها الخماسي عند الركن. لكن وجود اتجاهات منفصلة لا يكفي لمرور متصل. المطلوب وجود قوس متصل واحد داخل \(S_W\) يحتوي في الوقت نفسه على
اتجاه يحقق \(w_y(\theta)\le W\)، بحيث يستطيع الخماسي أن يستقر كاملًا داخل الذراع الأفقية المستقيمة، و
اتجاه يحقق \(w_x(\theta)\le W\)، بحيث يستطيع أن يستقر كاملًا داخل الذراع العمودية المستقيمة.
وبما أن فضاء الاتجاهات دوري modulo \(2\pi\)، فهو دائرة. يأخذ التنفيذ عينات كثيفة من هذه الدائرة، ويرتبها بحسب \(w(\theta)\) تصاعديًا، ثم يفعّل العينات بهذا الترتيب ويصل بين العينات النشطة المتجاورة. وتحفظ كل مركبة متصلة أصغر قيمتين شوهدتا لـ \(w_x\) و\(w_y\). وأول عتبة تملك عندها مركبة واحدة القيمتين معًا تكون هي عرض المرور المطلوب لذلك الخماسي.
لنأخذ
$$a=\frac{\pi}{2}.$$
عندئذٍ نحصل على
$$v_0=(0,0),\qquad v_1=(1,0),\qquad v_2=(1,1),\qquad v_4=(0,1),$$
وتكون نقطتا التقاطع
$$v_3=\left(\frac12,1\pm\frac{\sqrt3}{2}\right).$$
إذا اخترنا النقطة العليا نحصل على خماسي بسيط مساحته
$$A=1+\frac{\sqrt3}{4}\approx 1.4330127.$$
وعند الاتجاه \(\theta=0\) يكون الشكل أصلًا في وضعية تحقق \(x_{\min}=y_{\min}=0\)، ومن ثم
$$w_x(0)=1,\qquad w_y(0)=1+\frac{\sqrt3}{2},\qquad w(0)=1.$$
وهذا يعني أن الخماسي يستطيع الوقوف عند ركن ممر عرضه \(1\)، لأنه لا توجد نقطة تحقق معًا \(x>1\) و\(y>1\). لكنه لا ينساب بعد داخل ذراع أفقية مستقيمة بالعرض نفسه لأن امتداده الرأسي أكبر من \(1\). وهذا يوضح عمليًا لماذا تحتاج الخوارزمية إلى تتبع \(w\) و\(w_x\) و\(w_y\) معًا.
لكل قيمة مسموحة من \(a\)، يقيم التنفيذ الفرعين الانعكاسيين، ويحسب عرض الممر الأدنى الموافق \(W(a)\)، ثم يأخذ القيمة الأكبر لـ
$$F(a)=\frac{A(a)}{W(a)^2}.$$
ولأن البحث الخارجي أحادي البعد، ولأن المجال الضيق الذي يحتوي على أفضل خماسي متناظر يمكن التعامل معه عدديًا بسلاسة، فإن بحث المقطع الذهبي يعد وسيلة فعالة لتحسين الزاوية المثلى.
يبني تنفيذ C++ أولًا جدولًا كثيفًا لقيم الدوال المثلثية عند زوايا موزعة بانتظام على الدائرة كلها. ثم، لكل خماسي مرشح، يدير الرؤوس الخمسة عند كل زاوية مأخوذة بالعينة، ويترجم الوضعية إلى شكل مطبّع يلامس الركن السفلي الأيسر، ويسجل بعد ذلك المنحنيات الثلاثة \(w\) و\(w_x\) و\(w_y\).
بعد ذلك يرتب الاتجاهات وفقًا لدالة عرض الركن \(w\). ومع ارتفاع العتبة تندمج العينات النشطة المتجاورة على الشبكة الزاوية الدائرية بواسطة بنية مجموعات منفصلة. وكل مركبة تحفظ أصغر عرضين مستقيمين شوهدًا حتى اللحظة. وما إن تمتلك إحدى المركبات الشرطين \(w_x\le W\) و\(w_y\le W\) معًا حتى يتحدد عرض المرور لذلك الخماسي.
في المستوى الخارجي، ينفذ البرنامج بحثًا بالمقطع الذهبي على معامل الزاوية الوحيد، ويفحص فرعي تقاطع الدائرتين عند كل مرشح. وفي النهاية يجري تحققًا عدديًا للتأكد من أن الأضلاع الخمسة ما تزال بطول الوحدة وأن الخماسي المختار بسيط بلا تقاطعات ذاتية. أما تنفيذا Python وJava فيعتمدان على النواة العددية المترجمة نفسها ويعيدان فقط الناتج العددي بعد تحليله.
ليكن \(N_\theta\) عدد الاتجاهات المأخوذة بالعينة. بالنسبة إلى خماسي واحد، فإن توليد جميع الوضعيات المدارة وحساب المنحنيات الثلاثة يكلف \(O(N_\theta)\) من العمل الهندسي، لأن عدد الرؤوس والأضلاع ثابت ويساوي \(5\). أما الفرز بحسب \(w\) فيكلف
$$O(N_\theta\log N_\theta),$$
في حين أن مسح الاتصال باستخدام بنية المجموعات المنفصلة يكون فعليًا خطيًا، أي \(O(N_\theta \alpha(N_\theta))\).
وعليه فإن تقييم عرض المرور مرة واحدة تهيمن عليه كلفة \(O(N_\theta\log N_\theta)\) زمنًا و\(O(N_\theta)\) ذاكرة. وإذا استُخدم \(T\) تقييمًا للدالة الهدف في البحث الخارجي، تصبح الكلفة الكلية
$$O(T\,N_\theta\log N_\theta).$$
وتوزع نسخة C++ الحسابات الهندسية الخاصة بالزوايا على عدة خيوط معالجة، مما يحسن الزمن العملي من دون تغيير الرتبة التقاربية.