computational geometry (tsz. computational geometries)
A számítógépes geometria (computational geometry) a számítástechnika egy ága, amely geometriai problémák algoritmikus megoldásával foglalkozik. Célja hatékony algoritmusok és adatstruktúrák kidolgozása pontokkal, egyenesekkel, sokszögekkel, görbékkel és más geometriai objektumokkal végzett számításokra.
A számítógépes geometria kulcsfontosságú olyan területeken, mint:
| Fogalom | Leírás |
|---|---|
| Pont | Egy koordináta a térben (x, y) vagy (x, y, z) |
| Vektor | Két pont közötti irány és hossz |
| Egyenes / szakasz | Két pontot összekötő egyenes vagy részlete |
| Sokszög (poligon) | Több pontból álló zárt alakzat |
| Konvex / konkáv | Konvex: nincs „benyomódása”, konkáv: van |
| Belső / külső pont | Egy sokszögön belüli vagy kívüli pont |
Legkisebb konvex sokszög, amely tartalmaz egy pontmennyiséget.
Szükséges pl. konvex burokhoz.
Gyorsabb, mint O(n²): oszd meg és uralkodj → O(n log n)
Megállapítani, hogy két szakasz metszi-e egymást.
Egy pont a sokszög belsejében van-e? Algoritmus: Ray casting, Winding number
Térfelosztás legközelebbi pont szerint → pl. mobilcellák, térképek
Két szakasz (A–B és C–D) akkor metszik egymást, ha:
orient(A, B, C) ≠ orient(A, B, D) és orient(C, D, A) ≠ orient(C, D, B)
A orient(P, Q, R) megmondja, hogy a három pont óra járásával megegyező vagy ellentétes irányban van-e.
| Terület | Példák |
|---|---|
| Robotika | Útvonaltervezés akadályok között |
| GIS (térinformatika) | Térképek, régióhatárok, zónák |
| Grafika / CAD | Modellek összeütközése, vágás |
| Orvosi képfeldolgozás | Térbeli rekonstrukciók (pl. CT) |
| Játékfejlesztés | Látótér, ütközés, navigációs gráfok |
| Nyelv | Könyvtár / eszköz |
|---|---|
| C++ | CGAL (Computational Geometry Algorithms Library) |
| Python | Shapely, SymPy.geometry, SciPy.spatial |
| JavaScript | Turf.js (GIS-hez), Three.js (3D) |
| Java | JTS Topology Suite |
| MATLAB | convhull, voronoi, delaunay függvények
|
A számítógépes geometria a geometriai problémák hatékony algoritmikus megoldásával foglalkozik. Ez a terület kritikus minden olyan alkalmazásnál, ahol a térbeli objektumokkal történő automatikus számítás, vizsgálat vagy interakció szükséges. A témakörben való jártasság elengedhetetlen többek között a játékfejlesztés, robotika, térinformatika és grafikai tervezés területén.