Overlapping / Touching Shapes

edited November 2011 in General
Hello Matthias,

first of all, thank you for creating and maintaining this great project!

I'm looking for an iterator to select overlapping or touching shapes of 2 different layers. The iterator should not only select the area of intersection, but the whole shapes of both layers, which are in touch. Thus shapes with no intersection are not selected.

The RecursiveShapeIterator is pretty much what I'm looking for, except that polygons are no valid input for the search region. Is there a way to use polygons as search region or to achieve this task differently?



  • edited 8:09PM

    Hi Dan,

    since the RecursiveShapeIterator operates on the quad tree, it takes boxes as the search region only.

    One way to work around that limitation is to somehow split the polygon into rectangles (provided it's manhattan) and use every rectangle as an individual search region. Since there is no packaged decomposition function (yet) available in Ruby, that is quite tedious.

    Another way is to use the bounding box of the polygon for the search and then filter out the false hits inside the test loop by performing an interaction test between the found shape and the search polygon. Right now, the most efficient way to do an interaction test is to perform a logical AND between the test polygon and the found one using EdgeProcessor.boolean_p2e. The polygons overlap when the result is non-empty. Please note that this will not detect touching configurations. This method also works for non-manhattan polygons.

    Bottom line is that there is no really good solution for that problem. The second method can be implemented pretty easily right now but in certain configurations (i.e. ring-like search polygons), a huge number of false hits have to be tested and the boolean AND is not quite efficient as a simple interaction test.

    Both solutions will only be usable if you have few search shapes and not many subject polygons interacting with them. In the case of many-to-many interactions, there are much more efficient algorithms based on a scanline approach which will report all interactions in a single sweep.

    Best regards,


  • DanDan
    edited 8:09PM
    Hello Matthias,

    the second method is working perfectly. Thank you for that hint.

Sign In or Register to comment.