How to subdivide irregular polygons in SVG
Given a polygon of undefined shape, and if you know which path (s) to start with, I need to cut these polygons (defined in SVG format) into n shapes using the starting path as a guide.
Difficult to explain, but think about the seating sections and rows in the stadium:
When working with rectangles, this doesn't seem too difficult. What I'm stuck with is doing it with an irregularly shaped polygon. A one-size-fits-all solution would be better, especially if it can handle curves, but I can see how it only complicates things.
Is there a specific algorithm with which I should start my studies? I started digging into polygon triangulation and how to use ear clipping techniques to decompose these polygons monotonically, but my head starts spinning here.
PS: Not sure if this is super important, but these polygons are defined in SVG.
source to share
Here's a very naive approach: just interpolate the top and bottom vertices (which are sorted from left to right) depending on how many sections / lines you need.
I made 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's a preview with the top vertices marked in green, the bottom red, and interpolated vertices as blue:
As @Joseph O'Rourke mentions, the problem is more complicated if the bottom and bottom paths are not similar (same number of vertices and left to right, I guess). In this case, it should be possible to implement a mixing algorithm (like this one ). If you are already playing with different shapes in SVG format, you should be able to check if blending solves your problem by trying it in Inkscape or Illustrator beforehand.
source to share