Y-monoton sokszög háromszögesítése

A program egér segítségével megadott y monoton sökszög háromszögesítését végzi el grafikus üzemmódban. A program futásához szükséges az egavga.bgi állomány, melyben a Borland Pascal VGA grafikus üzemmódjának futtatásához szükséges driverek vannak.

A program fordításához szükséges az egavga.bgi, graph.tpu és eger.tpu. A graph.tpu unitban találhatók a Borland Pascal grafikus eljárásai és függvényei, az eger.tpu unitban pedig az egér használatához szükséges eljárások és függvények.

A háromszögesítéshez alkalmazott algoritmus röviden:

1. Meghatározzuk a sokszög jobb illetve bal oldali láncának pontjait, majd rendezzük növekvő sorrendbe az z koordináta szerint

2. Betesszük egy S verembe az első két csúcsot

3. Minden csúcspontra a harmadiktól az utolsó elöttiig ellenőrizzük, hogy azonos lancon van-e a verem tetején levő elemmel

4. Ha különböző láncon vannak, akkor rendre kiveszünk minden csúcsot a veremből, összekötjük az aktuálisan vizsgált ponttal, kivéve a verem legalsó csúcsát (ez már össze van kötve az aktuálisan vizsgált csúccsal) és visszatesszük a verembe az aktuálisan vizsgált csúcsot és az elötte levőt.

5. Ha azonos láncon van a két csúcs, akkor kivesszük az S-ből a legfelső elemet, majd annyi csúcsot veszünk ki rendre az S veremből, ahányat össze lehet kötni az aktuálisan vizsgált csúccsal és összekötjük. Ay utoljára kivett csúcsot visszatesszük averembe és rátesszük az aktuálisan vizsgált elemet.

6. Miután az utolsó elötti csúcsot is megvizsgáltuk, minden verembeli csúcsot kivéve a legalsót és a legfelsőt összekötünk az utolsó csúccsal.

A program bővebb leírása:

Globális változók: gd,gm:integer – a grafikus üzemmód bekapcsolásához, x,z:integer – az egérmutató poziciójának (koordináták) lekérdezésére, n,m:integer – a csúcspontok száma illetve a verem elemeinek száma (a verem magassága), i,lanc:byte – segédváltozók a ciklusokoz, illetve a láncok meghatározására, pont,stack: array[1..100,1..3]of integer – a csúcspontok koordinátáinak illetve láncszámának tárolására (x,y,lánc), stack a verem.

Főprogram: A főprogram a grafikus üzemmód elindításával kezdődik, megjelenítjük az egér mutatót, kezdetben a csúcsok száma 0 és a láncok száma 1. A csúcsok beolvasását egy repeat-until ciklus végzi, melynek akkor lesz vége, ha kattintunk egyet az egér jobb gombjával. Az egér bal gombjának lenyomásakor az egérmutató aktuális pozicióján első kattintáskor egy pont jelenik meg, majd a továbbiakban mindig az utolsó csúcspont kötődik össze az aktuális egérpozición levő ponttal. Az aktuális egérpozició bekerül a pont tőmbbe, minden kattintásra egyel nő a csúcspontok száma (n). Mivel y-monoton sokszőg csúcsait olvassuk be, csak egyszer történhet visszafordulás (lefele haladunk, majd felfele a pontok megadásával, illetve fordítva), ezért a láncok száma minden visszafordulásnál egyel nő, ha kettőnél több lánc van, akkor a sokszög nem y-monoton. Ebben az esetben hibaüzenet jelenik meg a képernyőn és a program bezárúl. A száz ezredmasodpercnyi időzítésre azért van szükség, hogy ne kerüljön be a tömbbe két azonos koordinátájú csúcs. A beolvasás végén összekötjük az utolsó csúcspontot az elsővel. Majd meghívjuk a haromszögesít eljárást, mely a fennti algoritmus alapján van megírva. A haromszögesítés után addig vár a program, amíg az egér jobb gombját le nem nyomják. Ezután lezárjuk a grafikus üzemmódot. A főprogram a Borland Pascal két előre megírt eljárását használja, melyek a Graph.tpu-ban találhatók: putpixel – pont rajzolására és line – vonal rajzolására.

Haromszogesit: az eljárás a fennti algoritmus szerint van megírva. Először rendezzük a pontokat tartalmazó tömböt (rendez eljárás) buborékos rendezéssel, novekvő sorrendben, mert a grafikus üzemmódban az y koordináták fenntről lefele nőnek. Betesszük a verembe a két első pontot (push eljárás). While ciklussal bisztosítjuk minden csúcspont ellenőrzését a harmadiktól az utolsó elöttiig. A pont tömb minden osylopában három elem van: x,y,lanc, igy könnyebben lehet dolgozni az értékekkel. A top eljárás visszatéríti a verem tetején levő csúcspont adatait, a pop eljárással pedig ki veszünk egy elemet a veremből. A rajzolásban két előre megírt Borland Pascal eljárást használunk: line – vonalak rajzolására és setcolor a színek változtatására.