javascript - 如何在给定 JavaScript 中的 Schläfli 符号的庞加莱圆盘上绘制双曲曲面分割？

Question

我对由 @TilingBot 生成的双曲曲面分割很感兴趣.为了进一步缩小范围，我希望能够构建一些 Uniform Tilings on the Hyperbolic Plane ，例如:

我找到的最接近的答案来自 Math SE并推荐这 3 个资源:

1. Ajit Datar's master's thesis
2. David Joyce's Hyperbolic Tessellations applet
3. 和大卫乔伊斯的对应Java source code .

这里我已经将 Java 翻译成 JavaScript(并保留了注释)，并尝试绘制中心形状:

class Polygon {
  constructor(n) {
    this.n = n // the number of sides
    this.v = new Array(n) // the list of vertices
  }

  static constructCenterPolygon(n, k, { quasiregular = false }) {
    // Initialize P as the center polygon in an n-k regular or quasiregular tiling.
    // Let ABC be a triangle in a regular (n,k0-tiling, where
    //    A is the center of an n-gon (also center of the disk),
    //    B is a vertex of the n-gon, and
    //    C is the midpoint of a side of the n-gon adjacent to B.
    const angleA = Math.PI / n
    const angleB = Math.PI / k
    const angleC = Math.PI / 2.0

    // For a regular tiling, we need to compute the distance s from A to B.
    let sinA = Math.sin(angleA)
    let sinB = Math.sin(angleB)
    let s = Math.sin(angleC - angleB - angleA)
      / Math.sqrt(1.0 - (sinB * sinB) - (sinA * sinA))

    // But for a quasiregular tiling, we need the distance s from A to C.

    if (quasiregular) {
      s = ((s * s) + 1.0) /  (2.0 * s * Math.cos(angleA))
      s = s - Math.sqrt((s * s) - 1.0)
    }

    // Now determine the coordinates of the n vertices of the n-gon.
    // They're all at distance s from the center of the Poincare disk.
    const polygon = new Polygon(n)
    for (let i = 0; i < n; ++i) {
      const something = (3 + 2 * i) * angleA
      const x = s * Math.cos(something)
      const y = s * Math.sin(something)
      const point = new Point(x, y)
      polygon.v[i] = point
    }
    return polygon
  }

  getScreenCoordinateArrays(dimension) {
    // first construct a list of all the points
    let pointList = null
    for (let i = 0; i < this.n; ++i) {
      const next = (i + 1) % this.n
      const line = new Line(this.v[i], this.v[next])
      pointList = line.appendScreenCoordinates(pointList, dimension)
    }

    // determine its length
    let _in = 0
    for (let pl = pointList; pl != null; pl = pl.link) {
      _in++
    }

    // now store the coordinates
    let pl = pointList
    let ix = []
    let iy = []

    for (let i = 0; i < _in; i++) {
      ix[i] = pl.x
      iy[i] = pl.y
      pl = pl.link
    }

    return { size: _in, ix, iy }
  }
}

class Line {
  constructor(a, b) {
    this.a = a // this is the line between a and b
    this.b = b

    // if it's a circle, then a center C and radius r are needed
    this.c = null
    this.r = null

    // if it's is a straight line, then a point P and a direction D
    // are needed
    this.p = null
    this.d = null

    // first determine if its a line or a circle
    let den = (a.x * b.y) - (b.x * a.y)

    this.isStraight = (Math.abs(den) < 1.0e-14)

    if (this.isStraight) {
      this.p = a; // a point on the line
      // find a unit vector D in the direction of the line
      den = Math.sqrt(
        (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)
      )
      let x = (b.x - a.x) / den
      let y = (b.y - a.y) / den
      this.d = new Point(x, y)
    } else { // it's a circle
      // find the center of the circle thru these points}
      let s1 = (1.0 + (a.x * a.x) + (a.y * a.y)) / 2.0
      let s2 = (1.0 + (b.x * b.x) + (b.y * b.y)) / 2.0
      let x = (s1 * b.y - s2 * a.y) / den
      let y = (a.x * s2 - b.x * s1) / den
      this.c = new Point (x, y)
      this.r = Math.sqrt(
          (this.c.x * this.c.x)
        + (this.c.y * this.c.y)
        - 1.0
      )
    }
  }

