Consider a region (2D) filled with lines randomly (following Figure). We are interested in filling the empty spaces between lines including four boundary edges in a way:
0- maximizing the size of parcels;
1- shape of filling parcels is square aligned horizontally or vertically;
2- shape of filling parcels is square, i.e., relaxed alignment;
3- shape of filling parcels is any quadrangle. our original question
So for now there are three different scenarios.
Note that the lines are of the form [x1,y1,x2,y2] point set, real numbers.
[* * *] Ideas of possible solutions/algorithms/code snippets/etc are more than welcome.
Update 1: We could manage a solution for the first case:
Steps are:
1- lines
2- rasterizing lines into a bitmap
3- searching nearby cells for each cell of desired color (i.e., the same color) with an objective function to maximize the area i.e., the number of cells.
It works well however it covers only the first scenario and it is also slow.
Update 2:
We assumed that the reader is familiar with the concept of space-filling-tiling. You may follow the link for inspiration. However note that our problem is different. As we do not fill the empty space randomly and we do not chose the size randomly. The solution should be iterative. For all the cases, there is no limit on the number of parcel being fitted. Indeed, it is up to user to limit the iteration number, by choosing a minimum area for parcels, for example. This is obvious in the example given above in which we discretized lines into pixels with specified size. That is, the procedure should run until entire empty area is filled respecting the criterion e.g., the maximum area of parcels.
Update 3:
summary:
One application is to find out the distribution of extractable intact 'rock' blocks in a heavily fractured 'mine'. This could be very helpful for many aspects including drilling design, financial evaluation etc.
description:
For a mine of decorative rock (stone) the products which are the blocks of intact rocks cut as rectangular cubes the price is closely dependent to the size of the block. Extraction of a block from a suitable area i.e., with no major fracture will be desired if the amount of remaining parts is small as possible. Usually, the small pieces of rocks have no economic value relatively and are considered so as waste.
The question in this post investigates solutions for this kind of problem.
A mathematical view for the problem can be stated as follows:
2D: Find all rectangles that could be extracted from a given 2D region with some lines optimized for larger rectangle size as possible.
3D: Find all rectangular cubes that could be extracted from a given 3D region with some sub-planes (better: polygons) optimized for larger block size as possible.
Since this is part of an on-going research, some of the questions asked in the comments below do not have certain answers that we can provide. We believe that the provided information here so far is indeed enough to get the overall picture of the problem. Nevertheless, we provide some details as we can for community benefits.
You may put some restrictions on the solution for the ultimate question, although, we believe it is always possible to add more later. For example, follow these:
{2D case}
The best size of a block (economically optimum rectangle) to be extracted under the conditions mentioned above, is 1x1 m given 10x10 m for the region in the example. This is one constraint defined based on economical value. The minimum workable size for cutting etc, let be 0.15x0.15 m; so this the second size limit.
The figure above shows the economic value function depending to the block size. So for this particular case every rock piece smaller than 0.15x0.15 m is just waste. There will be no block size larger than 1.7x1.7 m due to operation limits.
