Wednesday, February 16, 2011

Simple Polygon Offset

I was working on another POV-ray pysanky egg design and had to work with offsetting polygons.  Stack Overflow had a brief description of how this could be done.  I chose to go with the simplest solution: drawing offset lines and connecting their intersection points.

Update:  ΤΖΩΤΖΙΟΥ was kind enough to introduce me to the math.atan2 function, which correctly identifies the quadrant the angle theta falls in, and rewrote my verbose function(s) concisely:

def calcoffsetpoint(pt1, pt2, offset):
    theta = math.atan2(pt2[1] - pt1[1],
                       pt2[0] - pt1[0])
    theta += math.pi/2.0
    return (pt1[0] - math.cos(theta) * offset,
            pt1[1] - math.sin(theta) * offset)
getoffsetintercept gets the b in y = mx + b needed to calculate the new point:

def getoffsetintercept(pt1, pt2, m, offset):
    """
    From points pt1 and pt2 defining a line
    in the Cartesian plane, the slope of the
    line m, and an offset distance,
    calculates the y intercept of
    the new line offset from the original.
    """
    x, y = calcoffsetpoint(pt1, pt2, offset)
    return y - m * x

The function that gets a single point along the polygon:

def getpt(pt1, pt2, pt3, offset):
    """
    Gets intersection point of the two
    lines defined by pt1, pt2, and pt3;
    offset is the distance to offset
    the point from the polygon.
    """
    # get first offset intercept
    m = (pt2[1] - pt1[1])/(pt2[0] - pt1[0])
    boffset = getoffsetintercept(pt1, pt2, m, offset)
    # get second offset intercept
    mprime = (pt3[1] - pt2[1])/(pt3[0] - pt2[0])
    boffsetprime = getoffsetintercept(pt2, pt3, mprime, offset)
    # get intersection of two offset lines
    newx = (boffsetprime - boffset)/(m - mprime)
    newy = m * newx + boffset
    return newx, newy

Lastly, the function that works the polygon offset:

def offsetpolygon(polyx, offset):
    """
    Offsets a clockwise list of coordinates
    polyx distance offset to the inside of
    the polygon.
    Returns list of offset points.
    """
    polyy = []
    # need three points at a time
    for counter in range(0, len(polyx) - 3):
        # get first offset intercept
        pt = getpt(polyx[counter],
                   polyx[counter + 1],
                   polyx[counter + 2],
                   offset)
        # append new point to polyy
        polyy.append(pt)
    # last three points
    pt = getpt(polyx[-3], polyx[-2], polyx[-1], offset)
    polyy.append(pt)
    pt = getpt(polyx[-2], polyx[-1], polyx[0], offset)
    polyy.append(pt)
    pt = getpt(polyx[-1], polyx[0], polyx[1], offset)
    polyy.append(pt)
    return polyy

Shown below is the shape I was trying to offset.


As the "Simple" in the entry's title suggests, this is a best case scenario:

    1) no degenerate polygons inside or outside
    2) no zero or infinite slopes

Actually, I should have some zero slopes, but I cheated and changed the coordinates.  The differences won't be seen by the naked eye, but are big enough for the computer to handle them.

Here is the egg I was working on; it's a Hutsul design from the Sixty Score of Easter Eggs book:


Thanks for having a look.

No comments:

Post a Comment