Робота з розкиданими даними

У MATLAB входять функції для роботи з розкиданими даними, тобто наприклад, у двовимірному випадку це дані z_i, задані в крапках (x_i, y_i)_i=1,2,...,k. Ці функції дозволяють вирішувати наступні задачі.

• Інтерполювати розкидані дані різними способами. Для даних, визначених у крапках на площині, можливо кусочно-постійне наближення по найближчому сусіді, кусочно-лінійне наближення і більш гладке наближення з неперервними похідними (функція griddata). Дані, визначені в крапках тривимірного і n-мірного простору можуть бути наближені по найближчому сусіді і за допомогою кусочно-лінійних функцій (функції griddata3 і griddatan). Значення интерполянта повертається на ортогональній сітці, що накриває крапки, у яких задані розкидані дані.

• Будувати опуклу оболонку множини крапок на площині, у тривимірному і n-мірному просторі (функції convhull, convhulln).

• Реалізація опуклої оболонки множини крапок і її візуалізація

• Опукла оболонка conv(P) множини крапок, що належать n-мірному простору Rⁿ, визначається як найменша опукла множина, що містить усі ці крапки. Опукла множина, породжена крапками (p_i)_i=1,2,...,k, визначається як множина крапок:

• p = a₁p₁ + a₂p₂ + ... + a_kp_k

• де всі a_i >/= 0 і a₁ + a₂ + ... + a_k = 1 (тут крапки ототожнюються з векторами, що виходять з початку координат).

• У двовимірному випадку є проста інтуїтивно зрозуміла аналогія. Нехай на площині лежать крапки (убиті цвяхи), ми натягаємо навколо них мотузку.

• 

• Те, що вийде, і буде опуклою оболонкою (на правому малюнку її границя зображена червоним кольором). Усі крапки з множини знаходяться або усередині опуклої оболонки, або на її границі.

• Опукла оболонка є перетинанням кінцевого числа півпросторів (півпростір - частина простору, що лежить по одну сторону від гіперплощини). У двовимірному випадку гіперплощини це лінії, а в тривимірному випадку - площини.

• 

Для побудови опуклої оболонки в MATLAB служить функція convhull. Її вхідними аргументами є вектори з координатами абсцис і ординат крапок, а вихідними аргументами є номери крапок, що утворять вершини опуклої оболонки. У наступному прикладі генерується набір з 100 крапок з координатами, що змінюються випадковим образом від 0 до 1, потім за допомогою функції convhull будується опукла оболонка. Номера крапок, що є вершинами опуклої оболонки, заносяться в масив kvert. Потім вершини опуклої оболонки виділяються круглими маркерами і малюється сама опукла оболонка

x=rand(1,100);

y=rand(1,100);

figure

plot(x,y,'k.')

hold on

axis([-0.5 1.5 -0.5 1.5])

kvert=convhull(x,y)

pause(0.3)

plot(x(kvert(1)),y(kvert(1)),'ro')

for k=2:length(kvert)

plot([x(kvert(k-1)) x(kvert(k))],[y(kvert(k-1)) y(kvert(k))],'r')

plot(x(kvert(k)),y(kvert(k)),'ro')

pause(0.3)

end

Якщо функцію convhull викликати з другим додатковим вихідним аргументом, то в нього запишеться площа опуклої оболонки

>> [kvert, s] = convhull(x, y);

>> s

s = 0.9164

Для побудови опуклої оболонки крапок із тривимірного простору і просторів більш високих вимірностей використовується функція convhulln. Координати крапок задаються в рядках двовимірного масиву, що вказується як вхідний аргумент функції convhulln. Вона повертає двовимірний масив, кожен рядок якого містить номера крапок з вихідної множини, що утворять грань опуклої оболонки (у двовимірному випадку грань - відрізок, що з'єднує сусідні вершини опуклої оболонки).

Як приклад приведемо побудову опуклої оболонки крапоок, що випадковим образом розподілені в кубі [0,1]x[0,1]x[0,1]. Координати крапок генеруються за допомогою функції rand і записуються у вектори-стовпці. З цих стовпців створюється матриця, що вказується як вхідний аргумент функції convhulln. Функція convhulln повертає матрицю з трьох стовпців, кожний з який містить номера крапок вихідної множини, що утворять деяку грань опуклої оболонки. Для візуалізації опуклої оболонки застосовується функція trimesh, що будує полігональний об'єкт (patch) і повертає покажчик на нього. Вид цього полігонального об'єкта можна змінювати за своїм розсудом, включаючи прозорість і колір граней, маркери у вершинах і т.д. Коли опукла оболонка знайдена, та уся вихідна множина крапок розбивається на дві підмножини - крапки, що є вершинами опуклої оболонки, і внутрішні крапки.

У прикладі, що нижче приводиться, поруч із крапками цих типів розміщаються підписи різного кольору з номерами крапок. Для цього використовується функція text. При цьому виникає питання, як визначити номера крапок, що потрапили усередину опуклої оболонки вихідної множини, і тих, котрі належать вершинам опуклої оболонки. Як уже говорилося, номера вершин записані у вихідному аргументі функції convhulln (двовимірному масиві з трьома стовпцями). Однак, вони зустрічаються в різних рядках цього масиву і не по одному разі. Тому для виділення номерів крапок, що потрапили у вершини опуклої оболонки, можна робити так: послідовно об'єднати вміст стовпців матриці з номерами вершин, скориставшись функцією union. Оскільки дана функція робить об'єднання в змісті об'єднання множин, то повтори елементів виключаються. Аналогічно, для перебування номерів крапок, що потрапили усередину опуклої оболонки, можна застосувати функцію setdiff, що знаходить різницю множин. У нашому випадку з множини номерів усіх крапок варто відняти номера крапок, що утворять вершини опуклої оболонки.

k=20; задаємо двадцять крапок

rand('state',0); генератору випадкових чисел задаємо початковий стан

% генеруємо координати крапок множини і записуємо їх у вектори-стовпці x, y, і z

x=rand(k,1);

y=rand(k,1);

z=rand(k,1);

% утворимо двовимірний масив з координатами крапок множини

X=[x y z];

% знаходимо номера крапок, що утворять трикутної грані опуклої оболонки множини

kvert=convhulln(X)

% визуализируем опуклу оболонку за допомогою функції trisurf

figure('Color','w')

h=trisurf(kvert,X(:,1),X(:,2),X(:,3))

hold on

% установлюємо прозорість граней, червоні ребра

% і круглі червоні маркери у вершинах опуклої оболонки

set(h,'FaceAlpha',0.1,'FaceColor','g',...

'EdgeColor','r','Marker','о','MarkerSize',10)

% знаходимо номера крапок, що є вершинами опуклої оболонки, і записуємо їх у kv

kv=union(kvert(:,1),kvert(:,2))

kv=union(kv,kvert(:,3))

% підписуємо номера вершин опуклої оболонки

ht=text(x(kv), y(kv), z(kv),num2str(kv))

set(ht,'BackgroundColor','r','VerticalAlignment','Top',...

'FontWeight','bold')

% знаходимо номера крапок, що потрапили усередину оболонки, і записуємо їх у kinner

kinner=setdiff(1:k,kv)

% малюємо крапок, що потрапили усередину оболонки, круглими синіми маркерами

plot3(x(kinner),y(kinner),z(kinner),'Color','b','LineStyle','none',...

'Marker','о','MarkerSize',10)

% поміщаємо поруч сточками, що потрапили усередину оболонки, їхнього номера

ht=text(x(kinner), y(kinner), z(kinner),num2str(kinner'))

set(ht,'BackgroundColor','y','VerticalAlignment','Top',...

'FontWeight','bold','Color','b')

У результаті виконання цих команд на осі графічного вікна виводиться опукла оболонка, її пронумеровані вершини і пронумеровані крапки, що потрапили усередину опуклої оболонки, відповідно до їхніх номерів у вихідній множини:

Замість функції trisurf можна використовувати функцію trimesh, що на відміну від trimesh не заливає грані кольорами.

При виклику функції convhulln(X) із другим додатковим вихідним аргументом, у ньому повертається обсяг опуклої оболонки

>> [kvert,V]=convhulln(X);

>> V

V =

0.2582

У MATLAB для побудови опуклої оболонки використовується функція qconvex пакета Qhull (http://www.qhull.org).Ці функція підтримує ряд опцій для завдання деяких параметрів алгоритму побудови опуклої оболонки, який можна задавати й у функціях convhull, convhulln.

Алгоритми побудови опуклої оболонки, у тому числі й алгоритм Quickhull, описані, наприклад, на http://algolist.manual.ru/maths/geom/convhull/. Там же приведено кілька посилань на статті з описами алгоритмів побудови опуклої оболонки множини крапок.

Для візуалізації опуклої оболонки крапок тривимірного простору не обов'язково використовувати функцію trisurf. Замість її можна самому сконструювати полігональний об'єкт із заданими способами заливання кольором ребер і граней і їхньою прозорістю.

Одним зі способів завдання полігонального об'єкта є вказівка його вершин і матриці, що містить номери вершин кожної грані, тобто саме тієї матриці, що повертається функцією convhulln. При цьому, зокрема, можна вказати колір кожної вершини і спосіб заливання граней кольором, наприклад плавна зміна кольору від вершини до вершини, як це зроблено в наступному прикладі. Полігональний об'єкт створюється за допомогою функції patch. При його створенні використовуються властивості полігонального об'єкта: