Validating for rectangle overlaps in Solidity

Question

The blockchain is going to store an array of structs: x1,y1,x2,y2 (uint) to represent the upper left and lower right corners of a rectangle.

When a new rectangle is added, I need to validate that it does not overlap with any other rectangles in the blockchain.

This is what I'm thinking of doing. Create another struct for the points, containing: x, y, index to the main rectangle array.

I will have two arrays, one sorted by X, and another sorted by Y. Both corners that define each rectangle will have entries in both arrays.

For the validation of the new rectangle, I search for whether any entry in the X array exists in between the 2 X's. The same goes for Y. If any of the returned entries for X and Y have the same "main array" index, then there's an overlap. I also have to validate whether the new rectangle is totally within another rectangle.

I'm still getting myself started with Solidity to try this out. It seems though that this is a very expensive process, and may not be scalable. I have to scan through 2 arrays multiple times to validate every new rectangle that I add.

Is there a more efficient way of validating my new rectangle without having to scan through 2 arrays?

The other option is to keep to just 1 array, and validate each rectangle against the new one. Again, this sounds quite expensive.

Adam Kipnis Adam Kipnis · Accepted Answer · 2018-01-19T04:46:50

There are simple algorithms for detecting if two rectangles overlap. A common one can be found here.

In Solidity:

pragma solidity ^0.4.19;

contract A {
    struct Rectangle {
      uint _x1;
      uint _y1;
      uint _x2;
      uint _y2;
    }   

    Rectangle[] _rectangles;

    function addRectangle(uint x1, uint y1, uint x2, uint y2) public {
      for (uint i = 0; i < _rectangles.length; i++) {
        Rectangle storage rectangle = _rectangles[i];

        // Reject if rectangle overlaps with input            
        require(x1 > rectangle._x2 || rectangle._x1 > x2);
        require(y1 > rectangle._y2 || rectangle._y1 > y2);
      }

      _rectangles.push(Rectangle(x1, y1, x2, y2));
    }
}

As far as expense goes, this will probably be the least expensive way to tackle this within the contract. Since this will bail as soon as a collision is found (and refund any remaining gas), you may be able to improve upon it by sorting at insertion time which will allow you to stop comparisons at some point and assume success. Of course, worst case is still a full loop across all rectangles.

The other approach would be to avoid doing the comparison in the EVM. This would require you to use constant functions to retrieve all of the stored rectangles and doing the comparison on the client side. It would be slow and convoluted, but if expense is you primary concern, it is an option. The approach you pick is going to depend on how many rectangles your contract needs to support, the performance you're looking for, and your cost limits.

Validating for rectangle overlaps in Solidity

1 Answers