Closest point to an ellipsoid
Hello,
I think I know an easy way to get the closest point!!!
First you search the two focus-points, you find them by: (If (0,0) is the middle point)
(a = big radius)
(b = little radius)
Then if you have these, you connect these to the given point (I cal it P)
So focus1->P and focus2->P.
You now have an angle (F1 - P - F2).
Take the angle bisector of it, and where it hits the ellips, one of the two points is the closest (the other is the farthest)
I created a program to show this solution. (It does not calculate the point, you will have to do that yourself)
Screenshot
(The red line is the line to the center of the ellips)
Program-code:
Jeroen
I think I know an easy way to get the closest point!!!
First you search the two focus-points, you find them by:
Code: Select all
f32 c=sqrt(kwa(a)-kwa(b));
core::position2di focus1 = core::position2di((s32)(-c),0);
core::position2di focus2 = core::position2di((s32)(c),0);
(a = big radius)
(b = little radius)
Then if you have these, you connect these to the given point (I cal it P)
So focus1->P and focus2->P.
You now have an angle (F1 - P - F2).
Take the angle bisector of it, and where it hits the ellips, one of the two points is the closest (the other is the farthest)
I created a program to show this solution. (It does not calculate the point, you will have to do that yourself)
Screenshot
(The red line is the line to the center of the ellips)
Program-code:
Code: Select all
#include <iostream>
using namespace std;
#include <irrlicht.h>
using namespace irr;
IrrlichtDevice* device;
video::IVideoDriver* driver;
gui::ICursorControl* cursor;
#define SHOW_CMD_DEVICE
#ifdef _IRR_WINDOWS_
#pragma comment(lib, "Irrlicht.lib")
#ifndef SHOW_CMD_DEVICE
#pragma comment(linker, "/subsystem:windows /ENTRY:mainCRTStartup")
#endif
#endif
f32 kwa(f32 a){
return a*a;
}
void drawEllips(f32 a,f32 b)
{
u32 steps = 36;
f32 prevX=0.f;
f32 prevY=0.f;
for (f32 i = 0; i <= 360.f; i += 360.f / (f32)steps)
{
f32 nowX = 320 + a * cos(i*(core::PI/180));
f32 nowY = 240 + b * sin(i*(core::PI/180));
if(prevX!=0.f){
driver->draw2DLine(core::position2di((s32)prevX,(s32)prevY),core::position2di((s32)nowX,(s32)nowY), video::SColor(255,0,0,255));
}
prevX=nowX;
prevY=nowY;
}
}
int main(){
device=createDevice(video::EDT_OPENGL);
driver=device->getVideoDriver();
cursor=device->getCursorControl();
f32 a=200.f;
f32 b=80.f;
while(device->run()){
core::position2di cpos =cursor->getPosition();
core::position2df pos((f32)cpos.X-320,(f32)cpos.Y-240);
driver->beginScene();
drawEllips(a,b);
f32 c=sqrt(kwa(a)-kwa(b));
driver->draw2DLine(core::position2di((s32)(320-c),240),cpos);
driver->draw2DLine(core::position2di((s32)(320+c),240),cpos);
driver->draw2DLine(core::position2di(320,240),cpos,video::SColor(255,255,0,0));
driver->endScene();
}
device->drop();
}
Wow JeorenP, thanks! You're even providing source!
However, I think I have to disappoint you. I've fallen into the same mistake maybe only a couple of minutes before you, while browsing for the answer and finding this page:
http://www.mathopenref.com/ellipsetangent.html
I've marked with red what you suggest:
We'd need to know the closest point to get the right angles (from a and b), but our goal is exactly to get the closest point. The closest point will lay on the line marked with blue (CP to P direction), no matter how far it is.
Thanks, anyway!
However, I think I have to disappoint you. I've fallen into the same mistake maybe only a couple of minutes before you, while browsing for the answer and finding this page:
http://www.mathopenref.com/ellipsetangent.html
I've marked with red what you suggest:
We'd need to know the closest point to get the right angles (from a and b), but our goal is exactly to get the closest point. The closest point will lay on the line marked with blue (CP to P direction), no matter how far it is.
Thanks, anyway!
Hey but what if we'd combine it with SiO2's idea:
- find a proportionally larger ellipsoid, that P actually lays on
- if it lays on the ellipsoid, it's closest point is itself
- since we've made our ellipsoid larger, it has new focus points, so
- we can set up the P-F1, P-F2 lines now, get the middle angle
- the intersection of this angle from P, with the original ellipsoid yields the closest point
Is it logical? I'm gonna find out if it's true, but it definately sounds cool.
- find a proportionally larger ellipsoid, that P actually lays on
- if it lays on the ellipsoid, it's closest point is itself
- since we've made our ellipsoid larger, it has new focus points, so
- we can set up the P-F1, P-F2 lines now, get the middle angle
- the intersection of this angle from P, with the original ellipsoid yields the closest point
Is it logical? I'm gonna find out if it's true, but it definately sounds cool.
@ PI: The point you are searching is not the closest point, it's the intersection of PM (P=given ; M=middle) with the ellips...
That's because you scale around the center point.
The other solution with the tangent...
A solution:
You could eventualy calculate some points of the ellips, and for every point get the distance... See the code...
This works, is as precise as you want it, but takes CPU...
Jeroen
That's because you scale around the center point.
The other solution with the tangent...
A solution:
You could eventualy calculate some points of the ellips, and for every point get the distance... See the code...
This works, is as precise as you want it, but takes CPU...
Code: Select all
#include <iostream>
using namespace std;
#include <irrlicht.h>
using namespace irr;
IrrlichtDevice* device;
video::IVideoDriver* driver;
gui::ICursorControl* cursor;
#define SHOW_CMD_DEVICE
#ifdef _IRR_WINDOWS_
#pragma comment(lib, "Irrlicht.lib")
#ifndef SHOW_CMD_DEVICE
#pragma comment(linker, "/subsystem:windows /ENTRY:mainCRTStartup")
#endif
#endif
f32 kwa(f32 a){
return a*a;
}
void drawEllips(f32 a,f32 b)
{
u32 steps = 36;
f32 prevX=0.f;
f32 prevY=0.f;
for (f32 i = 0; i <= 360.f; i += 360.f / (f32)steps)
{
f32 nowX = 320 + a * cos(i*(core::PI/180));
f32 nowY = 240 + b * sin(i*(core::PI/180));
if(prevX!=0.f){
driver->draw2DLine(core::position2di((s32)prevX,(s32)prevY),core::position2di((s32)nowX,(s32)nowY), video::SColor(255,0,0,255));
}
prevX=nowX;
prevY=nowY;
}
}
core::position2df getClosestPoint(f32 a,f32 b,core::position2df from, u32 detail = 72)
{
f32 closeX=0.f;
f32 closeY=0.f;
f32 closedist=0.f;
bool init=false;
for (f32 i = 0; i < 360.f; i += 360.f / (f32)detail)
{
f32 thisX = a * cos(i*(core::PI/180));
f32 thisY = b * sin(i*(core::PI/180));
f32 thisdist = kwa(thisX-from.X)+kwa(thisY-from.Y);
if(!init){closedist=thisdist+1.f;init=true;}
if(thisdist<closedist){
closedist=thisdist;
closeX=thisX;
closeY=thisY;
}
}
return core::position2df(closeX,closeY);
}
int main(){
device=createDevice(video::EDT_OPENGL);
driver=device->getVideoDriver();
cursor=device->getCursorControl();
f32 a=200.f;
f32 b=80.f;
while(device->run()){
core::position2di cpos =cursor->getPosition();
core::position2df pos((f32)cpos.X-320,(f32)cpos.Y-240);
//this is the function that does everything
core::position2df Pf = getClosestPoint(a,b,pos,200);
driver->beginScene();
drawEllips(a,b);
s32 Px = (s32)Pf.X+320;
s32 Py = (s32)Pf.Y+240;
driver->draw2DLine(core::position2di((s32)Px,(s32)Py),cpos, video::SColor(255,0,255,0));
driver->endScene();
}
device->drop();
}
If you're going to search for an ellipse that intersects P then use a binary search - that should converge quickly. A single, direct calculation would be quickest of all though.
Another idea: could you project point P onto a 2D projection of ellipse E? Your 2D coordinate could then be projected back to 3D worldspace, giving two intersections - pick the nearest. Disclaimer: this idea may be rubbish.
Another idea: could you project point P onto a 2D projection of ellipse E? Your 2D coordinate could then be projected back to 3D worldspace, giving two intersections - pick the nearest. Disclaimer: this idea may be rubbish.
Irrlicht Demos: http://irrlicht.sourceforge.net/forum/viewtopic.php?f=6&t=45781
Me too! I wish I'd had more time over the past few days to find a solution, but the real world has been intruding on my computer time.Dorth wrote:Ok, I'm seriously having fun just reading this topic...
Can we have another math challenge after that one is concluded? This should go in the competition section or something
@JeroenP: nope you are wrong with the closest point, and PI is right. The closest point is the one which vector P and the point on the ellipse is upright to the tangent through the point on the ellipse. I thought that would be clear now
By the way JeroenP, your solution with the two foci and the bisector of F1-P-F2 cant be right, if you think about the extremum when point P lays on the same hight as the vector between F1 and F2 then you your bisector and the angle is zero.
I will ask my math professor, I think he can tell me if there is a nice and simple solution to this problem.
By the way JeroenP, your solution with the two foci and the bisector of F1-P-F2 cant be right, if you think about the extremum when point P lays on the same hight as the vector between F1 and F2 then you your bisector and the angle is zero.
If the competition is just to get a solution and not a working code than I won ! Maple gave me a unhandy solution.Can we have another math challenge after that one is concluded? This should go in the competition section or something
I will ask my math professor, I think he can tell me if there is a nice and simple solution to this problem.
@Dorth:
I have some other shapes, if you're interested... But I know the solution for those.
@JeroenP:
You're right, see below!
Yeah, but I need something faster than searching among many points. It'd depend on the "resolution" (amount of points), too. But for testing the solutions we're working out here, it could be a good reference!
@SiO2:
Your idea sounds good! But how to pick the viewport = projection plane? What's the direction?
@xray:
--------------------------------
To answer my question: I wasn't right.
Because we want P to lay perp. on the tangent of CP, and not reversed:
The red line shows what I've described, and the blue one shows the solution.
...But! This has led me to a previous drawing I've made... which I don't want to show here because it looks like as if the whole problem would be closely related to women
Practically growing ellipsoids, and the normals out of their selected points. But there the ellipsoids wasn't scaled proportionally, but by a certain length on each axis, where this length was constant.
So: I just need two ellipsoids (a smaller, and a larger; both are at the origin) that shares the same normal (= vector perp. to the tangent)!
Thus, the 2D solution of the problem is: (see below, why it's only 2D, as it looks 3D!)
Why it's only 2D?
- An ellipse has 2 focus points, right? Right. What does an ellipsoid has? Certainly not focus points, but a focus surface, formed by focus curves. (It does sound awful, doesn't it? )
- To avoid dealing with this monster, I should cut the ellipsoid, so that it forms a new ellipse (that has foci, etc.).
- That is, bringing down the whole problem into 2D.
Now, I just need to find where to cut
I have some other shapes, if you're interested... But I know the solution for those.
@JeroenP:
You're right, see below!
Yeah, but I need something faster than searching among many points. It'd depend on the "resolution" (amount of points), too. But for testing the solutions we're working out here, it could be a good reference!
@SiO2:
Your idea sounds good! But how to pick the viewport = projection plane? What's the direction?
@xray:
True! I need a working code, though.If the competition is just to get a solution and not a working code than I won Wink
That would be nice! Thanks!I will ask my math professor, I think he can tell me if there is a nice and simple solution to this problem.
--------------------------------
To answer my question: I wasn't right.
Because we want P to lay perp. on the tangent of CP, and not reversed:
The red line shows what I've described, and the blue one shows the solution.
...But! This has led me to a previous drawing I've made... which I don't want to show here because it looks like as if the whole problem would be closely related to women
Practically growing ellipsoids, and the normals out of their selected points. But there the ellipsoids wasn't scaled proportionally, but by a certain length on each axis, where this length was constant.
So: I just need two ellipsoids (a smaller, and a larger; both are at the origin) that shares the same normal (= vector perp. to the tangent)!
Thus, the 2D solution of the problem is: (see below, why it's only 2D, as it looks 3D!)
Code: Select all
// getClosestPointToEllipsoid
// returns the closest point to an axis-aligned ellipsoid, from a given point
// assumes that the ellipsoid is at the origin
// treats the ellispoid-problem as a sphere-problem
// \param Point: the point you want to project onto the ellipsoid
// \param Scale: the ellipsoid radius
// \return the closest point ont the ellipsoid
// issues:
// - getting more and more unaccurate the deeper "Point" is inside the ellipsoid
// - it's only 2D !!!!!!!!!!!!!!!!!!!!!!!!!
core::vector3df CGame::getClosestPointToEllipsoid(const core::vector3df& Point, const core::vector3df& Scale)
{
// find the largest scale factor (radius), and it's axis:
float mx = Scale.X;
core::vector3df axis = core::vector3df(1, 0, 0);
if (Scale.Y > mx) { mx = Scale.Y; axis = core::vector3df(0, 1, 0); }
if (Scale.Z > mx) { mx = Scale.Z; axis = core::vector3df(0, 0, 1); }
// find the smallest scale factor (radius), and prepare the transformation vectors:
float mn = core::min_(Scale.X, Scale.Y, Scale.Z);
core::vector3df mps = core::vector3df(mn) / Scale;
core::vector3df spm = Scale / core::vector3df(mn);
// get the intersection with the ellipsoid:
core::vector3df i = core::vector3df((Point * mps).normalize() * Scale);
// early exit, if it's right on the ellipsoid
float ilen = i.getLength(), plen = Point.getLength();
if (core::equals(ilen, plen)) return i;
// get the ratio we need to scale the ellipsoid,
// and transform the max. and min. scale factor (radius) with it
// note: finding the closest point gets more and more unaccurate the deeper "Point" is
ilen = !ilen ? 1 : ilen;
float ratio = plen / ilen;
float tmn = mn * ratio;
float tmx = (ilen < plen) ? mx + (tmn - mn) : mx * ratio;
// calculate the two foci, and Point->F1, Point->F2, then the half vector
float c = sqrt((tmx * tmx) - (tmn * tmn));
core::vector3df f1 = axis * c, f2 = -f1;
core::vector3df v1 = (f1 - Point).normalize();
core::vector3df v2 = (f2 - Point).normalize();
core::vector3df v = (v1 + v2).normalize();
// transform Q and Point
core::vector3df q = Point + v;
core::vector3df tp = Point * mps;
core::vector3df tq = q * mps;
// intersect TP->TQ with the sphere of the min. scale factor (radius)
double dist = 1;
core::line3df ray(tp, tq);
ray.getIntersectionWithSphere(core::vector3df(), mn, dist);
core::vector3df n = ray.getVector().normalize();
core::vector3df si = tp + (n * dist);
// transform back the intersection point
return si * spm;
}
- An ellipse has 2 focus points, right? Right. What does an ellipsoid has? Certainly not focus points, but a focus surface, formed by focus curves. (It does sound awful, doesn't it? )
- To avoid dealing with this monster, I should cut the ellipsoid, so that it forms a new ellipse (that has foci, etc.).
- That is, bringing down the whole problem into 2D.
Now, I just need to find where to cut