Két kör metszéspontjai analitikusan, képlettel kiszámíthatók. De most nem így oldjuk meg a feladatot, hanem a két kör adott számú pontjának felvételével, és ezek közül a legközelebbi pontok meghatározásával, majd e térrészben egyre több újabb pont generálásával és újabb közelségvizsgálattal. Ezt ismételjük addig, amíg a körök két vizsgált pontjának távolsága egy előre meghatározott hibahatáron belül nem lesz. Ekkor a két pontot a közös metszéspontnak tekintjük.

Miért választunk a képlettel történő számítás helyett egy numerikus, iteratív megoldást? Azért, mert most valójában nem a konkrét feladat eredménye az érdekes, hanem az odavezető út és az alkalmazott Python nyelvi elemek és szerkezetek gyakorlása. Ennek során látni fogjuk, hogy hogyan lehet egy problémát értékkeresési feladattá alakítani, hogyan lehet a keresési tartományt szűkíteni ahhoz, hogy a számításigényt minimalizáljuk, és hogyan működik az iteratív, fokozatosan közelítő eljárás.

Ráadásul a bemutatott megközelítés nem kizárólag körökre alkalmazható. Az alakzatok egy előre meghatározott elv szerinti relatív pozícióba hozása, majd egy szűkített paramétertartományban végzett numerikus egyezéskeresés némi módosítással szabályos konvex sokszögekre is adaptálható. Ez különösen nagyobb élszám esetén merülhet fel, mert a képleteken alapuló analitikus megoldás ilyenkor nehézkessé válik.

Mindemellett persze a konkrét feladathoz a geometriai ismereteinkre is szükség lesz, mert alkalmazni fogunk polárkoordinátákat, eltolást, forgatást és ezek inverz transzformációit, pontok távolságának számítását és körök pontjainak meghatározását.

Első lépésként a két kört egy rögzített, standard relatív helyzetbe transzformáljuk: a nagyobb kör középpontját az origóba toljuk, majd a kisebb kör középpontját a pozitív x tengelyre forgatjuk. Ezt szemlélteti a következő ábra, ahol ennek az elrendezésnek az előnyeit is felsoroltuk. E jellemzők biztosítják, hogy a számítások egyszerűbbek legyenek és kevesebb iterációt igényeljenek, hiszen egyre szűkülő szögtartományokban kell legközelebb eső pontok keresését végezni.

E geometriai transzformációkat, valamint a legközlebbi pontok keresését kell lekódolni. A pontok és a körök előállításához egy Point és egy Circle osztályt definiálunk az alább látható módon.

A Point osztályt adatosztállyal valósítottuk meg úgy, hogy a dataclass dekorátor frozen és slots paramétereit True értékre állítjuk. Az előbbivel biztosítjuk, hogy a Point példányok változtathatatlanok legyenek, az utóbbival pedig azt, hogy a példányok kevesebb memóriát igényeljenek. A memóriahasználatra olyankor különösen érdemes figyelni, amikor sok példány létrehozása várható. A geometriai pontok pedig általában ilyenek. A Point metódusai a pont eltolását, forgatását, valamint polárkoordinátáinak és egy másik ponttól való távolságának számítását valósítják meg.

A Circle osztály szintén rendelkezik metódusokkal, amelyek lehetővé teszik a kör eltolását és forgatását, valamint két kör középpontja távolságának számítását. Ezen felül képes arra, hogy egy megadható szögtartományban a kör adott számú pontját előállítsa azonos polárszög növekménnyel. A feladatunk szempontjából legfontosabb metódus az, amelyik a metszéspontokat határozza meg. Ezért ennek működését röviden összefoglaljuk.

Az intersection_points() metódus először ellenőrzi, hogy a körök egyáltalán metszik-e egymást. Ha a két kör  egymástól távoli, vagy egyik a másikban teljesen benne van, akkor nincs metszéspont. Ilyenkor üres halmazzal tér vissza a metódus. Azonos sugarú és középpontú körök esetén sincs véges számú metszéspont. Ezért ebben az esetben is üres halmaz lesz a visszatérési érték.

Ha az előbbiek nem állnak fenn, akkor kell, hogy legyen egy vagy két metszéspont. Ekkor a következő lépések történnek:

    1. A köröket a rögzített, standard relatív helyzetbe transzformálja  a _canonicalize_circle_pair() metódussal.

    2. Előállítja a körök pontjait a szögtartományokban.

    3. Megkeresi a két kör pontjai közül a legközelebb eső kettőt.

    4. Ha a pontok távolsága megfelelően kicsi, azokat metszéspontoknak tekinti és egy halmazban adja vissza.

    5. Ha a pontok nem elég közeliek, a keresési tartományt szűkíti és az eljárást megismétli a 2. lépéstől.

Ha kell, hogy legyen metszéspont, de a megadott toleranciaérték olyan kicsi, hogy a float számok véges ábrázolási tartománya miatt a pontok közötti távolság az iterációk számának növelésével már nem szűkíthető, akkor ez végtelen ciklust eredményezhet. Ezért bekorlátozzuk az iterációk számát. Ha ennél több ismétlés esetén sem tudott a metódus metszéspontot visszaadni, akkor kivételt dobunk. Ilyenkor a toleranciahatárt kell tágítani addig, amíg ki nem kerül a végtelen ciklusból.   

Megjegyezzük, hogy bár a pontpárok összevetésének futási ideje elvben O(n²) időkomplexitású, a rögzített pontszám (n=100) és az iterációnként szűkülő keresési tartomány miatt a tényleges futási idő kellően kicsi és jól kontrollálható. Ez rávilágít arra, hogy a keresési tartomány megfelelő korlátozásával egy elvben nagy időkomplexitású algoritmus is hatékonyan alkalmazható.

Mivel körök metszéspontjai vizuálisan jól megállapíthatók, ezért a teszteléshez egy egyszerű GUI alkalmazást készítettünk, amely megjeleníti a köröket, megjelöli a metszéspontokat és azok koordinátáit szövegesen kiírja. Ennek kódja a következő:

Néhány tesztfuttatás eredményének képernyőképe alább látható.

Ebben a bejegyzésben a math, cmath és itertools modulok függvényéit használtuk, valamint a dataclasses modult, hogy definiáljunk egy adatosztályt paraméteres dataclass dekorátorral. Az adatosztályok létrehozásához típusannotációk is szükségesek, amelyeket típushelyettesítőkkel, illetve a typing modul igénybevételével biztosítottunk. Mindezekről a a Python tudásépítés lépésről lépésre című e-könyv „Készétel fogyasztás – a szabványos könyvtár moduljainak használata” és „Különleges osztálydefiníciók” fejezetekben lehet részletesen olvasni. GUI alkalmazás fejlesztéséhez szükséges ismereteket pedig a „Grafikus felhasználói felület készítése” című részből lehet elsajátítani.