计算 space 中圆弧边界坐标的公式

formula to calculate bounding coordinates of an arc in space

我有 2 条线相交于已知坐标的点 - x1,y1 - x2,y2 - x3,y3

据此,我计算了直线之间给定半径的圆弧。所以我现在知道 - 2 个圆弧端点 x4、y4 和 x5、y5 - 圆弧中心点 Cx,Cy - 圆弧半径 r - 相对于极坐标 X 轴的起始角和结束角,即线之间的角度。

我想创建一个公式来计算圆弧的最大和最小 X 和 Y 值。 IE。包围圆弧的框的坐标。

在下面的例子中我可以找出最小X值和最大Y值,它们是已知值,但我不确定如何计算最大X和最小Y。

在其他情况下,弧可以是任何坐标,因此已知的最小值和最大值会发生变化。

我知道如何计算沿给定角度或间隔的圆弧上的点,但不知道特定方向上的最大值和最小值,在本例中为 X 轴和 Y 轴。

我打算在编程中使用公式。

先找出端点在哪个象限。

如果他们在同一个象限,那么圆弧是单调的,边界框很容易。

否则,每次穿过象限时,您都会得到一个极值点,即水平或垂直直径的端点。

为此编写算法并不太复杂,尽管可能需要考虑多种情​​况,包括弧的方向。

我有一个算法解决方案,您可以尝试使用。它涉及扫描圆弧上已知起点和终点之间的极坐标 space,并跟踪最小值和最大值。

算法的基本步骤如下:

  • 将圆弧上的两个输入(笛卡尔)点转换为极坐标
  • 在极坐标下沿圆弧逆时针走
  • 在每一步中,转换回笛卡尔坐标并检查 minima/maxima

我利用以下两个方程将极坐标转换为笛卡尔坐标:

x = r*cosθ
y = r*sinθ

这是一个将笛卡尔坐标转换为极角的方程式:

θ = tan-1(y / x)

你需要注意这个等式中可能被零除的部分。无穷大的反正切是 Pi / 2 弧度。

此解决方案假定圆弧从低弧度值开始并逆时针穿过高弧度值。

// Input Parameters:
// (x1, y1) first point on arc
// (x2, y2) second point on arc
// (xc, yc) center point of circle

public void findMinMax(double x1, double x2, double y1, double y2, double xc, double yc) {
    double xMin, yMin, xMax, yMax;
    // compute radius of circle
    double radius = Math.sqrt(Math.pow((xc - x1), 2) + Math.pow((yc - y1), 2));

    // compute starting and ending points in polar coordinates
    double t1 = 0.0;
    if (x1 == 0.0) {
        t1 = Math.PI / 2;
    }
    else {
        t1 = Math.atan(y1 / x1);
    }

    double t2 = 0.0;
    if (x2 == 0.0) {
        t2 = Math.PI / 2;
    }
    else {
        t2 = Math.atan(y2 / x2);
    }

    // determine starting and ending polar angles
    double tStart, tEnd;
    if (t1 < t2) {
        tStart = t1;
        tEnd = t2;
    }
    else {
        tStart = t2;
        tEnd = t1;
    }

    // now scan the polar space at fixed radius and find
    // the minimum AND maximum Cartesian x and y values
    double delta = 0.01;

    // initialize min and max coordinates to first point
    xMin = radius * Math.cos(tStart);
    yMin = radius * Math.sin(tStart);
    xMax = xMin;
    yMax = yMin;

    for (double theta=tStart; theta < tEnd; theta += delta) {
        // compute coordinates
        double x = radius * Math.cos(theta);
        double y = radius * Math.sin(theta);

        if (x > xMax) {
            xMax = x;
        }
        if (x < xMin) {
            xMin = x;
        }
        if (y > yMax) {
            yMax = y;
        }
        if (y < yMin) {
            yMin = y;
        }
    }

    // display min and max values
    System.out.println("xMin = " + xMin + ", yMin = " + yMin);
    System.out.println("xMax = " + xMax + ", yMax = " + yMax);
}

测试

