Splines: HitTest, Bounding Box, Isodistant points

[Marco F]

Hi.

I need some hints and hope somebody could help me.

I'm looking for two funtions for 2d cubic (Beziér) splines.

1) a "Hittest" (or: distance of a given point to nearest point on a beziér)
2) is a bounding box around a bezier courve.

I could think of a solution like walking along the bezier by splitting it at a given percentage, but thats ineffective and inexact.

Any better ideas or does anybody know some "off-the-shelf" algorithms ?



There's a third thing that is of interest for me, but not that important: Creating points that make up the bezier spline in a way, that the distance of the points is identical (e.g. point distance of 0.1 mm) that is not using recursive approaches or that are at least terminating after a deterministic time.

[cindyonlyone]

You can try the following steps:
1.You can split the spline to small line rgns.
2.Then hit test for each small line rgns.

To obtain the bounding rectangle you should calc all the small line rgns.

Or

Take a look at XD++ Flow/Diagram Kit,it has all the source codes you want,but it is not free,it can be found with:
http://www.********.net/index.htm

Hope this will be useful to you.

Cindy

[Marco F]

cindyonlyone,

that's what I meant by "I could think of a solution like walking along the bezier by splitting it at a given percentage", with all it's disadvantages, but thanks for your answer, anyway.

For information of interested readers:
My implementation for a bounding box looks like:
- get 101 points at the bezier using Casteljau algorithm ( position = 0, 0.01, 0.02, ..., 0.99, 1.00 )
- remember between which of those 101 points the minX, maxX, minY and maxY has been encountered
- arround those 4 points, look again (e.G. from iMinX-1 to iMinX+1) with a higher resolution ( i got 101 more points between those two, so a factor of 50 is added to the resolution there).

That approach is by far faster than I thought and looks like it's at least good enough for most applications. A more sophisticated approach could be to have more iterations or a higher resolution or using newton approximation with a termination condition you need (variation of minX, maxX, ... below your required accuracy after last iteration)