Message Boards Message Boards

Breaking up a graphics object

Posted 9 years ago

A friend of mine approached me with the problem of wanting to break up a Graphics object like so:

enter image description here

The only solution I could think of involved turning the Graphics object into a Graph, where points become vertices and lines become edges, and finding FundamentalCycles:

GraphicsBasis[graphic_] := Graphics[Line[Sequence @@@ #]] & /@ 
FindFundamentalCycles[Graph[UndirectedEdge @@@ First /@ MeshPrimitives[DiscretizeGraphics[graphic], 1]]]

But I really feel like there's a more direct way to perform this operation, i.e. only using geometry constructs. Can anyone think of a more direct way? I've banged my head on a wall for too long now.

Here's the graphic:

Graphics[{
Line[{{36.717, 45.221}, {45.896, 33.146}}], Line[{{111.144, 45.004}, {101.896, 32.983}}], 
Line[{{123.576, 116.856}, {106.063, 142.272}}], Line[{{24.704, 117.143}, {42.365, 142.458}}], 
Line[{{74.205, 139.444}, {78.114, 139.338}, {82.12, 139.21}, {86.197, 139.287}, {90.258, 139.666}, 
{94.251, 140.23}, {98.197, 140.858}, {102.131, 141.528}, {106.063, 142.272}, {109.985, 143.122},
 {113.885, 144.088}, {117.757, 145.163}, {121.601, 146.346}, {125.42, 147.651}, {129.163, 149.11}, 
{132.667, 150.539}, {136.035, 151.229}, {138.995, 150.688}, {140.926, 148.73}, {141.662, 145.748}, 
{141.063, 142.54}, {139.469, 139.188}, {137.445, 135.869}, {135.251, 132.668}, {132.953, 129.536}, 
{130.606, 126.405}, {128.258, 123.241}, {125.917, 120.056}, {123.576, 116.856}, {121.228, 113.643}, 
{118.861, 110.416}, {116.482, 107.153}, {114.158, 103.817}, {111.973, 100.376}, {110.015, 96.799}, 
{108.378, 93.071}, {107.106, 89.213}, {106.157, 85.261}, {105.476, 81.23}, {105.008, 77.134}, 
{104.698, 72.983}, {104.502, 68.765}, {104.47, 64.498}, {104.725, 60.24}, {105.395, 56.064},
 {106.62, 52.05}, {108.535, 48.318}, {111.144, 45.004}, {114.224, 42.1}, {117.57, 39.524}, 
{121.001, 37.193}, {124.373, 35.027}, {127.711, 32.94}, {131.093, 30.857}, {134.532, 28.726}, 
{137.755, 26.472}, {140.348, 24.009}, {142.027, 21.238}, {142.687, 17.979}, {142.328, 14.422}, 
{140.991, 11.041}, {138.774, 8.27}, {135.876, 6.366}, {132.635, 5.497}, {129.32, 5.78}, {126.116, 7.115},
 {123.312, 9.251}, {120.974, 11.978}, {118.878, 15.162}, {116.785, 18.603}, {114.449, 22.042},
 {111.764, 25.264}, {108.763, 28.188}, {105.465, 30.774}, {101.896, 32.983}, {98.108, 34.796}, 
{94.16, 36.212}, {90.104, 37.233}, {86.008, 37.859}, {81.93, 38.158}, {77.898, 38.255}, {73.911, 38.273}, 
{69.923, 38.278}, {65.891, 38.205}, {61.811, 37.929}, {57.711, 37.327}, {53.65, 36.33}, {49.694, 34.937}, 
{45.896, 33.146}, {42.314, 30.958}, {39.001, 28.391}, {35.983, 25.484}, {33.279, 22.278}, 
{30.923, 18.853}, {28.81, 15.425}, {26.695, 12.253}, {24.342, 9.539}, {21.525, 7.42}, {18.313, 6.103}, 
{14.996, 5.839}, {11.76, 6.727}, {8.874, 8.648}, {6.673, 11.432}, {5.356, 14.821}, {5.017, 18.38},
 {5.696, 21.635}, {7.391, 24.396}, {9.999, 26.844}, {13.235, 29.08}, {16.687, 31.19}, {20.08, 33.254},
 {23.43, 35.321}, {26.815, 37.467}, {30.26, 39.778}, {33.621, 42.335}, {36.717, 45.221}, {39.345, 48.519},
 {41.283, 52.241}, {42.531, 56.248}, {43.225, 60.419}, {43.504, 64.676}, {43.498, 68.943}, {43.326, 73.161},
 {43.041, 77.315}, {42.596, 81.413}, {41.939, 85.448}, {41.013, 89.406}, {39.764, 93.271}, {38.148, 97.009},
 {36.21, 100.596}, {34.046, 104.05}, {31.742, 107.4}, {29.382, 110.677}, {27.033, 113.917}, {24.704, 117.143},
 {22.382, 120.358}, {20.059, 123.556}, {17.73, 126.733}, {15.401, 129.878}, {13.121, 133.024}, 
{10.946, 136.238}, {8.941, 139.568}, {7.367, 142.93}, {6.787, 146.14},  {7.54, 149.118}, {9.482, 151.065},
 {12.446, 151.589}, {15.809, 150.879}, {19.306, 149.43}, {23.039, 147.949}, {26.851, 146.622},
 {30.688, 145.417}, {34.553, 144.319}, {38.448, 143.331}, {42.365, 142.458}, {46.293, 141.691},
 {50.222, 140.998}, {54.164, 140.347}, {58.154, 139.76}, {62.213, 139.357}, {66.29, 139.256}, 
{70.297, 139.361}, {74.205, 139.444}}]}]
POSTED BY: Greg Hurst
2 Replies

Here is a recursive routine for the region. It is not terribly general because it would not work as expected if one cross link crossed another, or if a cross link crossed the curve between the endpoints.

The initial data is:

initialGraphics = 
 Graphics[{Line[{{36.717, 45.221}, {45.896, 33.146}}], 
   Line[{{111.144, 45.004}, {101.896, 32.983}}], 
   Line[{{123.576, 116.856}, {106.063, 142.272}}], 
   Line[{{24.704, 117.143}, {42.365, 142.458}}], 
   Line[{{74.205, 139.444}, {78.114, 139.338}, {82.12, 
      139.21}, {86.197, 139.287}, {90.258, 139.666}, {94.251, 
      140.23}, {98.197, 140.858}, {102.131, 141.528}, {106.063, 
      142.272}, {109.985, 143.122}, {113.885, 144.088}, {117.757, 
      145.163}, {121.601, 146.346}, {125.42, 147.651}, {129.163, 
      149.11}, {132.667, 150.539}, {136.035, 151.229}, {138.995, 
      150.688}, {140.926, 148.73}, {141.662, 145.748}, {141.063, 
      142.54}, {139.469, 139.188}, {137.445, 135.869}, {135.251, 
      132.668}, {132.953, 129.536}, {130.606, 126.405}, {128.258, 
      123.241}, {125.917, 120.056}, {123.576, 116.856}, {121.228, 
      113.643}, {118.861, 110.416}, {116.482, 107.153}, {114.158, 
      103.817}, {111.973, 100.376}, {110.015, 96.799}, {108.378, 
      93.071}, {107.106, 89.213}, {106.157, 85.261}, {105.476, 
      81.23}, {105.008, 77.134}, {104.698, 72.983}, {104.502, 
      68.765}, {104.47, 64.498}, {104.725, 60.24}, {105.395, 
      56.064}, {106.62, 52.05}, {108.535, 48.318}, {111.144, 
      45.004}, {114.224, 42.1}, {117.57, 39.524}, {121.001, 
      37.193}, {124.373, 35.027}, {127.711, 32.94}, {131.093, 
      30.857}, {134.532, 28.726}, {137.755, 26.472}, {140.348, 
      24.009}, {142.027, 21.238}, {142.687, 17.979}, {142.328, 
      14.422}, {140.991, 11.041}, {138.774, 8.27}, {135.876, 
      6.366}, {132.635, 5.497}, {129.32, 5.78}, {126.116, 
      7.115}, {123.312, 9.251}, {120.974, 11.978}, {118.878, 
      15.162}, {116.785, 18.603}, {114.449, 22.042}, {111.764, 
      25.264}, {108.763, 28.188}, {105.465, 30.774}, {101.896, 
      32.983}, {98.108, 34.796}, {94.16, 36.212}, {90.104, 
      37.233}, {86.008, 37.859}, {81.93, 38.158}, {77.898, 
      38.255}, {73.911, 38.273}, {69.923, 38.278}, {65.891, 
      38.205}, {61.811, 37.929}, {57.711, 37.327}, {53.65, 
      36.33}, {49.694, 34.937}, {45.896, 33.146}, {42.314, 
      30.958}, {39.001, 28.391}, {35.983, 25.484}, {33.279, 
      22.278}, {30.923, 18.853}, {28.81, 15.425}, {26.695, 
      12.253}, {24.342, 9.539}, {21.525, 7.42}, {18.313, 
      6.103}, {14.996, 5.839}, {11.76, 6.727}, {8.874, 8.648}, {6.673,
       11.432}, {5.356, 14.821}, {5.017, 18.38}, {5.696, 
      21.635}, {7.391, 24.396}, {9.999, 26.844}, {13.235, 
      29.08}, {16.687, 31.19}, {20.08, 33.254}, {23.43, 
      35.321}, {26.815, 37.467}, {30.26, 39.778}, {33.621, 
      42.335}, {36.717, 45.221}, {39.345, 48.519}, {41.283, 
      52.241}, {42.531, 56.248}, {43.225, 60.419}, {43.504, 
      64.676}, {43.498, 68.943}, {43.326, 73.161}, {43.041, 
      77.315}, {42.596, 81.413}, {41.939, 85.448}, {41.013, 
      89.406}, {39.764, 93.271}, {38.148, 97.009}, {36.21, 
      100.596}, {34.046, 104.05}, {31.742, 107.4}, {29.382, 
      110.677}, {27.033, 113.917}, {24.704, 117.143}, {22.382, 
      120.358}, {20.059, 123.556}, {17.73, 126.733}, {15.401, 
      129.878}, {13.121, 133.024}, {10.946, 136.238}, {8.941, 
      139.568}, {7.367, 142.93}, {6.787, 146.14}, {7.54, 
      149.118}, {9.482, 151.065}, {12.446, 151.589}, {15.809, 
      150.879}, {19.306, 149.43}, {23.039, 147.949}, {26.851, 
      146.622}, {30.688, 145.417}, {34.553, 144.319}, {38.448, 
      143.331}, {42.365, 142.458}, {46.293, 141.691}, {50.222, 
      140.998}, {54.164, 140.347}, {58.154, 139.76}, {62.213, 
      139.357}, {66.29, 139.256}, {70.297, 139.361}, {74.205, 
      139.444}}]}]

We use the following structures: A list activePatches =={{patch, crossLinks},...}. A list of generated primitivePatches=={freePatch,...}.where a freePatch has no crossLinks.

The routine firstPatchLink finds the first link that intersects a curve. It either returns the link positions on the curve or None if there is no intersecting link.

firstPatchLink[patch : {_, _}] :=
 Module[{curve, patchLinks, linkPositions, work},
  {curve, patchLinks} = patch;
  linkPositions = 
   Flatten /@ 
    Map[Flatten[Sort[Position[curve, #] & /@ #], 1] &, 
     patchLinks, {1}];
  linkPositions = Cases[linkPositions, {_, _}, \[Infinity]];
  If[Length[linkPositions] > 0, First[linkPositions], None]]

The routine dividePatch uses the link to divide the curve into two curves that have a new set of links without the one just used.

dividePatch[curve_, linkPositions_, crossLinks_] :=
  Module[{curveLength = Length[curve], pos1, pos2, curve1, curve2, 
    newCrossLinks},
   {pos1, pos2} = linkPositions;
   curve1 = 
    Join[curve[[1 ;; pos1]], curve[[{pos1, pos2}]], 
     curve[[pos2 ;; curveLength]]];
   curve2 = Join[curve[[pos1 ;; pos2]], curve[[{pos2, pos1}]]];
   newCrossLinks = 
    crossLinks /. {curve[[pos1]], curve[[pos2]]} -> Sequence[];
   {{curve1, newCrossLinks}, {curve2, newCrossLinks}}
   ];

The main recursive routine, processPatches, spins off primitive patches or keeps dividing curves until they are all primitive.

processPatches[] :=
 Module[{patch, curve, crossLinks, link},
  If[ Length[activePatches] == 0, Return[]];
  patch = First[activePatches];
  {curve, crossLinks} = patch;
  link = firstPatchLink[patch];
  If[link === None,
   AppendTo[primitivePatches, curve]; 
   activePatches = Drop[activePatches, 1],
   activePatches = 
    Join[dividePatch[curve, link, crossLinks], 
     Drop[activePatches, 1]]];
  processPatches[]
  ]

Finally we initialize activePatches and primitivePatches and calculate.

curve = First[Drop[initialGraphics[[1]], 4] /. Line -> Identity];
crossLinks = Take[initialGraphics[[1]], 4] /. Line -> Identity;
activePatches = {{curve, crossLinks}};
primitivePatches = {};
processPatches[];
GraphicsRow@(Graphics[Line@#, ImageSize -> 100] & /@ primitivePatches)

enter image description here

Nice question! Because devising parts is a topological operation I doubt you can find something simpler than you suggested (I still hope though). What I will show is just an much more elaborate exercise in finding an alternative.

In image processing one can find basins at each regional minimum in image using WatershedComponents:

wsc = WatershedComponents[Dilation[ColorNegate[Binarize[g]], 1]];
Colorize[wsc]

enter image description here

You see your fragments right away and the are just particular integers in the matrix:

Union[Flatten[wsc]]

{0, 1, 2, 3, 4, 5, 6}

Extract them as:

frag = Table[Colorize[Map[KroneckerDelta[k, #] &, wsc, {2}]], {k, 0, 6}]

enter image description here

with 0 being the contour and 6 the background. But that's images now, geometry of the line is lost. To get it back you could try:

Graphics[Line[PixelValuePositions[EdgeDetect[frag[[-2]]], 1]]]

enter image description here

cool but useless ;-) So we need to order points:

Graphics[Line[#[[FindShortestTour[#][[2]]]] &@ PixelValuePositions[Thinning[EdgeDetect[frag[[-2]]]], 1]]]

enter image description here

To get a smoother line one just need to increase image resolution. All in all too complicated ;-)

POSTED BY: Vitaliy Kaurov
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract