3 Computing the Natural NeighborsIn

3 Computing the Natural Neighbors
Interpolant
When computing the natural neighbors interpolant,
it is important to intuit the relative ‘neighborliness,’
as (?) calls it, of adjacent Voronoi cells. These
neighbors are the points within the original point
set whose Voronoi cells intersect the Voronoi cell
of the interpolated point, if it were to be added to
the point set. The interpolated value is computed
as a weighted average of the area stolen from each
neighbor by the insertion of this point.
To compute this weighted average, we first compute
the Delaunay triangulation of the original set
of points P. Given DT(P) we need to calculate the
Voronoi cell of the point v, whose value we want to
estimate, if it were to be added to P. Since the insertion
of v will only alter DT(P) and consequently
Vor(P) locally, we do not need to recompute the entire
Delaunay triangulation. We only need to compute
a Delaunay triangulation for the points which
would be neighbors of v. In order to determine this
local point set we can use the existing triangulation
DT(P)and corresponding Voronoi diagram. The area
stolen from each neighbor of v can be computed by
finding the difference between the area of Voronoi
cell in Vor(P) and the area within the local Voronoi
diagram. The interpolated value for v is then calculated
as: P
neighbors ofv
areastolen
area of the Voronoi cell ofv
α
where alpha is the value, possibly an elevation value,
for the specific neighbor.
To compute DT(P) and transform to Vor(P) as described
earlier takes O(n logn) time where n is the
size of P. Vor(P) must be calculated once for the
original point set. The local Voronoi diagram must
be calculated for each interpolated point. Since the
size of this local subset of P does not depend on
n but rather the distribution of points in P and the
number of neighbors that the inserted point would
have, we can assume that for large point sets, this
local set of points will be much smaller than n and
will not depend on n. This means calculating the local
Voronoi diagram will take a relatively constant
amount of time independent of the size of P. In order
to determine which points belong in this local
point set we determine which triangle in DT(P) the
point lies within. We can follow the outgoing edges
from the vertices of this triangle to determine the appropriate
neighbors to include. This process again
depends on the the size of the local point set which
does not depend on n. To calculate the weighted average
we must locate Voronoi cells a constant number
of times. We can use the DAG search structure
for DT(P) to locate points and follow the dual pointers
into Vor(P). Locating a Voronoi cell will take
O(logn) time. For each point we need to interpolate
we need to perform a constant number of logn
searches plus a relatively constant amount of work
to compute the local Voronoi diagram, so to interpolate
k points for a point set of size n would take
O((n+k)logn) time.

ผลลัพธ์ (ไทย) 1:

