I have a 3D array, aka an array of 0s and 1s inside an array inside an array.
What I am trying to do is make an algorythm that removes all the 1s in this array in the form of rectangular prisms, returning me an array of prisms removed.
I am slightly confused as to how I should approach this. I was thinking of iterating through the arrays from a chosen point and try to get the size until it reaches a 0, but I always reach some sort of blockade in my thought.
All help is appreciated!
To answer the question, we first have to know whether you expect your prisms to be entirely filled, only the faces filled, or just the edges. It also depends on whether you only want to count the largest version of a given prism or all the sub-prisms contained within it. Finally, it also depends on the size of your entry. If it’s small enough and you don’t want to bother with a complicated algorithm, a brute-force solution will be suitable. For an efficient implementation, in the first case, dynamic programming seems to be a very good option, otherwise, it might be a good option as well. Backtrack the DP to retrieve the solutions and naively remove them from the original array.
I apologise for not being very specific in that regard. Answering your questions:
Entirely filled.
Ideally the largest distributions possible so long as it doesnt disrupt performance.
It will vary, as it will be used for all sorts of sizes.
Can you explain what you mean here?
The reason I need this algorythm, by the way, is to create pixelized destruction. Essencially, in the same fashion you would destroy terrain, this is supposed to create multyple prisms that fit the damage. The 0s in the previously mentioned array are the parts from the grid that are destroyed.
Dynamic programming is a paradigm that helps solve problems of this kind, where you can establish an induction relation between the solution of a problem of size N and the solution of the problem of size < N. Finding an induction relation generalized to 3D is easy enough when it comes to counting the number of solutions, but since you want to list the prisms and ignore sub-prisms, the problem becomes really more complicated. I don’t think you will be able to retrieve the prisms by backtracking numbers so it means you’ll have to carry over the DP the coordinates of the top left corner of each prism. Haven’t thought about it in depth so there may be other solutions, but the problem is absolutely not trivial. If you’re not familiar with algorithmics, the best option you may have is to find a different way of doing what you want to achieve, or otherwise, add some more constraints such as guaranteeing that prisms won’t overlap for instance.
For the later situation you mentioned, I thought of making all the 1s of a prisms you remove 0.
Not sure what you meant but replacing prisms with 0’s doesn’t help because you first have to determine where they are.
Nevermind what I just said. Are there any places I can read about this topic?
Search for “dynamic programming” on the internet, you’ll find tons of articles and videos on the topic. Just stating it again, solving this problem won’t be any easy.
Now that I think about it, what is your definition of a prism? Personally, I’d look forward to enumerating all shapes that are at least 1x1x1 in the form of prisms. But this is equivalent to finding all 1’s in the matrix, and if your goal is just to delete the associated parts, there’s no point in enumerating the prisms.
Basically, any volume. That could be something like a 1x2x1, 50x25x10, whatever. I want to remove them all, and keep their data.
Ok so we don’t just remove all 1’s directly because you want to remember where the prisms were. Is this information really crucial? Also say two prisms overlap each other, do you want to store the largest bounds possible for the two prisms or it doesn’t matter if one of them is complete and the other one is broken into pieces?
Yes, I will need it to be able to place the replacement parts for any sort of destruction. I mainly need their position in the array as well as the size of the prism.
Ideally, they will not overlap.
Ideally is not something we can stand with. If you can guarantee that prisms won’t overlap, there’s a simple enough DP algorithm that will work in O(npq). If not, DP must still work but it’s a lot harder to work with. I’ve made an algorithm that works in 2D in O(n²p), I’m trying to extend it to 3D, it would be at least in O(n²pq).
I do not want them to overlap. Does “npq” stand for three dimensions?
Are you sure they won’t overlap? That’s my question. O(npq), assuming your matrix has dimensions n * p * q, means the algorithm will take a time that’s at most proportional to npq.
I am not quite sure as to what you mean. This is a 3D Array made of 0s and 1s. Prisms do not have a clear border, yet. If I could find these borders or get the space diagonal of the prism, I believe this problem would have a simple solution. I do not know how to grab that data yet, though.
I mean is it possible that some of the prisms will intersect?
If I do this correctly, no, they wont. That is what I meant by “ideally”, earlier.
So a simple 3D dynamic programming that carries over the min-coordinates of the prism through the induction relation will do the job.
The minimum coordinates would be the first point it finds, correct? How would I get the maximum?