如何在SVG中细分不规则多边形

Question

给定一个不确定形状的多边形，并且你知道从哪个路径开始，我需要使用起始路径作为指引，将这些多边形（以SVG格式定义）切成n个形状。很难解释，但是想象一下体育场的座位区域和它们的排列方式： 对于矩形，似乎并不太困难。我卡在如何处理不规则多边形上了。最好有通用的解决方案，特别是如果可以处理曲线，但我可以看出这只会让事情变得更加复杂。是否有任何特定的算法我应该学习？我已经开始深入研究多边形三角剖分以及如何使用耳剪切方法以单调的方式分解这些多边形，但我的头已经开始晕了。PS：不确定是否非常重要，但这些多边形是在SVG中定义的。

- mmmeff

---

这两个示例多边形的路径和起始点是什么？这些多边形是否总是对称的？ - Peter O.

对称性：无。 我们的元数据将保存多边形哪一侧确定“前排”，以便我们知道起始点在哪里。 - mmmeff

顶部路径是否是底部起始路径的缩放版本？如果不是，问题就更具挑战性。 - Joseph O'Rourke

请参考polygon spiral filling。这是一个类似的问题。只需从主路径折线创建i*w距离的描边线，然后构建多边形即可。其中，w为图层厚度，i=0,1,2,3,...。 - Spektre

你想让你的路径始终保持相同，一步一步地移动吗？还是你想让你的路径随着其线条的斜率而收缩/增长？ - Daniel Möller

Answer 1

这里有一个非常朴素的方法：根据需要划分的行数，在按从左到右排序的顶部和底部顶点之间进行插值。

我已经使用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--;
}

这里是 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>

这里是一个预览，顶部的顶点标记为绿色，底部为红色，插值的顶点为蓝色：

正如@Joseph O'Rourke所提到的，如果底部和底部路径不相似（我猜想是顶点数量和从左到右的顺序不同），那么问题会更具挑战性。在这种情况下，可以实现混合算法（例如this one）。如果您已经在SVG格式中玩弄各种形状，那么您应该能够通过在Inkscape或Illustrator中先尝试它来测试混合是否解决了您的问题。

- George Profenza

---

太好了，谢谢。现在我已经拥有了所有必要的东西，可以开始着手完整的解决方案了。 - mmmeff

很高兴能够帮助！请记住我所提到的限制：我的天真方法总是假设顶部和底部路径具有相等数量的顶点。 - George Profenza