คุณสามารถใช้แนวคิดแรกในการเลือกขอบที่มีจุดกึ่งกลางตัดกับเส้นโวโรนอยได้โดยใช้ DelaunayTri คลาส และ edges< /a> และ nearestNeighbor วิธีการ นี่คือตัวอย่างที่มีค่า x และ y แบบสุ่ม 10 คู่:
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
และตอนนี้ edgeIndex เป็นเมทริกซ์ขนาด N คูณ 2 โดยแต่ละแถวมีดัชนีเป็น x และ y สำหรับขอบด้านหนึ่งที่กำหนดการเชื่อมต่อ "ใกล้" โครงเรื่องต่อไปนี้แสดงรูปสามเหลี่ยม Delaunay (เส้นสีแดง) แผนภาพโวโรนอย (เส้นสีน้ำเงิน) จุดกึ่งกลางของขอบรูปสามเหลี่ยม (เครื่องหมายดอกจันสีดำ) และขอบ "ดี" ที่ยังคงอยู่ใน edgeIndex (เส้นหนาสีแดง):
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
มันทำงานอย่างไร...
แผนภาพโวโรนอยประกอบด้วยชุดของรูปหลายเหลี่ยมโวโรนอยหรือเซลล์ ในภาพด้านบน แต่ละเซลล์แสดงถึงพื้นที่รอบๆ จุดยอดรูปสามเหลี่ยมที่กำหนด ซึ่งล้อมรอบจุดทั้งหมดในอวกาศที่อยู่ใกล้กับจุดยอดนั้นมากกว่าจุดยอดอื่นๆ ด้วยเหตุนี้ เมื่อคุณมีจุดยอด 2 จุดที่ไม่ใกล้กับจุดยอดอื่นๆ (เช่นจุดยอด 6 และ 8 ในภาพของคุณ) จุดกึ่งกลางของเส้นที่เชื่อมจุดยอดเหล่านั้นจะตกบนเส้นแบ่งระหว่างเซลล์ Voronoi สำหรับ จุดยอด
อย่างไรก็ตาม เมื่อมีจุดยอดที่สามซึ่งอยู่ใกล้กับเส้นที่เชื่อมจุดยอด 2 จุดเข้าด้วยกัน เซลล์โวโรนอยสำหรับจุดยอดที่สามอาจขยายระหว่างจุดยอด 2 จุดที่กำหนด โดยข้ามเส้นที่เชื่อมจุดนั้นเข้าด้วยกันและปิดจุดกึ่งกลางของเส้นนั้น จุดยอดที่สามนี้จึงถือได้ว่าเป็นเพื่อนบ้านที่ "ใกล้กว่า" กับจุดยอด 2 จุดที่กำหนด มากกว่าจุดยอด 2 จุดที่อยู่ติดกัน ในภาพของคุณ เซลล์โวโรนอยสำหรับจุดยอด 7 ขยายเข้าไปในขอบเขตระหว่างจุดยอด 1 และ 2 (และ 1 และ 3) ดังนั้นจุดยอด 7 จึงถือว่าเป็นจุดใกล้เคียงใกล้กับจุดยอด 1 มากกว่าจุดยอด 2 (หรือ 3)
ในบางกรณี อัลกอริธึมนี้อาจไม่ถือว่าจุดยอดสองจุดเป็น "ใกล้" เพื่อนบ้าน แม้ว่าเซลล์โวโรโนอิจะสัมผัสกันก็ตาม จุดยอด 3 และ 5 ในภาพของคุณคือตัวอย่างหนึ่งของสิ่งนี้ โดยที่จุดยอด 2 ถือเป็นจุดที่อยู่ใกล้เคียงกับจุดยอด 3 หรือ 5 มากกว่าจุดยอด 3 หรือ 5 ที่อยู่ใกล้เคียงกัน
person
gnovice
schedule
10.02.2011
