Re: sorting points or rectangles
- Posted by tone.skoda at siol.net Feb 21, 2002
- 530 views
----- Original Message ----- From: "Dan Moyer" <DANIELMOYER at prodigy.net> > ... if the edges of the rectangles are all vertical and horizontal with respect to > the coordinate system (the screen). I don't understand this quite. Rectangles allways have two horizontal and two vertical edges. If edges are not horizontal or vertical then that would be paralelogram or whatever, no? > Do you need to handle conditions other > than that? No. You all responded with functions how to find out if (and how) rectangle is inside rectangle. I have around 10.000 rectangles and I have to get all rectangles which have at least one of their four points inside a big rectangle. I want to be able to use binary search on sorted rectangles for speed. If I do it like this it is too slow: function get_rects_inside_rect (sequence rectangles, sequence big_rect) sequence rects_inside sequence rect rects_inside = {} for int i = 0 to length (rects) do rect = rects [i] if is_rect_partially_inside_rect (rect, big_rect) then rects_inside = append (rects_inside, rect) end if end for return rects_inside end function A little faster it would be if I woluld somehow sort them by their left-x, or something similar. Unclear to me right now.