3 คอมพิวเตอร์เพื่อนบ้านธรรมชาติInterpolantเมื่อคำนวณ interpolant เพื่อนบ้านธรรมชาติจำเป็นต้อง intuit ญาติ 'neighborliness,'เป็น (?) เรียกมัน เซลล์ที่ติด Voronoi เหล่านี้เพื่อนบ้านทั้งจุดในจุดเดิมชุดที่มีเซลล์ Voronoi ตัดเซลล์ Voronoiจุด interpolated หากมีการเพิ่มจุดที่ตั้ง คำนวณค่า interpolatedเป็นน้ำหนักเฉลี่ยของขโมยจากแต่ละพื้นที่เพื่อนบ้าน โดยการแทรกจุดนี้ในการคำนวณนี้ถ่วงน้ำหนัก เฉลี่ย เราก่อนคำนวณระบบสามสกุล Delaunay ชุดเดิมของจุด p รับ DT(P) เราจำเป็นต้องคำนวณการเซลล์ Voronoi ของจุด v ที่มีค่าที่เราต้องการหากมีการเพิ่ม P. ประเมิน ตั้งแต่การแทรกของ v จะเพียงเปลี่ยนแปลง DT(P) และจากนั้นVor(P) ท้องถิ่น เราไม่ต้องการ recompute ทั้งหมดDelaunay ระบบสามสกุล เราต้องคำนวณในระบบสามสกุล Delaunay สำหรับจุดซึ่งจะเป็นเพื่อนบ้านของ v เพื่อตรวจสอบชุดภายในจุดที่เราสามารถใช้ระบบสามสกุลที่มีอยู่DT (P) และสอดคล้องกัน Voronoi ไดอะแกรม พื้นที่ขโมยจากเพื่อนบ้านของ v สามารถคำนวณโดยหาความแตกต่างระหว่างพื้นที่ของ Voronoiเซลล์ใน Vor(P) และพื้นที่ภายใน Voronoi ท้องถิ่นไดอะแกรม จากนั้นคำนวณค่า interpolated สำหรับ vเป็น: Pเพื่อนบ้าน ofvareastolenพื้นที่ของ ofv Voronoi เซลล์Αค่า อาจจะมีค่าระดับ อัลฟาสำหรับเพื่อนบ้านเฉพาะในการคำนวณ DT(P) และแปลงเป็น Vor(P) ตามที่อธิบายไว้ก่อนหน้านี้ใช้เวลา O (n logn) โดยที่ n คือการต้องคำนวณขนาดของ P. Vor(P) ครั้งเดียวสำหรับการตั้งค่าจุดเดิม ไดอะแกรม Voronoi ท้องถิ่นต้องถูกคำนวณสำหรับแต่ละจุด interpolated เนื่องจากการขนาดของกลุ่มย่อยในท้องถิ่นของ P ไม่ขึ้นกับn แต่การกระจายของจุด P และจำนวนเพื่อนบ้านที่จุดแทรกมี เราสามารถสรุปได้ว่าสำหรับจุดใหญ่ชุด นี้ชุดท้องถิ่นของจุดจะมีขนาดเล็กกว่า n และไม่ขึ้นกับ n หมายถึงการคำนวณเฉพาะVoronoi ไดอะแกรมจะค่อนข้างคงจำนวนเวลาอิสระของขนาดของ P. ในใบสั่งการกำหนด จุดที่อยู่ในท้องถิ่นนี้ชี้ชุดเรากำหนดรูปสามเหลี่ยมซึ่งใน DT(P)จุดอยู่ในนั้น เราสามารถทำตามขอบขาออกจากจุดยอดของสามเหลี่ยมนี้เพื่อตรวจสอบเหมาะสมเพื่อนบ้านรวม กระบวนการนี้อีกครั้งขึ้นอยู่กับการตั้งค่าขนาดของจุดในท้องถิ่นซึ่งไม่ขึ้นกับ n การคำนวณค่าเฉลี่ยถ่วงน้ำหนักเราต้องค้นหาเซลล์ Voronoi จำนวนคงครั้ง เราสามารถใช้โครงสร้างค้นหา DAGสำหรับ DT(P) เพื่อค้นหาจุด และทำตามตัวชี้คู่เป็น Vor(P) ค้นหาเซลล์ Voronoi จะO(logn) ครั้ง แต่ละจุด ที่เราต้อง interpolateเราจำเป็นต้องดำเนินการอย่างต่อเนื่องจำนวน lognค้นหาและทำงานในจำนวนค่อนข้างคงในการคำนวณไดอะแกรม Voronoi ท้องถิ่น เพื่อการ interpolateจุด k สำหรับจุดชุดขนาด n จะใช้O((n+k)logn) ครั้ง

ผลลัพธ์ (ไทย) 2:

