N-dimensional bounding-boxes

[SwiftsNamesake]

This might be a tad too low-brow for your tastes, but is there any chance we could export a simple polymorphic n-dimensional BoundingBox (or similarly named) type from this library?

Given the universality of this package (and how it ties in quite nicely with the V[N] types)

Since there is no 'standard' type, people keep defining their own, making interop a bit of a trudge (and Haskellers don't trudge; they stride, right).

My own definition looks a bit like this:

data BoundingBox v = BoundingBox { cornerOf :: v, sizeOf :: v } deriving (Show, Eq)

The suffix is partly for aesthetics (cornerOf box reads nicely; of is a nice synonym for flip (^.), come to think of it), partly a guide for lens generation.

This got a bit long (sorry), but I have a final question: if this functionality should not be part of linear, do you have a suggestion for where it might fit in? Is there already a nice library that could become the de-facto standard? Where should I turn for this type of discussion?

Thanks for the good work.

[SwiftsNamesake]

@ekmett Pinging Ed.

[ekmett]

Nomenclature wise, Of has already picked up a pretty strong connotation in lens.

forOf, unsafePartsOf, universeOf ... it by convention takes a combinator that is usually written against a standard class like Foldable/Traversable and makes it parameterized in a lens/traversal of that same sort.

I'm kinda neutral on including an AABB at all. It does make nice use of pointwise min/max. corner based versions are better for us than center + radius versions as they are slightly more definable.

[SwiftsNamesake]

Yes, I thought about that. I'm certainly not hung up on any particular naming scheme (I tend to use a short prefix, as it plays well with lenses and DuplicateRecordFields).

data BoundingBox v = BoundingBox { fCorner :: v, fSize :: v } deriving (...)

The rationale behind the corner-based definition is (as you say), that it works well even for integral types.

I've defined a collection of lenses and functions that are designed to play well with any type of vector (for instance, the intersect logic is based on Applicative, since it's essentially an axis-wise operation).

Again, I'm not sure if this functionality belongs in linear. I'm open to suggestions.

[ekmett]

In lens and linear as a matter of style I particularly try to avoid camelCase names and random letters getting stuck on things as much as possible.

data Box f a = Box !(f a) !(f a)

or AABB with lenses lo and hi would fit my own personal style well. lo and hi vs. corner and size allows you to use the concept with points where differences are defined but addition, directly at least shouldn't be. None of the other data types in linear actually expose field names for their data types, preferring the lens style or matching, so we should probably stick with that.

One downside is that this dredges up all the allowing corner-case semantic crap around providing instances that makes my intervals package a nightmare to maintain, so I expect I'll be getting deluged with combinators to add to it if we do include it.

[SwiftsNamesake]

Fair points. I'd be happy to be the maintainer for a standalone package (the one I have needs some love and attention at the moment, perhaps I should create a new one which focuses on AABB:s only).

I'd appreciate your input and advice in that case, if you have time (I've seen your Hackage page, it goes on for miles). For instance, strictness annotations are something I've considered but haven't decided on. Are there any drawbacks at all, in this case? I suppose not, since you're mostly just doing arithmetic.

Also, the rationale behind using a single type argument is that it allows one-dimensional 'boxes' too (ie. Box Float could act as an interval). I liked the symmetry of it, although you could wrap it in a V1 obviously.

Finally, I wasn't familiar with intervals. I have to confess that I'm not sure what you're referring to re: corner-cases (maybe Infinity and nearZero).

Thanks for responding, I'm a bit of a neophyte when it comes to working on widely used software. I stick to my own projects mostly.

Do you want to keep this issue open or should I close?

[SwiftsNamesake]

@ekmett Pinging again, hope you don't mind.

[ekmett]

Sorry, am traveling.

The problem with 1d vs. n-dimensional intervals is you kind of want different things for them and the combinators to work with the various f as you get from linear are different than the ones you'd use to work with just a Num, etc. If you go to use the Ord instance directly on 'a' you'll get the wrong answers as it is lexicographical, so you can't just use min/max for the bounding boxes, you need to lift it into the functor.

As for corner cases that Kaucher-style intervals in the intervals package allow 'negative' bounding boxes, and then there is the question of if you include empty boxes or not.

[ekmett]

Let's keep the issue open at least. I'm not against adding a simple AABB type, for only non-empty intervals with the assumption that lo <= hi pointwise. It is probably the most common use type.

[SwiftsNamesake]

I have a separate package ready for publication (-ish) that I've been working on for the last few days (very similar to the old one from Cartesian, which is in a bit of a state at the moment).

It's very small and hasn't been properly tested yet, but you're welcome to take a look.

Also working on a demo program for shits and giggles.

As you'll see, there's no real integration with your intervals yet. I'm posting this as a sort of springboard for further discussion.

[ekmett]

I'm back from http://scala.world/ and now have internet access.

Skimming:

axes (and others) use zipA/unzipA.

It'd be safer to use the machinery from linear for merging at the cost of an Additive constraint, that way if 'f' is used as an IntMap or Map k it'd properly handle sparse intervals. You can decide if it should be intersection or union based from there.

If you switch to base + offset representation, then height, width, depth could become _x _y and _z. This may or may not be a good thing. Alternately you could supply an R3 instance to get the base point or lo part of the AABB.

Exporting:

y :: R2 f => Lens' (f a) a
y = _y

seems gratuitous.

[SwiftsNamesake]

@ekmett Sorry about the recent silence, hope you had a blast at that conf.

Yes, I'm not entirely happy with the way I'm using Applicative, and it might be a better idea to use a more specific class. I'll take another stab at it.

As for the offset alternative, it's the one I used originally. The change was your suggestion ;P
Guess neither of us are sure which one is better, and for that reason, I think I'll keep it as lo and hi for now.

I'd happily accept the input from other Haskellers who have ideas about how a general AABB might be used out in the wild. Maybe that'll improve the overall design.

And finally, yes, exporting y (et al) is entirely gratuitous. I just find underscores visually jarring. We obviously don't have to export those lenses in the public API; I'll probably remove them entirely from this library.