There is a black-and-white picture - some kind of flat figure filled in with black on a white background.

I create an image of the same size, where randomly located points attack only where the original is black.

I do this clearly not optimally: I choose a random point of the original image, and I see what color it is in the original - if black (or яркость < X ), then this point suits me and in these coordinates I put a dot in these coordinates (in fact, I place the sprite ).

How can you optimize / speed up the process so that there are no idle shots, of which most are usually, because the figure has an area much smaller than the whole field).

  • What about the size of the original image in pixels? - pavel
  • 1080x1080 (instagram) - Sergiks
  • 2
    I can suggest then making a list of dark (in your definition) cells and choosing from them already. There will be no more than a million cells, and given that the figure is smaller than the rectangle, it is even smaller. - pavel
  • 2
    What does "not optimal" mean? For example, imagine that every tenth point is "dark" in the image, then in order to select a random dark point, on average, you only need to try 10 times regardless of the image size. Compare, for example, with an algorithm that goes through 100_000 dark points from 1000_000 image points, and then selects the number of operations ~ 1000_000 instead of 10. Only from these 100_000 dark points. The second algorithm becomes preferable only if you want to select a significant part of dark points ( ~ 100_000). - jfs
  • one
    What big O behavior do you expect (N-all points, M-only dark, K-how many random ones are needed)? The first algorithm is O(K*N/M) , the second algorithm: O(K+N) . If K==1 , then obviously the first algorithm is more preferable. If K~N , then the second algorithm is better for large N, if M<<N - jfs

1 answer 1

There is a lot of unknown in the task.

You can try this option:

  1. Take the center line and check if there is a black dot on it.
  2. If not, check the lines at 1/4 and 3/4
  3. Etc. dividing the next step in half until we find a line with black dots.
  4. As we have found, we take it as the baseline and, using the same algorithm, we look for the leftmost and rightmost line in which there is still a point and take the next one as the border, on which there is no point
  • ask what is unknown in the problem. There is a working ineffective solution - I described it: random points are simply poked in the entire picture, and depending on the color of the selected pixel, a decision is made. - Sergiks
  • The described actions make it possible to find and circumvent the black points of a solid figure that has no islands, but why this? - Sergiks
  • @Sergiks There was no word about the islands. “black flattened figure” is a figure, not a set of figures. In the case of a small solid figure, this method will eliminate a lot of false positives. If in your case the fill can be broken and scattered over the entire area, then there is no other algorithm than pulling at random throughout the picture. Well, either you really need to scan all the points and gather them into an array from which to choose, but, IMHO, it will be much more expensive. - rjhdby