formula to calculate bounding coordinates of an ar

问题:

I have 2 lines that intersect at a point with know coordinates - x1,y1 - x2,y2 - x3,y3

From this I have calculated an arc at a given radius between the lines. So I now know - 2 arc endpoints x4,y4 and x5,y5 - arc centrepoint Cx,Cy - arc radius r - starting and ending angles relative to the X axis in polar and therefore the angle between the lines.

I want to create a formula that will calculate the maximum and minimum X and Y values of the arc. I.e. the coordinates of the box that would enclose the arc.

In the example below I can find out the minimum X value and maximum Y value, they are known values, but am unsure how to calculate the maximum X and minimum Y.

In other instances the arc could be any coordinates so the known minimum and maximum values will change.

I know how to calculate points along an arc at a given angle or intervals but not the maximum and minimum in a particular direction, in this case X and Y axis.

I am going to use the formula in programming.

回答1:

I have an algorithmic solution you can try using. It involves scanning the polar coordinate space in between your known starting and ending points on the arc, and keeping track of the minimum and maximum values.

Here are the basic steps of the algorithm:

• convert two input (Cartesian) points on the arc to Polar coordinates
• walk along the arc counter-clockwise in Polar coordinates
• at each step, convert back to Cartesian coordinates and check for minima/maxima

I took advantage of the following two equations to convert polar to Cartedian coordinates:

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

Here is an equation to convert Cartesian coordinates to a polar angle:

θ = tan-1(y / x)

You need to watch out for the potential divide by zero in this equation. Arc tangent of infinity is Pi / 2 radians.

This solution assumes that an arc begins and traverses counter-clockwise from a low radian value to a high radian value.

// 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);
}

Testing

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

回答2:

Suppose we have start angle θ1, end angle θ2 (both in radians), radus r, direction of the arc counterclockwise. We'd like to find Xmax,Ymax,Xmin and Ymin. Consider this values as functions of quadrants q=f(θ):

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

Instead of writing huge number of "if" statements it's convenient to represent this functions as an "extremum matrices". Evaluating functions f(q1,q2,r) we'll end up with this matrices.

So here is the algorithm:

1. Find quadrants (q1,q2) of θ1 and θ2;
2. Convert θ1,θ2,r to the Cartesian coordinates;
3. Find bounding box excluding extreme points;
4. Build extremum matrices;
5. Select Xmax,Ymax,Xmin,Ymin accoding to q1 and q2 from this matrices.

Here's my C#6 implementation:

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);
    }
}

It is fair for arc centre point at (0,0) but you can easily move resulting bounding box to your Cx,Cy.

Unlike Tim Buegeleisen's approximate solution this solution is exact, though it may be a little bit more memory expensive.

回答3:

First find in which quadrant the endpoints are.

If they are in the same quadrant, then the arc is monotonic and the bounding box is easy.

Otherwise, each time you cross a quadrant, you'll get an extreme point that is an endpoint of a horizontal or vertical diameter.

Not too complicated to write an algorithm for that, though there may be several cases to consider, including the orientation of the arc.

回答4:

Oleg Petrochenko's answer implemented in 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 };
};

Here is a jsfiddle: https://jsfiddle.net/brunoimbrizi/y3to5s6n/45/