Cum de a construi un grafic de puncte n? Cel mai simplu lucru este să le marchezi cu marcatori pe grilă. Cu toate acestea, pentru claritate, doriți să le combinați pentru a obține o linie ușor de citit. Cel mai simplu mod de a conecta punctele este prin linii drepte. Dar linia întreruptă este destul de greu de citit: vederea se agăță de colțuri, mai degrabă decât diapozitivele de-a lungul liniei. Și zgomotele nu arată foarte drăguț. Se pare că, în plus față de liniile întrerupte, trebuie să puteți construi curbe. Cu toate acestea, trebuie să aveți grijă să nu obțineți acest lucru:
Un pic de material
Recuperarea valorilor intermediare ale funcției, care în acest caz este tabelată ca puncte P1 # 038; nbsp ... # 038; nbspPn. se numește interpolare. Există multe modalități de a interpola, dar toate acestea pot fi reduse la faptul că trebuie găsită n # 038; nbsp- # 038; nbsp1 O funcție pentru calcularea punctelor intermediare pe segmentele corespunzătoare. În acest caz, punctele date trebuie să fie în mod necesar calculate prin funcțiile corespunzătoare. Pe baza acestui fapt, se poate construi un grafic:
Funcțiile fi pot fi foarte diferite, dar cel mai adesea folosesc polinoame de un anumit grad. În acest caz, funcția de interpolare rezultată (în formă de piesă definită la intervalele delimitate de punctele Pi) se numește spline.
Am pus experimente
Cel mai simplu exemplu este interpolarea liniară, în care se utilizează polinoame de gradul întâi și rezultatul este o linie întreruptă care leagă punctele date.
Să adăugăm câteva detalii. Iată un set de puncte (luate aproape de tavan):
Rezultatul interpolării liniare a acestor puncte arată astfel:
Cu toate acestea, după cum sa menționat mai sus, uneori doriți să obțineți o curbă lină ca rezultat.
Ce este netezirea? Răspunsul la domiciliu: lipsa colțurilor ascuțite. Matematică: continuitatea derivatelor. În matematică, netezimea este de aceeași ordine ca și numărul ultimului derivat continuu și regiunea pe care se păstrează această continuitate. Adică, dacă funcția are netezime de ordinul 1 pe intervalul [a; # 038; nbspb], înseamnă că [a; # 038; nbspb] are un prim derivat continuu, dar derivata a doua are o discontinuitate în unele puncte.
Un spline în contextul netezimii are un concept de defect. Defecțiunea spline este diferența dintre gradul său și netezirea sa. Gradul de spline este gradul maxim al polinomilor utilizați în el.
Este important să rețineți că punctele "periculoase" ale splinei (în care netezimea pot fi încălcate) sunt doar Pi. adică punctele de articulare a segmentelor în care există o tranziție de la un polinom la altul. Toate celelalte puncte sunt "sigure", deoarece un polinom pe domeniul definiției sale nu are probleme cu continuitatea derivatelor.
Pentru a obține o interpolare lină, este necesar să se mărească gradul de polinoame și să se aleagă coeficienții acestora, astfel încât continuitatea derivaților să rămână la punctele de graniță.
În mod tradițional, polinomii de gradul al treilea sunt utilizați pentru a rezolva o astfel de problemă și a realiza continuitatea primului și a celui de-al doilea derivat. Ce se întâmplă se numește un spline cubic al defectului 1. Așa arată datele noastre:
Curba este într-adevăr netedă. Dar dacă presupunem că acesta este un grafic al unui anumit proces sau fenomen care trebuie să fie arătat persoanei în cauză, atunci această metodă este cel mai probabil inadecvată. Problema este în extreme false. Ele au apărut din cauza prea multă curbură, care a fost menită să asigure netezirea funcției de interpolare. Dar acest comportament nu este deloc convenabil pentru privitor, deoarece el este înșelat în legătură cu valorile maxime ale funcției. Și pentru vizualizarea vizuală a acestor valori, de fapt, totul a început.
Așadar, trebuie să căutăm alte soluții.
O altă soluție tradițională, cu excepția splinelor cubice ale defectului 1, este polinomii Lagrange. Acestea sunt polinoame de gradul n # 038; nbsp1, care iau valorile date la anumite puncte. Adică nu există segmentare aici, întreaga secvență este descrisă de un polinom.
Dar iată ce se întâmplă:
Smoothness, desigur, este prezent, dar vizibilitatea a suferit atât de mult încât ... poate că merită să căutați alte metode. Pe unele seturi de date rezultatul este normal, dar în cazul general, eroarea în ceea ce privește interpolare liniară (și extreme, astfel, false) pot fi preparate prea mult - din cauza faptului că există doar un singur polinom pentru toate segmentele.
În grafica pe calculator, curbele Bezier sunt foarte utilizate. reprezentate de polinoame de gradul k.
Ele nu interpolă, deoarece de la k # Nbsp + # 038; nbsp1 puncte implicate în construcție, curba finală trece numai prin prima și ultima. Restul k Punctele nbsp1 joacă rolul unui fel de "centre gravitaționale", atrăgând o curbă.
Iată un exemplu de curbă cubică Bezier:
Cum se poate folosi aceasta pentru interpolare? Pe baza acestor curbe, puteți construi și un spline. Adică, pe fiecare segment al splinei va exista o curbă Bézier a puterii k (apropo, k # 038; nbsp = # 038; nbsp1 oferă interpolare liniară). Și întrebarea este doar cum să luăm k și cum să găsim k Punctul intermediar nbsp-nbsp1.
Există nenumărate variante (din moment ce k este nelimitat), totuși considerăm clasicul: k # 038; nbsp = # 038; nbsp3.
Pentru curba rezultată este netedă, este necesar pentru atingerea defectului 1 pentru componentele spline, adică păstrarea continuității prima și a doua derivate la punctele segmentelor de articulare (Pi), așa cum se face în versiunea clasică a spline.
Soluția acestei probleme în detaliu (cu codul sursă) este luată în considerare aici.
Iată ce se întâmplă în suita noastră de testare:
A devenit mai bine: extremele false sunt încă acolo, dar cel puțin nu sunt atât de diferite de cele reale.
Gândiți-vă și experimentați-vă
Puteți încerca să slăbească condiția de netezime: necesită defectul 2 și nu 1, adică păstrați continuitatea numai a primului derivat.
O condiție suficientă pentru realizarea defectului 2 în faptul că punctele de control intermediare ale curbei Bezier cubică adiacente punctului dat secvențelor interpolate sunt din acest punct pe o linie și echidistantă:
Ca linii drepte pe care se află punctele Ci # Nbsp- # 038; nbsp1 (2). Pi și Ci (1). se recomandă să luați tangente la graficul funcției interpolate la punctele Pi. Acest lucru asigură că nu există valori false, deoarece curba Bezier este limitată de o polilinie construită la punctele sale de control (dacă această polilinie nu are auto-intersecții).
Prin metoda de încercare și eroare, euristica pentru calcularea distanței de la punctul secvenței interpolate la testul intermediar a fost:
Primul și ultimul punct intermediar de control sunt egale cu primul și ultimul punct al graficului (punctele C1 (1) și Cn (2) coincid cu punctele P1 și, respectiv, Pn).
În acest caz, obținem această curbă:
Se pare că nu mai există valori false. Cu toate acestea, în comparație cu interpolarea liniară, eroarea este foarte mare în locuri. Puteți face chiar și mai mic, dar apoi se vor folosi și mai multe euristici viclene.
Pentru versiunea curentă, am venit, reducând netezimea cu o singură comandă. Puteți face acest lucru din nou: lăsați spline-ul să fie defect. 3. De fapt, astfel, funcția nu va fi deloc liniară: chiar și primul derivat poate tolera decalajele. Dar dacă o rupi cu grijă, nu se va întâmpla nimic teribil.
Respingem cerința de egalitate a distanțelor de la punctul Pi la punctele Ci (2) și Ci (1). dar în același timp le ținem pe toate într-o singură linie:
Heuristica pentru calcularea distanțelor va fi după cum urmează:
Calculul lui l1 și l2 este același ca în "euristic 1".
În acest caz, totuși, merită să verificăm dacă punctele Pi și Pi # 038; nbsp + # 038; nbsp1 de-a lungul ordinii și, dacă este potrivită, presupuneți l1 # 038; nbsp = # 038; nbspl2 # 038; nbsp = # 038; nbsp0. Acest lucru va proteja împotriva "umflarea" graficului pe segmente plate (ceea ce este important și din punct de vedere al afișării veridice a datelor).
Rezultatul este:
Ca urmare, eroarea a scăzut pe segmentul al șaselea, iar pe al șaptelea - a crescut: curbura lui Bezier a fost mai mult decât mi-aș dori. Puteți corecta situația prin reducerea forțată a curburii și prin aceasta "apăsarea" lui Bezier mai aproape de segmentul liniei drepte care leagă punctele de frontieră ale segmentului. Următorul euristic este folosit pentru aceasta:
Dacă abscisa punctului de intersecție a tangentelor la punctele Pi (xi, # 038; nbspyi) și Pi # 038; nbsp + # 038; nbsp1 (xi # 038; nbsp + # 038; nbsp1; # 038; nbspyi # 038; nbsp + # 038; nbsp1) se află în segmentul [xi; # 038; nbspxi # 038; nbsp + # 038; nbsp1], atunci l1 sau 12 este setată la zero. În cazul în care tangenta la punctul Pi este îndreptată în sus, setăm maximul de l1 și l2 la zero. dacă în jos - minimul.
Aceasta a fost decizia de a recunoaște obiectivul obținut.
Poate cineva va avea nevoie de cod.
Și cum o fac oamenii?
Revizuire promisă. Desigur, înainte de soluționarea problemei, ne-am uitat la cine se poate lăuda cu ceea ce, și apoi a început să înțeleagă cum să-l faceți singuri și, dacă este posibil, mai bine. Dar, de îndată ce au făcut-o, nu fără plăcere, au trecut din nou prin instrumentele disponibile și au comparat rezultatele lor cu roadele experimentelor noastre. Deci, hai să mergem.
Acest lucru este foarte similar cu defectul spline 1 considerat mai sus, pe baza curbelor Bezier. Cu toate acestea, spre deosebire de aceasta în forma sa pură, există doar două extreme false - primul și al doilea segment (am avut patru). Se pare că alte euristici se adaugă la căutarea clasică a punctelor de control intermediare. Dar nu au salvat toate extremele false.
LibreOffice Calc
În setări, se numește un spline cubic. Evident, se bazează și pe Bezier, iar aici este deja o copie exactă a rezultatului nostru: toate cele patru extreme false sunt în vigoare.
Există un alt tip de interpolare pe care nu am luat-o în considerare aici: B-spline. Dar pentru sarcina noastră, evident că nu se potrivește, deoarece dă aici un astfel de rezultat 🙂
Highcharts. una dintre cele mai populare biblioteci JS pentru construirea diagramelor
Aici există o "metodă de tangenți" în varianta de egalitate a distanțelor de la punctul secvenței interpolate la cele de control intermediare. Nu există extreme extreme, dar există o eroare relativ mare în ceea ce privește interpolarea liniară (al șaptelea segment).
amCharts. o altă bibliotecă populară JS
Imaginea este foarte asemănătoare cu Exilul, aceleași două extreme false în aceleași locuri.
Coreplot. Cea mai populară bibliotecă grafică pentru iOS și OS X
Există extreme false și se poate observa că spline-ul defectului 1 se bazează pe Bezier.
Biblioteca este deschisă, astfel încât să puteți vedea codul și să vă vedeți singur.
aChartEngine. cum ar fi cea mai populară bibliotecă grafică pentru Android
Cel mai similar cu curba Bezier de gradul n # Nbsp- nbsp1, deși în bibliotecă însăși graficul este numit "linia cubică". E ciudat! Fie ca și cum ar exista, nu sunt prezente aici doar extreme false, dar, în principiu, condițiile de interpolare nu sunt îndeplinite.
În loc să încheiem
În cele din urmă, se pare că "băieții mari" sunt cel mai bine rezolvați de problema Highcharts. Dar metoda descrisă în acest articol oferă o eroare și mai mică în ceea ce privește interpolarea liniară.
În general, a trebuit să facem acest lucru la cererea clienților care ne-au rezervat "colțuri ascuțite" ca un bug în motorul nostru de diagramă. Vom fi fericit dacă experiența descrisă este utilă pentru cineva.
Articole similare
Trimiteți-le prietenilor: