Anda dapat menerapkan ide pertama Anda dalam memilih tepi yang titik tengahnya berada pada perpotongan dengan garis Voronoi dengan memanfaatkan DelaunayTri kelas dan edges< /a> dan metode nearestNeighbor. Berikut ini contoh dengan 10 pasangan acak nilai x dan y:
x = rand(10,1); %# Random x data
y = rand(10,1); %# Random y data
dt = DelaunayTri(x,y); %# Compute the Delaunay triangulation
edgeIndex = edges(dt); %# Triangulation edge indices
midpts = [mean(x(edgeIndex),2) ... %# Triangulation edge midpoints
mean(y(edgeIndex),2)];
nearIndex = nearestNeighbor(dt,midpts); %# Find the vertex nearest the midpoints
keepIndex = (nearIndex == edgeIndex(:,1)) | ... %# Find the edges where the
(nearIndex == edgeIndex(:,2)); %# midpoint is not closer to
%# another vertex than it is
%# to one of its end vertices
edgeIndex = edgeIndex(keepIndex,:); %# The "good" edges
Dan sekarang edgeIndex adalah matriks N-kali-2 di mana setiap baris berisi indeks menjadi x dan y untuk satu sisi yang mendefinisikan koneksi "dekat". Plot berikut mengilustrasikan triangulasi Delaunay (garis merah), diagram Voronoi (garis biru), titik tengah tepi triangulasi (tanda bintang hitam), dan tepi "baik" yang tersisa di edgeIndex (garis merah tebal):
triplot(dt,'r'); %# Plot the Delaunay triangulation
hold on; %# Add to the plot
plot(x(edgeIndex).',y(edgeIndex).','r-','LineWidth',3); %# Plot the "good" edges
voronoi(dt,'b'); %# Plot the Voronoi diagram
plot(midpts(:,1),midpts(:,2),'k*'); %# Plot the triangulation edge midpoints
Bagaimana itu bekerja...
Diagram Voronoi terdiri dari serangkaian poligon atau sel Voronoi. Pada gambar di atas, setiap sel mewakili wilayah di sekitar titik triangulasi tertentu yang melingkupi semua titik dalam ruang yang lebih dekat ke titik tersebut dibandingkan titik lainnya. Akibatnya, jika Anda memiliki 2 simpul yang tidak berdekatan dengan simpul lainnya (seperti simpul 6 dan 8 pada gambar Anda), maka titik tengah garis yang menghubungkan simpul-simpul tersebut berada pada garis pemisah antara sel Voronoi untuk sudut.
Akan tetapi, jika ada simpul ketiga yang dekat dengan garis yang menghubungkan 2 simpul tertentu, maka sel Voronoi untuk simpul ketiga dapat memanjang di antara 2 simpul tersebut, melintasi garis yang menghubungkan keduanya dan menutup titik tengah garis tersebut. Oleh karena itu, simpul ketiga ini dapat dianggap sebagai tetangga yang "lebih dekat" dengan 2 simpul tertentu dibandingkan dengan 2 simpul satu sama lain. Pada gambar Anda, sel Voronoi untuk simpul 7 meluas ke daerah antara simpul 1 dan 2 (dan 1 dan 3), sehingga simpul 7 dianggap sebagai tetangga yang lebih dekat dengan simpul 1 daripada simpul 2 (atau 3).
Dalam beberapa kasus, algoritme ini mungkin tidak menganggap dua simpul sebagai tetangga "dekat" meskipun sel Voronoinya bersentuhan. Simpul 3 dan 5 pada gambar Anda adalah contohnya, di mana simpul 2 dianggap sebagai tetangga yang lebih dekat dengan simpul 3 atau 5 dibandingkan simpul 3 atau 5 satu sama lain.
person
gnovice
schedule
10.02.2011
