CODEWITHSUNDEEP
c++algorithmmath
jmasterx
jmasterx

Reputation: 54113

Line-Circle Algorithm not quite working as expected

First, see:

https://math.stackexchange.com/questions/105180/positioning-a-widget-involving-intersection-of-line-and-a-circle

I have an algorithm that solves for the height of an object given a circle and an offset.

It sort of works but the height is always off: Here is the formula: enter image description here

and here is a sketch of what it is supposed to do: enter image description here

And here is sample output from the application: enter image description here

In the formula, offset = 10 and widthRatio is 3. This is why it is (1 / 10) because (3 * 3) + 1 = 10.

The problem, as you can see is the height of the blue rectangle is not correct. I set the bottom left offsets to be the desired offset (in this case 10) so you can see the bottom left corner is correct. The top right corner is wrong because from the top right corner, I should only have to go 10 pixels until I touch the circle.

The code I use to set the size and location is:

void DataWidgetsHandler::resize( int w, int h )
    {
        int tabSz = getProportions()->getTableSize() * getProportions()->getScale();
        int r = tabSz / 2;
        agui::Point tabCenter = agui::Point(
            w * getProportions()->getTableOffset().getX(),
            h * getProportions()->getTableOffset().getY()); 

        float widthRatio = 3.0f;
        int offset = 10;
        int height = solveHeight(offset,widthRatio,tabCenter.getX(),tabCenter.getY(),r);
        int width = height * widthRatio;

        int borderMargin = height;

        m_frame->setLocation(offset,
            h - height - offset);

        m_frame->setSize(width,height);

        m_borderLayout->setBorderMargins(0,0,borderMargin,borderMargin);


    }

I can assert that the table radius and table center location are correct.

This is my implementation of the formula:

int DataWidgetsHandler::solveHeight( int offset, float widthRatio, float h, float k, float r ) const
{

    float denom = (widthRatio * widthRatio) + 1.0f;

    float rSq = denom * r * r;

    float eq = widthRatio * offset - offset - offset + h - (widthRatio * k);
    eq *= eq;
    return  (1.0f / denom) *
        ((widthRatio * h) + k - offset - (widthRatio * (offset + offset)) - sqrt(rSq - eq) );


}

It uses the quadratic formula to find what the height should be so that the distance between the top right of the rectangle, bottom left, amd top left are = offset.

Is there something wrong with the formula or implementation? The problem is the height is never long enough.

Thanks

Upvotes: 2

Views: 194

Answers (1)

DSM
DSM

Reputation: 353059

Well, here's my solution, which looks to resemble your solveHeight function. There might be some arithmetic errors in the below, but the method is sound.

You can think in terms of matching the coordinates at the point of the circle across from the rectangle (P).

Let o_x,o_y be the lower left corner offset distances, w and h be the height of the rectangle, w_r be the width ratio, dx be the desired distance between the top right hand corner of the rectangle and the circle (moving horizontally), c_x and c_y the coordinates of the circle's centre, theta the angle, and r the circle radius.

Labelling it is half the work! Simply write down the coordinates of the point P:

P_x = o_x + w + dx = c_x + r cos(theta)
P_y = o_y + h = c_y + r sin(theta)

and we know w = w_r * h.

To simplify the arithmetic, let's collect some of the constant terms, and let X = o_x + dx - c_x and Y = o_y - c_y. Then we have

X + w_r * h = r cos(theta)
Y + h = r sin(theta)

Squaring and summing gives a quadratic in h:

(w_r^2 + 1) * h^2 + 2 (X*w_r + Y) h + (X^2+Y^2-r^2) == 0

If you compare this with your effective quadratic, then as long as we made different mistakes :-), you might be able to figure out what's going on.

To be explicit: we can solve this using the quadratic formula, setting

a = (w_r^2 + 1) 
b = 2 (X*w_r + Y)
c = (X^2+Y^2-r^2)

Upvotes: 1

Related Questions