  // Reflect the point R thru the this line
  // to get Q the returned point
  reflect(point) {
    reflection = new Point()
    if (this.isStraight) {
      const factor = 2.0 * (
        (point.x - this.p.x)
          * this.d.x
          + (point.y - this.p.y)
          * this.d.y
        )
      reflection.x = 2.0 * this.p.x + factor * this.d.x - point.x
      reflection.y = 2.0 * this.p.y + factor * this.d.y - point.y
    } else {  // it's a circle
      const factor = (r * r) / (
          (point.x - this.c.x) * (point.x - this.c.x)
        + (point.y - this.c.y) * (point.y - this.c.y)
      )
      reflection.x = this.c.x + factor * (point.x - this.c.x)
      reflection.y = this.c.y + factor * (point.y - this.c.y)
    }
    return reflection
  }

  // append screen coordinates to the list in order to draw the line
  appendScreenCoordinates(list, dimension) {
    let x_center = dimension.width / 2
    let y_center = dimension.height / 2
    let radius = Math.min(x_center, y_center)

    let x = Math.round((this.a.x * radius) + x_center)
    let y = Math.round((this.a.y * radius) + y_center)

    const conditionA = (list == null || x != list.x || y != list.y)
    const conditionB = !isNaN(x) && !isNaN(y)

    if (conditionA && conditionB) {
      list = new ScreenCoordinateList(list, x, y)
    }

    if (this.isStraight) { // go directly to terminal point B
      x = Math.round((this.b.x * radius) + x_center)
      y = Math.round((this.b.y * radius) + y_center)
      const conditionC = x != list.x || y != list.y
      if (conditionC) {
        list = new ScreenCoordinateList(list, x, y)
      }
    } else { // its an arc of a circle
      // determine starting and ending angles
      let alpha = Math.atan2(
        this.a.y - this.c.y,
        this.a.x - this.c.x
      )

      let beta  = Math.atan2(
        this.b.y - this.c.y,
        this.b.x - this.c.x
      )

      if (Math.abs(beta - alpha) > Math.PI) {
        if (beta < alpha) {
          beta += (2.0 * Math.PI)
        }
      } else {
        alpha += (2.0 * Math.PI)
      }

      const curve = new CircularCurve(this.c.x, this.c.y, this.r)
      curve.setScreen(x_center, y_center, radius)

      list = curve.interpolate(list, alpha, beta)
    }

    return list;
  }

  draw(dimensions) {
    let x_center = dimensions.width / 2
    let y_center = dimensions.height / 2
    let radius = Math.min(x_center, y_center)
    // yet to write...
  }
}

class CircularCurve {
  // The circle in the complex plane
  constructor(x, y, r) {
    // coordinates of the center of the circle
    this.x = x
    this.y = y
    this.r = r // radius of the circle
  }

  // Add to the list the coordinates of the curve (f(t),g(t)) for t
  // between a and b. It is assumed that the point (f(a),g(a)) is
  // already on the list. Enough points will be interpolated between a
  // and b so that the approximating polygon looks like the curve.
  // The last point to be included will be (f(b),g(b)).}
  interpolate(list, a, b) {
    // first try bending it at the midpoint
    let result = this.bent(a, b, (a + b) / 2.0, list)
    if (result != list) return result

    // now try 4 random points
    for (let i = 0; i < 4; ++i) {
      const t = Math.random()
      result = this.bent(a, b, (t * a) + ((1.0 - t) * b), list)
      if (result != list) return result
    }

    // it's a straight line
    const b1 = this.xScreen(b)
    const b2 = this.yScreen(b)
    const conditionA = (list.x != b1 || list.y != b2)
    const conditionB = !isNaN(b1) && !isNaN(b2)

    if (conditionA && conditionB) {
      list = new ScreenCoordinateList(list, b1, b2)
    }

    return list // it's a straight line
  }

  // Determine if a curve between t=a and t=b is bent at t=c.
  // Say it is if C is outside a narrow ellipse.
  // If it is bent there, subdivide the interval.
  bent(a, b, c, list) {
    const a1 = this.xScreen(a)
    const a2 = this.yScreen(a)
    const b1 = this.xScreen(b)
    const b2 = this.yScreen(b)
    const c1 = this.xScreen(c)
    const c2 = this.yScreen(c)

    const excess =
        Math.sqrt((a1 - c1) * (a1 - c1) + (a2 - c2) * (a2 - c2))
      + Math.sqrt((b1 - c1) * (b1 - c1) + (b2 - c2) * (b2 - c2))
      - Math.sqrt((a1 - b1) * (a1 - b1) + (a2 - b2) * (a2 - b2))

    if (excess > 0.03) {
      list = this.interpolate(list, a, c)
      list = this.interpolate(list, c, b)
    }

    return list
  }

