Bine aţi venit pe Scientia QA!
Pentru a putea publica întrebări şi răspunsuri, trebuie să vă înregistraţi.
Atenţie! Este posibil ca e-mailul de confirmare a înregistrării să intre în Spam.
Pune o întrebare

Newsletter


3.5k intrebari

6.7k raspunsuri

15.3k comentarii

2.5k utilizatori

1 plus 0 minusuri
592 vizualizari

În desenul de mai jos, datele de intrare sînt pozițiile punctelor negre plasate în pătrat, iar împărțirea suprafeței pătratului în zone poligonale s-a făcut automat pornind de la aceste puncte și aplicînd o anumită regulă simplă.

Care credeți că este acea regulă?

Expert (12.8k puncte) in categoria Matematica
0 0
Se poate imagina un algoritm simplu si neechivoc pentru desenarea diagramei Voronoi corespunzatoare unui anumit set de puncte dintr-o anumita regiune a planului?
0 0
Da, se poate, de fapt exact așa am făcut imaginea din problemă. Nu știam, deși bănuiam, că au mai făcut și alții astfel de programe.

Pentru desenarea diagramei într-o imagine matricială (cu pixeli), algoritmul e super simplu: trebuie doar să iei fiecare pixel din imagine și să vezi care din punctele date e cel mai apropiat. În funcție de asta colorezi pixelul cu o culoare sau alta.

Pe de altă parte, pentru a desena diagrama ca imagine vectorială, eu am folosit următorul algoritm: pentru a calcula forma poligonului corespunzător unui punct dat (pe care îl numesc în continuare punct curent), am presupus mai întîi că punctul acela e singur, deci poligonul inițial are forma pătratului mare. Apoi am adăugat unul cîte unul celelalte puncte. La fiecare adăugare am tăiat o bucată din poligonul curent ca să țin cont de existența punctului nou adăugat. Pentru asta a trebuit să calculez mediatoarea punctului curent și a punctului adăugat, să intersectez poligonul curent cu acea mediatoare și să păstrez numai bucata mai apropiată de punctul curent. Calculul nu e complicat, e simplă geometrie analitică. Tot programul încape lejer pe o foaie A4, cu tot cu operațiile care țin de desenare și salvare într-un fișier SVG.

Desenul din enunț este de fapt vectorial, dar ca să-l pun aici a trebuit să-l transform în format matricial. Eu l-am convertit în PNG, dar undeva pe drum a devenit JPG, probabil cînd l-am urcat la Tinypic.com.

1 Raspuns

1 plus 0 minusuri
 
Cel mai bun raspuns
Oricare două poligoane adiacente au punctele din interior simetrice față de latura comună a acestora. Asta la o primă cercetare... În această diagramă orice vârf de poligon este centrul cercului circumscris triunghiului format cu cele mai apropiate trei puncte ”negre”, dar ar putea fi și mai mult de trei (dacă ar fi conciclice) și vârfurile aflate pe laturile pătratului nu ar trebui să facă excepție (deși în acest desen nu întâlnim asemenea cazuri).

https://en.wikipedia.org/wiki/Voronoi_diagram
Junior (971 puncte)
selectat de
0 0
E un bun început.
0 0
Mi se pare ca e un fel de generalizare a celulei primitive Wigner-Seitz din fizica solidului.In acest caz pentru o retea de puncte fara vreo simetrie de translatie. Interesant. :)
0 0
Așteptam un alt răspuns, dar l-am selectat pe acesta pentru că am învățat ceva din el. Mai exact nu știam că există noțiunea asta în știință și că se cheamă diagrama Voronoi.

Eu am pornit de la o problemă simplă: se dau niște puncte fixe în plan și se cere să se afle pentru fiecare loc din plan care dintre punctele date este cel mai apropiat. De aici rezultă împărțirea planului în poligoane. Astfel fiecare poligon este locul geometric al punctelor din plan pentru care unul din punctele date e cel mai apropiat. (Acesta e răspunsul pe care îl așteptam.)

De exemplu, să zicem că pe o cîmpie întinsă sînt mai multe puncte de interes – localități, surse de apă, magazine, spitale etc. – și întrebarea este: în funcție de locul în care te afli, care este cel mai apropiat punct de interes?

O altă situație în care se obține aceeași figură este aceea în care avem în plan cîteva surse de unde de viteză constantă – lumină, valuri, frontul de propagare al unei culturi de bacterii etc. – și din toate sursele pornesc simultan cîte o undă. Întrebarea e analoagă: în fiecare loc din plan, de la care sursă sosește mai întîi unda?

Văd acum în articolul de la Wikipedia că există mult mai multe aplicații, unele chiar în fizică, de care nu știam.

Așadar, mulțumesc!
0 0

Da, acestea si altele asemenea sunt lucruri foarte interesante! "Tot ce este gandire logica este ori matematica ori susceptibil de matematizare" (G. Moisil) Pentru cei rămași departe de mediul universitar/academic, ca mine, cercetarea matematică (și nu numai) a ajuns înspăimântător de departe! :)

0 0
Pentru amatorii de provocari, tot pe wiki - o lista interesanta si, desigur, mereu provizorie...

https://en.wikipedia.org/wiki/Lists_of_unsolved_problems

Extraordinare sunt cele sapte "probleme ale mileniului" din care una a fost rezolvata de genialul Perelman, care, mai nou, sustine ca lucreaza la un model matematic capabil sa explice mersul pe apa al lui Isus! Eu unul nu sunt cu religia, insa nici nu prea imi vine sa cred ca ADN-ul s-a autocreat...(ar fi necesitat o suma colosala de conditii, coincidente, potriviri etc.)
...