Find if bezier intersects with image's white pixels

ilya_f

Hi, I've generated a contour map which gives me a black and white image with edges that are 1 px thick. I'm trying to figure out a quick way to get the position t (percentage of the whole curve length 0 to 1) of the bezier curve where the underlying pixel is white. So far it tried iterating through the whole curve with various precisions for t (1/100, 1/1000, 1/10000) but because its not a linear interpolation sometimes the pixel is not detected because the step was too large at that particular section of the curve. My other thought is to rasterize the curve and compare the pixel arrays to find the intersections and then get the position t from the x,y values. But I'm not sure how to do that or even if its a good approach.

Let me know if you have any ideas.

quark

Since there is no simple formula to measure the length of a Bezier curve then any '% over white' you measure is going to be an approximation anyway.

So if your Bezier curve does not have very sharp bends then the spacing between the points for a given precision of t will be fairly constant along its length. So simply select a precision that gives reasonable results.

If the Bezier curve has sharp bends then the spacing between points (for a given precision of t) will vary greatly, i.e. the greater the radius of curvature the closer the points.

In this case I suggest that you vary deltaT along the line by calculating the distance between points and if too big reduce deltaT and if too small increase deltaT and keep going until t >1 at which point set t = 1 and calculate the last point.

ilya_f

thanks quark, that was my initial and more elaborate approach. Break the curve into a series of lines a certain length and iterate over those points instead of just t. Unfortunately because at the end to get the value of a pixel I need to convert to an int which rounds out my coordinates I still end up missing some of the intersections. I certainly get a better precision with the length method than just straight iteration of t but still not 100% perfect. What I think I need is to somehow average the nearby pixel values and determine how close to white I am. From there use the most white value of the set to determine the intersection.

ilya_f

Ok, so I tried the the above method with mixed results. For the most part it worked ok, but still I was missing several intersection even at really low number. The subdivision of a bezier is a bit tricky and time consuming so I ended up using the rasterization method instead. By comparing if the white values of the bezier curve matched the values of the contour image. Because the raster and the contour image are the same size the pixel location for both is the same so there was no need to check every pixel in the image. Than it was just a matter of solving for t for the bezier curve in question at the resulting x y points.

Hope this helps if anyone else has the same problem.