3 คอมพิวเตอร์เพื่อนบ้านธรรมชาติ
interpolant
เมื่อคำนวณเพื่อนบ้านธรรมชาติ interpolant,
มันเป็นสิ่งสำคัญที่จะตรัสรู้ญาติ 'มิตร'
เป็น (?) เรียกมันว่าของเซลล์ Voronoi ที่อยู่ติดกัน เหล่านี้
เพื่อนบ้านเป็นจุดภายในจุดเดิม
ชุดที่มีเซลล์ Voronoi ตัดเซลล์ Voronoi
ของจุดหยันถ้ามันจะถูกเพิ่มลงใน
ชุดจุด ค่าหยันคำนวณ
เป็นค่าเฉลี่ยถ่วงน้ำหนักของพื้นที่ที่ถูกขโมยมาจากแต่ละ
เพื่อนบ้านโดยการแทรกของจุดนี้.
การคำนวณนี้ถัวเฉลี่ยถ่วงน้ำหนักแรกเราคำนวณ
สม Delaunay ของชุดเดิม
ของจุดพี ป.ร. ให้ไว้ DT (P) เราต้อง ในการคำนวณ
เซลล์ Voronoi ของจุด V มีค่าเราต้องการที่จะ
ประเมินว่ามันจะถูกเพิ่มเข้าไปในพีตั้งแต่แทรก
ของโวลต์จะเปลี่ยน DT (P) และจึง
Vor (P) ในประเทศเราไม่จำเป็นต้อง เพื่อ recompute ทั้ง
สมเนย์ เราจะต้องคำนวณ
สม Delaunay สำหรับจุดที่
จะเป็นเพื่อนบ้านของ v. เพื่อตรวจสอบนี้
ชุดจุดท้องถิ่นเราสามารถใช้สมการที่มีอยู่
DT (P) และสอดคล้อง Voronoi แผนภาพ พื้นที่ที่
ถูกขโมยมาจากเพื่อนบ้านของแต่ละ V สามารถคำนวณได้โดย
การค้นหาความแตกต่างระหว่างพื้นที่ Voronoi
เซลล์ใน Vor (P) และพื้นที่ภายใน Voronoi ท้องถิ่น
แผนภาพ ค่าหยันสำหรับโวลต์จะถูกคำนวณแล้ว
เป็น: P
เพื่อนบ้าน OFV
areastolen
พื้นที่ของ Voronoi เซลล์ OFV
α
ที่อัลฟาเป็นค่าที่อาจจะมีมูลค่าสูง
. สำหรับเพื่อนบ้านที่เฉพาะเจาะจง
ในการคำนวณ DT (P) และการแปลงไป Vor (P) ตามที่อธิบายไว้
ก่อนหน้านี้ใช้เวลา O (n logn) เวลาที่ n คือ
ขนาดของพี Vor (P) จะต้องได้รับการคำนวณครั้งเดียวสำหรับ
ชุดจุดเดิม แผนภาพ Voronoi ท้องถิ่นจะต้อง
ได้รับการคำนวณสำหรับแต่ละจุดหยัน เนื่องจาก
ขนาดของกลุ่มย่อยในท้องถิ่นของ P ไม่ขึ้นอยู่กับ
n แต่การกระจายของคะแนนใน P และที่
จำนวนของประเทศเพื่อนบ้านที่จุดแทรกจะ
มีเราสามารถสรุปได้ว่าสำหรับชุดจุดขนาดใหญ่นี้
ชุดท้องถิ่นของจุดจะเป็น มีขนาดเล็กกว่า n และ
จะไม่ขึ้นอยู่กับ n ซึ่งหมายความว่าการคำนวณท้องถิ่น
แผนภาพ Voronoi จะใช้เวลาค่อนข้างคงที่
ระยะเวลาที่เป็นอิสระจากขนาดของพีเพื่อที่
จะตรวจสอบว่าจุดที่อยู่ในท้องถิ่นนี้
ชุดจุดที่เราตรวจสอบว่าสามเหลี่ยมใน DT (P) เดอะ
จุดอยู่ภายใน เราสามารถทำตามขอบขาออก
จากจุดของรูปสามเหลี่ยมนี้เพื่อตรวจสอบที่เหมาะสม
เพื่อนบ้านที่จะรวม กระบวนการนี้อีกครั้ง
ขึ้นอยู่กับขนาดของชุดจุดท้องถิ่นซึ่ง
ไม่ขึ้นอยู่กับ n ในการคำนวณค่าเฉลี่ยถ่วงน้ำหนัก
ที่เราต้องค้นหาเซลล์ Voronoi จำนวนอย่างต่อเนื่อง
ครั้ง เราสามารถใช้โครงสร้างการค้นหา DAG
สำหรับ DT (P) เพื่อหาจุดและทำตามคำแนะนำคู่
เข้า Vor (P) ตำแหน่งเซลล์ Voronoi จะใช้เวลา
O (logn) เวลา สำหรับแต่ละจุดที่เราต้องสอดแทรก
เราจำเป็นต้องดำเนินการจำนวนคงที่ของ logn
ค้นหาบวกเป็นจำนวนเงินที่ค่อนข้างคงที่ของการทำงาน
ในการคำนวณแผนภาพ Voronoi ท้องถิ่นเพื่อที่จะสอดแทรก
จุด K สำหรับชุดจุดขนาด n จะใช้เวลา
O ((N + k) logn) เวลา