4

I'm looking for information about how to draw borders around rectangles and provide a slightly different rendering for overlapped borders. These rectangles are user generated so they can have a variety of sizes and overlaps. Users specify the z-order. Here is an example:

enter image description here

My data is modeled with simple rect data structures. For simplicity, I'm expecting to draw all border with lines (even when there is no overlap). I'm planning to draw the rectangles and borders using SVGs in a browser, but I'm just looking for a generic solution that is platform agnostic. .

This problem domain is new to me. I don't have much experience in this area, but I'll happily take and information I can get.

Wesley Workman
  • 917
  • 9
  • 22
  • Is it possible that at a point more than 2 rectangles are overlapping? In the image the highest stack is 2. – maraca Mar 11 '17 at 04:17
  • [Algorithm to detect intersection of two rectangles?](http://stackoverflow.com/questions/115426/algorithm-to-detect-intersection-of-two-rectangles?rq=1) – Arash Mar 11 '17 at 04:43
  • @marca -- Absolutely, rectangles are user provided and can have a variety of sizes and overlaps. I provided a minimal mockup for simplicity, but I should have added a few more overlaps. Let me do that. – Wesley Workman Mar 11 '17 at 12:45
  • @arash -- Detecting intersection is well understood. What I'm having trouble wrapping my head around is how to evaluate N number of intersections. Then draw borders properly when there is no overlap vs when there is overlap. Additionally, it seems tough to know when there is overlap, if it should be drawn solid (because it's the top most overlap) or dashed (because something is above it). – Wesley Workman Mar 11 '17 at 12:47
  • How about pairwise comparison? Then you can use the same algorithm ... – Arash Mar 11 '17 at 16:44

1 Answers1

2

From the picture, it looks like the border of a rectangle is only affected by rectangles on top of it.

Draw the rectangles in order from top to bottom. For each of the eight corner-adjoining-edge pairs of the next rectangle to draw, loop through all currently drawn rectangles to find the rectangle which contains the corner and overlaps the longest portion of the edge. Render that portion of the edge as overlapped.

If this is too slow, use a two-dimensional segment tree to store all currently drawn rectangles so that the rectangles containing a given corner can be quickly identified.

Angela Pretorius
  • 243
  • 1
  • 7
  • Thanks for your answer. I updated my mockup to show that rectangles can have a variety of sizes and overlaps as there was some questions about that. I don't think that really changes your answer, would you agree? – Wesley Workman Mar 11 '17 at 13:06
  • I followed this exact technique and was successful. I know this answer doesn't go into deep detail, but the philosophy here is to break them all down into lines. Process rectangles sorted by highest z-order first. For each rectangle being checked, break it into 4 lines. Then test those 4 lines against the 4 lines of each rectangle above it. Break lines down into smaller segments as lines are determined to intersect. Render intersecting lines differently. All in all, it was about 140 lines of code. Thank you! – Wesley Workman Mar 13 '17 at 23:41