3

如果我们(x1,y1), (x2,y2)通过左上角和右下角定义一个矩形并假设所有点都是整数值，我想列出多个矩形联合中的所有点。

对于一个矩形，以下函数返回其中的所有点。

def findpoints(x1,y1,x2,y2):
    return [(x,y) for x in xrange(x1,x2+1) for y in xrange(y1,y2+1)]

我可以通过以下方式找到两个矩形联合中的所有点，

set(findpoints(x1,y1,x2,y2)) | set(findpoints(x3,y3,x4,y4))

但是我有很多矩形，这可能非常低效。例如，想象一下所有矩形是否几乎相同。有没有一种快速的方法来做到这一点？

4

1 回答 1

1

I agree with StoryTeller but I think it is better to write it in more detail so it is understandable even for those of us with poor English skills

  1. compute the minimal rectangle which is the overlapped area of all rectangles to test

    • x1 = max (rec[i].x1)
    • y1 = max (rec[i].y1)
    • x2 = min (rec[i].x2)
    • y2 = min (rec[i].y2)
    • i=0,... all rectangles -1
    • if x1>x2 or y1>y2 then all rectangles do not overlap and so no points are inside

  2. test all points only against this new rectangle (x1,y1,x2,y2)

    • if (x>=x1) and (x<=x2) and (y>=y1) and (y<=y2) then point(x,y) is inside
于 2013-11-16T10:07:34.247 回答