Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Let's say I have a polygon class that is represented by a list of vector classes as vertices, like so:

 var Vector  = function(x, y) { this.x = x; this.y = y; },
     Polygon = function(vectors) { this.vertices = vectors; };

Now I make a polygon (in this case, a square) like so:

var poly = new Polygon([
    new Vector(2, 2),
    new Vector(5, 2),
    new Vector(5, 5),
    new Vector(2, 5)
]);

So, the top edge would be [poly.vertices[0], poly.vertices[1]].

I need to stretch this polygon by moving each edge away from the center of the polygon by one unit, along that edge's normal. The following example shows the first edge, the top, moved one unit up:

polygons before and after

The final polygon should look like this new one:

var finalPoly = new Polygon([
    new Vector(1, 1),
    new Vector(6, 1),
    new Vector(6, 6),
    new Vector(1, 6)
]);

It is important that I iterate, moving one edge at a time, because I will be doing some collision tests after moving each edge.

Here is what I tried so far (simplified for clarity), which fails triumphantly:

for(var i = 0; i < vertices.length; i++) {
    var a = vertices[i],
        b = vertices[i + 1] || vertices[0]; // in case of final vertex

    var ax = a.x,
        ay = a.y,
        bx = b.x,
        by = b.y;

    // get some new perpendicular vectors
    var a2 = new Vector(-ay, ax),
        b2 = new Vector(-by, bx);

    // make into unit vectors
    a2.convertToUnitVector();
    b2.convertToUnitVector();

    // add the new vectors to the original ones
    a.add(a2);
    b.add(b2);

    // the rest of the code, collision tests, etc.
}

This makes my polygon start slowly rotating and sliding to the left, instead of what I need.

Finally, the example shows a square, but the polygons in question could be anything. They will always be convex, and always with vertices in clockwise order.

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

Your polygon is rotating to the left because the unit vectors you are adding have the opposite sign of your x component (gotten when you create the perpendicular vectors). Adding those to your original vectors will shift them counter clockwise (to the left for positive Y and to the right for negative Y values of your original vectors).

I assume you're trying to create the perpendicular vectors to make sure you increase the original vectors along the normal to the edge. I don't think you need to do that, you should probably just create UnitVectors for the original vectors and add them to the originals.

This still might not get the whole edge to move 1 exact unit away from the center. If that's the more important part of what you're trying to achieve, you might want to get the center point of the edge (by averaging the vectors together), getting the UnitVector for that, and then adding that UnitVector to each of your original vectors.

share|improve this answer
1  
This was actually the first idea that occurred to me, but I'm not sure which one would look better, always moving away from the center, or moving using the edge normal. About the suggestion to simply normalize the positions and use them, one caveat with this approach, is to make sure that the vertices are defined in local space, with the center of the polygon being the origin (0,0). Otherwise it's necessary to subtract the center of the polygon from the vertex position first before normalizing. :) –  David Gouveia Jul 6 '12 at 20:01
    
Are you saying that adding the UnitVector of the original vectors will always make the vectors move outward from the center of the polygon? –  Stephen Jul 6 '12 at 20:11
1  
@David, if I understand your comment: Could I find the midpoint between two vertices, subtract the center of the polygon, find the unit vector of that, and than add it to both original points? –  Stephen Jul 6 '12 at 20:37
    
@David: Good point, I had been assuming that the code took into account the center of the polygon versus the center of the coordinate system, though on further review it does not appear to do so. –  fnord Jul 6 '12 at 21:35
    
@Stephen In order to make sure the expansion happens from the center of the polygon, you have to work to make that the center of your coordinate system. You would need to subtract the vector to the polygon center from the vertices, then calculate vector, and then add your polygon center vector back in. –  fnord Jul 6 '12 at 21:45
show 2 more comments

I think the part where you get some new perpendicular vectors looks strange because a and b are positions, not vectors, and it doesn't make sense to get the perpendicular of a position.

I think you should probably start by doing a-b (or b-a depending on the vertex order, not sure which one now) to get the tangent of the edge, then get the perpendicular of that tangent, which will be the edge normal, and finally apply the same normal to both vertices. Don't forget to normalize first though.

Still I'm not sure the results will be as you want, because polygon offsetting is tricky business. Check this question for more information on the subject.

share|improve this answer
    
Also, depending on the language you're using, make sure it's really safe to do vertices[i+1] || vertices[0] when i+1 overflows the array. Might be, but I've never seen this idiom before. :) –  David Gouveia Jul 6 '12 at 19:53
1  
it's javascript. In javascript, undefined evaluates false, so if the array index is undefined, the left side of the || condition is false, so the right side is used. –  Stephen Jul 6 '12 at 20:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.