1
$\begingroup$

I am creating a 2D CAD drawing generator in C# using .netDXF library. Given a area I want to fill it with rectangles/circles (convex). For example, the regions marked with numbers in below image. This is just an example, the pattern may change.

I'am not an expert in the area of graphics. What should be my approach to this problem? Is there any algorithm that I can follow? What would be a generalized (not specific to .netDXF) way to fill an irregular region with 2D shapes.

Any help is appreciated!

enter image description here

$\endgroup$
  • $\begingroup$ So you want to place a bunch of small shapes of one type (same size?) inside a larger shape? Its not possible to fill the shapes in the images with circles completely with no overlap. $\endgroup$ – Andrew Wilson Oct 4 '17 at 3:18
  • $\begingroup$ Same sized polygon/circle, there'd be a fixed distance between them, and it's fine to have partial shapes near the boundary. $\endgroup$ – user7413 Oct 4 '17 at 3:49
  • 1
    $\begingroup$ For circles you'd hexagonally pack them to get them as tight as can be. Then clip ones that lie on boundaries. This wouldn't vary with regions or circle size. If all you want to do is fill these shapes with color then forget the rectangles/circles and just scanline them in. $\endgroup$ – Andrew Wilson Oct 4 '17 at 3:57
1
$\begingroup$

There is no general algorithm for packing problems. Only some of the special cases have known, and optimal, solutions. If you are packing one shape then finding a reasonable solution is possible. Like the known cases of hexagonal packing etc.

However, if you have multiple diffenently sized objects then easy just flew out of the door. Some heurestics have been developed, since there is a very big demand for such algorithms in manufacturing. But they are not usually very fast (performant?) or simple to implement. Many of them use a genetic algorithm. A free one that you may test can be found atsvgnest.com but faster ones and ones working on shaking and collision also exist.

Anyway your question is sufficiently vague, so i dont actually know if you want to do packing. I mean it is perfectly possible you mean tiling, which is pretty trivial.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.