Arc starting at (5, 0) and ending at (0, 5) with center point (0, 0)
findMinMax(5, 0, 0, 5, 0, 0)
xMin = 0.003981633553660766, yMin = 0.0
xMax = 5.0, yMax = 4.999998414659173

假设我们有起始角θ1,结束角θ2(均为弧度),半径r,圆弧方向逆时针。我们想找到 XmaxYmaxXminYmin。将此值视为象限 q=f(θ) 的函数:

Xmax=f(q1,q2,r), Ymax=f(q1,q2,r), Xmin=f(q1,q2,r), Ymin=f(q1,q2,r).

与其编写大量 "if" 语句,不如将此函数表示为 "extremum matrices"。计算函数 f(q1,q2,r) 我们将得到 this matrices.

算法如下:

  1. 找到θ1的象限(q1,q2) θ2;
  2. θ1,θ2,r转换为笛卡尔坐标;
  3. 查找排除极值点的边界框;
  4. 构建极值矩阵;
  5. Select Xmax,Ymax,Xmin,Ymin accoding to q1 and q2 from this matrices.

这是我的 C#6 实现:

using System;
using System.Windows;
using static System.Math;

public static class GeomTools
{
    public static Byte GetQuadrant(this Double angle)
    {
        var trueAngle = angle%(2*PI);
        if (trueAngle >= 0.0 && trueAngle < PI/2.0)
            return 1;
        if (trueAngle >= PI/2.0 && trueAngle < PI)
            return 2;
        if (trueAngle >= PI && trueAngle < PI*3.0/2.0)
            return 3;
        if (trueAngle >= PI*3.0/2.0 && trueAngle < PI*2)
            return 4;
        return 0;
    }
    public static Rect GetBounds(Double startAngle, Double endAngle, Double r)
    {
        var startQuad = startAngle.GetQuadrant() - 1;
        var endQuad = endAngle.GetQuadrant() - 1;

        // Convert to Cartesian coordinates.
        var stPt = new Point(Round(r*Cos(startAngle), 14), Round(r*Sin(startAngle), 14));
        var enPt = new Point(Round(r*Cos(endAngle), 14), Round(r*Sin(endAngle), 14));

        // Find bounding box excluding extremum.
        var minX = stPt.X;
        var minY = stPt.Y;
        var maxX = stPt.X;
        var maxY = stPt.Y;
        if (maxX < enPt.X) maxX = enPt.X;
        if (maxY < enPt.Y) maxY = enPt.Y;
        if (minX > enPt.X) minX = enPt.X;
        if (minY > enPt.Y) minY = enPt.Y;

        // Build extremum matrices.
        var xMax = new[,] {{maxX, r, r, r}, {maxX, maxX, r, r}, {maxX, maxX, maxX, r}, {maxX, maxX, maxX, maxX}};
        var yMax = new[,] {{maxY, maxY, maxY, maxY}, {r, maxY, r, r}, {r, maxY, maxY, r}, {r, maxY, maxY, maxY}};
        var xMin = new[,] {{minX, -r, minX, minX}, {minX, minX, minX, minX}, {-r, -r, minX, -r}, {-r, -r, minX, minX}};
        var yMin = new[,] {{minY, -r, -r, minY}, {minY, minY, -r, minY}, {minY, minY, minY, minY}, {-r, -r, -r, minY}};

        // Select desired values
        var startPt =new Point(xMin[endQuad, startQuad], yMin[endQuad, startQuad]);
        var endPt=new Point(xMax[endQuad, startQuad], yMax[endQuad, startQuad]);
        return new Rect(startPt,endPt);
    }
}

圆弧中心点在 (0,0) 处是公平的,但您可以轻松地将生成的边界框移动到您的 Cx、Cy。

的近似解不同,此解是精确的,尽管它可能会占用更多内存。

Oleg Petrochenko 的答案在 Javascript 中实现:

const PI = Math.PI;
const HALF_PI = Math.PI / 2;
const TWO_PI = Math.PI * 2;
const DEG_TO_RAD = Math.PI / 180;
const RAD_TO_DEG = 180 / Math.PI;

