Sokszögekkel számos területen találkozhatunk a számítógépes grafikától és a geometriai algoritmusoktól kezdve egészen a matematikai optimalizálásig (konvex optimalizáció). Ezekben az alkalmazásokban gyakran felmerül, hogy egy adott pontsorozat konvex vagy konkáv sokszöget határoz-e meg.
Elsőre a kérdés nem is tűnik bonyolultnak: ránézésre, vizuálisan az emberi szem általában könnyen megállapítja, hogy egy sokszög konvex vagy konkáv. Ha azonban ezt számítógéppel kell ellenőrizni, a feladat korántsem magától értetődő. A programnak ugyanis kizárólag a csúcspontok koordinátáiból kell következtetnie a sokszög alakjára, ezért matematikai szabályokra van szükség, amelyek egyértelműen meghatározzák, mikor tekintünk egy sokszöget konvexnek. Az erre vonatkozó, geometriából ismert definíciókat láthatjuk a következő ábrán.
E meghatározások azonban nem alkalmasak arra, hogy egy csúcspontjaival megadott sokszögről algoritmikusan, programmal eldöntsük, hogy konvex-e. Az 1) esetben ugyanis végtelen sok egyenes metszéspontját kellene vizsgálnunk. A 2) esetben bár a csúcsoknál lévő szögek nagysága kiszámítható lenne, de nehézséget jelent annak eldöntése, hogy a kapott szög a belső szög, vagy a 180°-nál nagyobb, úgynevezett homorúszög.
Megfigyelhetjük azonban, hogy ha egy konvex sokszög csúcsait azonos irányban járjuk be, az oldalak mindig ugyanabba az irányba – vagyis mind balra, vagy mind jobbra – fordulnak. Ez a tulajdonság a konkáv sokszögekre már nem igaz. Ha tehát van módszerünk annak megállapítására, hogy egy oldalt követő csúcspont az adott oldal egyenesének bal vagy jobb oldalára esik, és ezt a vizsgálatot sorban minden oldalra elvégezzük, akkor a sokszög konvexitása egyértelműen meghatározható.
A következő ábrákon bemutatott módszerek eltérő megközelítést alkalmaznak, de ugyanarra a feltételre vezetnek. Az első az egyenes egyenletéből indul ki, míg a második az oldalvektorok vektoriális szorzatait (keresztszorzatait) használja, és a kapott vektorok merőleges komponenseinek (z-komponenseinek) előjeleit vizsgálja.
Mivel a szakirodalomban általában az utóbbi módszert alkalmazzák, a konvexitás ellenőrzésére szolgáló is_convex() nevű függvényben is ezt valósítjuk meg. A függvény definíciója a segédfüggvényekkel együtt alább látható. A működési logika megértését a részletes kommentek segítik.
|
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 |
# Python 3.12+ from math import isclose from typing import Iterable, Literal from itertools import islice, chain, pairwise type RealNum = int | float def sgn(x: RealNum) -> Literal[-1, 0, +1]: """A visszatérési érték +1, ha x> 0, -1, ha x < 0, és 0, ha x nulla.""" return +1 if x > 0 else (-1 if x < 0 else 0) def vector2d_from_points(point_initial: tuple[RealNum, RealNum], point_terminal: tuple[RealNum, RealNum]) -> tuple[RealNum, RealNum]: """Kétdimenziós helyvektort ad vissza a kezdő- és végpontokból.""" return point_terminal[0] - point_initial[0], point_terminal[1] - point_initial[1] def cross_product_z(vector_a: tuple[RealNum, RealNum], vector_b: tuple[RealNum, RealNum]) -> RealNum: """Az x-y síkban fekvő két vektor keresztszorzatának z komponensét adja vissza.""" return vector_a[0] * vector_b[1] - vector_b[0] * vector_a[1] def is_convex(vertices: Iterable[tuple[RealNum, RealNum]]) -> bool: """Visszatérési értéke True, ha az argumentumként megadott csúcspontokkal meghatározott sokszög konvex, egyébként False. Az argumentum bármilyen iterálható objektum lehet, amely legalább három csúcspontot szolgáltat kételemű - (x, y) koordinátapárokat tartalmazó - tuple objektumok formájában. Kivétel keletkezik, ha a csúcspontok száma kevesebb mint három, valamint akkor, ha a csúcspontok egy egyenesbe esnek. A függvény a csúcspontokat nem tárolja, ezért nagyszámú pont esetén is memóriatakarékos a működése. """ vertices_iterator = iter(vertices) first_three_points: list[tuple[RealNum, RealNum]] = list(islice(vertices_iterator, 3)) if len(first_three_points) < 3: raise ValueError('Sokszög meghatározásához legalább három pontot kell megadni.') # Oldalvektorok előállítása a csúcspontokból. vectors = (vector2d_from_points(p1, p2) for p1, p2 in pairwise(chain(first_three_points, vertices_iterator, [first_three_points[0]]))) # Fontos, hogy az utolsó és első vektor keresztszorzatot is képezzük, mert annak előjele is lényeges. # Ezért eltároljuk az első vektort. first_vector = next(vectors) # Az oldalvektorokat páronként sorrendben véve kiszámítjuk a vektoriális szorzatokat. cross_product_z_components = (cross_product_z(v1, v2) for v1, v2 in pairwise(chain([first_vector], vectors, [first_vector]))) # Kiszűrjük a nulla értékű keresztszorzatokat. non_zero_cross_product_z = (cpz for cpz in cross_product_z_components if not isclose(cpz, 0, abs_tol=1e-10)) # Előállítjuk a vektoriális szorzatok z komponensének előjeleit. cross_products_signs = (sgn(cpz) for cpz in non_zero_cross_product_z) # Ellenőrizzük, hogy minden előjel azonos-e, és ennek megfelelő logikai értékkel térünk vissza. # Ha nincs pozitív vagy negatív előjelű keresztszorzat, vagyis a megadott csúcspontok egy egyenesen vannak, akkor # kivételt dobunk. first_sign = next(cross_products_signs, None) if first_sign is not None: return all(sign == first_sign for sign in cross_products_signs) raise ValueError('A pontok egy egyenesen vannak.') |
Ahogy említettük, az ember vizuálisan könnyen meg tudja állapítani, hogy egy sokszög konvex-e. A teszteléshez ezért egy egyszerű GUI alkalmazást készítünk. Ennek felületén bal egérgomb kattintással jelölhetünk ki pontokat, amelyek a sokszög csúcsai lesznek. Ha egy pontot el akarunk távolítani, azt a pont feletti jobb egérgomb kattintással tehetjük meg.
Miután megadtuk a csúcspontokat, a Ctrl + bal egérgomb lenyomásával létrehozhatjuk a sokszöget: a pontok az elhelyezés sorrendjében egyenes szakaszokkal összekapcsolódnak. Ezt követően a program ellenőrzi a konvexitást, és az eredményt egy felirat formájában megjeleníti.
Új teszt esetén a Töröl gomb segítségével eltávolíthatjuk a jelenlegi sokszöget, és új pontokat jelölhetünk ki.
A tesztalkalmazás kódja az alábbi:
|
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 |
import tkinter as tk from itertools import batched # Bal egérgombbal kattintva egy pontot rajzol ki. # Jobb egérgombbal egy pont felett kattintva eltávolítja a pontot. # A Ctrl és bal egérgomb lenyomása után a pontoknak megfelelő sokszöget rajzol a pontok felvitelének sorrendje szerint. # A kirajzolt pont koordinátái alapján ellenőrzi, hogy konvex-e a sokszög és ennek eredményét kiírja. # A Törlés gomb hatásra a sokszög és a szöveg eltávolításra kerül és új sokszöget lehet rajzolni. root = tk.Tk() root.title('Sokszög konvex/konkáv ellenőrzés') canvas_width, canvas_height = 400, 400 cnv = tk.Canvas(root, width=canvas_width, height=canvas_height, bg='light yellow') cnv.pack() def draw_point(event: tk.Event): """Kirajzol egy pontot az egérmutató aktuális pozíciójában.""" _cnv: tk.Canvas = event.widget if _cnv.drawing_points_enabled: x, y = event.x, event.y # Az egérmutató aktuális pozíciójának koordinátái. r = 3 # A pont mint kör sugara pixelben. _cnv.create_oval(x - r, y - r, x + r, y + r, fill='blue', tags=('point',)) def delete_point(event: tk.Event): """Az egérmutató pozíciójában levő pontot eltávolítja.""" _cnv: tk.Canvas = event.widget # Összegyűjtjük a kattintás helye alatt levő grafikus rajzelemeket. Ez jelen esetben legfeljebb egy objektum. item_ids: tuple[int, ...] = _cnv.find_overlapping(event.x, event.y, event.x, event.y) # Ha van rajzelem és az egy kör, akkor azt töröljük. if item_ids and cnv.type(item_id := item_ids[0]) == 'oval': cnv.delete(item_id) # Ha van kör, eltávolítjuk. def draw_polygon(event: tk.Event): """A kirajzolt pontok mint csúcspontok alapján kirajzolja a sokszöget a pontok felvitelének sorrendje szerint.""" _cnv: tk.Canvas = event.widget point_ids = _cnv.find_withtag("point") # Összegyújtjük az összes pont egyedi azonosítóját. # Összegyűjtjük a pontok középpontjait. coords = [] for point_id in point_ids: x1, y1, x2, y2 = _cnv.coords(point_id) cpx, cpy = (x1 + x2) / 2, (y1 + y2) / 2 coords.extend([cpx, cpy]) # A pontok középpontjainak koordinátáival kirajzoljuk a sokszöget. _cnv.create_polygon(coords, fill='', outline='blue', width=2, tags=('polygon',)) # Generálunk egy eseményt, ami azt jelzi, hogy a sokszög ki lett rajzolva. _cnv.event_generate('<<PolygonDrawn>>') # Letiltjuk a további pontok felvitelét, mert a sokszög már kész. _cnv.drawing_points_enabled = False def check_convex(event: tk.Event): """Ellenőrzi, hogy az aktuálisan kirajzolt sokszög konvex-e. Az eredményt egy kirajzolt szöveg közli.""" _cnv: tk.Canvas = event.widget # Meghatározzuk a sokszög csúcspontjainak koordinátáit, és a pontokat kételemű tuple objektumok # sorozataként állítjuk elő. polygon_vertices = (xy for xy in batched(_cnv.coords('polygon'), 2)) # A csúcspontok ismeretében ellenőrizzük, hogy konvex-e a sokszög, és az eredményt egy szöveges grafikus rajzelemen # jelenítjük meg. cnv_center_x, cnv_center_y = _cnv.winfo_width() // 2, _cnv.winfo_height() // 2 _cnv.create_text(cnv_center_x, 0, text='A sokszög konvex' if is_convex(polygon_vertices) else 'A sokszög konkáv', font=('Consolas', 16, 'bold'), anchor='n', tags=('text',)) def clear_canvas(canvas: tk.Canvas): """Törli a vászon tartalmát, vagyis eltávolítja a pontokat, a sokszöget és a szöveges rajzelemet. Lehetővé teszi, hogy a vásznon pontokat lehessen kijelölni. """ canvas.delete('point', 'polygon', 'text') canvas.drawing_points_enabled = True # Globális változó helyett a Canvas példányon új attribútum definiálása (monkey patching) annak jelzésére, hogy # a vásznon lehet-e pontokat kirajzoltatni vagy sem. cnv.drawing_points_enabled = True cnv.bind('<Button 1>', draw_point) # bal egérgomb kattintás esemény és pontrajzolás összerendelés. cnv.bind('<Button 3>', delete_point) # jobb egérgomb kattintás esemény és pont törlés összerendelés. cnv.bind('<Control Button 1>', draw_polygon) # Ctrl + bal egérgomb kattintás esemény és sokszög kirajzolás összerendelés. cnv.bind('<<PolygonDrawn>>', check_convex) # A sokszög rajzolása után generált esemény és konvexitás-ellenőrzés összerendelés. button_clr = tk.Button(root, text='Törlés', font=('Helvetica', 14), command=lambda: clear_canvas(cnv)) button_clr.pack(fill=tk.BOTH) tk.mainloop() |
Két eredményképet a következő ábrán láthatunk.
Ebben a bejegyzésben számos helyen 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. 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.