]> granicus.if.org Git - graphviz/commit
Changed get_overlap_graph
authorYifan Hu <yifanhu@yahoo.com>
Wed, 9 Oct 2013 19:23:15 +0000 (15:23 -0400)
committerYifan Hu <yifanhu@yahoo.com>
Wed, 9 Oct 2013 19:23:15 +0000 (15:23 -0400)
commit250606505352be62f4168f9080b1f6bdba751080
tree9c2ec1ff53da2fc2ac46572c24ede0e8355050c8
parente7b0d8f479301f9a3861f3137fb09e3803f05758
Changed  get_overlap_graph
1. added check_overlap_only for fast checking when we only want to check if any overlap exist
2. Fix a bug when two y intervals are [a,b] and [c,d], with [a,b] inside [c,d] (c < a < b < d). When both are in the GB tree, and [a,b] is leaving, previously code starts with b, find a, then finish and found no overlap. How we finds all interval end points below b (thus a and c), and check if their corresponding interval intersects with [a,b]. This can double count overlaps in the case when [c,d] is inside [a,b], but I think that is OK.

Fixed a bug for the graph

graph G {
  node [shape=box]

  a [pos="100,0", width = 0.75, height = 0.5]
  b [pos="0,100", width = 0.75, height = 0.5]
  c [pos="200,100", width = 0.75, height = 0.5]
  d [pos="100,300", width = 0.75, height=8]
  a -- b -- c -- a
  d -- b
  d -- c
}

where the default scaling of 4 x edgelength gives no overlap, but the amount of shrinking calculated is based on the edges, and missed the overlap caused by nodes a and d for which no edge exist. We now added overlap_scaling which uses bisection to find thebest scaling. This can also be used for simple scaling only based overlap removal.
lib/neatogen/overlap.c
lib/neatogen/overlap.h