Pinta-ala-algoritmi · 2020 · syksy

Tason monikulmio voidaan esittää järjestettynä listana $[(x_1,y_1), \ldots, (x_n,y_n)]$ kärkipisteitä niin, että monikulmion reuna saadaan yhdistämällä peräkkäiset kärkipisteet sekä ensimmäinen ja viimeinen kärkipiste janoilla. Oletetaan, että monikulmion reuna ei leikkaa itseään. Käytössä on menetelmä, joka laskee annetun kolmion pinta-alan, ja se halutaan yleistää monikulmioille. 1. Piirrä tarkka kuva monikulmiosta, joka vastaa listaa $[(2,2), (3,-1), (5,2), (7,3), (4,6)]$. (2 p.) 2. Terje ehdottaa seuraavaa algoritmia monikulmion pinta-alan määrittämiseksi: - Valitaan satunnainen kärkipiste. - Piirretään siitä janat kaikkiin muihin kärkiin, jolloin muodostuu joukko kolmioita. - Lasketaan näiden kolmioiden pinta-alat yhteen. Anna esimerkki monikulmiosta, jolle algoritmi antaa väärän pinta-alan ja toinen esimerkki sellaisesta monikulmioista, jonka pinta-alan algoritmi antaa oikein. (5 p.) 3. Aale ehdottaa seuraavaa toimintaohjetta monikulmion pinta-alan määrittämiseksi: - Jaetaan monikulmio kolmioihin yhdistämällä sopivasti kärkipisteitä. - Lasketaan yhteen näiden kolmioiden pinta-alat. Mitä puutteita Aalen ehdotuksessa on, eli miksi tämä ei ole algoritmi? (5 p.)