Let say I have this diagram,

enter image description here

Given that i have all the co-ordinates of outer polygon and the distance between inner and outer polygon is d is also given. How to calculate the inner polygon co-ordinates? Edit: I was able to solved the issue by getting the mid-points of all lines. From these mid-points I can move d distance, So I can get three points. No I have 3 points and 3 slopes. From this, I can get three new equations. Simultaneously, solving the equation get the 3 points.

  • 1
    \$\begingroup\$ My first shot is to compute inner lines and their intersections. Inner lines can be computed from outer lines bz shifting them in correct direction (you can go for example counter clockwise and always shift line to the right). \$\endgroup\$ – zacharmarz Apr 12 '12 at 8:09
  • 1
    \$\begingroup\$ Can you provide an example. \$\endgroup\$ – user960567 Apr 12 '12 at 8:24
  • \$\begingroup\$ I think @zacharmarz was trying to say that you have to start from a P0 point on your poly, then march counterclockwise. For each P_i P_i+1 pair of points you need to find the inwards pointing vector (for counter clockwise it's in the positive semiplane if Pi.x<Pi+1.x, else in the negative semiplane determined by the Pi Pi+1 line) If you need more help, I could provide an explanation with a figure. \$\endgroup\$ – teodron Apr 12 '12 at 10:59

March counterclockwise on the edge list March counterclockwise on the edge list. For each Pi-Pi+1 edge, project Pi and Pi+1 inwards via the perpendicular on the Pi_Pi+1 line. Use a simple positive/negative half space check to get the correct inwards direction. ( perpendicular vectors in 2D, positive half plane/negative half plane).

Once you compute the normally displace Pi_Pi+1 line, you can check it for intersection with its homologous Pi+1_Pi+2 normally displaced line. The intersection is called P'i+1 and is a vertex of your required polygon.

Do note that the set of points that are d units away from the initial polygon and lie inside your polygon do not form a polygon, they form a "rounded corner" polyline. Note the little circle I drew. The arc between the two green and blue radii is part of this set. But the polygon you get is a "decent" approximation.

  • \$\begingroup\$ See my edited post. \$\endgroup\$ – user960567 Apr 12 '12 at 11:43

I know this has already been answered, but I believe the following code may be helpful to readers looking for an implementation of the solution.

// This function is a bit tricky. Given a path ABC, it returns the
// coordinates of the outset point facing B on the left at a distance
// of 64.0.
//                                         M
//                            - - - - - - X
//                             ^         / '
//                             | 64.0   /   '
//  X---->-----X     ==>    X--v-------X     '
// A          B \          A          B \   .>'
//               \                       \<'  64.0
//                \                       \                  .
//                 \                       \                 .
//                C X                     C X
FTPoint FTContour::ComputeOutsetPoint(FTPoint A, FTPoint B, FTPoint C)
    /* Build the rotation matrix from 'ba' vector */
    FTPoint ba = (A - B).Normalise();
    FTPoint bc = C - B;

    /* Rotate bc to the left */
    FTPoint tmp(bc.X() * -ba.X() + bc.Y() * -ba.Y(),
                bc.X() * ba.Y() + bc.Y() * -ba.X());

    /* Compute the vector bisecting 'abc' */
    FTGL_DOUBLE norm = sqrt(tmp.X() * tmp.X() + tmp.Y() * tmp.Y());
    FTGL_DOUBLE dist = 64.0 * sqrt((norm - tmp.X()) / (norm + tmp.X()));
    tmp.X(tmp.Y() < 0.0 ? dist : -dist);

    /* Rotate the new bc to the right */
    return FTPoint(tmp.X() * -ba.X() + tmp.Y() * ba.Y(),
                   tmp.X() * -ba.Y() + tmp.Y() * -ba.X());

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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