const getQuadrant = (_angle) => {
    const angle = _angle % (TWO_PI);

    if (angle > 0.0 && angle < HALF_PI) return 0;
    if (angle >= HALF_PI && angle < PI) return 1;
    if (angle >= PI && angle < PI + HALF_PI) return 2;
    return 3;
};

const getArcBoundingBox = (ini, end, radius, margin = 0) => {
    const iniQuad = getQuadrant(ini);
    const endQuad = getQuadrant(end);

    const ix = Math.cos(ini) * radius;
    const iy = Math.sin(ini) * radius;
    const ex = Math.cos(end) * radius;
    const ey = Math.sin(end) * radius;

    const minX = Math.min(ix, ex);
    const minY = Math.min(iy, ey);
    const maxX = Math.max(ix, ex);
    const maxY = Math.max(iy, ey);

    const r = radius;
    const xMax = [[maxX, r, r, r], [maxX, maxX, r, r], [maxX, maxX, maxX, r], [maxX, maxX, maxX, maxX]];
    const yMax = [[maxY, maxY, maxY, maxY], [r, maxY, r, r], [r, maxY, maxY, r], [r, maxY, maxY, maxY]];
    const xMin = [[minX, -r, minX, minX], [minX, minX, minX, minX], [-r, -r, minX, -r], [-r, -r, minX, minX]];
    const yMin = [[minY, -r, -r, minY], [minY, minY, -r, minY], [minY, minY, minY, minY], [-r, -r, -r, minY]];

    const x1 = xMin[endQuad][iniQuad];
    const y1 = yMin[endQuad][iniQuad];
    const x2 = xMax[endQuad][iniQuad];
    const y2 = yMax[endQuad][iniQuad];

    const x = x1 - margin;
    const y = y1 - margin;
    const w = x2 - x1 + margin * 2;
    const h = y2 - y1 + margin * 2;

    return { x, y, w, h };
};

这是一个 jsfiddle:https://jsfiddle.net/brunoimbrizi/y3to5s6n/45/

添加另一个解决方案;我将 https://groups.google.com/g/comp.graphics.algorithms/c/GtvMc05E0CQ/m/duaoXIWaqJIJ 中的想法应用到以下示例中:

  • 角度以度为单位,从“3 点”顺时针方向
  • 0,0在圆心
  • 轴 +ve 朝向右下角
  • startAngle === endAngle arc 是整个圆还是什么都不清楚时,默认方法 returns 整个圆的边界框。

const svg = d3
  .select("section")
  .append("svg")
  .attr('width', 200)
  .attr('height', 200)
  .append('g')
  .attr('transform', d3.zoomIdentity.translate(100, 100).toString());

const pathShape = d3
  .arc()
  .startAngle(datum => degToRad(datum.startAngle))
  .endAngle(datum => degToRad(datum.endAngle))
  .innerRadius(datum => datum.radius)
  .outerRadius(datum => datum.radius);

function mod(
  n,
  m
) {
  return ((n % m) + m) % m;
}

function degToRad(
  degree
) {
  return degree * Math.PI / 180;
}

