What's the quickest way to find all sizes of circles?
Given a completely black and white image (so the only colors are black or white with no grayscale) there are many circles of different sizes (in black) on it, what is a quick way to find the coordinate of the center of the circles and the sizes of the circles and store them as a dictionary entry? When I mean, I would say that if I called this circle find function 10 or 20 times per second, it wouldn't be too far behind. Also I did some research and found out that I could find the center of a circle or radius by taking three points on the circle, can this help?
source to share
The first thing that comes to mind is to scan pixel by pixel, looking for black pixels. When you find him, start the flood. Once the fill has finished measuring the left, right, top, and bottom extents, then infer the center point by dividing it by 2. This assumes that none of the circles overlap. I'm sure there are probably a few more optimized methods out there that can avoid flooding the whole circle.
optimization # 1: Instead of filling padding when you find the first black pixel, find adjacent pixels along all 8 neighbors that have at least one white neighbor. Keep tracking these pixels until you click the first pixel again. This should give you an outline, from there you can get the width, height and center point just like in my original answer.
Optimization # 2: If the circles are at a minimum size, you don't need to scan pixel by pixel. You can scan horizontal and vertical lines at minimum size looking for black pixels.
source to share
I think you cannot avoid checking all white pixels, so the complexity of the algorithm will always be O (width * height). However, you definitely don't need to check all black pixels.
Once you find the edge of the circle, you can simply walk horizontally to the next edge and then vertically to the other edge. With these three points on the edge, you can draw a rectangle that has the same center as the circle. Then just go vertically or horizontally to find the radius of the circle.
source to share
You need a simple ray tracer that scans your space from left to right, top to bottom, pixel by pixel. When you hit the black pixel, you have a job. Here's the algorithm.
- As long as the current pixel is white, move on to the next (left to right or next row of pixels).
- when you hit the black pixel, move down the vertical line until you hit the white pixel. Whats your diameter, you use this to calculate the size of your circle (whatever you mean by size). To mark this circle as visited, paint the perimeter green (simple edge detection algorithm); thus, if you hit the green pixel first when traveling, continue cruising in the black circles until you hit green on the other symmetrical side of the circle. This way, there is no need for a complete flood filling algorithm and you will get away with sizing or missing the visited circles in a fraction of the cost required by the flood filling algorithm.
Note 1: The screen is rasterized, which means that the first pixel you click is not necessarily the top one, it might be one of them to the right of it, so you need to go right and left a bit, from anti-aliasing, to determine the top right and knock off from him.
Note 2: If your circles overlap, let's say and dump this algorithm and think about something else :-)
source to share