Tuesday, September 9, 2008

Algorithm to buffer a polygon

I came across the need to buffer a polygon. Of course, ESRI provides tool in ArcMap to achieve this, but I needed an algorithm to use in an application rather than a tool. I could not find the algorithm, but I found the code to achieve this. Still, it should be fairly easy to figure out the algorithm by reading the code. You can find by clicking here. It's in VB, so I had to convert it to C++.

In case the link is broken, I am including the source code:

Private Type XY
p_X As Double
p_Y As Double
End Type
Dim MyPoly() As XY
Dim MyPoly2() As XY
Dim MyMidLines() As XY
Dim MyLine() As XY

Private Sub OUTLINE_IT()
'MyPoly is a matrix from 0 to N, containing the X and Y values of the
'points of the original polygon
'MyPoly2 is the Output Poly

Dim I As Integer
Dim PI As Integer
Dim NI As Integer '
Dim p_1 As XY
Dim p_2 As XY
Dim t1 As Double
Dim t2 As Double
Dim MidP As XY
Dim MySign As Integer

ReDim MyMidLines(UBound(MyPoly))
ReDim MyPoly2(UBound(MyPoly))
ReDim MyLine(UBound(MyPoly))
Dim MyD As Long
MyD = Val(txtSize.Text)
MySign = Sgn(MyD)
Picture1.Cls
If MySign <> 0 Then
For I = 0 To UBound(MyPoly)
PI = ((I - 1) + UBound(MyPoly) + 1) Mod (UBound(MyPoly) + 1)
NI = ((I + 1) + UBound(MyPoly) + 1) Mod (UBound(MyPoly) + 1)
Picture1.Line (MyPoly(I).p_X, MyPoly(I).p_Y)-(MyPoly(NI).p_X, MyPoly(NI).p_Y), vbBlack
MyLine(I).p_X = MyPoly(NI).p_X - MyPoly(I).p_X
MyLine(I).p_Y = MyPoly(NI).p_Y - MyPoly(I).p_Y
t1 = Sqr(((MyPoly(PI).p_X - MyPoly(I).p_X) ^ 2 + (MyPoly(PI).p_Y - MyPoly(I).p_Y) ^ 2) / _
((MyPoly(NI).p_X - MyPoly(I).p_X) ^ 2 + (MyPoly(NI).p_Y - MyPoly(I).p_Y) ^ 2))
MidP.p_X = (MyPoly(PI).p_X + (MyPoly(NI).p_X - MyPoly(I).p_X) * t1 + MyPoly(I).p_X) / 2
MidP.p_Y = (MyPoly(PI).p_Y + (MyPoly(NI).p_Y - MyPoly(I).p_Y) * t1 + MyPoly(I).p_Y) / 2

MyMidLines(I).p_X = (MidP.p_X - MyPoly(I).p_X)
MyMidLines(I).p_Y = (MidP.p_Y - MyPoly(I).p_Y)

Next I

t1 = MySign * Sqr((MyD ^ 2) / (MyMidLines(0).p_X ^ 2 + MyMidLines(0).p_Y ^ 2))

MyPoly2(0).p_X = t1 * MyMidLines(0).p_X + MyPoly(0).p_X
MyPoly2(0).p_Y = t1 * MyMidLines(0).p_Y + MyPoly(0).p_Y

For I = 0 To UBound(MyPoly)
PI = ((I - 1) + UBound(MyPoly) + 1) Mod (UBound(MyPoly) + 1)
NI = ((I + 1) + UBound(MyPoly) + 1) Mod (UBound(MyPoly) + 1)
t2 = (MyLine(I).p_Y * MyPoly2(I).p_X - MyLine(I).p_X * MyPoly2(I).p_Y + MyLine(I).p_X * MyPoly(NI).p_Y - _
MyLine(I).p_Y * MyPoly(NI).p_X) / (MyLine(I).p_Y * MyMidLines(NI).p_X - MyLine(I).p_X * MyMidLines(NI).p_Y)
MyPoly2(NI).p_X = MyMidLines(NI).p_X * t2 + MyPoly(NI).p_X
MyPoly2(NI).p_Y = MyMidLines(NI).p_Y * t2 + MyPoly(NI).p_Y
Picture1.Line (MyPoly2(I).p_X, MyPoly2(I).p_Y)-(MyPoly2(NI).p_X, MyPoly2(NI).p_Y), vbBlack
Next I
End If

End Sub

1 comment:

Surya Prakash said...

Hello,
This is good. c++ variant is available some where?

Prakash