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

Improve this question
$\endgroup$
3
  • $\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, 2017 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, 2017 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, 2017 at 3:57

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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