python中点线裁剪算法

Question

这个中点算法在 python(2.7) 中不起作用。他没有退出递归。错误在哪里？请帮助我。

# 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 是 Point( class, fields(x, y));

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

Answer 1

你的代码工作正常，除了它返回的最终值 count首次调用该方法时。因此，count将始终为 1。要更正此问题，您需要设置 count到 average_point 的返回值.然后，您的代码将如下所示:

# 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

这将取代 count重视每一次迭代，确保添加 return count s in 因为否则它不会收到正确的值。

这也包括索引 1 和 2 中的点，因为在 Python 中你可以在数组中有多个“类型”，所以你可以返回点和计数。