3

I have a set of rectangles (stored as a set of xmin,ymin and xmax,ymax coordinates in an R data frame), some of which overlap, that I would like to plot on a chart and distribute them along the y-axis so that no two rectangles overlap. Their x coordinates must stay preserved; I need to achieve the goal by shifting the rectangles only vertically.

A concrete example:

df <- structure(list(xmin = c(67.705914, 6.005184, 66.162244, 87.99481, 
46.082243, 16.280928, 47, 3.4155154, 23.347187, 84.895525, 82.80274, 
16.85878, 4.3557265, 6.625263, 7.626907, 96.220383, 12.115471, 
30.235073, 46.082243, 16.280928, 79.90225, 29.42548, 84.895525, 
23.347184, 3.198581, 7.2832146, 25.539455, 1.695044, 34.425616, 
3.87074, 78.284034, 89.64427, 87.0506, 87.68941, 75.329986, 2.213225, 
3.4155154, 4.6098725, 0.5424367, 80.416396, 12.115471, 6.625263, 
32.722494, 8.344733, 89.64427, 52.48499, 90.12926, 30.235073, 
2.9885126, 8.719267), xmax = c(73.705914, 12.005184, 72.162244, 
93.99481, 52.082243, 22.280928, 53, 9.4155154, 29.347187, 90.895525, 
88.80274, 22.85878, 10.3557265, 12.625263, 13.626907, 102.220383, 
18.115471, 36.235073, 52.082243, 22.280928, 85.90225, 35.42548, 
90.895525, 29.347184, 9.198581, 13.2832146, 31.539455, 7.695044, 
40.425616, 9.87074, 84.284034, 95.64427, 93.0506, 93.68941, 81.329986, 
8.213225, 9.4155154, 10.6098725, 6.5424367, 86.416396, 18.115471, 
12.625263, 38.722494, 14.344733, 95.64427, 58.48499, 96.12926, 
36.235073, 8.9885126, 14.719267), ymin = c(15.6854458039728, 
29.280227138751, 85.6077652217337, 11.1447959143222, 88.6507847970509, 
47.8780668201714, 58.249961106352, 20.7963843697899, 39.1374442773956, 
14.253314246173, 31.2038928836167, 75.406238562994, 90.8407922528565, 
34.3969058783788, 90.0758115822633, 47.8810408921933, 41.9826622904241, 
18.4008825788269, 64.0816967514961, 26.1344753018713, 87.6969580943045, 
29.8031653049004, 25.5889076966207, 24.8832114234653, 65.6939979329678, 
83.7251558885676, 62.3262453418105, 52.1180170583712, 22.2274072090833, 
46.6403205808079, 51.4982774017124, 52.9611597344073, 86.5149513741532, 
8.71673006759099, 73.63580649852, 10.2390589604505, 79.6728413001311, 
27.0399934909858, 17.2084996917785, 28.7198728007395, 27.7845507714287, 
64.8898031132345, 77.518346688506, 11.785758214691, 51.2219947101639, 
55.4683310942946, 59.4959604756725, 15.6990628891733, 53.6174786549635, 
49.4079504426206), ymax = c(17.2907089618675, 31.2234089569328, 
87.3295043521685, 13.2730010425273, 90.8437672531913, 50.9203203412982, 
60.4271762962254, 23.1819265384646, 41.6096664996178, 15.6887703563279, 
34.0475653401924, 77.3496347894091, 93.4576597227361, 37.1520079191952, 
92.2237107419272, 52.1189591078067, 43.7265046549561, 21.6912051594721, 
65.7843994541988, 28.3922072606342, 89.9154454892625, 33.7570368040767, 
27.4828470905601, 26.6122436815298, 69.5273312663012, 86.1164074074011, 
64.1048569740807, 55.1107177882982, 23.6523109318047, 48.9688920093793, 
54.4445139608521, 55.219401492649, 88.3781992374011, 11.2337368703121, 
75.7899915205464, 13.1508236663329, 85.2391063603721, 29.4730210139216, 
20.1518959181936, 33.1198728007395, 30.7228223763669, 66.81402503475, 
79.1315542356758, 13.8413137702466, 52.7337440574224, 57.6201635550276, 
61.8678354756725, 19.1313772996537, 55.6110888786056, 51.560255051839
)), row.names = c(NA, -50L), class = "data.frame")

ggplot(df,aes(xmin=xmin,xmax=xmax,ymin=ymin,ymax=ymax)) + geom_rect(color="black",fill="cyan") + theme_void()

results in

The actual output of plotting rectangles

whereas I would need something like this

The desired output

Is there a way how to achieve this in R?

I have encountered a few similar posts thorough the web, most notably here, here, or here, but none of them seem to solve my problem of distributing rectangles only vertically to prevent overlaps, and in the R language.

What I have tried out of desperation is randomly shifting the rectangles using the swarmy function from the beeswarm package an checking for overlaps, but this is not usable as with a large number of rectangles, you could wait ages till the random algorithm finds a solution.

EDIT

Following the advice given in Dave's answer (any drawing some inspiration from Marcus's answer), I made a working piece of code:

library(ggplot2)

