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).

Jogo

Zoals sommigen onder de lezers waarschijnlijk wel weten ben ik bezig aan het project Jogo: “Een spelontwerper om grafsiche games te maken”. Dit project won voirg jaar in eind april de Capgemini OpenSource Award, sindsdien lag het project zo goed als stil.

Sinds een aantal dagen ben ik terug beginnen programmeren, maar dan vanaf een helemaal cleane broncode.
Redenen van deze rewrite:

• De API was slecht
• De code voor de GUI zat zeer onhandig in elkaar
• Er misten een aantal belangrijke features, die moeilijk nog te programmeren waren in deze oude code.

Met de rewrite volg ik een veel schoner ontwikkelingsschema:

1. Eerst wordt de Kern helemaal herschreven, en elke keer als er iets nieuws wordt toegevoegd wordt er meteen een Unit test geschreven.
2. Daarna zal de runtime aan bod komen, mogelijkheid tot automatische tests zal nog onderzocht worden.
3. Daarna pas zal er een GUI worden ontwikkeld, die ook volledig getest gaat worden door LDTP

Doelen van de rewrite:

• Veel stabielere kern/GUI (door de vele tests)
• Veel betere API
• Undo/Redo vanaf het begin
• Debugger voor runtime
• Een volledig nieuwe GUI, die veel beter eruit zal zien dan de vorige
• Plugins voor oa taalgeneratie/compilatie
  Dit zou als verder doel (dus na 0.1) moeten hebben dat niet alleen C#/SDL games kunnen gemaakt worden, maar vanuit een zelfde project ook bijvoorbeeld een Flash versie, of een versie met SVG en javascript direct in de browser te gebruiken.
• …

Momenteel zal deze versie van Jogo 0.5 zijn (waar vroeger alleen nog maar 0.1 was gereleased en 0.2 in ontwikkeling), maar mogelijk wordt dit meteen 1.0

Momenteel is de planning om een basis kern af te hebben tegen het eind van de kerstvakantie. Een eerste bruikbare versie voor de GUI zou dan moeten volgen tegen de paasvakantie, of mogelijk later nog.

Ik zoek ook nog mede geïntresseerden die eventueel nog goede ideeën hebben, of mee willen programmeren.