  setScreen(x_center, y_center, radius) {
    // screen coordinates
    this.x_center = x_center // x-coordinate of the origin
    this.y_center = y_center // y-coordinate of the origin
    this.radius = radius // distance to unit circle
  }

  xScreen(t) {
    return Math.round(this.x_center + (this.radius * this.getX(t)))
  }

  yScreen(t) {
    return Math.round(this.y_center + (this.radius * this.getY(t)))
  }

  getX(t) {
    return this.x + (this.r * Math.cos(t))
  }

  getY(t) {
    return this.y + (this.r * Math.sin(t))
  }
}

class ScreenCoordinateList {
  constructor(link, x, y) {
    // link to next one
    this.link = link
    // coordinate pair
    this.x = x
    this.y = y
  }
}

class Point {
  constructor(x, y) {
    this.x = x
    this.y = y
  }
}

body {
  padding: 50px;
  display: flex;
  justify-content: center;
  align-items: center;
}

<canvas width="1000" height="1000"></canvas>
<script>
  window.addEventListener('load', draw)

  function draw() {
    const canvas = document.querySelector('canvas')
    const ctx = canvas.getContext('2d')

    const polygon = Polygon.constructCenterPolygon(7, 3, {quasiregular: true
    })

    const { size, ix, iy } = polygon.getScreenCoordinateArrays({
      width: 100,
      height: 100
    })

    ctx.fillStyle = '#af77e7'
    ctx.beginPath()
    ctx.moveTo(ix[0], iy[0])
    let i = 1
    while (i < size) {
      ctx.lineTo(ix[i], iy[i])
      i++
    }
    ctx.closePath()
    ctx.fill()
  }
</script>

对于这个 n，我怎样才能同时绘制中心形状和从中心向外绘制 1 或两层(或者 {7,3} 从中心向外绘制层，如果它很简单的话) HTML5 Canvas 上 JavaScript 中的双曲线曲面分割？

我目前得到这个:

理想情况下，我想绘制上面附加的第一个双曲线镶嵌图像，但如果考虑到我目前从 David Joyce 的作品中得到的东西，这太复杂了，那么第一步是计算中心多边形并用填充和线条正确吗？

Answer 1

我建议您使用描边而不是填充，这样您就可以看到多边形给您带来的效果。

运行下面的代码，以便您可以看到不同之处...
现在，将该结果与您的图像进行比较，它看起来与您想要的完全不同

class Polygon {
  constructor(n) {
    this.n = n // the number of sides
    this.v = new Array(n) // the list of vertices
  }

  static constructCenterPolygon(n, k, { quasiregular = false }) {
    // Initialize P as the center polygon in an n-k regular or quasiregular tiling.
    // Let ABC be a triangle in a regular (n,k0-tiling, where
    //    A is the center of an n-gon (also center of the disk),
    //    B is a vertex of the n-gon, and
    //    C is the midpoint of a side of the n-gon adjacent to B.
    const angleA = Math.PI / n
    const angleB = Math.PI / k
    const angleC = Math.PI / 2.0

    // For a regular tiling, we need to compute the distance s from A to B.
    let sinA = Math.sin(angleA)
    let sinB = Math.sin(angleB)
    let s = Math.sin(angleC - angleB - angleA)
      / Math.sqrt(1.0 - (sinB * sinB) - (sinA * sinA))

    // But for a quasiregular tiling, we need the distance s from A to C.

    if (quasiregular) {
      s = ((s * s) + 1.0) /  (2.0 * s * Math.cos(angleA))
      s = s - Math.sqrt((s * s) - 1.0)
    }

    // Now determine the coordinates of the n vertices of the n-gon.
    // They're all at distance s from the center of the Poincare disk.
    const polygon = new Polygon(n)
    for (let i = 0; i < n; ++i) {
      const something = (3 + 2 * i) * angleA
      const x = s * Math.cos(something)
      const y = s * Math.sin(something)
      const point = new Point(x, y)
      polygon.v[i] = point
    }
    return polygon
  }

