CODEWITHSUNDEEP
svggraphicscomputational-geometry
mmmeff
mmmeff

Reputation: 1033

How to subdivide irregular polygons in SVG

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.

Upvotes: 3

Views: 451

Answers (1)

George Profenza
George Profenza

Reputation: 51847

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.

Upvotes: 1

Related Questions