2-D geometry problem - HELP!

Hello:

I have an irregular polygon defined by a set of ~1000
coordinate vertices. I know the area and perimeter of the
polygon and I need to increase the polygon area to an
arbitrary user-defined area by a certain distance (buffering all
sides). The end result will be a scaled-up version of the old
polygon, with the same center

In order to do this, I need to know the buffer distance. Does
anyone know how to calculate the buffer distance, if I'm
given the old polygon area, the old polygon perimeter, and the
new polygon area?

Thanks for any clues you can provide!!!

Is this a convex polygon? I can't think of any reliable way to do this on a concave polygon. I also forget the exact definition of convex vs concave for polygons, so if you aren't sure, you might have to look it up.

The advantage of a convex polygon is that it can be drawn as a set of triangles. In fact, that may be the definition. It is convex if you can draw a straight line from each point to every other point without going outside of the polygon.

The math might get a little complicated, but the sum of the area of all the triangles would be the area of the whole surface. If you increase area from 10 to 30, and triangle 1 makes up 5% of the total area, increase the size of triangle 1 by 5% of 20 (30-10, the increase in area). This seems to work best only if you can use the center of the polygon as a fixed vertex for all the triangles. If you use one of the perimeter vertices, it seems like this would cause the polygon to expand away from that point.

Another possibility if you can count on the polygon being roughly round, is to just use a circle, since 100 vertices would pretty much describe a circle, but I imagine you have already ruled that out.

Hope this helps.

Shaggy Hiker:

Yeah. I forgot to mention that the polygons will generally
be concave ... but it was a nice thought. Thanks for the
response, and sorry if I wasted your time by not providing
the specifics. This seems to be a very tough analytical
geometry prob. I was able to determine that the area of
a polygon grows linearly (when expanded equally in all
directions). I think the slope of this line is a factor that is
specific to each individual polygon, and I have no idea
how this would be determined.

Let me know if you (or anyone else listening in!) can give
me another leg up!

Good Night,

I think you have the answer given to yourself.
You said:

Quote:

---

I was able to determine that the area of a polygon grows linearly (when expanded equally in all
directions).

---

You have the actual area size.
Increase the area by stepping the 1 increment in each direction, caculate the area-size now.
The relation of both sizes will give you the slope of the linear groth!

I don't think it will work when you're buffering the polygon.
Buffering is NOT the same as scaling it up.
With irregular concave polygons holes might occur when you're buffering the sides. This will happen when two ears of the polygon will overlap due to the buffer. (An ear is an area formed by a triangle which exists of two following sides of the polygon and a third side, which connects the end points of both sides. An ear is always on the inside of a polygon, as opposed to a mouth.)

I'm afraid there's no analytical way to solve your problem. (Or maybe "just" a very complex way). Just trial and error. But I do not know for sure.

riis, opus:

Opus, your method would work, but Riis brings up something
that I hadn't considered. With the polygons that I'm dealing
with, I would expect to see such "holes" from time to time.

Thanks all for your time.

Any concave polygon can be seen as being composed of some number of convex polygons. It may be easier to detach your concave polygon into individual convex polygons, but you would then have to be very careful how each polygon expanded, since the area of the total would not be the sum of the areas of the individuals. This would be because as the individual convex polygons expand, they will overlap, such that the concave polygon they represent will be less than the sum of the convex polygons.

However, it may still be of value to consider it this way. You might see if you can come up with a series of equations to calculate the areas of the convex polygons, then expand the concave polygon and re-calculate. The change in the equations for the convex polygons may lead somewhere useful.

I tend to focus on convex polygons because all 3-D graphics take this approach. Each concave polygon is broken into convex polygons, and in about the same step, the convex polygons are broken into triangles. I suspect your problem is solvable for convex polygons, but may not be directly solvable for concave polygons.

Shaggy Hiker:

Once again, thank you. That's a novel approach, but it just
seems like there would be a lot of steps in there. Perhaps
an iterative algorithm (whereby I would grow the contour
until the user-selected area is reached) would be simpler
to code and work just as well? I was more just seeing if
there was a math equation I could set up.

