How to subdivide irregular polygons in SVG

Question

Given a polygon of indeterminate shape, and given you know which path(s) to start from, I need to slice up these polygons (defined in SVG format) into n shapes using the start-path as a guide.

It's kind of hard to explain, but think seat sections and their rows in a stadium: sections cut into rows

When dealing with rectangles, it doesn't seem too difficult. What I'm stuck on is how to do it with an irregularly shaped polygon. A universal solution would be best, especially if it can work with curves but I can see how that would only complicate matters.

Is there any specific algorithm that I should start my studies with? I've started digging into polygon triangulation and how to use ear clipping methods to decompose these polygons in a monotone fashion, but my head is starting to spin here.

PS: Not sure if it's super important, but these polygons are defined in SVG.

What are the paths and their starting points for the two example polygons? Will the polygons always be symmetric? — Peter O., Jul 09 '15 at 22:14
Symmetry: no. Our metadata will hold onto which side(s) of the polygon determine the "front row" so we know what the starting point is. — mmmeff, Jul 09 '15 at 22:28
Is the top path a scaled version of the bottom start path? If not, the problem is more challenging. — Joseph O'Rourke, Jul 09 '15 at 22:54
see [polygon spiral filling](http://stackoverflow.com/a/31013424/2521214) it is similar problem. just create stroke line with `i*w` distance from the leading path polyline and then construct the polygons. `w` is the layer thickness and `i=0,1,2,3,...` — Spektre, Jul 10 '15 at 12:16
Do you want your path to be always the same, moved in steps. Or do you want your path to shrink/increase depending on the slope of its lines? — Daniel Möller, Jul 10 '15 at 18:08

score 1 · Accepted Answer · answered Jul 10 '15 at 19:26

Here is a very naive approach: simply interpolating between top and bottom vertices (that are sorted left to right) based on how many division/'rows' you need.

I've done a quick test using Processing:

PShape svg,shape;

int divisions = 3;

ArrayList<PVector> top = new ArrayList<PVector>();
ArrayList<PVector> bottom = new ArrayList<PVector>();

int numVerts;
int ptSize = 5;

void setup(){
  svg = loadShape("shape.svg");
  size((int)svg.width,(int)svg.height);
  shape = svg.getChild(0);
  //find top and bottom vertices
  numVerts = shape.getVertexCount();
  float minY = height,maxY = 0;
  for(int i = 0 ; i < numVerts; i++){
    PVector v = shape.getVertex(i);
    if(v.x < minY) minY = v.y;
    if(v.y > maxY) maxY = v.y;
  } 
  float yThresh = (maxY-minY) * .25;//1/4 of height as top/bottom thresh
  //store vertices belonging to top and bottom based on min and max y values and threshold
  for(int i = 0 ; i < numVerts; i++){
    PVector v = shape.getVertex(i);
    if(v.y <= minY+yThresh) top.add(v);
    if(v.y >= maxY-yThresh) bottom.add(v);
  }
  //manual left to right sorting, this needs to be implemented properly
  PVector last = bottom.get(bottom.size()-1);
  PVector first = bottom.get(0);
  bottom.set(0,last);
  bottom.set(bottom.size()-1,first);
  //assumptions is top is a list of the top vertices of the contour sorted left to right
  //and simillary bottom is a list of bottom vertices, sorted left to right
}

void draw(){
  background(255);
  shape(shape,0,0);
  //visualize top/bottom vertices
  stroke(0,192,0);
  for(PVector v : top) ellipse(v.x,v.y,ptSize,ptSize);
  stroke(192,0,0);
  for(PVector v : bottom) ellipse(v.x,v.y,ptSize,ptSize);
  stroke(0,0,255);

  //compute interpolation step value
  float lerpStep = 1.0/(divisions+1);

  //for each division
  for(int i = 0 ; i < divisions; i++){

    //loop through contour vertices top to bottom
    for(int j = 0 ; j < top.size(); j++){
      //get top and bottom vertices
      PVector vTop = top.get(j);
      PVector vBottom = bottom.get(j);
      //interpolate between them
      PVector vLerp = PVector.lerp(vTop,vBottom, lerpStep * (i+1));
      //draw on screen
      ellipse(vLerp.x,vLerp.y,ptSize,ptSize);
    }

  }
}

void keyPressed(){
  if(keyCode == UP) divisions++;
  if(keyCode == DOWN) divisions--;
}

And here is shape.svg:

<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg version="1.1" id="Layer_2" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" x="0px" y="0px"
     width="960px" height="560px" viewBox="0 0 960 560" enable-background="new 0 0 960 560" xml:space="preserve">
<polygon fill="#D8D8D8" points="279,100 479,60 681,100 641,501 480,482 322,501 "/>
</svg>

Here is a preview, with top vertices marked green, bottom red and interpolated vertices as blue:

SVG vertex interpolation

As @Joseph O'Rourke mentions, the problem is more challenging if the bottom and bottom paths aren't similar (same number of vertices and left to right order I guess). In this case it should be possible to implement a blending algorithm (like this one for example). If you're already playing with various shape in SVG format, you should be able to test if blending solves your problem by trying it in Inkscape or Illustrator beforehand.

Brilliant, thank you. I now have everything I need to get moving on a full-fledged solution. — mmmeff, Jul 14 '15 at 18:06
Glad that helps! Keep in mind the limitations I've mentioned: my naive approach always assumes a top and bottom path with equal number of vertices. — George Profenza, Jul 15 '15 at 00:44

How to subdivide irregular polygons in SVG

1 Answers1