0

I'm working with plane surfaces, related to lasercut parts, and for this purpose I wish to find an algorithm to break the parts into sub-divided rectangular polygons describing the surface (as a basis for 3d rendering).

The parts that I'm working with always observe right-angles around the perimeter and always observe rectangular cutouts in the interior. Here's an example of a boolean-mesh to clarify

       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 
    2  * * * T T T T * T T T T T * T T T T * * * 
    1  T * T T T T T T T T T T T T T T T T T * T 
    0  T * T T T T T T T T T T T T T T T T T T T 
    9  T T T T T T T T T T T T T T T T T T T T T 
    8  T T T T T * * * * * T * * * * * T T T T T 
    7  T T T T T T T T T T T T T T T T T T T T T 
    6  T T T T * * T T T * * * T T T * * T T T T 
    5  T * T T * * T T T * * * T T T * * T T * T 
    4  T * T T T T T T T T T T T T T T T T T * T 
    3  T * T T T * * * * * T * * * * * T T T * T 
    2  T * T T T * * * * * T * * * * * T T T T T 
    1  T T T T T * * * * * T * * * * * T T T T T 
    0  T T T T T T T T T T T T T T T T T T T T T

The asterisk {*} indices empty space, either the internal rectangles or the right-angled perimeter.

The mesh here of size (21,13) does not match 1:1 to physical dimension, it is just a guide in visualization generated by the boundaries [all(x),all(y)]. The shape corresponding to this example looks like this (top part)

enter image description here

The input data is a closed-loop list of vertices describing the perimeter, together with a set of closed-loop list for the interior cutouts.

Here's another simple example, of the input shape and the kind of result that I'd like to arrive at

enter image description here

The single-slotted plane requiring four rectangles to describe it. Incidentally, it is evident that the set of possible subdivisons is > 1. For graphics applications it would be more interesting arriving at solutions that avoid making thin strips and also arriving at as few parts as possible.

I've managed one solution by iteration and querying the special extents against occupancy in the mesh, but I'm pretty sure there are better ways. If anyone knows a smart way to do it, I'd be grateful to know.

Robb Hoff
  • 1,719
  • 2
  • 17
  • 32
  • This is hard to do optimally (but you can, with integer linear programming), how good does it have to be? – harold Aug 18 '15 at 14:11
  • I have a preference for easy, but I like optimal too, for my purpose the shapes will not extend to any kind of inhibiting size – Robb Hoff Aug 18 '15 at 14:13
  • Is it allow to do a rotation of a shape after/before the cut ? – Galigator Aug 18 '15 at 16:37
  • 2
    The techniques described in [this question + answers](http://stackoverflow.com/q/30818645/555045) should apply, you have rectangles instead of squares but that only means more columns in the problem. If it gets too bad you can use column generation. – harold Aug 18 '15 at 16:39

0 Answers0