创建 Voronoi 图 2/3
4.76/5 (6投票s)
Voronoi 图的创建，二叉搜索树的描述
引言
本文的代码基于我之前的文章 创建 Voronoi 图 1/2（看起来我有点乐观，称之为 1/2 而不是 1/3）。如果您有任何关于基本功能的问题，应该先查看那篇文章，因为我将假定您已知其中描述的信息。
基于 Fortune 算法的 Voronoi 图实现起来相当复杂，因此我将提供许多不同的测试项目，以便您可以一步一步地跟进实现过程。
背景
我们想要构建一个 Voronoi 图，并且如前一篇 文章中所述，基于 Fortune 的扫描线方法，Voronoi 图的变化主要由两个事件构成，即
- 站点事件，一个新点出现在扫描线上
- 圆事件，这可能发生在扫描线找到下一个点之前，也是弧消失并且再也不会可见的唯一时间。
当我们沿着扫描线移动时，我们会很快意识到我们需要在前进的过程中存储一些信息，并且需要找出线条应该在哪里被切割。
二叉搜索树
假设我们从扫描线开始下降开始，所有点都已排序。我们遇到第一个点，并且知道这个点本身不会形成一条线，也不能形成一个圆事件，因为此时还没有足够的点来做到这一点。
然后我们遇到第 2 个点，并且我们知道点 1 和点 2 会形成一条线，因为我们已经对点进行了排序。这条新线也将是 Voronoi 图中的第一个子节点。
但是现在随着我们下降，情况变得更加困难，因为我们不知道是圆事件还是新的线事件。所以我们有两种可能性：
- 这是一个圆事件，并且现有的线包含圆中的三个点。这三个点形成一个不包含任何其他点的圆。这意味着我们的第一条线将至少有两个新的子节点。一个在右边，一个在左边。
- 这是一个新的站点事件，并且新线将被添加为 Voronoi 图的附加子节点。但是它应该被添加到哪里？答案是，它应该被添加到完全在左边或完全在右边的地方。
当出现一个圆事件，且圆心位于我们的盒子之外时，我们应该怎么做？这很重要，因为我们将不得不切割我们之前计算的线。我们通常会遇到下图所示的情况，其中我们的前两个点创建了一条线，这条线必须在我们的边界之外被切割。当然，我们可以拒绝计算边界外的任何点，但这会导致两个点形成一条线，而我们的边界框无法看到该线，并在我们看到图中的第一条线之前就分割了该线。
为了控制所有这些事件，我们需要一个地方来存储所有关于计算出的线条和 Voronoi 顶点的所有信息。二叉树是理想的选择。然而，所有关于抛物线弧消失的讨论可能有点误导，因为消失的不是点，而是两个先前点形成 Voronoi 图中新线的可能性。请看下图：
Voronoi 顶点只是表示，点 1 和点 2 一起将不再影响 Voronoi 图。但是点 1 和点 3 会，点 2 和点 3 也会。理解这一点很重要。受影响的不是原始点本身，而是它们之间的关系。（有趣的是，这在很多方面让我想起了离婚，旧的两个点被扫描线中的事件迫使寻找新的伴侣。）
以编程方式执行此操作还有一个问题。那就是第一条线，它的端点将被 Voronoi 顶点切割，而两条新线都将以 Voronoi 顶点作为起点。但我应该将端点设置在哪一侧？如果您看下面的图片，它包含三个点。旧线的切割很简单，因为我们知道端点是 Voronoi 顶点，但是两条新线的切割则更加麻烦，我们知道新线从哪里开始，但这两个点中哪个是正确的点？这个问题在下面进行了说明，请记住，这必须对所有圆事件都成立：
选择将作为其端点的点的最简单方法是确定一个点是否相对于旧线位于同一侧，这是基于两个向量的叉积，并且可以在这里找到解释。
也有可能两条独立的线会形成圆中的三个点。这种情况更容易计算，因为这两条线都会有一个新的端点，并且该线将继续与这三个点中的两个点相关联。这通常发生在您闭合一个 Voronoi 单元格时。
我们也明白，位于直线上的点无法形成圆，我们应该检查不存在这种情况的圆事件。如果您看下面的第二个例子，我们可以清楚地看到这三个点无法形成任何圆，并且所有点都将成为第一条空 Voronoi 线的父节点。（如果中间点高于两侧的点，也会发生这种情况，因为圆事件尚未发生。）
那么我们如何利用所有这些新创建的线条的存储信息呢？我们假设我们的线条将形成某种分形树，类似于维基百科的插图：
二叉搜索树相对于其他数据结构的主要优点是相关的排序算法和搜索算法（如中序遍历）可以非常高效。这就是我们在 Fortune 算法中获得 O(log n) 复杂度的原因。
要了解它的作用，请看下图
我们现在意识到，我们的海滩线可以从二叉树中推断出来。我们还注意到，我们可以从二叉树中找到所有圆事件，因为我们可以简单地检查中心点左右两侧的海滩线点来创建一个新圆。理解任何圆事件总是会这样找到是至关重要的，因为这将在之后使用。
我们假设我们必须跟踪形成海滩线的中心点，但是由于圆事件是唯一可以删除任何点的事件，我们意识到只需存储我们需要与圆事件进行检查的点就足够了，并且我们将自动获得海滩线点。如果我们使用二叉树中存储的信息作为潜在圆事件将如何出现的必要信息。
存储所有 Voronoi 点的 Voronoi 线
我们需要一个类来存储所有将形成任何中心点封闭多边形的原始点。这个类还必须包括一些用于所有线终止的检查。最终问题是我们到底需要存储多少信息？
我们可以很容易地使用两点生成的线上的 信息 来计算相应的函数。我创建的用于存储点的类现在看起来是这样的
Public Class VoronoiLine
Sub New()
End Sub
Private _VoronoiParent As VoronoiLine
Public Property VoronoiParent() As VoronoiLine
Get
Return _VoronoiParent
End Get
Set(ByVal value As VoronoiLine)
_VoronoiParent = value
End Set
End Property
Private _VoronoiChildren As New List(Of VoronoiLine)
Public Property VoronoiChildren() As List(Of VoronoiLine)
Get
Return _VoronoiChildren
End Get
Set(ByVal value As List(Of VoronoiLine))
_VoronoiChildren = value
End Set
End Property
'A check to see if one of the points is the same as the creation point
Public Function Contains(ByVal P As Point) As Boolean
If CreationPointLeft = P Or CreationPointRight = P Then
Return True
Else
Return False
End If
End Function
''' <summary>
''' Finds which side of a line the point is
''' </summary>
''' <param name="PointToBeEvaluated">Evaluation point</param>
''' <returns>-1 for a point to the right, 0 for a point on the line, +1 for a point to the left</returns>
''' <remarks></remarks>
Public Function WhichSide(ByVal PointToBeEvaluated As Point) As Integer
Dim ReturnvalueEquation As Double
ReturnvalueEquation = ((PointToBeEvaluated.Y - Me.StartPoint.Y) _
* (Me.EndPoint.X - Me.StartPoint.X)) - ((Me.EndPoint.Y - Me.StartPoint.Y) _
* (PointToBeEvaluated.X - Me.StartPoint.X))
If ReturnvalueEquation > 0 Then
Return -1
ElseIf ReturnvalueEquation = 0 Then
Return 0
Else
Return 1
End If
End Function
Private _CreationPointRight As New Point
Public Property CreationPointRight() As Point
Get
Return _CreationPointRight
End Get
Set(ByVal value As Point)
_CreationPointRight = value
End Set
End Property
Private _StartPointCreatedByCircle As Boolean = False
Public Property StartPointCreatedByCircle() As Boolean
Get
Return _StartPointCreatedByCircle
End Get
Set(ByVal value As Boolean)
_StartPointCreatedByCircle = value
End Set
End Property
Private _EndPointCreatedByCircle As Boolean = False
Public Property EndPointCreatedByCircle() As Boolean
Get
Return _EndPointCreatedByCircle
End Get
Set(ByVal value As Boolean)
_EndPointCreatedByCircle = value
End Set
End Property
Private _CreationPointLeft As New Point
Public Property CreationPointLeft() As Point
Get
Return _CreationPointLeft
End Get
Set(ByVal value As Point)
_CreationPointLeft = value
End Set
End Property
'Use this if you want to cut the lines afterword
Sub New(ByVal p1 As Point, ByVal p2 As Point)
'In this class it is irrelevant witch point is the startpoint
'and witch is the endpoint, as they are only used to calculate
'the line equation coefficients first.
StartPoint = p1
EndPoint = p2
End Sub
'Use this if you want to cut the lines at creation
Sub New(ByVal p1 As Point, ByVal p2 As Point, ByVal b As Boundary)
'In this class it is irrelevant witch point is the startpoint
'and witch is the endpoint, as they are only used to calculate
'the line equation coefficients. However they cant be equal.
StartPoint = p1
EndPoint = p2
CutLinesByBoundaries(b)
End Sub
Private _StartPoint As New Point
Public Property StartPoint() As Point
Get
Return _StartPoint
End Get
Set(ByVal value As Point)
_StartPoint = value
End Set
End Property
Private _EndPoint As New Point
Public Property EndPoint() As Point
Get
Return _EndPoint
End Get
Set(ByVal value As Point)
_EndPoint = value
End Set
End Property
'It is important to notice that another line event would never cut an existing line!
'A line can only be cut if one of these two events below occurs!
'All the calculated lines must in any event be cut by the boundaries
'This is mearly a test function and has to be changed later on.
Public Function CutLinesByBoundaries(ByVal Box As Boundary) As Polyline
' We first calculate the equation coefficients
CalculateLineEquation(StartPoint, EndPoint)
Dim TempTopY, TempTopX, TempBottomY, TempBottomX As Double
TempTopY = Box.TopLeft.X * A + B
TempTopX = (Box.TopLeft.Y - B) / A
TempBottomY = Box.BottomRight.X * A + B
TempBottomX = (Box.BottomRight.Y - B) / A
'Deals with startpoint
If Not StartPointCreatedByCircle Then
If TempTopX > Box.TopLeft.X Then
If TempTopX < Box.BottomRight.X Then
StartPoint = New Point(TempTopX, Box.TopLeft.Y)
Else
StartPoint = New Point(Box.BottomRight.X, TempBottomY)
End If
Else
StartPoint = New Point(Box.TopLeft.X, TempTopY)
End If
End If
'Deals with endpoint
If Not EndPointCreatedByCircle Then
If TempBottomX > Box.TopLeft.X Then
If TempBottomX < Box.BottomRight.X Then
EndPoint = New Point(TempBottomX, Box.BottomRight.Y)
Else
EndPoint = New Point(Box.BottomRight.X, TempBottomY)
End If
Else
TempBottomY = Box.TopLeft.X * A + B
EndPoint = New Point(Box.TopLeft.X, TempBottomY)
End If
End If
Dim d As New Polyline
d.Points.Add(StartPoint)
d.Points.Add(EndPoint)
d.ToolTip = Math.Round(StartPoint.X, 0) & " and " & Math.Round(StartPoint.Y, 0) & "; " & Math.Round(EndPoint.X, 0) & " and " & Math.Round(EndPoint.Y, 0)
d.Stroke = Brushes.Black
d.StrokeThickness = 2
Return d
End Function
'All the lines in the center of the Voronoi map would be cut by at least one or two circle events
Public Function GetLine() As Polyline
Dim d As New Polyline
d.Points.Add(StartPoint)
d.Points.Add(EndPoint)
d.Stroke = Brushes.Black
d.StrokeThickness = 2
Return d
End Function
'We will store up to two points in the private collection
Private CircleEvents As New List(Of Point)
Private LineIsCreatedFromVertexEvent As Boolean = False
Public Sub CircleEventAppear(ByVal CircleCenter As Circle)
CircleEvents.Add(CircleCenter.CenterPoint)
If CreationPointLeft = Nothing Then
LineIsCreatedFromVertexEvent = True
End If
End Sub
Public Sub CutLineOnCircleEvents()
'If we at the end end up with just one circle event we would have to assume that
'the line go's from the one Voronoi vertex (circle point) to one of the boundaries
If CircleEvents.Count = 0 Then
'This could happen if we for instance design a Voronoi diagram with just two points
Exit Sub
End If
If CircleEvents.Count = 1 Then
'The circle cuts the line in half, the question is witch half sould you cut?
If LineIsCreatedFromVertexEvent Then
' The Vertex is below either one or both line creation points meaning that it is
' Remove the line that goes from the higest Y point
_StartPoint = CircleEvents(0)
Else
_EndPoint = CircleEvents(0)
End If
Else
'The maximum circle event for a single line is two
If CircleEvents(0).Y > CircleEvents(1).Y Then
_StartPoint = CircleEvents(0)
_EndPoint = CircleEvents(1)
Else
_StartPoint = CircleEvents(1)
_EndPoint = CircleEvents(0)
End If
End If
'To determine witch of the two boundary points we would have to remove, we can do that by checking the creation point
'and the circle point. If the circle point is below the CreationPoint, The line below have to go, and if the circle
'point is above the CreationPoint the line above have to be cut. Remember that this is only valid if just one circle
'event is present when the diagram is completed!
End Sub
'Line equation coefficients, only used internally in this class
' y = Ax + B
Dim A, B As Double
Private Sub CalculateLineEquation(ByVal p1 As Point, ByVal p2 As Point)
'Calculate and store the A and B coefficients from the equation here
'http://en.wikipedia.org/wiki/Line_equation#Two-point_form
Dim slope As Double
slope = (p2.Y - p1.Y) / (p2.X - p1.X)
A = (slope)
B = (-slope * p1.X + p1.Y)
End Sub
''' <summary>
''' Calculates the line between two Parabolic intersections
''' </summary>
''' <param name="Point1">A point in the Voronoi diagram</param>
''' <param name="point2">A Point in the Voronoi diagram (different from point 1)</param>
''' <param name="ys">The position of the sweep line</param>
''' <remarks>It would give wrong values if the two points have the same or close to the same Y coordinate, as the double has limited significant storage</remarks>
Public Sub ParabolicCut(ByVal Point1 As Point, ByVal point2 As Point, ys As Double) 'As VoronoiLine
'Stores the values in double format, as I didnt bother to rewrite Benjamin Dittes quadratic equation.
Dim x1, y1, x2, y2 As Double
'Inizialize Point 1
x1 = Point1.X
y1 = Point1.Y
'Inizialize Point 2
x2 = point2.X
y2 = point2.Y
'Sweep line, added 500 to make sure the two calculated points are well of the boundaries
ys = ys + 500
'Setting ut calculation of the quadratic equation
Dim a1 As Double = 1 / (2 * (y1 - ys))
Dim a2 As Double = 1 / (2 * (y2 - ys))
'The two resulting values of x from the quadratic equation
Dim xs1 As Double = 0.5 / (2 * a1 - 2 * a2) * (4 * a1 * x1 - 4 * a2 * x2 + 2 * Math.Sqrt(-8 * a1 * x1 * a2 * x2 - 2 * a1 * y1 + 2 * a1 * y2 + 4 * a1 * a2 * x2 * x2 + 2 * a2 * y1 + 4 * a2 * a1 * x1 * x1 - 2 * a2 * y2))
Dim xs2 As Double = 0.5 / (2 * a1 - 2 * a2) * (4 * a1 * x1 - 4 * a2 * x2 - 2 * Math.Sqrt(-8 * a1 * x1 * a2 * x2 - 2 * a1 * y1 + 2 * a1 * y2 + 4 * a1 * a2 * x2 * x2 + 2 * a2 * y1 + 4 * a2 * a1 * x1 * x1 - 2 * a2 * y2))
'Generate two points to store the two intersection points
Dim p1, p2 As New Point
p1.X = xs1
p2.X = xs2
p1.Y = 0
p2.Y = 0
'Find the resulting Y values calculated from the quadratic equation
' (It dosent matter that the Y is 0 as the function Intersection2 only uses the X value for computation)
p1.Y = Intersection2(p1, Point1, ys)
p2.Y = Intersection2(p2, Point1, ys)
'Sort first and then add the two calculated poitns
If p1.Y > p2.Y Then
Me.StartPoint = (p1)
Me.EndPoint = (p2)
ElseIf p1.Y = p2.Y Then
' if they are the same save them in the order of the X values
If p1.X < p2.X Then
Me.StartPoint = (p1)
Me.EndPoint = (p2)
Else
Me.StartPoint = (p2)
Me.EndPoint = (p1)
End If
Else
Me.StartPoint = (p2)
Me.EndPoint = (p1)
End If
If WhichSide(Point1) >= 0 Then
CreationPointRight = Point1
CreationPointLeft = point2
Else
CreationPointRight = point2
CreationPointLeft = Point1
End If
End Sub
''' <summary>
''' Returns the y value construcked by the event from the newpoint and the contructed arc of the oldpoint
''' </summary>
''' <param name="NewPoint">This is the point on the sweep line</param>
''' <param name="OldPoint">This is one point above the sweep line</param>
''' <param name="SweepLine">Y position of the sweep line</param>
''' <returns>Calculates the distance fromn a point (NewPoint) to the Parabolic arc generated by the OldPoint and the Sweep line</returns>
''' <remarks>The Function only gives you the Y value of the position on the parabolic intersection given the X location</remarks>
Private Function Intersection2(ByVal NewPoint As Point, ByVal OldPoint As Point, ByVal SweepLine As Double) As Double
Dim res As Double
res = (1 / (2 * ((OldPoint.Y) - SweepLine)))
res *= (NewPoint.X ^ 2 - 2 * OldPoint.X * NewPoint.X + OldPoint.X ^ 2 + OldPoint.Y ^ 2 - SweepLine ^ 2)
Return (res)
End Function
End Class
创建 Voronoi 图的边界
Voronoi 图的边界仅在您希望所有点具有有限区域时才需要。该图实际上会给点集合外部的点一个无限区域，因此我们将生成限制在一个预定义的矩形框内。
我们已经假设您已经根据 Y 值对点进行了排序，但为了使此功能正常工作，我还要根据 X 值对它们进行排序。（也就是说，我实际上不需要对点进行排序，我只需要 Ymin 和 Ymax 值以及 Xmin 和 Xmax 值，来形成限制站点区域的矩形。
我们有两种选择，我们可以在执行扫描线之前定义我们感兴趣创建 Voronoi 图的区域，或者我们可以根据您想要从中创建 Voronoi 图的点来计算区域。
我们将构建一个自己的类（称为 boundary），它足够通用，可以用于任何点集，因此它非常庞大，我不会在这里详细解释它，因为它与 Voronoi 图的构建关系不大。
Public Class Boundary
'You cant set these variables outside the function
Private _TopLeft As New Point
Private _BottomRight As New Point
'In case you change the increase the values are stored
Private pSortedByXdirection, pSortedByYdirection As New PointCollection
Public ReadOnly Property TopLeft() As Point
Get
Return _TopLeft
End Get
End Property
Public ReadOnly Property BottomRight() As Point
Get
Return _BottomRight
End Get
End Property
#Region "Constructors"
Sub New(ByVal pTopLeft As Point, pBottomRight As Point)
_TopLeft = pTopLeft
_BottomRight = pBottomRight
End Sub
Sub New(ByVal SortedByX_directioon As PointCollection, ByVal SortedByYdirection As PointCollection)
CalculateBondariesFromPointCollection(SortedByX_directioon, SortedByYdirection)
pSortedByXdirection = SortedByX_directioon
pSortedByYdirection = SortedByYdirection
End Sub
Sub New(ByVal OriginalPointcollection As PointCollection)
pSortedByXdirection = SortPoints(OriginalPointcollection, True)
pSortedByYdirection = SortPoints(OriginalPointcollection, False)
CalculateBondariesFromPointCollection(pSortedByXdirection, pSortedByYdirection)
End Sub
Sub New()
End Sub
#End Region
''' <summary>
''' Returns a sorted pointcollection based on Lexografically sorting
''' </summary>
''' <param name="samplepoints"></param>
''' <param name="SortByXdirection"></param>
''' <returns></returns>
''' <remarks></remarks>
Private Function SortPoints(ByVal samplepoints As PointCollection, ByVal SortByXdirection As Boolean) As PointCollection
'Create another array so we can keep the original array out of order
Dim copySamplePoints As Point() = New Point(samplepoints.Count - 1) {}
samplepoints.CopyTo(copySamplePoints, 0)
If SortByXdirection Then
Array.Sort(copySamplePoints, New PointSort(PointSort.Mode.X))
Else
Array.Sort(copySamplePoints, New PointSort(PointSort.Mode.Y))
End If
Dim result As New PointCollection
For Each p As Point In copySamplePoints
result.Add(p)
Next
Return result
End Function
Private Class PointSort
Implements IComparer
Public Enum Mode
X
Y
End Enum
Private currentMode As Mode = Mode.X
Public Sub New(ByVal mode As Mode)
currentMode = mode
End Sub
'Comparing function
'Returns one of three values - 0 (equal), 1 (greater than), -1 (less than)
Private Function IComparer_Compare(ByVal a As Object, ByVal b As Object) As Integer Implements IComparer.Compare
Dim point1 As Point = CType(a, Point)
Dim point2 As Point = CType(b, Point)
If currentMode = Mode.X Then
'Compare X values
If point1.X > point2.X Then
Return 1
ElseIf point1.X < point2.X Then
Return -1
Else
If point1.Y > point2.Y Then
Return 1
ElseIf point1.Y < point2.Y Then
Return -1
Else 'Identical points
Return 0
End If
End If
Else
If point1.Y > point2.Y Then
'Compare Y Values
Return 1
ElseIf point1.Y < point2.Y Then
Return -1
Else 'Y1 = Y2
If point1.X > point2.X Then
'Compare Y Values
Return 1
ElseIf point1.X < point2.X Then
Return -1
Else 'Identical points
Return 0
End If
End If
End If
End Function
End Class
Private Sub CalculateBondariesFromPointCollection(ByVal SortedByX_directioon As PointCollection, ByVal SortedByYdirection As PointCollection)
Dim p1, p2, p3, p4 As New Point
p1 = SortedByX_directioon(0)
p2 = SortedByYdirection(0)
'Temporary storage of min and max values in the pointcollection
Dim Xmin, Ymin, Xmax, Ymax As Double
If p1.X < p2.X Then
Xmin = p1.X
Else
Xmin = p2.X
End If
If p1.Y < p2.Y Then
Ymin = p1.Y
Else
Ymin = p2.Y
End If
p3 = SortedByX_directioon(SortedByX_directioon.Count - 1)
p4 = SortedByYdirection(SortedByYdirection.Count - 1)
If p3.X < p4.X Then
Xmax = p4.X
Else
Xmax = p3.X
End If
If p3.Y < p4.Y Then
Ymax = p4.Y
Else
Ymax = p3.Y
End If
'We are going to base the increase at the Width and Height of the rectangle
'so we are going to performe some calculations in order to make these adjustments
Dim height As Double = Math.Abs(Ymax - Ymin)
Dim width As Double = Math.Abs(Xmax - Xmin)
'Scale the with and height in order to add and substract the values to Y and X
Dim _height As Double = height * (ProcentIncrease) / 100
Dim _width As Double = width * (ProcentIncrease) / 100
'Store the final values
_TopLeft = New Point(Xmin - _width, Ymin - _height)
_BottomRight = New Point(Xmax + _width, Ymax + _height)
End Sub
Public Sub ReturnRectangle(ByVal can As Canvas)
Dim p As New Rectangle
p.Fill = Nothing
p.StrokeThickness = 2
p.Stroke = Brushes.Blue
' Set the width and height of the Rectangle.
' The values can be negative therefore the Math.Abs
p.Width = Math.Abs(_BottomRight.X - _TopLeft.X)
p.Height = Math.Abs(_BottomRight.Y - _TopLeft.Y)
can.Children.Add(p)
Canvas.SetLeft(p, _TopLeft.X)
Canvas.SetTop(p, _TopLeft.Y)
End Sub
'In reality the value of 50 (width is incresed by the factor 1.5) that would increase the bondaries with 25% on all sides
' To use it you simply write in the increase at for instance 40 (percent)
Private _ProcentIncrease As Double = 50
Public Property ProcentIncrease() As Double
Get
Return _ProcentIncrease
End Get
Set(ByVal value As Double)
_ProcentIncrease = (value)
'Value is changed we need to update the topmost and bottommost points
CalculateBondariesFromPointCollection(pSortedByXdirection, pSortedByYdirection)
End Set
End Property
End Class
历史
现在这样就足够了，因为所有的主要概念都已处理完毕，只剩下构建最终实现。
本文没有可供下载的代码，因为我只处理了二叉搜索树，还没有进行最终实现。二叉搜索树也需要一个自己的类，就像 Benjamin Dittes 使用的那样。
更新
我决定包含未完成的代码文件，但它不包含二叉树，并且在任何方面都不完整，不像之前的代码。它只是为了让您在着手下一次（也是最后一次）关于这个主题的文章时，能够自己测试一下。
参考文献
上一篇文章中的两本书仍然是本文的主要参考资料：
- “计算几何：算法与应用”，第三版，2008 年，Mark de Berg，Otfried Cheong，Marc van Kreveld 和 Mark Overmars。
- “C 语言计算几何”，第二版，2008 年，Joseph O'Rourke
BenDi 的实现也很有用：
https://codeproject.org.cn/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C
他更新了他的代码，您可以在这里下载他的新版本：
https://sites.google.com/site/bdittes/FortuneVoronoi.zip
还有一个链接解释了历史并提供了详细的数学描述：
http://www.pi6.fernuni-hagen.de/publ/tr198.pdf
http://cgm.cs.mcgill.ca/~mcleish/644/Projects/DerekJohns/Sweep.htm