Buffer a Polygon

[THEROB]

Does anyone have a program (preferably in C++) that can look at a polygon and return another polygon around it or inside it - offset by a certain amount.

Thanks

Rob

[A$$Bandit]

Hmm, although this is the maths forum, I think you're in the wrong place, doh Programming hardly ever seems to come up here. Try the general forum or the C++ one at that...

[bugzpodder]

i can probably help you if you explain yourself a little better

[riis]

If the new shape is outside your polygon, then you won't get a polygon actually.
When a point of the polygon sticks out, and you buffer it, you'll get an arc. So, you'll get a shape which consists of lines and arcs.

[THEROB]

What I'm looking for is like the attached image

Thanks

Rob

[plenderj]

What you could do right, is pick a point to be the centrepoint of the polygon.
Then, find out the vertices of the polygon.

Imaginarily, draw points a small distance from the original vertices, in the direction of the centrepoint.
Then join up the dots

[NotLKH]

What is the format of the input data?
-Lou

[THEROB]

I am using Borland Builder so I use the TPoint, so for a square:
TPoint P[4];

P[0].x = 10;
P[0].y = 10;
P[1].x = 100;
P[1].y = 10;
P[2].x = 100;
P[2].y = 100;
P[3].x = 10;
P[3].y = 100;

But any other array form will do.

Rob

[THEROB]

plenderj - I can't find the center point and apply your rules because if the polygons center or centroid is not inside the polygon then the rules fail.

Thanks

Rob

[DiGiTaIErRoR]

Perhaps a function to find what's inside and what's out of the polygon.

The build onto it.

[NotLKH]

I've built a working progie, so I know the attached theory is good.

[NotLKH]

Here is some functional, uncommented 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

And, attached is an image of what it does:

[NotLKH]

And here's a Progie.
Just right click on the picture box to build your original Poly.

Press the "Complete the Polygon" button to close the Poly.

By altering the value from Negative to Positive in the textbox,
You will see the scribed poly built.

Double click the picture to start over.


-Lou

[THEROB]

Thanks a million - thats exactly what Iwanted

Rob

[NotLKH]

BTW, I think you should prefilter your points to make sure you
don't have two {or more } successive points with the same coordinates, and
you don't have 3 {Or More} successive points that lie on the same line.

Obviously, if you have 3 successive linear points, you only need
the first and third for your poly, and obviously if you have
two or more successive points with identical coordinates, you
only need 1.

I believe those conditions are what causes the division by zero.


-Lou

[NotLKH]

Also, you might want to know beforehand, what Offset Distance values will build
a poly "inside" vrs "outside" your original.

I beleive the best way would be a negative value should be the indicator for the progie to build outside, and Positive would be "inside". Build a preflight loop into the code, and have it build a Poly2 only slightly different with an Offset Distance value of, oh, lets say 10.

Once it builds the Preflight Poly2, it measures the total Point to Point distance of Poly2's perimeter, and Compares it to the original. Obviously, if the perimiter is smaller, then Positive values build inside, else if it was larger, then Negative values build inside.

So then it would automatically calibrate itself to change the sign of the input value you've entered to build Poly2 in the right direction.


BTW, You can't rely on measuring Poly2's perimiter to determine if Poly2 is inside vrs Outside, for large values of Offset Distance Input. Poly2 turns itself inside out when building inwards, and starts growing again.




And, 1 Last Thing. The Offset Distance Value is Not a direct measurement of how far away poly2 is from your original poly.

Its a measure of how far away their Vertice with index Zero Are from each other.

If you need to have the Offset Distance Value represent the
Exact Perpendicular distance from Wall to Wall2, well, you'll have
to tweak the code a bit, to determine MyPoly2(0) a little
differently.

-Lou

[shsavage]

Any way to do this in JavaScript?

[NotLKH]

I'm sure some JavaScript Guru can figure it out.
I don't JS.

Sorry.

[THEROB]

I think it would be very hard to do in javascript - and very slow. But here is a good place to start:
http://www.walterzorn.com/jsgraphics/jsgraphics_e.htm