用于计算空间中弧的边界坐标的公式

问题描述 投票:3回答:4

我有2条线在一个知道坐标的点相交 - x1,y1 - x2,y2 - x3,y3

由此我计算了线之间给定半径的弧。所以我现在知道了 - 2个圆弧端点x4,y4和x5,y5--圆弧中心点Cx,圆弧半径r - 极性中相对于X轴的起始和终止角度,因此是线之间的角度。

bounding coordinates of an arc in space

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

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

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

我知道如何以给定的角度或间隔计算沿弧的点,但不知道特定方向上的最大值和最小值,在这种情况下是X和Y轴。

我将在编程中使用该公式。

math formula
4个回答
1
投票

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

以下是该算法的基本步骤:

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

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

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
投票

首先找到端点所在的象限。

如果它们在同一象限中,那么弧是单调的并且边界框很容易。

否则,每次越过象限时,您将获得一个极值点,即水平或垂直直径的终点。

虽然可能有几种情况要考虑,包括弧的方向,但为此编写算法并不复杂。


1
投票

假设我们有逆时针的起始角θ1,终止角θ2(弧度均为弧度),弧度r,弧的方向。我们想找到Xmax,Ymax,Xmin和Ymin。将此值视为象限q = f(θ)的函数:

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

而不是编写大量的“if”语句,将这些函数表示为“极值矩阵”很方便。评估函数f(q1,q2,r)我们最终会得到this matrices

所以这是算法:

  1. 找到θ1和θ2的象限(q1,q2);
  2. 将θ1,θ2,r转换为笛卡尔坐标;
  3. 找到不包括极值点的边界框;
  4. 构建极值矩阵;
  5. 从该矩阵中选择Xmax,Ymax,Xmin,Ymin,编码为q1和q2。

这是我的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。

Tim Buegeleisen的近似解决方案不同,这个解决方案是准确的,虽然它可能会有更多的内存昂贵。


0
投票

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/

© www.soinside.com 2019 - 2024. All rights reserved.