  getScreenCoordinateArrays(dimension) {
    // first construct a list of all the points
    let pointList = null
    for (let i = 0; i < this.n; ++i) {
      const next = (i + 1) % this.n
      const line = new Line(this.v[i], this.v[next])
      pointList = line.appendScreenCoordinates(pointList, dimension)
    }

    // determine its length
    let _in = 0
    for (let pl = pointList; pl != null; pl = pl.link) {
      _in++
    }

    // now store the coordinates
    let pl = pointList
    let ix = []
    let iy = []

    for (let i = 0; i < _in; i++) {
      ix[i] = pl.x
      iy[i] = pl.y
      pl = pl.link
    }

    return { size: _in, ix, iy }
  }
}

class Line {
  constructor(a, b) {
    this.a = a // this is the line between a and b
    this.b = b

    // if it's a circle, then a center C and radius r are needed
    this.c = null
    this.r = null

    // if it's is a straight line, then a point P and a direction D
    // are needed
    this.p = null
    this.d = null

    // first determine if its a line or a circle
    let den = (a.x * b.y) - (b.x * a.y)

    this.isStraight = (Math.abs(den) < 1.0e-14)

    if (this.isStraight) {
      this.p = a; // a point on the line
      // find a unit vector D in the direction of the line
      den = Math.sqrt(
        (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)
      )
      let x = (b.x - a.x) / den
      let y = (b.y - a.y) / den
      this.d = new Point(x, y)
    } else { // it's a circle
      // find the center of the circle thru these points}
      let s1 = (1.0 + (a.x * a.x) + (a.y * a.y)) / 2.0
      let s2 = (1.0 + (b.x * b.x) + (b.y * b.y)) / 2.0
      let x = (s1 * b.y - s2 * a.y) / den
      let y = (a.x * s2 - b.x * s1) / den
      this.c = new Point (x, y)
      this.r = Math.sqrt(
          (this.c.x * this.c.x)
        + (this.c.y * this.c.y)
        - 1.0
      )
    }
  }

  // Reflect the point R thru the this line
  // to get Q the returned point
  reflect(point) {
    reflection = new Point()
    if (this.isStraight) {
      const factor = 2.0 * (
        (point.x - this.p.x)
          * this.d.x
          + (point.y - this.p.y)
          * this.d.y
        )
      reflection.x = 2.0 * this.p.x + factor * this.d.x - point.x
      reflection.y = 2.0 * this.p.y + factor * this.d.y - point.y
    } else {  // it's a circle
      const factor = (r * r) / (
          (point.x - this.c.x) * (point.x - this.c.x)
        + (point.y - this.c.y) * (point.y - this.c.y)
      )
      reflection.x = this.c.x + factor * (point.x - this.c.x)
      reflection.y = this.c.y + factor * (point.y - this.c.y)
    }
    return reflection
  }

  // append screen coordinates to the list in order to draw the line
  appendScreenCoordinates(list, dimension) {
    let x_center = dimension.width / 2
    let y_center = dimension.height / 2
    let radius = Math.min(x_center, y_center)

    let x = Math.round((this.a.x * radius) + x_center)
    let y = Math.round((this.a.y * radius) + y_center)

    const conditionA = (list == null || x != list.x || y != list.y)
    const conditionB = !isNaN(x) && !isNaN(y)

    if (conditionA && conditionB) {
      list = new ScreenCoordinateList(list, x, y)
    }

    if (this.isStraight) { // go directly to terminal point B
      x = Math.round((this.b.x * radius) + x_center)
      y = Math.round((this.b.y * radius) + y_center)
      const conditionC = x != list.x || y != list.y
      if (conditionC) {
        list = new ScreenCoordinateList(list, x, y)
      }
    } else { // its an arc of a circle
      // determine starting and ending angles
      let alpha = Math.atan2(
        this.a.y - this.c.y,
        this.a.x - this.c.x
      )

      let beta  = Math.atan2(
        this.b.y - this.c.y,
        this.b.x - this.c.x
      )

      if (Math.abs(beta - alpha) > Math.PI) {
        if (beta < alpha) {
          beta += (2.0 * Math.PI)
        }
      } else {
        alpha += (2.0 * Math.PI)
      }

      const curve = new CircularCurve(this.c.x, this.c.y, this.r)
      curve.setScreen(x_center, y_center, radius)

      list = curve.interpolate(list, alpha, beta)
    }

    return list;
  }

  draw(dimensions) {
    let x_center = dimensions.width / 2
    let y_center = dimensions.height / 2
    let radius = Math.min(x_center, y_center)
    // yet to write...
  }
}

class CircularCurve {
  // The circle in the complex plane
  constructor(x, y, r) {
    // coordinates of the center of the circle
    this.x = x
    this.y = y
    this.r = r // radius of the circle
  }

