Та одоо юу харж байна вэ? Хэрэв та биш бол параллель ертөнц, бүгд вектор мониторын ард сууж байгаа газар, дараа нь таны өмнө растер зураг. Энэ зурвасыг хараарай: /. Хэрэв та монитор руу ойртвол вектор шугам мэт дүр эсгэхийг оролдож буй пикселийн алхмуудыг харж болно. Энэ зорилгоор янз бүрийн растерчлалын алгоритмууд байдаг, гэхдээ би растер координат дахь вектор сегментийн ойролцоо утгыг олдог Bresenham алгоритм ба Y алгоритмын талаар ярихыг хүсч байна.
Би барилгын төлөвлөгөөний процедурын генератор дээр ажиллаж байхдаа растержуулалтын асуудалтай тулгарсан. Би өрөөний ханыг хоёр хэмжээст массивын эсүүдээр дүрслэх хэрэгтэй болсон. Хэрэв орон зайг хуваах аргыг хэрэглэвэл физикийн тооцоолол, зам хайх алгоритм эсвэл гэрэлтүүлгийн тооцоололд ижил төстэй асуудлууд тулгарч болно. Растерчлалын алгоритмтай танилцах нь хэзээ нэгэн цагт хэрэг болно гэж хэн санах билээ?
Брезенхэмийн алгоритмын ажиллах зарчим нь маш энгийн. Хэсэг ба түүний анхны координатыг ав x. Циклийн х дээр бид сегментийн төгсгөлд нэг нэгээр нь нэмнэ. Алхам бүрт алдааг тооцдог - бодит координатын хоорондох зай yэнэ байршилд болон хамгийн ойрын сүлжээний үүрэнд. Хэрэв алдаа нь нүдний өндрийн хагасаас хэтрэхгүй бол түүнийг бөглөнө. Энэ бол бүхэл бүтэн алгоритм юм.
Энэ бол алгоритмын мөн чанар байсан бөгөөд бодит байдал дээр бүх зүйл иймэрхүү харагдаж байна. Нэгдүгээрт, налууг тооцоолно (y1 - y0)/(x1 - x0). Сегментийн эхлэлийн цэг дээрх алдааны утга (0,0) хүлээн зөвшөөрсөн тэгтэй тэнцүүэхний нүд дүүрсэн байна. Дараагийн алхамд налууг алдаа дээр нэмж, алдаа бага байвал түүний утгыг шинжилнэ 0.5 , дараа нь нүд дүүрнэ (x0+1, y0), хэрэв илүү бол нүд дүүрнэ (x0+1, y0+1)алдааны утгаас нэгийг хасна. Доорх зурган дээр шаррастержуулалтын өмнөх шугамыг ногоон, улаанаар харуулсан - хамгийн ойрын нүд хүртэлх зай. Налуу нь зургаагийн нэгтэй тэнцүү, эхний алхамд алдаа нь налуутай тэнцүү болж, бага байна 0.5 , энэ нь ординат хэвээр байна гэсэн үг. Шугамын дунд хэсэгт алдаа нь шугамыг давж, түүнээс нэгийг нь хасч, шинэ пиксел нь илүү өндөр өснө. Сегментийн төгсгөл хүртэл үргэлжилнэ.
Бас нэг нюанс. Хэрэв сегментийн тэнхлэг дээрх проекц xтэнхлэг дээр бага проекц yэсвэл сегментийн эхлэл ба төгсгөлийг сольсон тохиолдолд алгоритм ажиллахгүй. Үүнээс урьдчилан сэргийлэхийн тулд та векторын чиглэл ба түүний налууг шалгаж, шаардлагатай бол сегментийн координатыг сольж, тэнхлэгүүдийг эргүүлж, эцэст нь бүгдийг нэг эсвэл дор хаяж хоёр тохиолдол болгон багасгах хэрэгтэй. Хамгийн гол нь зурахдаа тэнхлэгүүдийг байрандаа буцааж өгөхөө мартаж болохгүй.
Тооцооллыг оновчтой болгохын тулд бүх бутархай хувьсагчдыг үржүүлэх аргыг ашиглана уу dx = (x1 - x0). Дараа нь алхам бүрт алдаа өөрчлөгдөнө dy = (y1 - y0)оронд нь налуугэх мэт dxнэгний оронд. Та мөн логикийг бага зэрэг өөрчилж, хил хязгаарыг тэглэхийн тулд алдааг "нүүлгэж", алдааны тэмдгийг шалгаж болно.
Bresenham алгоритмыг ашиглан растер шугам зурах код нь иймэрхүү харагдах болно. Википедиагийн псевдокодыг C# руу хөрвүүлсэн.
void BresenhamLine(int x0, int y0, int x1, int y1) ( var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); // х тэнхлэгийн дагуу сегментийн өсөлтийг шалгана уу. ба y тэнхлэгийн дагуу / / Хэрэв хазайлтын өнцөг хэт том бол шугамыг диагональаар тусгах (эгц) ( Swap(ref x0, ref y0); // Координатыг холих нь дараах байдлаар хийгддэг. тусдаа функц for beauty Swap(ref x1, ref y1);< y1) ? 1: -1; // Выбираем направление роста координаты y
int y = y0;
for (int x = x0; x <= x1; x++)
{
DrawPoint(steep ? y: x, steep ? x: y); // Не забываем вернуть координаты на место
error -= dy;
if (error < 0)
{
y += ystep;
error += dx;
}
}
}
) // Хэрэв шугам зүүнээс баруун тийш өсөхгүй бол (x0 > x1) бол сегментийн эхлэл ба төгсгөлийг солино ( Swap(ref x0, ref x1); Swap(ref y0, ref y1); ) int dx = x1 - x0;
int dy = Math.Abs(y1 - y0);
int алдаа = dx / 2; // Энэ нь int ystep = (y0) нэмэлт бутархайг арилгахын тулд dx-ээр үржүүлсэн оновчлолыг ашигладаг.< 0) { radiusError += 2 * y + 1; } else { x--; radiusError += 2 * (y - x + 1); } } }
Одоо Ву Сяолины гөлгөр шугам зурах алгоритмын тухай. Энэ нь алхам бүрт шугаманд хамгийн ойр байгаа хоёр пикселийн тооцоог хийж, зайнаас хамааран өөр өөр эрчимтэйгээр будсанаараа ялгаатай. Пикселийн дундыг яг гатлах нь 100% эрчимийг өгдөг; хэрвээ пиксел нь 0.9 пикселийн зайд байвал эрчим нь 10% болно. Өөрөөр хэлбэл, эрчмийн зуун хувь нь вектор шугамыг хоёр талдаа хязгаарлах пикселүүдийн хооронд хуваагдана.
Дээрх зурган дээр улаан ба ногоонхоёр хөрш пиксел хүртэлх зайг харуулав.
Алдааг тооцоолохын тулд та хөвөгч цэгийн хувьсагчийг ашиглаж, алдааны утгыг бутархай хэсгээс авч болно.
Ву Шиаолины C# хэл дээрх гөлгөр шугамын жишээ код.
private void WuLine(int x0, int y0, int x1, int y1) ( var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); if (эгц) ( Swap(ref x0, ref y0) ); Энэ функц нь эгц DrawPoint (эгц, x1, y1, 1) хэмжигдэхүүнээс хамаарч координатыг автоматаар өөрчилдөг. // Сүүлийн аргумент нь нэг флотын эрчмийг dx = x1 - x0 float dy = y1 - y0; float y = y0 + градиент (var x = x0 + 1; x<= x1 - 1; x++)
{
DrawPoint(steep, x, (int)y, 1 - (y - (int)y));
DrawPoint(steep, x, (int)y + 1, y - (int)y);
y += gradient;
}
}
Хэрэв та ирээдүйд торон дээр ажиллаж байгааг олж мэдвэл хэсэгхэн зуур бодоод үзээрэй, магадгүй та дугуйг дахин зохион бүтээж байгаа бөгөөд та үүнийг мэдэхгүй ч пикселтэй ажиллаж байгаа байх. Эдгээр алгоритмуудын өөрчлөлтийг тоглоомонд ашиглан газрын зураг дээрх нэгжийн урд байгаа нүдийг хайх, буудлагын цохилтын талбайг тооцоолох, объектуудыг сайхан зохион байгуулах боломжтой. Эсвэл та доорх линкээс програмын адил шугам зурж болно.
Сургуулийн геометрийн хичээлийн нэлээд хэсэг нь барилгын асуудалд зориулагдсан байдаг. Геометрийн дүрсийг бүтээх алгоритмтай холбоотой асуултууд эртний математикчдын сонирхлыг татдаг байв. Хожмын судалгаанууд нь математикийн үндсэн асуултуудтай нягт холбоотой болохыг харуулсан (өнцгийн гурвалсан хэсэг ба тойргийн квадратын сонгодог бодлогуудыг эргэн санахад хангалттай). Компьютер гарч ирсэн нь математикчдад компьютерийн өмнөх эрин үед гарч ирж байгаагүй цоо шинэ асуултуудыг тавьжээ. Эдгээрт энгийн график объектууд болох шугам, тойрог үүсгэх даалгаврууд орно.
Аливаа геометрийн дүрсийг хавтгай дээрх цэгүүдийн багц гэж тодорхойлж болно. Геометрийн хувьд энэ багц нь дүрмээр бол хязгааргүй; сегмент хүртэл хязгааргүй олон цэгүүдийг агуулна.
Компьютер графикийн хувьд байдал өөр байна. Бүх дүрсийн үндсэн бүрэлдэхүүн хэсэг болох цэг нь бодит физик хэмжигдэхүүнийг олж авдаг бөгөөд "энэ зураг хэдэн оноотой вэ?" гэх мэт асуултуудыг олж авдаг. хэн ч гайхахгүй. Бүх зүйлийг харьцуулж, хэмжиж, тоолж болох хязгаарлагдмал ертөнцөд бид өөрсдийгөө олдог. Тэр ч байтугай "цэг" гэдэг үг нь өөрөө ховор хэрэглэгддэг. Үүнийг пиксел (пиксел - зургийн элементээс - зургийн элемент) гэсэн нэр томъёогоор сольсон. Хэрэв та дэлгэцийн дэлгэцийг томруулдаг шилээр харвал нүцгэн нүдэнд хатуу мэт харагдах дүрсний хэсэг нь салангид пикселийн багцаас бүрддэг болохыг харж болно. Гэсэн хэдий ч бага нарийвчлалтай дэлгэц дээр үүнийг томруулдаг шилгүйгээр ажиглаж болно.
Пикселийг хуваах боломжгүй, учир нь энэ нь зургийн хамгийн бага элемент юм - "хоёр ба хагас пиксел" гэж байдаггүй. Тиймээс, компьютерийн график дээр бид цэгүүд дээр байрлуулсан бүхэл тоон координатын сүлжээтэй байдаг. Компьютерийн графикт үйлчилдэг бүх алгоритмууд энэ нөхцөл байдлыг харгалзан үзэх ёстой.
Асуудлын өөр нэг тал бий. Та алим идмээр байна гэж бодъё. Та алимыг бүхэлд нь идэх үү эсвэл 2 хэсэг болгон хувааж, тус тусад нь идэх үү танд хамаагүй юу? Хэрэв алим хангалттай амттай бол та хоёр сонголтыг дуртайяа зөвшөөрөх болно. Харин программист хүний нүдээр харахад сайхан бүхэл бүтэн алимыг хоёр хуваавал маш том алдаа хийж байна гэсэн үг. Эцсийн эцэст, гайхамшигтай бүхэл тооны оронд та хоёр бутархайтай харьцах хэрэгтэй бөгөөд энэ нь хамаагүй муу юм. Үүнтэй ижил шалтгаанаар 1 + 1 = 2 ба 1.5 + 0.5 = 2 гэсэн хоёр тэгшитгэлээс програмист үргэлж эхнийхийг нь сонгох болно - учир нь энэ нь эдгээр эвгүй бутархай тоог агуулаагүй болно. Энэ сонголт нь хөтөлбөрийн үр ашгийг нэмэгдүүлэхтэй холбоотой юм. Бидний хувьд давтан ашиглах шаардлагатай энгийн график объектуудыг бүтээх алгоритмын талаар ярихдаа үр ашиг нь зайлшгүй шаардлага юм. Ихэнх микропроцессоруудад зөвхөн бүхэл тоон арифметик байдаг ба бодит тоон дээр ажиллах хүчин чадал байдаггүй. Мэдээжийн хэрэг, ийм үйлдлүүд хэрэгждэг, гэхдээ нэг үйлдэл нь компьютерээс хэдэн арван ба түүнээс дээш тушаалуудыг гүйцэтгэхийг шаарддаг бөгөөд энэ нь алгоритмын гүйцэтгэлд ихээхэн нөлөөлдөг.
Энэхүү нийтлэл нь програмчлалын урлагийн шилдэг бүтээлүүдийн нэг болох Брезенхамын санал болгосон тойрог барих алгоритмыг авч үзэхэд зориулагдсан болно. Төв болон радиусын координатыг ашиглан бүхэл тооны координатын сүлжээнд тойрог байгуулах аргыг боловсруулах шаардлагатай. Мөн бид алгоритмын гүйцэтгэлийн хугацааг аль болох багасгах ёстой бөгөөд энэ нь биднийг аль болох бүхэл тоогоор ажиллахад хүргэдэг. Бидэнд ямар график хэрэгслүүд байгаа вэ? Бараг байхгүй. Мэдээжийн хэрэг, бид дэлгэцийн зөв газарт цэг (пиксел) байрлуулах чадвартай байх ёстой. Жишээлбэл, Borland програмчлалын хэл нь putpixel процедурыг агуулдаг бөгөөд үүний тусламжтайгаар та хүссэн координат, өнгө бүхий дэлгэцэн дээр цэг үлдээж болно. Тодорхой байхын тулд өнгө нь бидэнд хамаагүй, цагаан өнгөтэй байг.
1. Та юугаа орхих хэрэгтэй вэ...
Сангийн хувьд бид хязгаарлагдмал биш гэж төсөөлөөд үз дээ. Бид зөвхөн бутархай тоонуудтай ажиллахаас гадна трансцендент тригонометрийн функцуудыг ашиглах боломжтой (дашрамд хэлэхэд энэ нь ийм тооцоолол хийдэг математикийн сопроцессороор тоноглогдсон машинуудад боломжтой юм). Даалгавар ижил хэвээр байна - тойрог барих. Бид юу хийх гэж байна? Тойргийг параметрийн дагуу тодорхойлсон томьёог бид санаж байгаа байх. Эдгээр томьёо нь маш энгийн бөгөөд тригонометрийн функцүүдийн тодорхойлолтоос шууд авч болно. Тэдний хэлснээр радиусын тойрог Рцэг дээр төвтэй ( x 0 , y 0) цэгүүдийн багц гэж тодорхойлж болно М(x, y), координатууд нь тэгшитгэлийн системийг хангадаг
| м | x = x 0 + Ручир нь а y = y 0 + Рсина, |
a O = 2 x 2 би+1 +2y 2 би+1 +4x би+1 -2y би+1 +3-2Р 2 = 2(x i+1) 2 +2y i 2 +4(x i+1)-2y i+3-2Р 2 = D би +4x би +6.
Д би+1 [хамт y би+1 = y i-1] = 2x 2 би+1 +2y 2 би+1 +4x би+1 -2y би+1 +3-2Р 2 = 2(x i+1) 2 +2(y i-1) 2 +4(x i+1)-2(y i-1)+3-2Р 2 = D би +4(x i-y i)+10. Одоо бид D-ийн давтагдах илэрхийлэлийг олж авлаа би D-ээр дамжуулан +1 би, энэ нь D 1 (эхлэх цэг дэх хяналтын утгыг) олж авахад үлддэг. Үүнийг давтан авах боломжгүй, учир нь өмнөх утга нь тодорхойлогдоогүй, гэхдээ үүнийг хялбархан шууд олох боломжтой. x 1 = 0, y 1 = РЮ Д 1 1 = (0+1) 2 +( Р-1) 2 -Р 2 = 2-2Р, D 1 2 = (0+1) 2 + Р 2 -Р 2 = 1 D 1 = D 1 1 + D 1 2 = 3-2 Р. Тиймээс, bres_circle-д хэрэгжсэн тойрог байгуулах алгоритм нь цэгүүдийг дараалан сонгоход суурилдаг; хяналтын утгын тэмдгээс хамаарч D бидараагийн цэгийг сонгож, шаардлагатай бол хяналтын утгыг өөрөө өөрчилнө. Процесс нь цэгээс эхэлдэг (0, r), сим процедурын тогтоосон эхний цэг нь координаттай ( xc, yc+r). At x = yпроцесс дуусна. Хэрэв орон зай салангид биш юм бол яагаад Ахиллес яст мэлхийг гүйцэж түрүүлсэн бэ? Хэрэв орон зай салангид байвал бөөмс Брезенхэмийн алгоритмыг хэрхэн хэрэгжүүлэх вэ? Орчлон ертөнц бүхэлдээ ямар байдаг, ялангуяа түүний ажлын хуулиудын талаар би удаан хугацааны турш бодож байсан. Заримдаа Википедиа дээрх зарим физик үзэгдлийн тайлбар нь энэ талбараас тийм ч холгүй хүмүүст ч ойлгомжгүй хэвээр байх нь нэлээд будлиантай байдаг. Түүгээр ч барахгүй над шиг хүмүүс азгүй байсан - ядаж энэ нутгаас маш хол байсан хүмүүс. Гэсэн хэдий ч програмист хүний хувьд би бараг өдөр бүр арай өөр хавтгай - алгоритмтай тааралддаг. Тэгээд нэг өдөр консол дээр ямар нэгэн 2D физикийг хэрэгжүүлэх явцад би: "Гэхдээ Ертөнц бол үндсэндээ үл мэдэгдэх хэмжээстэй ижил консол юм. Энэ консолын дэлгэцэн дээрх шугаман хөдөлгөөний хувьд бөөмс нь Бресенхам алгоритмыг хэрэгжүүлэх ёсгүй гэж үзэх үндэслэл байна уу? Тэгээд ямар ч шалтгаан байхгүй юм шиг байна. Брезенхэмийн алгоритм гэж юу болох, энэ нь физиктэй хэрхэн холбогдож болох, энэ нь түүний тайлбарт хэрхэн нөлөөлж болохыг сонирхож буй хэн бүхэн мууранд тавтай морилно уу. Магадгүй та параллель орчлон ертөнцийн оршин тогтнох шууд бус баталгааг олох болно. Эсвэл бүр орчлон ертөнцүүд хоорондоо үүрлэсэн байдаг. Брезенхэмийн алгоритмЭнгийнээр хэлбэл, алаг дэвтрийн хуудсан дээр нэг нүдний зузаантай зураас зурахын тулд дараалсан нүднүүдийг зурах хэрэгтэй. Тэмдэглэлийн дэвтрийн хуудасны хавтгай нь нүдэнд салангид байна гэж үзье, өөрөөр хэлбэл зэргэлдээх нүдний хоёр талыг будаж, 0.5-ийн зөрүүтэй нүдийг будсан гэж хэлж болохгүй, учир нь салангид байх нь ийм үйлдэл хийхийг зөвшөөрөхгүй гэсэн үг юм. Тиймээс нүднүүдийг дараалан зурснаар та хүссэн уртын сегментийг авах болно. Одоо та үүнийг ямар ч чиглэлд 45 градус эргүүлэх хэрэгтэй гэж төсөөлөөд үз дээ - одоо та нүдийг диагональ байдлаар будах болно. Үндсэндээ энэ нь бидний тархи хоёр энгийн функцийг ашигладаг.F(x) = 0 F(x) = x F(x) = x * бор(55) Энэхүү аглоритмийг 1962 онд Жек Бресенхэм IBM-д ажиллаж байхдаа боловсруулсан. Энэ нь үйлдвэрлэлийн тоног төхөөрөмжөөс эхлээд OpenGL хүртэлх олон хэрэглээний болон системийн системд виртуал графикийг хэрэгжүүлэхэд ашиглагдаж байна. Энэ алгоритмыг ашиглан тухайн шугамын байрлаж буй хавтгайн салангид байдлын өгөгдсөн түвшинд өгөгдсөн шугамын хамгийн тохиромжтой ойролцоо утгыг тооцоолох боломжтой. Ерөнхий тохиолдолд Javascript дээр хэрэгжүүлэх var draw = (x, y) => ( ... ); // цэг зурах функц var bresenham = (xs, ys) => ( // xs, ys нь массив бөгөөд үүний дагуу deltaX = xs - xs, deltaY = ys - ys, алдаа = 0, deltaError = deltaY, y = ys ; for (x = xs; x<= xs; x++) {
draw(x, y);
error += deltaError;
if ((2 * error) >= deltaX) ( y -= 1; алдаа -= deltaX; ); ); ); Одоо биднийг хүрээлж буй орон зай нь салангид хэвээр байна гэж төсөөлөөд үз дээ. Түүнээс гадна юу ч, бөөмс, зөөгч, Хиггсийн талбай эсвэл өөр зүйлээр дүүрсэн эсэх нь хамаагүй - тодорхой ойлголт байдаг.хамгийн бага тоо хэмжээ орон зай, үүнээс бага зүйл юу ч байж чадахгүй. Энэ нь харьцангуй эсэх, харьцангуйн онолын зөв эсэх нь хамаагүй - хэрэв орон зай муруй бол орон нутгийн хувьд муруй байгаа газарт энэ нь салангид хэвээр байх болно, гэхдээ өөр байрлалаас харахад энэ нь тэнд байгаа мэт санагдаж болох юм. үүнтэй ижил өөрчлөлт байсанхамгийн бага босго аль ч чиглэлд. Энэ таамаглалаар аливаа үзэгдэл, аж ахуйн нэгж, дүрэм нь материйн бөөмс болон харилцан үйлчлэлийн тээвэрлэгчдийн аль алиных нь аль алиных нь хөдөлгөөнд Брезенхамын алгоритмыг хэрэгжүүлэх ёстой болох нь харагдаж байна. Энэ нь бичил ертөнц дэх бөөмсийн хөдөлгөөний квантчлалыг тодорхой хэмжээгээр тайлбарладаг - тэдгээр нь огторгуйн нэг хэсгээс нөгөө хэсэг рүү "цацах"гүйгээр үндсэндээ шугаман байдлаар хөдөлж чадахгүй, учир нь орон зай огт салангид биш болох нь тодорхой болсон. Орон зайн салангид байдлын өөр нэг шууд бус баталгаа нь дээр дурдсан үндэслэлээр хийсэн дүгнэлт байж болно: хэрэв ажиглагдсан масштабыг тодорхой хэмжээгээр бууруулснаар Евклидийн геометрийг ашиглан дүрслэх чадвараа алдвал хамгийн бага зайд байх нь ойлгомжтой. босго давсан, аргаодоо ч гэсэн сэдэв байх ёстой. Ийм геометрт нэг параллель шугам нь анхны шулуунд хамааралгүй цэгийг дайран өнгөрч буй нэгээс олон шулуунтай тохирч болно, эсвэл ийм геометрт шугамын параллелизм, тэр ч байтугай шугамын тухай ойлголт огт байдаггүй, гэхдээ Хамгийн бага уртаас бага хэмжээтэй объектын геометрийг дүрслэх таамаглалаар төсөөлж болох арга байдаг. Та бүхний мэдэж байгаагаар ийм геометрийг мэдэгдэж буй хамгийн бага босго дотор дүрслэх боломжтой гэж үздэг нэг онол байдаг. Энэ бол хэлхээний онол юм. Энэ нь оршихуйг урьдчилан таамаглаж байна ямар нэг зүйл, тайлбар болон тайлбараас хамааран 10/11/26 хэмжигдэхүүнээр эрдэмтдийн утас буюу branes гэж нэрлэдэг. математик загвар. Би хувьдаа бүх зүйл ойролцоогоор ийм байгаа юм шиг санагдаж байгаа бөгөөд миний үгсийг батлахын тулд би чамтай бодлын туршилт хийх болно: хоёр хэмжээст хавтгай дээр, түүний геометр нь бүрэн "Евклидийн" дээр дурдсан дүрэм үйлчилдэг: дамжуулан нэг цэг дээр та зөвхөн нэг шулуун шугамыг өгөгдсөнтэй параллель зурж болно. Одоо бид энэ дүрмийг хэмждэг гурван хэмжээст орон займөн бид авдаг хоёрүүнээс үүдэн гарсан шинэ дүрэм:
Зэрэгцээ болон үүрлэсэн орчлон ертөнцүүд үү?Эртний философичид зан төлөвийг атомын загвараас харж байсан байж магадгүй юм селестиел биетүүдхарин ч эсрэгээрээ үнэнээс тийм ч хол байсан гэж хэлж байсан хүмүүсээс тийм ч хол байсангүй бүрэн утгагүй зүйл. Эцсийн эцэст, хэрэв та бүх зүйлээс өөрийгөө чөлөөлвөл мэдлэгба логик үндэслэлтэй - онолын хувьд доод хязгаар нь бидний мэддэг Евклидийн геометрийн үйлдлийг хязгаарлахын тулд бидний зохион бүтээсэн уран зохиолоос өөр зүйл биш юм. Өөрөөр хэлбэл, Планкийн уртаас бага, тодорхой хэлбэл, бүх зүйл бодит Планк урт, зүгээр л Евклидийн геометрийн аргаар тооцоолох боломжгүй, гэхдээ энэ нь байхгүй гэсэн үг биш юм! Эндээс харахад брень бүр олон ертөнцийн багц бөгөөд Планкийн уртаас үл мэдэгдэх X хүртэлх зайд бодит байдлын геометр нь Планкийн уртаас доош Евклид хэлбэртэй байдаг - жишээлбэл, Лобачевскийн геометр эсвэл бөмбөрцөг хэлбэртэй байдаг. геометр, эсвэл өөр нэг нь бидний нислэгийг уран зөгнөлөөр хязгаарлахгүйгээр давамгайлдаг бөгөөд X хязгаараас дээш - жишээлбэл, Десаргусын бус ба бөмбөрцөг геометрийн аль алинд нь. Зүүдлэх нь хор хөнөөлгүй - хэрэв тийм биш бол та хэлж болно квант хөдөлгөөн, шугаман (бичил ертөнцийн түвшинд квантлагдсан хэвээр байгаа) тухай дурдахгүй бол бөөмс нь хэрэв орон зай нь салангид байвал Брезенхам алгоритмыг хэрэгжүүлэх ёстой.Өөрөөр хэлбэл, Ахиллес яст мэлхийг хэзээ ч гүйцэхгүй, эсвэл бид матрицад, бүх ажиглаж болох ертөнц болон алдартай физик, хамгийн их магадлалтай - бодит байдлын боломжит олон янз байдлын асар том далайд дусал л. Брезенхэмийн алгоритм нь өгөгдсөн хоёр цэгийн хоорондох шулуун шугамын ойролцоо утгыг олж авахын тулд хоёр хэмжээст растер дээрх аль цэгүүдийг сүүдэрлэх шаардлагатайг тодорхойлдог алгоритм юм. Сегментийг (x0,y0) ба (x1,y1) гэсэн хоёр цэгийн хооронд зурсан бөгөөд эдгээр хосуудад багана ба мөрийг тус тус зааж, тоо нь баруун ба доошоо нэмэгддэг. Эхлээд бид шугам доошоо баруун тийшээ явж, хэвтээ зай x1 − x0 нь босоо зай y1 − y0-аас давсан гэж үзэх болно, өөрөөр хэлбэл. хэвтээ шугамын налуу нь 45 ° -аас бага байна. Бидний зорилго бол х0-оос x1-ийн хоорондох х багана бүрийн хувьд y-ийн аль мөр шулуунд хамгийн ойр байгааг тодорхойлж (x,y) цэг зурна. Ерөнхий томъёоХоёр цэгийн хоорондох шугамууд: Бид x баганыг мэддэг тул y мөрийг бүхэл тоо болгон бөөрөнхийлсөнөөр олж авна дараагийн утга:
Гэхдээ энэ илэрхийллийн утгыг нарийн тооцоолох шаардлагагүй. y нь y0-аас өсөхөд хангалттай бөгөөд алхам бүрт бид x дээр нэгийг нэмж, налуугийн утгыг y дээр нэмнэ.
үүнийг урьдчилан тооцоолж болно. Түүнээс гадна, алхам бүрт бид хоёр зүйлийн аль нэгийг хийдэг: бид ижил y-г хадгалах эсвэл 1-ээр нэмэгдүүлэх. Эдгээр хоёрын алийг нь сонгох вэ гэдгийг алдааны утгыг хянах замаар шийдэж болох бөгөөд энэ нь хоорондох босоо зай гэсэн үг юм одоогийн үнэ цэнэ y ба яг үнэ цэнэОдоогийн x-ийн хувьд y. Бид x-ийг нэмэгдүүлэх болгонд алдааны утгыг дээр өгөгдсөн налуу s-ийн хэмжээгээр нэмэгдүүлнэ. Хэрэв алдаа 0.5-аас их байвал шугам дараагийн y-д ойртох тул алдааны утгыг 1-ээр багасгахын зэрэгцээ у-г нэгээр нэмэгдүүлнэ. Доорх алгоритмыг хэрэгжүүлэхэд plot(x,y) цэгийг зурж, abs хийнэ. буцаж ирдэг үнэмлэхүй үнэ цэнэтоо: функцмөр(x0, x1, y0, y1) int Deltax:= abs(x1 - x0) int deltay:= abs(y1 - y0) жинхэнэалдаа: = 0 жинхэнэ deltaerr:= deltay / deltax int y:=y0 төлөө x -аас x0 руу x1 алдаа:= алдаа + deltaerr хэрэвалдаа >= 0.5 алдаа: = алдаа - 1.0 Сегментийн эхлэлийг координат (X 1,Y 1), төгсгөлийг (X 1,X 2) болго. гэж тэмдэглэе Dx=(X 2 -X 1),dy=(Y 2 -Y 1) . Ерөнхий байдлыг алдалгүйгээр бид сегментийн эхлэл нь координатын гарал үүсэлтэй давхцаж, шулуун шугам нь хэлбэртэй байна гэж таамаглах болно. Хаана. Бид үүнд итгэдэг эхлэх цэгзүүн талд байна. (i-1)-р алхам дээр сегментийн одоогийн цэгийг P i -1 =(r,q) гэж үзье. Дараагийн цэгийн сонголт S i эсвэл T i нь ялгааны (s-t) тэмдэгээс хамаарна. Хэрэв (s-t)<0 , то P i =T i =(r+1,q) и тогда X i +1 =i+1;Y i +1 =Y i , хэрэв (s-t)≥0 бол P i =T i =(r+1,q+1) дараа нь X i +1 =i+ 1 ; Y би +1 =Y би +1 ; dx=(s-t)=2(rdy-qdx)+2dy –dx dx=(s-t) тэмдэг нь ялгааны тэмдэгтэй давхцаж байгаа тул d i =dx(s-t) илэрхийллийн тэмдгийг шалгана. . r=X i -1 ба q=Y i -1 байх тул d i +1 = d i +2dy -2dx(y i -y i -1) . Өмнөх алхам дээр d i<0 , тогда(y i -y i -1)=0 и d i +1 = d i +2dy . Если же на предыдущем шаге d i ≥0 , тогда(y i -y i -1)=1 и d i +1 = d i +2dx(y i -y i -1) d i-г хэрхэн тооцоолохыг олж мэдэх л үлдлээ. Учир нь i=1 Процедур Bresenham(x1,y1,x2,y2,Өнгө: бүхэл тоо); dx,dy,incr1,incr2,d,x,y,xend: бүхэл тоо; dx:= ABS(x2-x1); dy:= Abs(y2-y1); d:=2*dy-dx; (d-ийн анхны утга) incr1:=2*dy; (d-ийн өсөлт<0} incr2:=2*(dy-dx); (d>=0-ийн өсөлт) хэрэв x1>x2 бол (бага x утгатай цэгээс эхэлнэ) PutPixel(x,y, Өнгө); (сегментийн эхний цэг) байхад x d:=d+incr1 (доод цэгийг сонгох) d:=d+incr2; (дээд цэгийг сонгох, y-өсөх) PutPixel(x,y, Өнгө); 26. Ерөнхий Брезенхэмийн алгоритм.
Алгоритм нь сегментийг төлөөлөх оновчтой растер координатуудыг сонгодог. Δx эсвэл Δy хоёрын аль нэгийг нь растерийн нэгж болгон сонгоно. Ашиглалтын явцад координатуудын аль нэг нь - x эсвэл y (налуугаас хамаарч) нэгээр өөрчлөгддөг. Өөр координатыг (0 эсвэл 1 болгож) өөрчлөх нь сегментийн бодит байрлал ба хамгийн ойрын сүлжээний координат хоорондын зайнаас хамаарна. Энэ зай нь алдаа юм. Алгоритм нь зөвхөн энэ алдааны тэмдгийг мэдэхэд л хангалттай байхаар бүтээгдсэн. Иймээс растер цэг (1, 1) нь (1, 0) цэгээс сегментийн чиглэлийг илүү ойртуулдаг. Хэрэв налуу нь ½-ээс бага бол эсрэгээрээ байна. ½ налуугийн хувьд давуу сонголт байхгүй. Энэ тохиолдолд алгоритм нь цэгийг (1, 1) сонгоно. Зөвхөн алдааны тэмдгийг шалгах нь зүйтэй тул эхлээд -½ гэж тохируулсан. Тиймээс хэрвээ сегментийн налуу нь ½-ээс их буюу тэнцүү бол дараагийн растер цэг дээрх алдааны утгыг e = -½ + Δy/Δx гэж тооцоолж болно. Бресенхамын алгоритмыг бүрэн хэрэгжүүлэхийн тулд бүх октант дахь сегментүүдийг боловсруулах шаардлагатай. Алгоритмд сегмент байрлах квадратын тоо болон түүний өнцгийн коэффициентийг харгалзан үзэхэд үүнийг хийхэд хялбар байдаг. Налуугийн абсолют утга 1-ээс их байвал y нь нэгээр байнга өөрчлөгддөг ба х-ийн утгыг өөрчлөх эсэхийг шийдэхийн тулд Брезенхэмийн алдааны шалгуурыг ашигладаг. Байнга өөрчлөгддөг (+1 эсвэл -1) координатыг сонгох нь квадрантаас хамаарна
var x,y,sy,sx,dx,dy,e,z,i: Бүхэл тоо; 27. Тойрог үүсгэх Брезенхэмийн алгоритм
Растерийг шугаман болон бусад, илүү төвөгтэй функц болгон өргөжүүлэх шаардлагатай. Кель, эллипс, парабол, гипербол зэрэг терминалын зүслэгийн хуваарилалтыг роботын үнэ цэнэд өгсөн. Хамгийн их хүндэтгэлтэйгээр гадас нэмсэн нь ойлгомжтой. Хамгийн үр дүнтэй бөгөөд ойлгоход хялбар тойрог үүсгэх алгоритмуудын нэг бол Бресенхам юм. Кобын хувьд гадасны наймны нэгийг л бий болгох нь чухал. Эдгээр хэсгүүдийг дараалсан цохилтоор арилгаж болно. Эхний октант үүссэний дараа (жилийн эсрэг сумны 0-ээс 45 ° хүртэл) нөгөө октантыг y = x шулуун шугамын толин тусгал дүрсээр илэрхийлж болох бөгөөд энэ нь хамтдаа эхний квадратыг өгдөг. Эхний квадрантыг шууд х = 0 тогшуулж, гадасны тулгуур хэсгийг нөгөө квадрантаас салгана. Даалгавраа дуусгахын тулд дээд талынх нь = 0 үед шууд доош унана. Алгоритмыг харуулахын тулд координатын коб дээр төвлөрсөн гадасны дөрөвний нэгийг харцгаая. Алгоритм нь x = 0, y = R цэгээс эхэлдэг тул эхний квадрат дахь жилийн сумны ард тойрог үүсгэх үед y нь аргументуудын нэг хэвийн буурах функц болохыг анхаарна уу. Үүний нэгэн адил, хэрэв гаралтын цэг нь y = 0, x == R бол сумны эсрэг тойрог үүсгэх үед x нь аргумент у-ийн монотон буурах функц болно. Манай тохиолдолд гадасны төв болон кобын цэг яг растер цэгүүд дээр байгаа гэж х = 0 цэгт кобтой жилийн сумны үүслийг сонгосон. Жилийн сумны ард үүсгэх үед тойрог дээрх өгөгдсөн цэгийн хувьд хамгийн ойрын тойрог болох дараагийн пикселийг сонгох гурван сонголт л байна: хэвтээ баруун тийш, диагональ доош, баруун тийш, босоо доош. Алгоритм нь эдгээр пикселүүдийн аль нэг болон тойргийн хооронд хамгийн бага квадрат нь байх пикселийг сонгоно. 28. Фракталын тухай ойлголт. Фрактал графикийн түүх
Өдөр тутмын амьдралдаа та математикийн хувьд тайлбарлах боломжгүй дүрсийг (загвар) ажиглаж болно. Жишээ нь: өвлийн улиралд цонхнууд хөлддөг тул та зургийг ажиглаж болно. Ийм олонлогуудыг фрактал гэж нэрлэдэг. Фракталууд нь геометрийн сайн мэддэг тоонуудтай төстэй биш бөгөөд тэдгээрийг компьютер дээр хэрэгжүүлж болох тодорхой алгоритмуудыг ашиглан бүтээдэг. Энгийнээр хэлбэл, фрактал нь анхны хэлбэрт дахин дахин хийгдсэн өөрчлөлтийн үр дүнд бий болсон дүрс юм. Фрактал нь хэсгүүдээс бүрдэх геометрийн дүрс бөгөөд үүнийг хэсэг болгон хувааж болох бөгөөд тус бүр нь бүхэлдээ жижиг хуулбарыг төлөөлдөг. Фракталуудын гол шинж чанар нь өөрөө ижил төстэй байдал, i.e. Фракталын аль ч хэлтэрхий нь түүний глобал бүтцийг ямар нэг байдлаар хуулбарладаг. Фракталууд нь геометрийн, алгебрийн, стохастик, давтагдах функцийн системд хуваагддаг. 29. Хэмжээний тухай ойлголт, түүний тооцоо
Өдөр тутмын амьдралдаа бид хэмжээстэй байнга тулгардаг. Бид замын уртыг тооцоолж, орон сууцны талбайг олж мэдэх гэх мэт. Энэ үзэл баримтлал нь нэлээд зөн совинтой бөгөөд тодруулах шаардлагагүй юм шиг санагдаж байна. Энэ шугам нь 1 хэмжигдэхүүнтэй байна. Энэ нь лавлагаа цэгийг сонгосноор бид эерэг эсвэл сөрөг гэсэн 1 тоог ашиглан энэ шулуун дээрх дурын цэгийг тодорхойлж болно гэсэн үг юм. Түүнээс гадна энэ нь тойрог, дөрвөлжин, парабола гэх мэт бүх мөрөнд хамаарна. Хэмжээ 2 гэдэг нь бид ямар ч цэгийг хоёр тоогоор өвөрмөц байдлаар тодорхойлж чадна гэсэн үг юм. Хоёр хэмжээст гэдэг нь хавтгай гэсэн үг гэж битгий бодоорой. Бөмбөрцгийн гадаргуу нь мөн хоёр хэмжээст (үүнийг өргөн, уртраг гэх мэт хоёр утгыг ашиглан тодорхойлж болно). Хэрэв бид үүнийг математикийн үүднээс авч үзвэл хэмжээсийг дараах байдлаар тодорхойлно: нэг хэмжээст объектын хувьд шугаман хэмжээг хоёр дахин нэмэгдүүлэх нь хэмжээ (энэ тохиолдолд урт) хоёр дахин (2^) нэмэгдэхэд хүргэдэг. 1). Хоёр хэмжээст объектын хувьд шугаман хэмжээсийг хоёр дахин нэмэгдүүлэх нь хэмжээ (жишээлбэл, тэгш өнцөгтийн талбай) дөрөв дахин (2 ^ 2) нэмэгдэхэд хүргэдэг. 3 хэмжээст объектын хувьд шугаман хэмжээсийг хоёр дахин нэмэгдүүлэх нь эзлэхүүнийг 8 дахин нэмэгдүүлэхэд хүргэдэг (2^3) гэх мэт. Геометрийн фракталууд Чухам эдгээр фракталуудаар фракталуудын хөгжлийн түүх ерөнхийдөө эхэлсэн юм. Энэ төрлийн фракталыг энгийн геометрийн байгууламжаар олж авдаг. Ихэвчлэн геометрийн фракталуудыг бүтээхдээ дараах алгоритмыг ашигладаг. Геометрийн фракталуудын жишээ: Пиано муруй, Кохын цас, оймын навч, Сиерпинскийн гурвалжин, Алгебрийн фракталууд Фрактал- өөртэйгөө ижил төстэй шинж чанартай, өөрөөр хэлбэл хэд хэдэн хэсгээс бүрдэх, тус бүр нь бүхэл бүтэн дүрстэй төстэй геометрийн нарийн төвөгтэй дүрс. Алгебрийн фракталууд нь алгебрийн функцүүдийн үндсэн дээр бүтээгдсэн тул нэрээ авсан. Алгебрийн фракталд: Манделбротын багц, Жулиа багц, Ньютоны сав газар, биоморфууд орно. -Манделбротын багц:Манделбротын багцыг анх 1905 онд Пьер Фату дүрсэлсэн байдаг. Фатоу хэлбэрийн рекурсив процессыг судалсан Нарийн төвөгтэй хавтгай дээрх цэгээс эхлэн эдгээр томьёог дараалан хэрэглэснээр шинэ оноо авах боломжтой. Ийм цэгүүдийн дарааллыг хувиргах тойрог зам гэж нэрлэдэг Фату энэхүү өөрчлөлтийн дагуу тойрог зам нь нэлээд төвөгтэй, сонирхолтой зан чанарыг харуулдаг болохыг олж мэдэв. Хязгааргүй тооны ийм хувиргалт байдаг - утга тус бүрт нэг. (Манделброт гэж нэрлэсэн, учир нь тэр компьютер ашиглан шаардлагатай тооны тооцоог хамгийн түрүүнд хийж байсан). -Жулиа тавьсан: Жулиа оновчтой зураглалын багц -Ньютоны усан сангууд:Шугаман бус тэгшитгэлийн язгуурыг Ньютоны алгоритмаар нарийн төвөгтэй хавтгайд ойролцоогоор олох үед фрактал хил хязгаартай мужууд гарч ирдэг (бодит хувьсагчийн функцийн хувьд Ньютоны аргыг ихэвчлэн нэрлэдэг. шүргэгч арга, энэ тохиолдолд цогц хавтгайд ерөнхийлсөн болно). Процедурыг ашиглан комплекс хувьсагчийн функцийн тэгийг олохын тулд Ньютоны аргыг хэрэглэцгээе. Анхны ойролцоо тооцооллын сонголт нь онцгой анхаарал татаж байна. Учир нь Функц олон тэгтэй байж болох ба өөр өөр тохиолдолд арга нь өөр өөр утгуудад нийлж болно. -биоморфууд: z=z 3 +c томъёогоор тооцоолсон Жулиа багцын товчилсон хэлбэр. Энэ нь нэг эст организмтай төстэй учраас энэ нэрийг авсан. Стохастик фракталууд Энэ төрлийн фракталын ердийн төлөөлөгч нь плазм гэж нэрлэгддэг. Үүнийг бүтээхийн тулд тэгш өнцөгтийг авч, түүний булан бүрийн өнгийг тодорхойлно. Дараа нь тэгш өнцөгтийн төв цэгийг олж, тэгш өнцөгтийн булан дахь өнгөний арифметик дундажтай тэнцэх өнгөөр + зарим санамсаргүй тоогоор будна. Энэ санамсаргүй тоо том байх тусам зураг урагдсан байх болно. Байгалийн объектууд ихэвчлэн фрактал хэлбэртэй байдаг. Стохастик (санамсаргүй) фракталуудыг загварчлахад ашиглаж болно. Стохастик фракталуудын жишээ: хавтгай ба орон зайд броуны хөдөлгөөний замнал; Хавтгай дээрх Брауны хөдөлгөөний траекторийн хил. 2001 онд Лоулер, Шрамм, Вернер нар түүний хэмжээс нь 4/3 гэсэн Манделбротын таамаглалыг баталжээ. Шрамм-Ловнерийн хувьсал нь статистикийн механикийн чухал хоёр хэмжээст загварт, жишээлбэл, Исинг загвар болон нэвтрэлтэд үүсдэг конформын инвариант фрактал муруй юм. янз бүрийн төрлийн санамсаргүй фрактууд, өөрөөр хэлбэл алхам бүрт санамсаргүй параметрийг нэвтрүүлсэн рекурсив процедурыг ашиглан олж авсан фракталууд. Плазма бол ийм фракталыг компьютерийн графикт ашиглах жишээ юм. Фрактал монотип буюу сточатипи нь санамсаргүй фракталын дүрсийг олж авах дүрслэх урлагийн чиг хандлага юм. Холбогдох мэдээлэл. |
- ойр орчмын динамик нь тодорхой утгаараа анхны байрлалын бага зэргийн хямралын хувьд тогтворгүй байдаг цэгүүдийн багц. тохиолдолд е- олон гишүүнт, бид мөн дүүргэсэн Жулиа олонлогийг авч үздэг - хязгааргүйд чиглэдэггүй цэгүүдийн багц. Жулиагийн ердийн багц бол түүний хил хязгаар юм.
