Egyenes szakaszok vagy sokszögek metszéspontjának meghatározása nem csupán egy iskolai matematikai feladvány, hanem számos gyakorlati esetben lehet szükség erre. A számítógépes grafikában például minden ütközésvizsgálat – legyen szó egy játékban elrepülő lövedékről vagy egy karakter mozgásáról – ilyen számításokra épül. Térinformatikai rendszerekben is szükséges ellenőrizni, hogy egy tervezett útvonal keresztezi-e egy zóna határát. A robotikában a navigáció alapja, hogy a robot előre látja, metszi-e mozgási pályáját valamely akadály. A mérnöki és építészeti tervezésben is kiemelt szerepe van ennek: falak, vezetékek, szerkezeti elemek találkozási pontjait meg kell tudni határozni.
Ha két egyenes szakaszt grafikonon ábrázolunk, akkor vizuálisan könnyen megállapíthatjuk, hogy azok metszik-e egymást, és ha igen, akkor mely pontban. Ha programmal akarjuk ugyanezt meghatározni, ahhoz némi koordinátageometriai levezetés szükséges, aminek az eredményét utána megfelelő módon programkódban meg tudunk valósítani a metszéspont koordinátáinak kiszámításához. Ezt a levezetést láthatjuk a következő ábrán, ahol a metszéspontot végeredményben vektoriális szorzatok – pontosabban azok síkra merőleges z komponensei – segítségével fejezzük ki.
Minthogy a síkbeli vektorok és a komplex számok kölcsönösen megfeleltethetők, így két egyenes szakasz metszéspontját komplex számokkal is kifejezhetjük. Ennek levezetését az alábbi ábrán lehet követni.
A két előbb vázolt matematikai megközelítés szerint megvalósított függvények definícióit láthajuk alább. Az elvi ábrák és a kommentek segítik a működés megértését.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
# Python 3.12+ from itertools import pairwise, chain, product, batched from typing import Iterable, Iterator, Callable from math import isclose import tkinter as tk type RealNum = int | float type Point = tuple[RealNum, RealNum] type Vector2D = tuple[RealNum, RealNum] type NoIntersection = tuple[()] type Vertex = tuple[RealNum, RealNum] def intersection_using_xprod(p1: Point, p2: Point, p3: Point, p4: Point) -> Point | NoIntersection: """Két egyenes-szakasz metszéspontját számítja ki vektoriális szorzatok segítségével. Az egyenes-szakaszokat a két-két végpontjuk definiálja: - az első szakasz p1 → p2 - a második szakasz p3 → p4 Visszatérési érték: - Ha a szakaszok metszik egymást, akkor a metszéspont koordinátáit visszaadó kételemű tuple. - Ha nincs metszéspont (párhuzamos vagy nem szakaszon belüli), akkor egy üres tuple. """ # A metszéspont számítása: # - Először a szakaszok vektorait képezzük: d12, d34 # - A cross_product_z() függvény segítségével meghatározzuk a szakaszok vektorainak kereszt-szorzatát. # - Ellenőrizzük, hogy az egyenesek párhuzamosak-e. # - Ha van metszéspont, meghatározzuk a k paramétert (az első szakaszon) és h paramétert (a másodikon) # - Ha 0 ≤ k ≤ 1 és 0 ≤ h ≤ 1, a metszéspont a szakaszokon belül található. def cross_product_z(vector_a: Vector2D, vector_b: Vector2D) -> RealNum: """Visszaadja a megadott két síkbeli vektor vektoriális szorzatának z-komponensét.""" return vector_a[0] * vector_b[1] - vector_a[1] * vector_b[0] # Szakasz-vektorok létrehozása. d12 = (p2[0] - p1[0], p2[1] - p1[1]) d34 = (p4[0] - p3[0], p4[1] - p3[1]) d13 = (p3[0] - p1[0], p3[1] - p1[1]) # Az egyenesek párhuzamosságának vizsgálata. if isclose(denominator := cross_product_z(d12, d34), 0, abs_tol=1e-12): # Nincs egyedi metszéspont (a szakaszok vagy párhuzamosak, vagy egybeesnek, de nincsen metszéspont # a hagyományos értelemben). return () # Paraméterek kiszámítása a lineáris kombinációhoz. k = cross_product_z(d13, d34) / denominator h = cross_product_z(d13, d12) / denominator # Ellenőrzés, hogy a metszéspont a szakaszokon belül van-e. if not (0 <= k <= 1) or not (0 <= h <= 1): return () # A metszéspont koordinátái. isect_point: Point = (p1[0] + k * d12[0], p1[1] + k * d12[1]) return isect_point def intersection_using_complex(p1: Point, p2: Point, p3: Point, p4: Point) -> Point | NoIntersection: """Két egyenes-szakasz metszéspontját számítja ki komplex számok segítségével. Az egyenes-szakaszokat a két-két végpontjuk definiálja: - az első szakasz p1 → p2 - a második szakasz p3 → p4 Visszatérési érték: - Ha a szakaszok metszik egymást, akkor a metszéspont koordinátáit visszaadó kételemű tuple. - Ha nincs metszéspont (párhuzamos vagy nem szakaszon belüli), akkor egy üres tuple. """ # A metszéspont számítása: # - A pontokat komplex számokkal reprezentáljuk. # - A szakaszvektorok mint komplex számok meghatározása. # - A párhuzamosság vizsgálata. # - Ha van metszéspont, kiszámítjuk a k és h paramétereket a lineáris kombinációhoz. # - Ha 0 ≤ k ≤ 1 és 0 ≤ h ≤ 1, a metszéspont a szakaszokon belül található. # A bemeneti pontokat komplex számokká alakítjuk. z1, z2, z3, z4 = (complex(*p) for p in [p1, p2, p3, p4]) # A szakaszvektorok mint komplex számok. d12 = z2 - z1 d34 = z4 - z3 d13 = z3 - z1 # A k és h paraméterek képletében a nevező mint kereszt szorzat meghatározása komplex számokkal. denominator = (d12 * d34.conjugate()).imag # Az egyenesek párhuzamosságának vizsgálata. if isclose(denominator, 0, abs_tol=1e-12): return () # Paraméterek kiszámítása a lineáris kombinációhoz. k = (d13 * d34.conjugate()).imag / denominator h = (d13 * d12.conjugate()).imag / denominator # Ellenőrzés, hogy a metszéspont a szakaszokon belül van-e. if not (0 <= k <= 1) or not (0 <= h <= 1): return () # Metszéspont komplex számként. isect: complex = z1 + k * d12 # A metszéspont koordinátáinek visszaadása. isect_point: Point = (isect.real, isect.imag) return isect_point |
A komplex számokat használó megvalósítást nem csupán érdekességként mutatjuk. A szakaszok végpontjait általában int vagy float típusú számként adjuk meg, de elvben nem kizárt hogy az int mellett Fraction vagy Decimal típust használjunk a törtértékek megadására. Ez utóbbi esetekben azonban jelentős futási idő megtakarítást tapasztalhatunk, ha a komplex számokra épülő függvényt alkalmazzuk. Erre vonatkozó teszteseteket mutatunk alább:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
from timeit import timeit from fractions import Fraction from decimal import Decimal print('A vektoriális szorzattal és a komplex számok használatával megvalósított függvények futási idejének viszonya ' 'különböző számtípus-kombinációk alkalmazásánál.\n') print('--- int/float ---') tx = timeit('intersection_using_xprod((1.5, 4), (10.5, 6), (0.5, 20), (5, 1))', globals=globals(), number=100_000) tc = timeit('intersection_using_complex((1.5, 4), (10.5, 6), (0.5, 20), (5, 1))', globals=globals(), number=100_000) print(f'{tx / tc:.0%}') print('--- int/float/Fraction ---') tx = timeit('intersection_using_xprod((Fraction(3,2), 4), (10.5, 6), (Fraction(1,2), 20), (5, 1))', globals=globals(), number=100_000) tc = timeit('intersection_using_complex((Fraction(3,2), 4), (10.5, 6), (Fraction(1,2), 20), (5, 1))', globals=globals(), number=100_000) print(f'{tx / tc:.0%}') print('--- int/Fraction ---') tx = timeit('intersection_using_xprod((Fraction(3,2), 4), (Fraction(21,2), 6), (Fraction(1,2), 20), (5, 1))', globals=globals(), number=100_000) tc = timeit('intersection_using_complex((Fraction(3,2), 4), (Fraction(21,2), 6), (Fraction(1,2), 20), (5, 1))', globals=globals(), number=100_000) print(f'{tx / tc:.0%}') print('--- int/Decimal ---') tx = timeit('intersection_using_xprod((Decimal("1.5"), 4), (Decimal("10.5"), 6), (Decimal("0.5"), 20), (5, 1))', globals=globals(), number=100_000) tc = timeit('intersection_using_complex((Decimal("1.5"), 4), (Decimal("10.5"), 6), (Decimal("0.5"), 20), (5, 1))', globals=globals(), number=100_000) print(f'{tx / tc:.0%}') # Eredmény: # A vektoriális szorzattal és a komplex számok használatával megvalósított függvények futási idejének viszonya # különböző számtípus-kombinációk alkalmazásánál. # --- int/float --- # 76% # --- int/float/Fraction --- # 406% # --- int/Fraction --- # 503% # --- int/Decimal --- # 134% |
Minthogy a gyakorlatban a koordináták megadására többnyire int vagy float típusú számokat használunk, és ezekkel a vektoriális szorzatot alkalmazó függvény teljesít jobban, ezért alapértelmezetten ezzel fogunk a továbbiakban dolgozni.
Most tehát rendelkezünk olyan függvénnyel, amely két szakasz metszéspontjának koordinátáit adja vissza egy tuple objektumban. Ha nincs metszéspont vagy a szakaszok egy vonalba esnek, akkor az eredmény egy üres tuple.
Egy sokszög felfogható úgy, mint a csúcspontok által meghatározott egyenes szakaszok sorozata. Ha tehát azt akarjuk megtudni, hogy két sokszög hol, mely pontokban metszi egymást, akkor nem kell mást tenni, mint az egyik sokszög minden oldalának mint szakasznak a másik sokszög minden oldalával való metszéspontját vizsgálni. És, ha vannak metszéspontok, akkor azokat valamilyen módon sorban visszaadni.
Az ezt megvalósító függvényt láthatjuk alább:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
def find_polygons_intersections(polygon1_vertices: Iterable[Vertex], polygon2_vertices: Iterable[Vertex], find_segment_intersection: Callable = intersection_using_xprod) -> Iterable[Point]: """Visszaadja a csúcspontjaival megadott két sokszög metszéspontjait.""" polygon1_vertex_iterator = iter(polygon1_vertices) polygon2_vertex_iterator = iter(polygon2_vertices) # Kinyerjük az első csúcspontokat. polygon1_first_vertex = next(polygon1_vertex_iterator) polygon2_first_vertex = next(polygon2_vertex_iterator) # A sokszögek oldalainak végpontpárjait sorban egymás után szolgáltató iterátorok. vx_pairs_iterator1 = pairwise(chain([polygon1_first_vertex], polygon1_vertex_iterator, [polygon1_first_vertex])) vx_pairs_iterator2 = pairwise(chain([polygon2_first_vertex], polygon2_vertex_iterator, [polygon2_first_vertex])) # Az egyik sokszög minden oldalának a másik sokszög minden oldalával való metszéspont vizsgálata. # Ha van metszéspont, akkor azok eltárolása és visszaadása. return (isect_point for vertex_pair1, vertex_pair2 in product(vx_pairs_iterator1, vx_pairs_iterator2) if (isect_point := find_segment_intersection(*vertex_pair1, *vertex_pair2))) |
Bár ez a megoldás O(n*m) időkomplexitású (ahol n és m a sokszögek éleinek száma), de ha a csúcspontok száma nem túl sok, akkor a futási idő általában elfogadható. Ha a csúcspontok száma nagyon sok, akkor az adott alkalmazáshoz illeszkedő, optimalizált algoritmus szükséges, amelyre vannak kidolgozott módszerek.
Mivel vizuálisan elég könnyen át tudjuk tekinteni, hogy két sokszög mely pontokban metszi egymást, ezért függvényeink tesztelésére egy GUI alkalmazást készítünk, amelynek programkódja a következő:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
class PolygonIntersectionTestApp(tk.Tk): def __init__(self): super().__init__() self.title('Sokszögek metszéspontjai'.upper()) self.canvas = tk.Canvas(self, bg='light yellow', width=500, height=500) self.canvas.pack() self.canvas.bind('<Button 1>', self._draw_point) self.polygons_done: int = 0 button_font = dict(font=('Arial', 12)) self.btn_build_poly1 = tk.Button(self, text="Sokszög megrajzolás", command=self._draw_polygon, **button_font) self.btn_build_poly1.pack(side=tk.LEFT, expand=True) self.btn_calc = tk.Button(self, text='Metszéspontok meghatározása', command=self._show_intersections, **button_font) self.btn_calc.pack(side=tk.LEFT, expand=True) self.btn_clear = tk.Button(self, text='Új rajz', command=self._clear_canvas, **button_font) self.btn_clear.pack(side=tk.LEFT, expand=True) def _draw_point(self, event: tk.Event): """Az egérmutató pozíciójában egy fekete színű pontot rajzol, ha nincs még meg minkét sokszög. Minden egyes pont törölhető, ha a pont felett a jobb egérgombot lenyomjuk. """ if not self.polygons_done == 2: x, y = event.x, event.y r = 3 oid = self.canvas.create_oval(x - r, y - r, x + r, y + r, fill='black', tags=('point',)) self.canvas.tag_bind(oid, '<Button 3>', lambda e: self.canvas.delete(tk.CURRENT)) @staticmethod def _box_center(x1, y1, x2, y2) -> Point: """A bal felső (x1,y1) és jobb alsó (x2, y2) sarokpontok által meghatározott téglalap középpontját adja vissza.""" return (x1 + x2) / 2, (y1 + y2) / 2 def _draw_polygon(self): """A megjelenített pontok mint csúcspontok alapján egy sokszöget rajzol ki. Ezt követően a pontok törlődnek.""" # Összegyújtjük a kirajzolt pontok egyedi azonosítóit. vertex_ids: tuple[int, ...] = self.canvas.find_withtag('point') if vertex_ids: # Meghatározzuk a pontok középpontját, amelyek a sokszög csúcspontjai lesznek. vertices_coords = [self._box_center(*self.canvas.coords(vx_id)) for vx_id in vertex_ids] # A csúcspontok alapján kirajzoljuk a sokszöget. self.canvas.create_polygon(vertices_coords, outline='blue' if self.polygons_done == 0 else 'red', fill='', width=3, tags=('polygon',)) self.polygons_done += 1 # Nyilvántartjuk, hogy hány sokszög készült el. self.canvas.delete('point') # Eltávolítjuk a pontokat. def _show_intersections(self): """Ha a két sokszög ki van rajzolva, akkor megjeleníti azok metszéspontjait, ha vannak.""" if len(polygon_ids := self.canvas.find_withtag('polygon')) == 2: # A sokszög csúcspontjait szolgáltató két iterátor előállítása. polygons_vertices_iterators: Iterator[Iterator[tuple]] = (batched(self.canvas.coords(polygon_id), 2) for polygon_id in polygon_ids) # A csúcspontok ismeretében a metszéspontok meghatározása és kirajzolása. for x, y in find_polygons_intersections(*polygons_vertices_iterators): r = 5 self.canvas.create_oval(x - r, y - r, x + r, y + r, fill='green', outline='blue', tags=('xpoint',)) def _clear_canvas(self): """Törli a megjelenített rajzelemeket.""" self.canvas.delete('polygon', 'point', 'xpoint') self.polygons_done = 0 # Az elkészült sokszögek számlálójának alaphelyzetbe állítása. def run(self): self.mainloop() PolygonIntersectionTestApp().run() |
A tesztalkalmazás elindítása után megjelenő felületen két sokszöget rajzoltathatunk ki. Mindkettőt oly módon, hogy bal egérgomb kattintással kijelöljük a csúcspontokat. Ha a pontok megvannak, akkor a „Sokszög megrajzolás” gomb lenyomásával a sokszög megjelenik. Ha mindkét sokszög megvan, akkor a „Metszéspontok meghatározása” nyomógomb hatására a metszéspontok, ha vannak, megjelennek. Ha másik két sokszöget akarunk vizsgálni, akkor az „Új rajz” gombbal törölhetjük a felületet, és az előbb leírt módon készíthetünk két új sokszöget.
Példaként néhány eredménykép:
Ebben a bejegyzésben többször is használtunk iterálható objektumokat, iterátorokat és generátorokat, valamint az itertools modul iterátorait. Ezekről részleteiben, példákkal magyarázva a Python tudásépítés lépésről lépésre című e-könyvben a „Kérem a következőt! – iterálható objektumok”, a „Kifogyhatatlan sorozatlövők – generátorfüggvények” fejezetekben, valamint a „Készétel fogyasztás – a szabványos könyvtár moduljainak használata” fejezeten belül a „Speciális iterátorok” című alfejezetben lehet olvasni. A futási idő meghatározáshoz a „A programvégrehajtás felfüggesztése és a futási idő mérése” alfejezetet érdemes átnézni. A GUI alkalmazás fejlesztéséhez szükséges ismereteket pedig a „Grafikus felhasználói felület készítése” című fejezetből lehet elsajátítani.