  // Add to the list the coordinates of the curve (f(t),g(t)) for t
  // between a and b. It is assumed that the point (f(a),g(a)) is
  // already on the list. Enough points will be interpolated between a
  // and b so that the approximating polygon looks like the curve.
  // The last point to be included will be (f(b),g(b)).}
  interpolate(list, a, b) {
    // first try bending it at the midpoint
    let result = this.bent(a, b, (a + b) / 2.0, list)
    if (result != list) return result

    // now try 4 random points
    for (let i = 0; i < 4; ++i) {
      const t = Math.random()
      result = this.bent(a, b, (t * a) + ((1.0 - t) * b), list)
      if (result != list) return result
    }

    // it's a straight line
    const b1 = this.xScreen(b)
    const b2 = this.yScreen(b)
    const conditionA = (list.x != b1 || list.y != b2)
    const conditionB = !isNaN(b1) && !isNaN(b2)

    if (conditionA && conditionB) {
      list = new ScreenCoordinateList(list, b1, b2)
    }

    return list // it's a straight line
  }

  // Determine if a curve between t=a and t=b is bent at t=c.
  // Say it is if C is outside a narrow ellipse.
  // If it is bent there, subdivide the interval.
  bent(a, b, c, list) {
    const a1 = this.xScreen(a)
    const a2 = this.yScreen(a)
    const b1 = this.xScreen(b)
    const b2 = this.yScreen(b)
    const c1 = this.xScreen(c)
    const c2 = this.yScreen(c)

    const excess =
        Math.sqrt((a1 - c1) * (a1 - c1) + (a2 - c2) * (a2 - c2))
      + Math.sqrt((b1 - c1) * (b1 - c1) + (b2 - c2) * (b2 - c2))
      - Math.sqrt((a1 - b1) * (a1 - b1) + (a2 - b2) * (a2 - b2))

    if (excess > 0.03) {
      list = this.interpolate(list, a, c)
      list = this.interpolate(list, c, b)
    }

    return list
  }

  setScreen(x_center, y_center, radius) {
    // screen coordinates
    this.x_center = x_center // x-coordinate of the origin
    this.y_center = y_center // y-coordinate of the origin
    this.radius = radius // distance to unit circle
  }

  xScreen(t) {
    return Math.round(this.x_center + (this.radius * this.getX(t)))
  }

  yScreen(t) {
    return Math.round(this.y_center + (this.radius * this.getY(t)))
  }

  getX(t) {
    return this.x + (this.r * Math.cos(t))
  }

  getY(t) {
    return this.y + (this.r * Math.sin(t))
  }
}

class ScreenCoordinateList {
  constructor(link, x, y) {
    // link to next one
    this.link = link
    // coordinate pair
    this.x = x
    this.y = y
  }
}

class Point {
  constructor(x, y) {
    this.x = x
    this.y = y
  }
}

<canvas width="400" height="400"></canvas>
<script>
  window.addEventListener('load', draw)

  function draw() {
    const canvas = document.querySelector('canvas')
    const ctx = canvas.getContext('2d')
    ctx.translate(150, 150);

    const polygon = Polygon.constructCenterPolygon(7, 3, {quasiregular: true})
    const { size, ix, iy } = polygon.getScreenCoordinateArrays({width: 80, height: 80})
    
    for (i = 0; i < size; i++) {
      ctx.lineTo(ix[i], iy[i])
    }    
    ctx.stroke()
  }
</script>

---

但是如果您要解决的问题是:

what would be the first step, of computing the center polygon and drawing it

那个中心多边形看起来像一个等边多边形，代码可以更简单，见下文

const canvas = document.getElementById('c');
const ctx = canvas.getContext('2d');

function drawEquilateralPolygon(x, y, lines, size) {
  ctx.beginPath();
  for (angle = 0; angle < 360; angle += 360 / lines) {
    a = angle * Math.PI / 180
    ctx.lineTo(x + size * Math.sin(a), y + size * Math.cos(a));
  }
  ctx.lineTo(x + size * Math.sin(0), y + size * Math.cos(0));
  ctx.stroke();
}

drawEquilateralPolygon(20, 20, 5, 20)
drawEquilateralPolygon(60, 50, 6, 30)
drawEquilateralPolygon(130, 70, 7, 40)
drawEquilateralPolygon(200, 35, 8, 30)
drawEquilateralPolygon(200, 35, 9, 25)
drawEquilateralPolygon(200, 35, 10, 35)

<canvas id="c"></canvas>