#' tests if a rectangle overlaps with any other rectangle from a set of rectangles
#'
#' @param testRect the rectangle to be tested for overlaps (in the form of any structure having the $xmin, $xmax, $ymin, and $ymax attributes)
#' @param rectList a data frame with the xmin, xmax, ymin, and ymax columns containing the set of rectangles to test the overlaps with
#' @returns a Boolean value, TRUE if there any any overlaps, FALSE if there are not
#' 
overlaps_any <- function(testRect, rectList) {
  if(nrow(rectList)==0) {
    return(FALSE)
  }
  for (r in 1:nrow(rectList)) {
    # If rectangle has area 0, no overlap
    if (testRect$xmin == testRect$xmax || testRect$ymax == testRect$ymin || rectList[r,"xmin"] == rectList[r,"xmax"] || rectList[r,"ymax"] == rectList[r,"ymin"]) {
      next
    }
    
    # If one rectangle is on the left side of the other
    if (testRect$xmin > rectList[r,"xmax"] || rectList[r,"xmin"] > testRect$xmax) {
      next
    }
    
    # If one rectangle is above the other
    if (testRect$ymin > rectList[r,"ymax"] || rectList[r,"ymin"] > testRect$ymax) {
      next
    }
    return(TRUE)
  }
  return(FALSE)
}

# Create an empty data frame
df.new <- data.frame()

# Iterate over each row of the original data frame
for(r in 1:nrow(df)) {
  # Select the rectangle from the original data frame
  testRect <- df[r,]
  
  # Calculate the height of the rectangle
  rect_height <- testRect$ymax - testRect$ymin
  
  # Set the minimum y-coordinate of the rectangle to 0
  testRect$ymin <- 0
  
  # Set the maximum y-coordinate of the rectangle based on the height
  testRect$ymax <- testRect$ymin + rect_height
  
  # Check if the rectangle overlaps with any existing rectangles in the new data frame
  while(overlaps_any(testRect, df.new)) {
    # Increment the y-coordinates of the rectangle by 1 to avoid overlap
    testRect$ymin <- testRect$ymin + 1
    testRect$ymax <- testRect$ymax + 1
  }
  
  # Append the updated rectangle to the new data frame
  df.new <- rbind(df.new, testRect)
}

# Plot the rectangles using ggplot
print(
  ggplot(df.new, aes(
    xmin = xmin,
    xmax = xmax,
    ymin = ymin,
    ymax = ymax
  )) +
    geom_rect(color = "black", fill = "cyan") + coord_fixed() + theme_void()
)

Result:

Rectangles after the reordering

kurpav00
  • 138
  • 6

3 Answers3

3

First, create a function that will find the max overlap for any given rectangle (testRect) against a list of all rectangles (rectList).

library(purrr)
library(dplyr)

MaxYOverlap <- function(testRect, rectList) {
  
  overlaps <- rectList |> 
    # filter for potentially overlapping rectangles,
    # which will include the test rectangle itself
    filter(
      xmin <= testRect$xmax, 
      xmax >= testRect$xmin,
      ymin <= testRect$ymax,
      ymax >= testRect$ymin,
      # avoid duplicates by searching only above
      ymax >= testRect$ymax
    ) |> 
    mutate(
      yoverlap = testRect$ymax - ymin
    ) 

  if(NROW(overlaps) > 1){
    # will overlap perfectly with itself, so take second greatest
    overlaps |> 
      arrange(-yoverlap) |> 
      slice(2) |> 
      pluck("yoverlap")
  } else {
    # ignore if it only overlaps with itself
    0
  }
  
}

Then starting from the bottom, progressively shift the rectangles by the cumulative amount of overlap up until that rectangle's position (which have been ordered bottom to top)

# ensure applying shifts from bottom up
df <- df |>
  arrange(ymax)

df_jittered <- df |> 
  mutate(
    maxOverlap = pmap_dbl(df, \(...) MaxYOverlap(data.frame(...), rectList = df)),
    # shift by additional 100% to create visual separation
    cumShift = cumsum(maxOverlap) * 5,
    ymin = ymin + lag(cumShift, default = 0),
    ymax = ymax + lag(cumShift, default = 0)
  )

You could get fancy and only apply the shifts to the rectangles directly above two overlapping ones, but I'll that as an exercise to the reader :-) jittered rectangles

Marcus
  • 3,478
  • 1
  • 7
  • 16
2

Since all valid solutions are equally good, we can use something dead simple.

Pick any rectangle to be your first rectangle, and shift it vertically so the smaller y-coord is at zero.

Repeatedly do the following:

  • pick any rectangle and call it 'cur', and lets call the prior rectangle placed 'pri'
  • delta = pri.y_max - cur.y_min
  • cur.y_min = cur.y_min + delta
  • cur.y_max = cur.y_max + delta
  • We've now shifted the cur rectangle to be immediately above the prior rectangle placed.
  • repeat

This won't be as compact as it could be (in most cases) and won't preserve relative vertical positioning, but is fast and gets the job done.

Dave
  • 7,460
  • 3
  • 26
  • 39
0

I'm not aware of a R package to solve this but in general your question could pointing to "Computational Geometry Algorithms" in the field of "Point/Polygon-Feature Label Placement" if you assume or imagine, that your frames are the extent some text labels with a root point may be in the center or the lower left corner of the shown rectangle (...see image below) .

Example from Christensen, Marks, Schieber: "An Empirical Study of Algorithms for Point-Feature Label Placement"

enter image description here

So the buzzwords to internet searches in this field could be:

In common the algorithms tries to handle a optimization problem, to move the rectangles along or around rule based paths form the start or root point with the following conditions:

  1. The frames should not to overlap each other.

  2. The extent of the resulting frame ensemble should span a minimal area around the complete root point ensemble.

  3. Optionally maintenance of the "spatial order" could be demanded ("Constraint Labeling Algorithm").

I have not tested this but R the package rgeos with the function polygonsLabel(...) some of your requested features looks promising and the inner functionality could be investigated to exchange the text driven input with the frames.

huckfinn
  • 644
  • 6
  • 23