Polygonen, triangulataties, kapen

Gisteren hadden we op school de wiskunde B dag. De opdracht ging over veelhoeken, triangulaties, kapen, ..... De dag was op zich zeer interessant, maar de opdrachten waren wel zeer moeilijk, het resultaat van onze groep is dan ook wel zeer magertjes.
Voor diegenen die minder goed mee zijn in deze wiskunde even de volgende uitleg:
Een polygoon is gewoon een veelhoek, onze opdracht ging vooral over simpele polygonen (dat zijn veelhoeken die zichzelf niet doorsnijden - de meeste polyonen zijn dus zo). Een triangulatie is het opdelen van een veelhoek in driehoeken die elkaar niet overlappen, en volledig in de veelhoek liggen, en waarvan de hoekpunten, hoeken zijn van de veelhoek zelf. Een kaap is simpelweg een hoek waarvan de 2 buurpunten kunnen verbinden, en de verbindingslijn volledig in de veelhoek ligt.

Zo was er bijvoorbeeld een vraag: "Bereken het aantal mogelijke triangulaties voor een convexe (zonder inspringende hoeken) van een n-veelhoek". Er stond ook de suggestie bij dat je daar een programma voor mocht schrijven, want ik natuurlijk meteen heb gedaan (weliswaar zonder resultaat want het werkte niet).

Vannacht heb ik ook bedacht hoe ik deze kennis nu kan gebruiken in Jogo. In vorige versies van jogo konden objecten met elkaar botsen, maar hadden deze objecten een rechthoekige vorm. Door middel van een object om te zetten naar een veelhoek zouden veel betere botsingsresultaten kunnen worden gevonden. Ik dacht eraan om het op deze manier te doen:

1. Het object (of beter de tekening van het object) wordt omgezet naar een polygoon
2. De polygoon wordt getrianguleerd.
   Deze eerste 2 stappen zouden tijdens het "compileren" van het programma kunnen gebeuren en moeten dus niet supersnel zijn.
3. Tijdens het draaien van het spel wordt voor elk object telkens gecontroleerd of het één of meerdere punten gemeenschappelijk heeft met een ander object (= een botsing). Dit kan gebeuren door dit te doen voor elke 3hoek met elke andere 3hoek (dit is al veel simpeler dan een polygoon op zijn eigen controleren)

Dit is hoe ik het zag. Toen begon ik te denken over punt 2: het trianguleren. Aangezien dat ik gisteren heb geleerd dat je een veelhoek kunt trianguleren door telkens een kaap af te snijden leek mij dat de meest simpele oplossing - mogelijk niet de snelste, maar snelheid is in dat stadium niet superbelangrijk.
Toen dacht ik: hoe herken ik een kaap? Zeer simpel, je pakt een willekeurig punt, je zoekt de 2 buurpunten, je trekt er een lijn tussen, je controleert of die lijn een zijde snijdt, zo niet is het een kaap, anders ga je naar het volgende punt van de polygoon. Toen ging ik over naar punt 3: hoe kan ik controleren of 2 driehoeken "botsen"? Ik bedacht het volgende : je controleert van 3hoek A de 3 zijden die snijden met een van de zijden van 3hoek B.
Toen viel mijn frank (of euro), als ik nu gewoon de zijdes van polygoon van object 1 met de zijdes van object 2, dan moet ik veel minder zijdes controleren dan als ik met 3hoeken werk, dus dat zou sneller moeten zijn. En dan valt een deel van het probleem weg (het trianguleren).