Say you have a bunch of rectangles like these:

enter image description here

They get organized into 3 distinct final shapes like this:

enter image description here

As you can see, there are a few "complete contours", as in here:

enter image description here

The way you figure out the contour of the thing is by visually going around the edge of the final shape, sort of like this:

enter image description here

The question is, given that you start with a set of arbitrarily sized curves, in this case, rectangles (assume they were drawn as real rectangles), how to efficiently/effectively figure out what the final paths are on the final set of shapes. So in the pink drawing, there are 4 paths that define the whole system. I am having a hard time imagining how you would formulate this as perhaps a graph theory problem or something in order to iterate through a list of rectangles, determine their "connectivity", then create some sort of mental sketch of the "perimeter". It seems like it would get complicated fast.

Wondering if there are any areas of research that delve into this stuff, or if there is a straightforward solution to the problem.

  • $\begingroup$ Do you have all "blocks" in advance? Your input is set of shapes and final raster? There are ideas like skeletonization, vectorization, blob detection, shape detection, Viola-Jones descriptors, feature detection, crossing point detection and many more concepts ressembling your problem. That said, I have a hard time understanding what is the input and what is your goal. What do you mean by paths? If your curves are given than finding intersections and "connectivity" is a good start, but what is next point? Finding blobs and detecting loops? $\endgroup$ – Evil Jan 31 '19 at 23:25
  • $\begingroup$ Yes I have all the blocks in advance. The shapes are in a data structure with width/height/x/y/bezier/etc. like svg path. $\endgroup$ – user10869858 Feb 1 '19 at 2:10
  • 1
    $\begingroup$ Can segments of the rectangles have any orientation ? Or only along 2 orthogonal axis ? $\endgroup$ – Optidad Feb 1 '19 at 9:53
  • 2
    $\begingroup$ I don't understand the problem statement. You want to find out what "the final paths" are, but what do you mean by "the final paths"? That phrase is never defined. Can you edit the question to clarify what is the input and what is the desired output? $\endgroup$ – D.W. Feb 1 '19 at 23:43

Your Answer

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

Browse other questions tagged or ask your own question.