Calculating the edges of a rectangle (cuboid discussion).

Discussion in 'Plugin Development' started by Father Of Time, May 30, 2012.

Thread Status:
Not open for further replies.
  1. Offline

    Father Of Time

    Good afternoon all,

    So I have a quick algebra question for everyone. I am trying to figure out an efficient way of obtaining the edges of a rectangle cuboid. Here is a graphic to demonstrate what I mean:

    Diagram.JPG

    Notice how the edge blocks are green and the center blocks are marked red (pretend this is true for the unseen sides of the cube as well). What I am trying to do is take a cuboid and return a collection of all the blocks that are located on the edges of the cuboid; so with the above example the collection would contain every block that is marked green and none that are marked red.

    I have thought of a few methods to achieve this, such as taking the high point and using block iterators to grab each block along the same axis for the length of the cuboid and repeating for all the edges, but this just seems inefficient, and my past algebra experience leads me to believe that there is a formula for this…

    So, anyone know of a method to achieve this goal? Thank you in advance to all who assist with this subject.
     
  2. Offline

    BobbyD441

    Basicly you need to find all the blocks that have either x,y or z = 0 or 3.
    So run a for / while loop to find all those blocks =)
     
  3. Offline

    ZachBora

    I think he meant a generic formula.
     
  4. Offline

    kumpelblase2

    Code:
    int maxX;
    int minX;
    int maxY;
    int minY;
    int maxZ;
    int minZ;
     
    for(int x = minX; x <= maxX; x++)
    {
        for(int y = minY; y <= maxY; y++)
        {
            for(int z = minZ; z <= maxZ; z++)
            {
                  if(x == minX || x == maxX || y == minY || y == maxX || z == minZ || z == maxZ)
                         //Add block
            }
        }
    }
    About that. So i'm going through each block and check if it's on one of the edges, nothing more.
     
  5. Offline

    ZachBora

    I think that will include the red marked blocks.
     
  6. Offline

    kumpelblase2

    Actually yeah. If I look over it again you're right.

    Replace the original if with that:
    Code:
    int edgeIntesectionCount = 0;
     
    if(x == minX || x == maxX)
      edgeIntersectionCount++;
     
    if(y == minY || y == maxY)
      edgeIntersectionCount++;
     
    if(z == minZ || z == maxZ)
      edgeIntersectionCount++;
     
    if(edgeIntersectionCount > 2)
      //Block is on an edge.
    Since a red marked block will only fulfill one of these and greens at least two, this should work now.

    EDIT by Moderator: merged posts, please use the edit button instead of double posting.
     
    Last edited by a moderator: May 26, 2016
  7. Offline

    Father Of Time

    Wow, I can't believe I didn't think of that... If it's on a boarder then that means that it's coordinates must have either the MAX or MIN of either the Z or X.

    I wonder if this is fool proof? I mean if it has at least one of the X or Z's high/low points then it MUST be a boarder block; the question then becomes is there ever an instance where a block could have either the max/min X or Z coordinate and not be a boarder block?

    I swear, sometimes the answers seem so obvious that all I can think is "How didn't I think of that!?".

    You guys are awesome, thanks for contributing towards this thought experiment.

    Oh and p.s.
    *Begins singing the doom song while he lays face down in a pile of mashed potatoes!*

    Hey Kumpel,

    I'm curious why you added this in at the end of your example:

    Code:
    if(edgeIntersectionCount > 2)
      //Block is on an edge.
    is this just additional code for example sake to determine if a block is one of the rectangles vertex(corners), or does this server a larger function for returning positive results?

    EDIT by Moderator: merged posts, please use the edit button instead of double posting.
     
    Last edited by a moderator: May 26, 2016
  8. Offline

    kumpelblase2

    Well, there are blocks which aren't corner blocks that have a X max/min (or Z or Y)but they don't meet at least one of the other two requirements.

    If you don't add this, blocks that are on the outside, but not an edge block, will be added too since they meet one of those requirements. But to be an edge block, at least two of the requirements need to be true.

    EDIT by Moderator: merged posts, please use the edit button instead of double posting.
     
    Last edited by a moderator: May 26, 2016
  9. Offline

    Father Of Time

    Oh, I think I may have confused you. I actually do want the entire "edge", not just the corners.

    So in the above image the cuboid consist of a 3x3 block volume, or 27 blocks. The collection I am looking to obtain in this instance would contain 20 blocks, all of the blocks along the edges of the cube; where if we were to only obtain the edge blocks the collection would contain 8 blocks.

    I get what you are saying now...any block on one of the faces of the rectangle can have only 1 Max/Min coordinate; but a true "edge" block must have 2.

    EDIT by Moderator: merged posts, please use the edit button instead of double posting.
     
    Last edited by a moderator: May 26, 2016
  10. Offline

    kumpelblase2

    Yep, you got it! That's why the check if it actually mets at least two requirements ;)
     
  11. Offline

    desht

    The problem with the above approach is that it scans the entire cuboid, searching for blocks on the edge. OK for a small cuboid, but as the cuboid gets larger, it rapidly becomes a very inefficient algorithm. E.g. a 3x3x3 cuboid has 27 blocks of which 20 are edges. So you're searching 27 blocks to find 20 - not bad. But a 10x10x10 cuboid has 1,000 blocks and only 104 edges. A 50x50x50 cuboid has 125,000 blocks and only 584 edges - that's an awful lot of unnecessary searching.

    It makes more sense to just scan along the edges like this (untested code):
    PHP:
    // Given Vectors v1 and v2 (which must be sorted), return a list of Vectors which represent
    // all the points along the edges of the cuboid formed by v1 & v2.
    public List<Vectoredges(Vector v1Vector v2) {
            List<
    Vectorresult = new ArrayList<Vector>();
            for (
    int x v1.getVectorX(); <= v2.getVectorX(); x++) {
                    
    result.add(new Vector(xv1.getBlockY(), v1.getBlockZ()));
                    
    result.add(new Vector(xv1.getBlockY(), v2.getBlockZ()));
                    
    result.add(new Vector(xv2.getBlockY(), v1.getBlockZ()));
                    
    result.add(new Vector(xv2.getBlockY(), v2.getBlockZ()));
            }
            for (
    int y v1.getVectorY() + 1v2.getVectorY(); y++) {
                    
    result.add(new Vector(v1.getBlockX(), yv1.getBlockZ()));
                    
    result.add(new Vector(v1.getBlockX(), yv2.getBlockZ()));
                    
    result.add(new Vector(v2.getBlockX(), yv1.getBlockZ()));
                    
    result.add(new Vector(v2.getBlockX(), yv2.getBlockZ()));
            }
            for (
    int z v1.getVectorZ() + 1v2.getVectorZ(); z++) {
                    
    result.add(new Vector(v1.getBlockX(), v1.getBlockY(), z));
                    
    result.add(new Vector(v1.getBlockX(), v2.getBlockY(), z));
                    
    result.add(new Vector(v2.getBlockX(), v1.getBlockY(), z));
                    
    result.add(new Vector(v2.getBlockX(), v2.getBlockY(), z));
            }
            return 
    result;
    }
    It's a little more long-winded, but performance is linear in relation to the size of the cuboid you're scanning.
    I've used Vectors there but any class which represents a 3d point could be used instead.
     
    Father Of Time and kumpelblase2 like this.
  12. Offline

    AmoebaMan

    desht has the right code, but personally I don't like the way it's written. Here's my take on it:

    Code:java
    1.  
    2. public static HashSet<Block> cuboidEdges(Block lowBlock, Block highBlock){
    3. Location low = lowBock.getLocation();
    4. Location high = highBlock.getLocation();
    5. HashSet<Block> toReturn = new HashSet<Block>();
    6. //These variables are the components of the displacement between the two corners
    7. //The difference in x, y, and z
    8. int dx = highBlock.getX() - lowBlock.getX();
    9. int dy = highBlock.getY() - lowBlock.getY();
    10. int dz = highBlock.getZ() - lowBlock.getZ();
    11. for(int x = 0; x <= dx; x++{
    12. Location temp = low.add(x, 0, 0);
    13. toReturn.add(temp.getBlock());
    14. toReturn.add(temp.clone().add(0, dy, 0).getBlock());
    15. toReturn.add(temp.clone().add(0, 0, dz).getBlock());
    16. toReturn.add(temp.clone().add(0, dy, dz).getBlock());
    17. }
    18. for(int y = 0; y <= dy; y++{
    19. Location temp = low.add(0, y, 0);
    20. toReturn.add(temp.getBlock());
    21. toReturn.add(temp.clone().add(dx, 0, 0).getBlock());
    22. toReturn.add(temp.clone().add(0, 0, dz).getBlock());
    23. toReturn.add(temp.clone().add(dx, 0, dz).getBlock());
    24. }
    25. for(int z = 0; z <= dz; z++{
    26. Location temp = low.add(0, 0, z);
    27. toReturn.add(temp.getBlock());
    28. toReturn.add(temp.clone().add(dx, 0, 0).getBlock());
    29. toReturn.add(temp.clone().add(0, dy, 0).getBlock());
    30. toReturn.add(temp.clone().add(dx, dy, 0).getBlock());
    31. }
    32. return toReturn;
    33. }
    34.  


    Keep in mind that this code assumes that all of the low block's coordinates are less than the corresponding coordinates of the high block. You'll need to write a simple algorithm to ensure this by yourself.

    Offhand, how does one create the specialized Java code box with BBCode?
     
    Father Of Time likes this.
  13. Offline

    desht

    Couple of problems with that approach:
    1. Location is a mutable class (a very poor piece of design IMHO but impossible to change at this point) and the add() method modifies the Location object in-place and returns a reference to it. So you're continually modifying the same low object inside your loops with the .add() method (even when you modify temp, because that's just another reference to low anyway). That code will not do what you expect it to.
    2. Your implementation will return multiple references to the 8 corner blocks. Note how for the Y and Z axes, I started at <low + 1>, and stopped at <high - 1> - that was specifically to avoid that problem, since the corners were already included when the X axis was scanned.
    Still, I guess returning a List<Block> directly is easier for callers of the method than my more abstracted List<Vector> approach. Although arguably less flexible since you don't know what the caller intends to do with the returned data, so the relatively heavyweight getBlock() calls may or may not be necessary. I have a tendency to write stuff as generically as possible :)
    You can use the "syntax=java" tag but that has its own problems (mainly, trying to edit it afterwards will destroy any indentation you added). I prefer to use the "php" tag, which does a reasonable job of colouring Java syntax too.
     
  14. Offline

    IcyRelic

    [ syntax=java ]

    [ /syntax ]

    just remove the spaces
     
  15. Offline

    AmoebaMan

    1. You're absolutely right, and I was aware of this although I appear to have forgotten it when writing that snippet. The problem is easily fixed by using .clone() on the Location object before applying the .add(...) method.
    2. Easily fixed by using a HashSet rather than a list. This is a practice that I usually apply whenever dealing with unique objects such as Players and Blocks, but once again I seem to have forgotten it here.
    I'll apply these changes to the code now.
     
  16. Offline

    desht

    You'll also need to call .clone() on low for the three low.add() calls you make. That mutable design sucks, doesn't it? ;)


    True, but using a List will perform much better than using a Set, especially given that the normal usage will be to simply iterate over all blocks (or whatever) returned. Adding and iterating over an ArrayList will always be quicker than with a HashSet.

    A further optimisation is that we also know the size of the List in advance (a cuboid of dimensions x,y,z has 4x + 4y + 4z - 16 edge blocks - except for the degenerate case of 1-block thick cuboids) so we can preallocate the returned list. Adding objects to a preallocated ArrayList is about as efficient as it gets.
     
  17. Offline

    kumpelblase2

    Wouldn't it be even more efficient if you use an array instead of a list if you're already creating a list with a predefined size?
     
  18. Offline

    desht

    Good point :) Although the difference would be minimal. And from an API stability point of view, returning a Collection might be the best bet if the only intention is to iterate over it. Then the method can return whatever collection type it wants...
     
  19. Offline

    Father Of Time

    As usual a wonderful contribution to the conversation, thanks desht. I was indeed worried about this because the volumes of the rectangles I will be using this functionality on can be as large as 4 million blocks in volume.

    Out of curiosity I am going to implement both (the other method already exist in the project) and time their execution times to see the difference; I know you're method will be faster, but the question then becomes "by how much".

    Thank you for your insight Desht!


    p.s. sorry for the delayed response, had to go to an interview between post! ;)
     
  20. Offline

    desht

    Father Of Time for 4,000,000 blocks I estimate my method will be about 10,000 times faster, give or take :)
     
    Father Of Time likes this.
  21. Offline

    Father Of Time

    So we've got that going for us.... Which is niiice... :D
     
  22. Offline

    ZachBora

    Sort of wondering what you're using this for..
     
  23. Offline

    Father Of Time

    I tend to play my cards close to my chest, but it's pretty apparent that this system is to outline a cuboid system so that users can visual determine the boarders and not be required to rely on enter/exit messages.

    You are more than welcome to stop on by and check it out, it's currently on our live server. :D
     
  24. Offline

    ZachBora

    Well this thread tells me someone should make minecraft rubik :p
     
  25. Offline

    Bone008

    This number just caught my attention, it looks familiar to me for some reason :D
    Awesome idea, I wondered about that inconvenience (you know what I am talking about) as well.

    Seeing the first approach (iterating everything) already made me ask: "what if that is used in that specific plugin where it is most likely to be used, wouldn't that be slow?". Now that those alternatives came up, I am quite sure that it's going to be a wiser approach :p
     
  26. Offline

    AmoebaMan

    Well if you're dealing with that many blocks then of course you'll want to use desht 's method. Most of my work is small-scale, so executio time rrely makes its way into my considerations. And yes, God damn mutable objects.

    Offhand, what is this server that Father Of Time is referring to?
     
  27. Offline

    desht

    Actually that was a bit optimistic - probably closer to a factor of 2,500 (4,000,000 blocks vs ~1600)
     
    Father Of Time likes this.
  28. Offline

    AmoebaMan

    Makes more sense. When you first posted that I thought you were referring to the efficiency of your code vs. mine :p I thought it seemed a bit high...
     
    desht likes this.
  29. Offline

    Father Of Time

    *grins evily* I was hoping to surprise you with it next time you logged in. :D

    Check it out, go onto the server and do /md view <dominionname>, it's pretty awesome. It's on a 30 second cooldown like your info command to keep the workload from being too intense. It's on our SVN and still utilizing the old method, so if you get to it before I do please feel free to upgrade it to the faster model stated above. I personally love it because it's encouraging our players to "push" their houses against each other to create a "strip mall" feel.

    AmoebaMan I am not entirely sure whether or not I can advertise our server on Bukkit forums; however, the banner in my signature (the extremely outdated banner in my first post) is a link to the server.

    You are the only person on this forum desht that I would expect to correct their humorous estimation with a logic based projection... I love analytical thinkers such as yourself. :D

    EDIT by Moderator: merged posts, please use the edit button instead of double posting.
     
    Last edited by a moderator: May 26, 2016
Thread Status:
Not open for further replies.

Share This Page