Thanks!

Offhand I'd scale the coordinates by
f = Sqr(NewArea / CurrentArea)

Scaling just isn't right. Here's a simple example.
Suppose, you have a rectangle (which is a polygon, even convex) with dimensions 5 x 2. The area of it is 10. If you want the short side to be 3 you have to multiply the long side with 1 1/2 as well. The new dimensions will be 7 1/2 x 3.
If you buffer the rectangle with a 1/2 unit, then the dimensions will be (5 + 1) x (2 + 1) = 6 x 3.

Quote:

---

Originally posted by riis
Scaling just isn't right. Here's a simple example.
Suppose, you have a rectangle (which is a polygon, even convex) with dimensions 5 x 2. The area of it is 10. If you want the short side to be 3 you have to multiply the long side with 1 1/2 as well. The new dimensions will be 7 1/2 x 3.
If you buffer the rectangle with a 1/2 unit, then the dimensions will be (5 + 1) x (2 + 1) = 6 x 3.

---

The buffering distance is not necessarily the same for each side, otherwise you can't preserve the aspect ratio (in your example above you have 5/2 = 2.5 and 6/3 = 2).

Well, I thought the idea was to replot a new polygon given the new area. If I have correctly understood, the problem is plotting the new polygon after dragging on one of the sides.

Referring to the attached figure, If you drag the mouse from point P to point P', then the buffering distance for the corresponding side will be PQ. To calculate it you have to find the intercept between the straight lines OPQ and MN, the parellel to side AB through point Q.

http://www.vbforums.com/attachment.p...postid=1380685

Let the various coordinates be:

A: x_k, y_k
B: x_k+1, y_k+1
O: 0,0
P: x₀, y₀
P': x₁, y₁
Q: x₂, y₂

Then the equation of OPQ is

y = (y₀/x₀)x

and that of MN:

y = y₁ + (x - x₁) * [(y_k+1 - y_k) / (x_k+1 - x_k)]

Calling s the slope,

s = (y_k+1 - y_k) / (x_k+1 - x_k)

the coordinates of the intercept Q are:

x₂ = (sx₁ - y₁) / (s - y₀/x₀)
y₂ = (y₀/x₀)x₂

Now the scaling factor
f = x₂/x₀ = y₂/y₀

can be used to scale all the polygon coordinates.

I think we need something sorted out by HeVa!

Riis is trying to increase an polygon by increasing one side.
krtxmrtz is moving the polygon

And as I understood the thing from HeVa he wanted to increase the TOTAL area by a factor.

Which is true!!


and for krtxmrtz:
If you move the poygon from p to p' you have the deltaX and deltaY that could be added to any polygon edge, and than you'Re done!

I'm not MOVING the polygon, I'm blowing it up. I use the shift to derive the scaling factor that's to be applied to all the coordinates. For example, by applying my recipe above you could update the shape in a mouse move event subroutine.

Hi everyone!

I appreciate your interest, and I'm afraid that the debate
is all my fault. This part of my problem description was
correct:

Quote:

---

...I know the area and perimeter of the
polygon and I need to increase the polygon area to an
arbitrary user-defined area by a certain distance (buffering all
sides).

---

However, this part was indeed misleading (sorry krtxmrtz,
preserving the aspect ratio isn't necessary):

Quote:

---

...The end result will be a scaled-up version of the old
polygon, with the same center.

---

I was trying to describe buffering as RIIS correctly inferred.
When I said "scaled up" I didn't mean a scaling transformation,
which (I agree with you) would be quite easy!

Instead of wanting to drag just one side to a new extent,
as you describe, I'm looking to expand on all sides by a
uniform amount. This means that no matter where you are
on polygon p, you will be x distance from the closest point
on p' (the new polygon), except in the 'ears' case that RIIS
describes. I agree with RIIS's assessment that these 'ears'
appear to make what I'm after a virtual impossibility.

I truly appreciate all of your input, and glad I could spark
such a lively debate on 2-D geometry.

Thanks So Much.