Tools for more accurate boundary calculations in common cases

[fryguybob]

(Imported from http://code.google.com/p/diagrams/issues/detail?id=60. Original issue from byor...@gmail.com on November 11, 2011, 03:07:56 PM UTC)

(09:46) < Taejo> are the bounds functions for polygons exact?
(09:47) < byorgey> Taejo: they are exactly what they are defined to be =)
(09:47) < byorgey> Taejo: the bounding function tells you how far you have to go to reach a line which completely encloses the polygon
(09:48) < byorgey> Taejo: so placing two things next to each other means there will be a perpendicular line with one on one side and one on the other
(09:48) < Taejo> byorgey, but they are approximations, in general?
(09:48) < byorgey> Taejo: no
(09:49) < fryguybob> For anything convex the union of bounds calls on all "angles" would be the exact complement of the shape.
(09:49) < byorgey> Taejo: they are exact. Sorry, I wasn't sure what you were asking at first.
(09:50) < Taejo> no problem. let me upload a picture to show what's going on
(09:50) < Taejo> http://i.imgur.com/EtmX8.png
(09:51) < byorgey> Taejo: ah, yeah, I see what's going on
(09:51) < byorgey> Taejo: it follows from what I said if you think about it carefully
(09:52) < Taejo> ah, you're right
(09:52) < Taejo> I see now
(09:52) < byorgey> if you ask for the "boundary" of a polygon in a direction not perpendicular to one of its edges...
(09:52) < byorgey> it is a bit annoying though. I'm trying to think of the best way to do what you want to do.
(09:53) < byorgey> Taejo: well, one easy solution would be to draw the lines between the centers of the polygons
(09:53) < byorgey> and just draw the polygons on top of them
(09:54) < Taejo> byorgey, yeah, that works... until I add arrowheads :(
(09:54) < byorgey> ah, hmm
(09:54) < Taejo> I think in that case I'll just have to live with the gaps
(09:56) < fryguybob> I think we could make an approximate solution that gave any desired accuracy.
(09:56) < byorgey> yeah, I've thought about things like that before
(09:57) < fryguybob> Not for bounds in general, but for this specific kind of case.
(09:57) < byorgey> you can automatically vary the angle at which you query the bounding function to try to find a local minimum
(09:57) < byorgey> we could also put in a special case for polygons which would work exactly
(09:57) < fryguybob> true
(09:58) < byorgey> well, for arbitrary paths really
(09:58) < Taejo> byorgey, I'm working on a library to draw graphs with arbitrary diagrams as nodes
(09:58) < byorgey> Taejo: cool!
(09:58) < Taejo> I could have a special case for when the nodes are described by a path
(10:00) < byorgey> Taejo: I don't think this is something your graph library ought to have special cases for
(10:00) < byorgey> we ought to put tools in the diagrams standard library to help deal with such situations
(10:01) < byorgey> hmm, rather than special-casing the bounding function code, we could have something which extends a path right up to a diagram
(10:01) < byorgey> since we do have more exact coverage information from the query
(10:02) < byorgey> you could specify an extension length which is long enough and then it would do a binary search
(10:02) < fryguybob> Something like binary search between the center and the bounds?
(10:02) < byorgey> exactly
(10:02) < byorgey> oh! even better.
(10:03) < fryguybob> I think that will only work if you are convex.
(10:03) < byorgey> true
(10:03) < byorgey> I actually meant a binary search between the end of the path and some specified distance beyond it
(10:04) < fryguybob> Yeah, holes are a problem
(10:04) < byorgey> but exact boundary points for convex shapes via binary search would be good too
(10:04) < fryguybob> Most of the time it would probably work well though.
(10:05) < byorgey> yup

[fryguybob]

(Imported. Original comment by byor...@gmail.com on November 11, 2011, 09:46:57 PM UTC)

We have an even better idea now: along with the current bounding function, track a function of type

Point -> Vector -> Scalar

which tells you the distance from the given point to the furthest point contained in the diagram along the given vector. Making the point an argument is required so that these can be translated properly.

Such a function would not be useful for putting diagrams next to each other but IS useful for finding points on the actual boundary of a diagram.

This function would also be added to the information you get in a LocatedBounds object (when using withName etc.)

Functions like 'boundary' etc. should use this new feature. 'align', '(|||)', etc. should remain as they are.

[byorgey]

We have this now! They are called Traces. See e.g. 09dd772 and related commits around the same time.