function reDraw() {
  const radius = 100;

  const startAngleInput = parseInt($('#start-angle').val());
  const endAngleInput = parseInt($('#end-angle').val());

  $('[data-field=start-angle]').text(startAngleInput);
  $('[data-field=end-angle]').text(endAngleInput);

  const startAngle = Math.min(startAngleInput, endAngleInput);
  const endAngle = Math.max(startAngleInput, endAngleInput);

  const cross0 = mod(startAngle, 360) >= mod(endAngle, 360);
  const cross90 = mod(startAngle - 90, 360) >= mod(endAngle - 90, 360);
  const cross180 = mod(startAngle - 180, 360) >= mod(endAngle - 180, 360);
  const cross270 = mod(startAngle - 270, 360) >= mod(endAngle - 270, 360);

  $('[data-field=cross-0]').text(cross0);
  $('[data-field=cross-90]').text(cross90);
  $('[data-field=cross-180]').text(cross180);
  $('[data-field=cross-270]').text(cross270);

  const startX = radius * Math.cos(degToRad(startAngle));
  const startY = radius * Math.sin(degToRad(startAngle));
  const endX = radius * Math.cos(degToRad(endAngle));
  const endY = radius * Math.sin(degToRad(endAngle));

  const right = cross0 ? +radius : Math.max(startX, endX);
  const bottom = cross90 ? +radius : Math.max(startY, endY);
  const left = cross180 ? -radius : Math.min(startX, endX);
  const top = cross270 ? -radius : Math.min(startY, endY);

  $('[data-field=right]').text(right.toFixed(2));
  $('[data-field=top]').text(top.toFixed(2));
  $('[data-field=left]').text(left.toFixed(2));
  $('[data-field=bottom]').text(bottom.toFixed(2));

  const pathSelectAll = svg
    .selectAll('path')
    .data([{
      // input angles start at 3 o'clock
      // SVG angle starts at 12 o'clock 
      startAngle: startAngle + 90,
      endAngle: endAngle + 90,
      radius: radius,
    }]);

  const pathEnter = pathSelectAll
    .enter()
    .append('path')
    .attr('fill', 'none')
    .attr('stroke', 'black');

  pathSelectAll
    .merge(pathEnter)
    .attr('d', datum => pathShape(datum));

  const circleSelectAll = svg
    .selectAll('circle')
    .data([{
      cx: startX,
      cy: startY,
    }, {
      cx: endX,
      cy: endY,
    }]);

  const circleEnter = circleSelectAll
    .enter()
    .append('circle')
    .attr('fill', 'none')
    .attr('stroke', 'blue');

  circleSelectAll
    .merge(circleEnter)
    .attr('r', 10)
    .attr('cx', datum => datum.cx)
    .attr('cy', datum => datum.cy);


  const rectSelectAll = svg
    .selectAll('rect')
    .data([{
      right: right,
      top: top,
      left: left,
      bottom: bottom,
    }]);

  const rectEnter = rectSelectAll
    .enter()
    .append('rect')
    .attr('fill', 'none')
    .attr('stroke', 'red');

  rectSelectAll
    .merge(rectEnter)
    .attr('x', datum => datum.left)
    .attr('y', datum => datum.top)
    .attr('width', datum => Math.abs(datum.left - datum.right))
    .attr('height', datum => Math.abs(datum.top - datum.bottom));
}

reDraw();

$(document).on('input', '#start-angle', reDraw);
$(document).on('input', '#end-angle', reDraw);
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/5.16.0/d3.js" integrity="sha512-F63QPFxQ27mn9COmkZhSirC1pBNeVJ7MJJs4wtK6XfiAaH3WM1SfX6Sv2Pme/499+hafP0dALVZOADw4W2r6eQ==" crossorigin="anonymous"></script>

<table>
  <tbody>
    <tr>
      <th>
        <label for="start-angle">Start Angle</label>
        <input id="start-angle" type="range" min="0" max="360" value="10" step="1">
      </th>
      <td data-field="start-angle"></td>
    </tr>
    <tr>
      <th>
        <label for="end-angle">End Angle</label>
        <input id="end-angle" type="range" min="0" max="360" value="200" step="1">
      </th>
      <td data-field="end-angle"></td>
    </tr>
  </tbody>
</table>

<section></section>

<table>
  <tbody>
    <tr>
      <th>Cross 0?</th>
      <td data-field="cross-0"></td>
    </tr>
    <tr>
      <th>Cross 90?</th>
      <td data-field="cross-90"></td>
    </tr>
    <tr>
      <th>Cross 180?</th>
      <td data-field="cross-180"></td>
    </tr>
    <tr>
      <th>Cross 270?</th>
      <td data-field="cross-270"></td>
    </tr>
    <tr>
      <th>Right</th>
      <td data-field="right"></td>
    </tr>
    <tr>
      <th>Top</th>
      <td data-field="top"></td>
    </tr>
    <tr>
      <th>Left</th>
      <td data-field="left"></td>
    </tr>
    <tr>
      <th>Bottom</th>
      <td data-field="bottom"></td>
    </tr>
  </tbody>
</table>


我知道这是旧的,但当前的 确实效率低下,甚至不准确,它只是通过沿弧线尝试一堆点来强行获得答案...

JavaScript 实现似乎崩溃了 某些点例如: