471,071 Members | 1,340 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,071 software developers and data experts.

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

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

7 posts views Thread by Maxim Shemanarev | last post: by
14 posts views Thread by G Patel | last post: by
3 posts views Thread by Zorpiedoman | last post: by
3 posts views Thread by Otavio Macedo | last post: by
10 posts views Thread by Fernando Cacciola | last post: by
7 posts views Thread by Chris | last post: by
2 posts views Thread by =?Utf-8?B?QXRoZW5hQw==?= | last post: by
12 posts views Thread by gsal | last post: by
3 posts views Thread by =?ISO-8859-1?Q?Norbert_P=FCrringer?= | last post: by
reply views Thread by leo001 | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.