Given a set of points to define a shape, how can I contract this shape like Photoshop's Selection>Contract

I have a set of points to define a shape. These points are in order and essentially are my "selection".

I want to be able to contract this selection by an arbitrary amount to get a smaller version of m开发者_如何学运维y original shape.

In a basic example with a triangle, the points are simply moved along their normal which is defined by the points to the left and the right of the points in question.

Eventually all 3 points will meet and form one point but until that point they will make a smaller and smaller triangle.

For more complex shapes, when moving the individual points inward, they may pass through the outer edge of the shape resulting in weird artifacts. Obviously I'll need to cull these points and remove them from the array.

Any help in exactly how I can do that would be greatly appreciated.

Thanks!

This is just an idea but couldn't you find the center of mass of the object, create a vector from the center to each point, and move each point along this vector?

To find the center of mass would of course involve averaging each x and y coordinate. Getting a vector is as simple a subtracting the point in question with the center point. Normalizing and scaling are common vector operations that can be found with the Google.

EDIT
Another way to interpret what you're asking is you want to erode your collection of points. As in morphology erosion. This is typically applied to binary images but you can slightly modify the concept to work with a collection of points. Essentially, you need to write a function that, given a point, will return true (black) or false (white) depending on if that point is inside or outside the shape defined by your points. You'd have to look up how to do that for shapes that aren't always concave (it's harder but not impossible).

Now, obviously, every single one of your actual points will return false because they're all on the border (by definition). However, you now have a matrix of points around your point of interest that define where is "inside" and where is "outside". Average all of the "inside" points and move your actual point along the vector between itself and towards this average. You could play with different erosion kernels to see what works best.

You could even work with a kernel with floating point weights instead of either/or values which will affect your average calculation proportional to their weights. With this, you could approximate a circular kernel with a low number of points. Try the simpler method first.

1. Find the selection center (as suggested by colithium)
2. Map the selection points to the coordinate system with the selection center at (0,0). For example, if the selection center is at (150,150), and a given selection point is at (125,75), the mapped position of the point becomes (-25,-75).
3. Scale the mapped points (multiply X and Y by something in the range of 0.0..1.0)
4. Remap the points back to the original coordinate system

Only simple maths required, no need to muck about normalizing vectors.