[Enhancement] combine :unknown intervals

[Timeroot]

Difficult problems often leave a lot of adjacent or overlapping :unknown intervals. As an example:

function f( x )
  return sqrt(1-cos(x)^2) + sin(x) + 0.01*x
end

X = -5 .. 5

rt = roots(f, X)
rt = sort(rt, by=x->x.interval.lo)
println("# of intervals: ",length(rt))
num_adj = sum(
  (rt[i].interval.hi == rt[i+1].interval.lo && rt[i].status==:unknown && rt[i+1].status==:unknown)
for i = 1:length(rt)-1)
println("# of adjancies: ",num_adj)

prints out

# of intervals: 100
# of adjancies: 98

That is, it's returning one :unique interval, and then 99 :unknown intervals, which each share endpoints with each other. For the end-user, it would make sense to combine these into a larger interval, since there's no information lost in combining them.

As another example (one with continuous derivatives everywhere):

function f( (x, y) )
  return SVector(
    x + (y-0.3)^3 - 0.7,
    x - (y-0.3)^2 - 0.7
  )
end

X = 0 .. 1

rt = roots(f, X × X)

gives

 Root([0.699999, 0.700001] × [0.299999, 0.3], :unknown)
 Root([0.699999, 0.700001] × [0.299999, 0.3], :unknown)
 Root([0.699999, 0.700001] × [0.299999, 0.300001], :unknown)
 Root([0.699999, 0.700001] × [0.3, 0.300001], :unknown)
 Root([0.699999, 0.700001] × [0.299999, 0.3], :unknown)
 Root([0.699999, 0.700001] × [0.3, 0.300001], :unknown)

all share essentially the same x range, and the y-ranges are often overlapping or adjacent. Dumping out the first intervals shows that several are indeed identical:

Interval{Float64}
  lo: Float64 0.6999999999999998
  hi: Float64 0.7000000000000002
Interval{Float64}
  lo: Float64 0.6999999999999998
  hi: Float64 0.7000000000000002
Interval{Float64}
  lo: Float64 0.6999999734173034
  hi: Float64 0.700000032978307
Interval{Float64}
  lo: Float64 0.6999999999999997
  hi: Float64 0.7000000000000001
Interval{Float64}
  lo: Float64 0.6999999999999998
  hi: Float64 0.7000000000000002
Interval{Float64}
  lo: Float64 0.6999999999999997
  hi: Float64 0.7000000000000001

These could also be merged or de-duplicated somehow.

[dpsanders]

Thanks, it's a good idea and we have explored it before. The main difficulty comes in higher dimensions when it's not so clear how to combine the rectangles, or how to decide when not to combine them.