0

I'm looking for advice on an algorithm I've been struggling with. I have something represented in code (shown later) that looks like the following diagram (initial state on left, desired output on right): enter image description here

I have this represented in C++ as the following:

#include <vector>

using namespace std;

class Shape {

    public:
        Shape(vector<vector<float> > c) {
            coordinates = c;
        }

        vector<vector<float> > coordinates; // in format {{x1,y1},{x2,y2}}
};

class Shape_Group {
    public:
        Shape_Group(vector<Shape> s) {
            shapes = s;
        }

        vector<Shape> shapes;
        Shape generate_border();
};

Shape Shape_Group::generate_border() {
    /* 
        define algorithm here
    */
}

int main() {
    // define rectangle shapes
    Shape s1({{0,0}, {0,1}, {1,1}, {1,0}});
    Shape s2({{0,0}, {0,1}, {1,-1}, {-1,0}});

    Shape_Group group({s1, s2}); 
    Shape border = group.generate_border(); // should return a shape with the exterior border
    // border should be filed with {{1,0}, {1,1}, {1,-1}, {-1,0}};
}

My initial idea for generating this exterior shape was to do something like the following: 

loop through each line segment for each shape in the Shape_Group object
    loop through every other segment in the Shape_Group object
        if both line segments are colinear and overlap, remove them

whatever's left over should be the exterior border

However, with large inputs this is a very slow algorithm. What else can I do?

k-a-v
  • 326
  • 5
  • 22
  • Can your input shapes overlap? (A point can exist which is inside two shapes?) Can there be holes in the resulting shape? (Multiple shapes form the outer ring of the letter O, but there is no shape covering the center?) Can there be multiple "islands" of shapes that do not connect, so that you would effectively be looking for two output shapes, not just one? Any guarantees about the input at all, or purely arbitrary shapes? – DeducibleSteak Feb 10 '20 at 19:32
  • The only guarantee is that input shapes do not overlap. Yes, there can be "islands" of shapes, and there can also be holes in the resulting shape. – k-a-v Feb 10 '20 at 19:52
  • Then first of all you, of course, need a datastructure that can represent the fact that the resulting Shape actually represents two shapes. Right now it's just a list of points, with no indication of where one would begin and the other would end. Also, your proposed algorithm would only work if there was an additional guarantee - any bordering shapes would need to share the same exact edges (one smaller shape having a short segment that is touching part of a larger shapes longer edge in the middle, for example, would break it). Is that also guaranteed? – DeducibleSteak Feb 10 '20 at 19:59
  • No, this is not guaranteed, but this would not break the proposed algorithm. The lines are still both colinear and overlap (overlap meaning that greater than one point is shared by the lines). You are correct in saying this data structure needs modification - a three dimensional vector would work for this. I can edit the question. – k-a-v Feb 10 '20 at 20:10
  • 1
    Yes, it would break it. Imagine an axis aligned square (x1=0, y1=0, x2=3, y2=3), and another axis aligned square (x1=1, y1=3, x2=2, y2=4). If the edge (0,3) -> (3,3) of the larger square is represented only by two points, you would detect that it overlaps with the edge (1,3) -> (2,3) of the smaller square and remove them both, leaving you with an "open" shape. – DeducibleSteak Feb 10 '20 at 20:19
  • Anyway, assuming you have some way of working around that, have you thought about making a lookup table where you would store all your edges, sorted by the normal and distance from origin, so the question of "are there any colinear edges with this edge?" would become a O(log n) question, instead of an O(n) question? That would improve you expected runtime from O(n^2) to O(n log n). – DeducibleSteak Feb 10 '20 at 20:52
  • Ah, I see now. I think that I will use the boost polygon or geometry library, since I'm not too experienced in geometry and algorithms. Thanks for the help! – k-a-v Feb 10 '20 at 22:21
  • Yeah, this is not an easy problem, and doing it with floating point coordinates instead of integers will be extra messy, so if you can find some library to do this for you, that's definitelly the way to go. If you end up with a good solution, drop a line here, I'd be interested in how boost polygon / geometry handles this. – DeducibleSteak Feb 10 '20 at 23:42
  • If you can use additional libraries, look at OpenCV findCountours() with RETR_EXTERNAL – MBo Feb 11 '20 at 04:20
  • I ended up using the C++ implementation of Clipper, a polygon clipping library. Thanks for the help! – k-a-v Feb 23 '20 at 16:19

1 Answers1

1

Geometry O(n^2) approach:

  1. make list of all edges

  2. remove all interrior edges

    use hit test to detect interior/exterior edges.

  3. reconnect all remaining edges into new polygon

    simply connect edges sharing the same end point.

If you want something simpler then O(n) graphics approach:

  1. render your shape
  2. fill background with specific color
  3. remove all edges not neighboring background color

this is somewhat related:

it also combines vector graphics and pixel access ...

There are also different approaches to this problem for example like this one:

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380