给定点到给定椭圆的距离 [英] distance from given point to given ellipse

问题描述

我有一个椭圆，由中心点"，radiusX和radiusY定义，并且有一个点.我想在椭圆上找到最接近给定点的点.在下图中，该名称为S1.

I have an ellipse, defined by Center Point, radiusX and radiusY, and I have a Point. I want to find the point on the ellipse that is closest to the given point. In the illustration below, that would be S1.

现在我已经有了代码，但是其中有些地方存在逻辑错误，而且我似乎找不到它.我将问题分解为以下代码示例:

Now I already have code, but there is a logical error somewhere in it, and I seem to be unable to find it. I broke the problem down to the following code example:

#include <vector>
#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <math.h>

using namespace std;

void dostuff();

int main()
{
    dostuff();
    return 0;
}

typedef std::vector<cv::Point> vectorOfCvPoints;

void dostuff()
{

    const double ellipseCenterX = 250;
    const double ellipseCenterY = 250;
    const double ellipseRadiusX = 150;
    const double ellipseRadiusY = 100;

    vectorOfCvPoints datapoints;

    for (int i = 0; i < 360; i+=5)
    {
        double angle = i / 180.0 * CV_PI;
        double x = ellipseRadiusX * cos(angle);
        double y = ellipseRadiusY * sin(angle);
        x *= 1.4;
        y *= 1.4;
        x += ellipseCenterX;
        y += ellipseCenterY;
        datapoints.push_back(cv::Point(x,y));
    }

    cv::Mat drawing = cv::Mat::zeros( 500, 500, CV_8UC1 );

    for (int i = 0; i < datapoints.size(); i++)
    {
        const cv::Point & curPoint = datapoints[i];
        const double curPointX = curPoint.x;
        const double curPointY = curPoint.y * -1; //transform from image coordinates to geometric coordinates

        double angleToEllipseCenter = atan2(curPointY - ellipseCenterY * -1, curPointX - ellipseCenterX); //ellipseCenterY * -1 for transformation to geometric coords (from image coords)

        double nearestEllipseX = ellipseCenterX + ellipseRadiusX * cos(angleToEllipseCenter);
        double nearestEllipseY = ellipseCenterY * -1 + ellipseRadiusY * sin(angleToEllipseCenter); //ellipseCenterY * -1 for transformation to geometric coords (from image coords)


        cv::Point center(ellipseCenterX, ellipseCenterY);
        cv::Size axes(ellipseRadiusX, ellipseRadiusY);
        cv::ellipse(drawing, center, axes, 0, 0, 360, cv::Scalar(255));
        cv::line(drawing, curPoint, cv::Point(nearestEllipseX,nearestEllipseY*-1), cv::Scalar(180));

    }
    cv::namedWindow( "ellipse", CV_WINDOW_AUTOSIZE );
    cv::imshow( "ellipse", drawing );
    cv::waitKey(0);
}

它产生以下图像:

您可以看到它实际上在椭圆上找到近"点，但不是最近"点.我故意想要的是:(对不起，我的绘画不好)

You can see that it actually finds "near" points on the ellipse, but it are not the "nearest" points. What I intentionally want is this: (excuse my poor drawing)

您可以扩展上一张图像中的线条，它们会越过椭圆的中心，但是上一张图像中的线条却不是这种情况.
希望你能明白.谁能告诉我我在做什么错?

would you extent the lines in the last image, they would cross the center of the ellipse, but this is not the case for the lines in the previous image.
I hope you get the picture. Can anyone tell me what I am doing wrong?

推荐答案

考虑围绕给定点(c，d)的边界圆，该边界圆通过椭圆上的最近点.从图中可以清楚地看出，最接近的点是这样的，即从该点到给定点的直线必须垂直于椭圆和圆的共同切线.任何其他点都将在圆之外，因此必须远离给定点.

Consider a bounding circle around the given point (c, d), which passes through the nearest point on the ellipse. From the diagram it is clear that the closest point is such that a line drawn from it to the given point must be perpendicular to the shared tangent of the ellipse and circle. Any other points would be outside the circle and so must be further away from the given point.

因此，您要查找的点不是直线和椭圆之间的交点，而是图中的点(x，y).

So the point you are looking for is not the intersection between the line and the ellipse, but the point (x, y) in the diagram.

切线渐变

行的渐变:

垂直线的状况-梯度的乘积= -1:

Condition for perpedicular lines - product of gradients = -1:

重新排列并代入椭圆方程后...

When rearranged and substituted into the equation of your ellipse...

...这将根据x或y给出两个讨厌的四次(四次多项式)方程. AFAIK没有通用分析(精确代数)方法可以解决这些问题.您可以尝试使用一种迭代方法-查找Newton-Raphson迭代寻根算法.

...this will give two nasty quartic (4th-degree polynomial) equations in terms of either x or y. AFAIK there are no general analytical (exact algebraic) methods to solve them. You could try an iterative method - look up the Newton-Raphson iterative root-finding algorithm.

看看关于这个主题的这篇很好的论文: http://www.spaceroots.org/documents/distance/distance-to -ellipse.pdf

Take a look at this very good paper on the subject: http://www.spaceroots.org/documents/distance/distance-to-ellipse.pdf

抱歉，答案不完整-我完全怪罪数学定律和自然定律...

Sorry for the incomplete answer - I totally blame the laws of mathematics and nature...

哎呀，我似乎在xD图中以错误的方式绕过了a和b

oops, i seem to have a and b the wrong way round in the diagram xD

这篇关于给定点到给定椭圆的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！