471,071 Members | 1,340 Online

Interesting Geometry Problem - IQ of 140+ Required :-)

//Shrinks the specified polygon by one pixel (in any relevant direction)
//so that the shrunken polygon sits exactly within the original (specifed)
polygon.
public void Point[] ShrinkPolygon(Point[] polygon)
{
//How do I do this?
}
Sep 24 '06 #1
6 1954
//Shrinks the specified polygon by one pixel (in any relevant direction)
//so that the shrunken polygon sits exactly within the original (specifed)
polygon.
public void Point[] ShrinkPolygon(Point[] polygon)
{
//How do I do this?
}

Take this to comp.graphics.algorithms
Sep 24 '06 #2
//Shrinks the specified polygon by one pixel (in any relevant direction)
//so that the shrunken polygon sits exactly within the original (specifed)
polygon.
public void Point[] ShrinkPolygon(Point[] polygon)
{
//How do I do this?
}

You start by finding the 'middle' of the polygon. Add all X-values up and
divide by the number of values. Add all Y-values up and divide by the number
of values.

Compose a System.Drawing.Drawing2D.Matrix object that translates the points
to the origin, Scale() it in both directions by, say, 0.99 and translate it
back to its original position
Sep 24 '06 #3
On Sun, 24 Sep 2006 00:16:01 -0700, "John Smith" <js****@nowhere.com>
wrote:
>//Shrinks the specified polygon by one pixel (in any relevant direction)
//so that the shrunken polygon sits exactly within the original (specifed)
polygon.
Impossible in the general sense because purely mathematical
calculations won't be pixel-precise. You will have to draw the entire
polygon outline and then take the first line of pixels inside.

My Tektosyne library has a Polygon class that can do floating-point
transformations on regular polygons if you want to try that:
http://www.kynosarges.de/Tektosyne.html
--
http://www.kynosarges.de
Sep 24 '06 #4
John Smith wrote:
//Shrinks the specified polygon by one pixel (in any relevant
direction) //so that the shrunken polygon sits exactly within the
original (specifed) polygon.
public void Point[] ShrinkPolygon(Point[] polygon)
{
//How do I do this?
}
You haven't provided enough information. Is the polygon displayed in
2D or 3D? Is there an orthogal projection of the polygon on the screen
or not?

if it's an orthogonal projection in 2D, you also could have done it
(translate the x / y of the vertices passed in towards the center of
it) so I guess it's not orthogonal in 2D ;).

If it's a problem which means that you want to end up with a polygon
P' which is exactly 1 pixel inside polygon P in _pixelspace_ (thus
after translation), you've to first calculate the end polygon of P in
pixelspace, thus after translation, then do a subtract towards the
center, and then use an inverse matrix to get to the original polygon.

FB

--
------------------------------------------------------------------------
Lead developer of LLBLGen Pro, the productive O/R mapper for .NET
LLBLGen Pro website: http://www.llblgen.com
My .NET blog: http://weblogs.asp.net/fbouma
Microsoft MVP (C#)
------------------------------------------------------------------------
Sep 24 '06 #5
On Sun, 24 Sep 2006 00:16:01 -0700, "John Smith" <js****@nowhere.com>
wrote:
>//Shrinks the specified polygon by one pixel (in any relevant direction)
//so that the shrunken polygon sits exactly within the original (specifed)
polygon.
public void Point[] ShrinkPolygon(Point[] polygon)
{
//How do I do this?
}
Unless you know in advance the resolution that the polygon will be
drawn at, this cannot be done. It might be possible in an idealised
pixellated surface, iff you know exactly which pixels are filled in
when drawing a line (say). You could then decide according to some
scheme or other which pixels counted as "inside" and which not (this
isn't as easy a choice as a first inspection might show). If you were
to repeat the algorithm, the pixels filled in would get less and less
like a polygon as you approached the centre.

In other words, not a trivial problem at all, and one which I suspect
you would do better to solve another way.
Sep 24 '06 #6
Thanks to everyone for their answers. I guess it's an even harder problem
than I anticipated since I have no control of how the pixels are painted
between any two points.
Sep 25 '06 #7