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

Question

给定一个形状不确定的多边形，并且您知道从哪条路径开始，我需要使用起始路径作为指导将这些多边形（以 SVG 格式定义）分割成 n 个形状。

这有点难以解释，但想一想体育场内的座位区及其排列：

处理矩形时，似乎并不太难。我坚持的是如何用不规则形状的多边形来做。一个通用的解决方案是最好的，特别是如果它可以使用曲线，但我可以看到这只会使事情复杂化。

我应该从什么特定算法开始学习？我已经开始研究多边形三角剖分以及如何使用耳朵剪裁方法以单调方式分解这些多边形，但我的头开始在这里旋转。

PS：不确定它是否超级重要，但这些多边形是在 SVG 中定义的。

Answer 1

这是一种非常幼稚的方法：根据您需要的除法数/'rows'，简单地在顶部和底部顶点（从左到右排序）之间进行插值。

我已经使用 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 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 或事先 Illustrator。

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

How to subdivide irregular polygons in SVG

svg

graphics

computational-geometry