Finding an approximate algorithm to find the largest crisp circle in an area
Related: Is there a simple algorithm for calculating the maximum inscribed circle in a convex polygon?
I am writing a graphics program whose goals are artistic, not mathematical. It is presented step by step using geometric primitives such as line segments or low angle arcs. As this happens, he looks for open areas to fill in in more detail; as the available open areas become smaller, the details become finer, so it is freely fractal.
At this point, to decide what to do next, we want to know: where is the largest circular area that is still free of existing geometric primitives?
Some problem limitations
- It doesn't have to be exact. Close enough answer.
- Inaccuracy should depend on the conservative side: a near maximum circle is acceptable, but a circle that is not completely empty is not acceptable.
- CPU efficiency is a priority because it will be called frequently.
- The program will run in a browser, so memory efficiency will also be a priority.
- I need to set a limit on the verbosity, presumably limited by the amount of memory.
- We can keep track of primitives already drawn in any way we want, for example. spatial index. Precision is not required; for example keeping bounding rectangles instead of arcs would be OK. However, the higher the precision, the better, because it will allow the program to paint at a higher level of detail. But given that the number of primitives can increase exponentially with the level of detail, we would like the storage of past parts not to increase linearly with the number of primitives.
To summarize the order of priorities
- Memory efficiency
- Processor efficiency
- Accuracy
PS
I've phrased this question in terms of circles, but if it's easier to find the largest transparent golden rectangle (or golden ellipse), that works too.
PPS
This image gives some idea of what I am trying to achieve. Here is the start of a tendril-based drawing program in which decisions about where to sprout the tendril and how large are made without considering the remaining open space. But now we want to know where is the place to draw the tendril, and how big? And where after that?
source to share
One very effective way would be to recursively divide your area into rectangular subzones, dividing them when necessary to separate occupied areas from unoccupied areas. Then you just need to keep track of the largest unoccupied area at any given time. See https://en.wikipedia.org/wiki/Quadtree - but you don't need to square.
For any rectangle, you can draw a line within it, so that at least one of the rectangles on each side of the line will be a golden rectangle. Therefore, you can recursively construct the sections within the rectangle so that all but one of the section rectangles are golden rectangles, and the remaining add rectangle is vanishingly small. You can do this to create a quadrant structure where almost all of the remaining rectangles were golden rectangles.
source to share
This is like a situation where a randomized algorithm might be useful. Pick points at random, reject and choose more if they are somehow inappropriate, then find the minimum distance from your options to each of the already included numbers. The random point with the maximum number of minutes will be your choice.
The number of dot patterns can increase as the complexity of the pattern increases.
The random algorithm can be improved by checking points near good choices. Keep checking neighbors until the improvement is improved.
source to share
Here's a simple way that uses a fixed amount of memory and an update time, no matter how many drawing primitives you use. How much memory (and update time) needs to be controlled depending on how high the "resolution" you want:
- Divide the space up into a grid of dots. We will maintain a 2D array, d [], which records the minimum distance from a grid point (x, y) to any already drawn primitive in d [x, y]. First, set each element in this array to infinite (or some huge amount).
- Whenever you draw some primitive, repeat all the grid points (x, y), calculating the minimum distance (or some conservative approximation to it) from (x, y) to the newly drawn primitive. For example, if only the primitive primitive was surrounded by radius r centered at (p, q), then that distance would be sqrt ((xp) ^ 2 + (yq) ^ 2) - r. Then update d [x, y] with this new distance value if it is less than its current value.
- The grid point at which the largest circle can be drawn without touching any already drawn primitive is the grid point farthest from any primitive drawn so far. To find it, simply scan through d [] to find its maximum value, and note the corresponding indices (x, y). d [x, y] will be the maximum radius you can safely use for this circle.
Repeat steps 2 and 3 as needed.
A few points:
- For primitives that have an area, you can assign 0 or a negative value to all d [x, y] corresponding to the grid points within the primitive.
- For any convex primitive, it is often possible to avoid updating most of the d [] array by scanning rows (or columns) "outward" from the primitive boundary just drawn: the distance from the current grid point to the primitive will never decrease, so if that distance gets larger than the previous maximum value in d [], then we know that we can stop scanning this line, because no other distance value that we would calculate on it would possibly be less than the distance that exists on it.
source to share