Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://uneex.mithril.cs.msu.su/LecturesVMSH/2011-02-02
Äàòà èçìåíåíèÿ: Unknown
Äàòà èíäåêñèðîâàíèÿ: Sun Apr 10 02:48:10 2016
Êîäèðîâêà: UTF-8
LecturesVMSH/2011-02-02 - UNÈX

Êîìáèíàòîðèêà. PyGame

  • {o} ? òåìà ïî Linux

  • <!> ?? íåîáÿçàòåëüíàÿ òåìà

Äîìàøíåå çàäàíèå

  • {i} ? òåîðåòè÷åñêîå çàäàíèå

  • {*} ? íîâàÿ òåìà

  1. Ðåàëèçîâàòü ýôôåêòèâíûé àëãîðèòì äëÿ ëîìàíûõ íà îêðóæíîñòè (çäåñü áóäåò ññûëêà íà ìàòåìàòèêó ñ äîñêè).

  2. {i} Ïîñòàâèòü ñåáå PyGame, îñâîèòüñÿ â äîêóìåíòàöèè

  3. Íà PyGame íàïèñàòü ïðîãðàììó äëÿ ðèñîâàíèÿ ãðàôèêà ôóíêöèè êðàñèâî. Ëèáî ðèñîâàòü ëîìàíóþ, ëèáî çàïîëíÿòü òî÷êè ýêðàíà ñ ïîìîùüþ fill. Ïîñëåäíåå ïðåäïî÷òèòåëüíåå, ò.ê. ðàáîòàåò áûñòðåå.

    1. ñ ïîìîùüþ fill íàðèñîâàòü îòðåçîê íà ýêðàíå.
      1. êàêîé-íèáóäü
      2. òîëùèíîé 2-3 ïèêñåëÿ
      3. äîáàâèòü anti-aliasing (ñãëàæèâàíèå êðàåâ ëèíèè ìåòîäîì äîðèñîâûâàíèÿ ïèêñåëåé ïðîìåæóòî÷íîãî öâåòà)
    2. íàðèñîâàòü ãðàôèê íåëèíåéíîé ôóíêöèè

Î ïðîâåäåíèè ëèíèé (ïî ñóòè ? ïðÿìîóãîëüíèêîâ)

Ðàñòåðèçàöèÿ îòðåçêîâ íà Âèêèïåäèè.  íàøåì ñëó÷àå ýòè àëãîðèòìû íå âïîëíå ïðèãîäíû.

Îáùèé ìåòîä: ðàññìîòðèì äâå ïàðàëëåëüíûå ïðÿìûå (ãðàíèöû ?òîëñòîé? ëèíèè). Òî÷êè ðàñòðà, öåëèêîì ñîäåðæàùèåñÿ ìåæäó ïðÿìûõ, çàêðàñèì ÷åðíèëàìè. Òî÷êè ðàñòðà, ÷àñòè÷íî ëåæàùèå âíóòðè îáëàñòè, çàêðàñèì öâåòîì, ñìåøàííûì èç ÷åðíèë è èñõîäíîãî öâåòà òî÷êè â ïðîïîðöèè, ñîîòâåòñòâóþùåé ïëîùàäè ïåðåêðàøèâàåìîé ÷àñòè òî÷êè.

Åñëè ñ÷èòàòü òî÷êè ðàñòðà êâàäðàòíûìè, ïðèäåòñÿ èìåòü äåëî ñ ïëîùàäüþ 3-,4- è ïÿòèóãîëüíèêîâ (èñõîäíèê êàðòèíêè â ôîðìàòå KSEG):

lines-antialias.png

Îäíàêî âû÷èñëÿòü ïëîùàäü ïîëó÷åííîãî ìíîãîóãîëüíèêà äîâîëüíî ìóòîðíî, ìîæíî ïîñ÷èòàòü òî÷êè ðàñòðà êðóãëûìè (ýòî â ÷åì-òî ïðàâäà) è âû÷èñëÿòü ïëîùàäü ñåãìåíòà (èñõîäíèê êàðòèíêè â ôîðìàòå KSEG):

lines-antialias2.png

Àëãîðèòì ïåðåáîðà òî÷åê âíóòðè îáëàñòè ìîæíî ïîëó÷èòü èç àëãîðèòìà Âó. Äëÿ ïðîñòîòû âû÷èñëåíèÿ çàìåòèì, ÷òî äëÿ ýòîãî àëãîðèòìà ðàçëè÷àþòñÿ 8 íàïðàâëåíèé, èç êîòîðûõ 4 ïîëó÷àþòñÿ èç äðóãèõ 4 ðèñîâàíèåì îò êîíöà ê íà÷àëó (èñõîäíèê êàðòèíêè â ôîðìàòå KSEG):

lines8.png

Íà÷àëî êîîðäèíàò, â ñòèëå PyGame, ëåâûé âåðõíèé óãîë. Äëÿ ïðîñòîòû íà÷àëüíàÿ òî÷êà A ïîìåùåíà â íà÷àëî êîîðäèíàò. Èìååì 4 ðàçëè÷íûõ ïàðàìåòðà àëãîðèòìà (ñëó÷àè AB?, ãäå Y>0 àíàëîãè÷íû B?A):

AB

|X|>|Y|

X™0, Y™0

AB'

|X'|˜|Y'|

X'™0, Y'™0

AB"

|X"|˜|Y'|

X"<0, Y'™0

AB"'

|X"'|>|Y|

X"'<0, Y™0

Âîïðîñû ?÷òî ðèñîâàòü â íà÷àëå è â êîíöå îòðåçêà?? è ?êàê ðèñîâàòü ëèíèè òîëùèíîé < 2**0,5?? íå ðàññìàòðèâàþòñÿ

CategoryClass CategoryVmsh

LecturesVMSH/2011-02-02 (ïîñëåäíèì èñïðàâëÿë ïîëüçîâàòåëü FrBrGeorge 2011-02-09 00:03:36)