Ha valakinek minimális konvex befoglaló poligon számító algoritmus kellene ... Sosem lehet tudni ... Mi annak idején OTDK kapcsán foglalkoztunk olyannal, hogy ultrahangos (aztán saját készítésű lézeres) szenzorral térképeztük fel a környezetet. Ott kellett a kapott ponthalmazt vektorizálni, hogy könnyebb legyen kezelni. Akkor ezt nem ismertük, és mindenféle saját algoritmust találtunk ki erre, pedig csak rá kellett volna találni. Így magában persze nem olyan izgalmas (de, az! :)), de mikor a kisautó magától kitalál a labirintusból, az már látványosabb. Ezek alatt meg ilyenek vannak ...
http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan
Nagyon érdekesek ezek a gráfos feladatok. Amikor a Lines windowsos verzióját írtam, akkor kellett ilyen. Az nem bonyolult, csak meg kellett tudni mondani át lehet-e mozgatni a golyót a tábla egyik pontjáról a másikra. Az utat végül nem rajzoltam ki, megálltam annak eldöntésénél, hogy a mozgás lehetséges-e, de a játékhoz ez elég volt.
VálaszTörlés