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

[John Smith]

//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?
}

 

[Martijn Mulder]

//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

 

[Martijn Mulder]

//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

 

[Chris Nahr]

//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

 

[Frans Bouma [C# MVP]]

//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#)
------------------------------------------------------------------------

 

[Ben Newsam]

//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.

 

[John Smith]

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.