Hi, I'm trying to determine the name of the algorithm which will determine if a set of blocks listed as Xl,Yl-X2Y2 are part of a contiguous larger block.
I'm just really looking for the name of, so I can go pull it out the NAG library. Bob.
+1
A:
It sounds like you describe a packing problem solving algorithm.
Edit: 2d packing algorithms were linked to in the see also section.
rsp
2009-11-28 22:34:29
Thanks RSP, but it's a 2d algo I'm looking for.
scope_creep
2009-11-29 16:23:45
+1
A:
I see 2 interpretations of your question: "given a collection of rectangles of coordinates X1, Y1, X2, Y2,:...
1) does the union of these rectangles form one unique shape" - i.e. one "island", as opposed to "separate islands",
2) do all these rectangles intersect (or even are included in) a given shape.
I can't tell which one it is, but this sounds related to the Set Cover problem (which is related to the packing problem mentioned by rsp through duality), and possibly the Hitting Set.
Mathias
2009-11-29 17:58:50
Mathias, I think to complex an answer. I'm just looking for an algo which enables a yes answer if a rectangle is within the boundaries of a greater rectangle.
scope_creep
2009-12-02 15:01:02
oh that sounds easier! 2 questions: 1) should the rectangle be included, or simply intersect? and 2) are the sides of the rectangles parallel, or can they have any orientation?
Mathias
2009-12-02 17:48:53
A:
I finally found out from a friend that the sweep line algo can be used for this. Simple in hindsight. Here is a link. Sweep Line Algo
scope_creep
2009-12-09 23:50:36