/info/grudat09/points.txt
)
kan ritas så här.
from turtle import * for line in open("points.txt"): x,y = line.split() x = float(x) y = float(y) goto(x,y)I turtle finns bland annat anropen
up(), down(), circle(2)
som
du kan använda för att lyfta och sänka pennan och för att rita
en liten cirkel. Gör det så att du får sju små cirklar.
Tillverka nu en egen klass Point
med fälten x
och y
och metoderna rita()
och ring()
. Den första ritar ett streck till punkten, den andra går
osynligt till punkten och ritar där en ring. I inläsningsslingan
skapar du Point-objekt och pushar på en stack i stället för att
rita. Sedan ska du poppa stacken och för varje punkt anropa
p.ring()
.
Algoritmen Graham scan börjar med att föra
över punkterna till en kö queue
, alla utom punkten
längst till vänster.
Poppa först en punkt och kalla den p0
. Poppa sedan
alla punkter och för över till queue
, men kolla först
att dom ligger till höger om p0
. Annars får punkterna
byta plats, så här enkelt.
if - - -: p0,p = p,p0Om dom har samma x-koordinat väljs den undre som
p0
.
För att se att du gjort rätt kan du tömma kön och för varje
punkt göra en ring och ett streck till p0
. Det blir
en solfjäder med sex streck. Sen kommenterar du bort detta.
Algoritmen fortsätter med att ordna punkterna i kön efter
streckens lutning, nerifrån och upp. För att avgöra vilken av
punkterna p1
och p2
som ska komma först kan
man se på triangeln p0,p1,p2
. Om den gås runt motsols
ska p1
vara först. Du ska definiera en funktion
def wrong(p0,p1,p2)
som returnerar True om dom
går medsols och
alltså p1
och p2
bör byta plats. Ett enkelt
sätt är att beräkna kryssprodukten mellan vektorerna
(a,b)=p1-p0
och (c,d)=p2-p0
, nämligen
a*d-b*c
. Om den är positiv går det medsols.
För sortering behöver du en tom hjälpkö q
.
Ta ut en punkt ur queue
och kalla den p2
. För sedan över alla punkter till
q
men kolla för varje punkt p1
att inte
def wrong(p0,p1,p2)
gäller, för då ska
p1
och p2
byta plats, precis som när du
hittade vänstraste punkten. När queue
är tom är
p2
den översta punkten i solfjädern och den pushar
du på stacken. Sedan kan du sätta queue=q
och så är
det bara att upprepa förfarandet, alltså skapa en tom
hjälpkö, ta ut p2
osv. Iterera tills kön är tom
så ska du ha alla punkter utom p0
i stacken med
den nedersta i solfjädern överst i stacken.
För att kolla att du gjort rätt poppar du stacken och ritar solfjäder som förut. Den koden kommenteras bort sedan.
Nu behövs en till stack, hull
, där punkterna i
convex hull ska hamna. Du kan genast pusha p0
på hull
. Poppa p1
och pusha även den på
hull
, för den måste ingå. För varje punkt p2
i stacken ska du nu kolla om p0,p1,p2
går medsols.
I så fall ska p1
kasseras, p0
pushas
tillbaka på hull
och p2
pushas tillbaka
på stack
. Men om det går motsols kan alla tre
punkterna pushas på hull
.
Rita nu längs alla
Testa också fosterlandets konturer
Med denna labb tackar Grudat för ditt intresse och dina goda insatser.
Om du inte redan gjort webbkursvärderingen är tillfället nog inne nu!
hull
-punkter, men sätt först
color("blue")
. Blev det fint? Byt då punktfilen till
/info/grudat09/pentagon.txt
)
och kör om programmet. Blev det något konstigt? Det beror
i så fall på att din wrong(p0,p1,p2)
inte
fungerar så bra när punkterna ligger på linje, alltså då
a*d=b*c
. I så fall ska det anses som wrong
när punkten p1
ligger mellan dom båda andra. Det
kan räcka att kolla att abs(a)
abs(b)
/info/grudat09/sweden.txt
). Med många punkter är
speed("fastest")
lämpligt.
Löst av ............................................hoppas.....................den.......................
Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 22 november 2009
Tekniskt stöd: <webmaster@nada.kth.se>