CODEWITHSUNDEEP
pythonalgorithmgraphicsgeometry
i.krivosheev
i.krivosheev

Reputation: 397

python midpoint line clipping algorithm

This midpoint algorithm in python(2.7) doesn't work. He isn't go out of recursion. Where is the mistake? Please help me.

# Where is point
def vcode(rect, p):
    value = 0
    if p.x < rect.x_min:
        value += LEFT
    if p.x >= rect.x_max:
        value += RIGHT
    if p.y < rect.y_min:
        value += BOT
    if p.y >= rect.y_max:
        value += TOP

    return value

# algorithm
def average_point(rect, p1, p2, count=0):
    code_a = vcode(rect, p1)
    code_b = vcode(rect, p2)
    if math.sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y)) < EPS:
        return
    if not (code_a | code_b):
        return
    if code_a & code_b:
        return
    mid = Point((p2.x+p1.x)/2.0, (p2.y+p1.y)/2.0)
    count += 1
    average_point(rect, p1, mid, count)
    mid.x = mid.x+1
    mid.y = mid.y+1
    average_point(rect, mid, p2, count)
    return count


p1, p2 is Point( class, fields(x, y));

rect is Rectangle( class, fields(x_min, y_min, x_max, y_max));

Upvotes: 1

Views: 880

Answers (1)

Liam McInroy
Liam McInroy

Reputation: 4366

You're code works fine, except it is returning the final value of count when the method is first called. Therefore, count will always be 1. To correct this, you need to set count to the return value of average_point. Then, your code will look like:

# algorithm
def average_point(rect, p1, p2, count=0):
    returnArray = []
    code_a = vcode(rect, p1)
    code_b = vcode(rect, p2)
    if math.sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y)) < EPS:
        returnArray.append(count)
        returnArray.append(p1)
        returnArray.append(p2)
        return returnArray
    if not (code_a | code_b):
        returnArray.append(count)
        returnArray.append(p1)
        returnArray.append(p2)
        return returnArray
    if code_a & code_b:
        returnArray.append(count)
        returnArray.append(p1)
        returnArray.append(p2)
        return returnArray
    mid = Point((p2.x+p1.x)/2.0, (p2.y+p1.y)/2.0)
    count += 1
    returnArray = average_point(rect, p1, mid, count)
    mid.x = mid.x+1
    mid.y = mid.y+1
    returnArray = average_point(rect, mid, p2, count)
    return returnArray

This will replace the count value every iteration, and make sure you add the return counts in because otherwise it will not receive the correct value.

This also include the points in indexes 1 and 2 because in python you can have multiple "types" in arrays so you can return both points and the count.

Upvotes: 1

Related Questions