Page 2 of 3

Posted: Tue Sep 01, 2009 6:44 pm
by PI
I think I understand it, I'm gonna "test" it on paper. Thanks for the idea!

Posted: Tue Sep 01, 2009 8:08 pm
by Dorth
That is a very sweet and tasty solution, nice job! However, you can probably fold a lot of those steps by using trig identities and folding operations. But the thinking behind it is sweet :)

Posted: Tue Sep 01, 2009 9:32 pm
by xray
Yep the idea is good, but i would wait until someone has calculated the equation... somehow I have the intuition that the solution could be the same like the equation I got :?

Posted: Wed Sep 02, 2009 1:08 pm
by PI
I think the weakest point of my approach is simply that I don't pick the right angle. The right angle would be perpendicular to the tangent.

Also, I can see that my solution could be greatly simplified.

Posted: Wed Sep 02, 2009 2:11 pm
by JeroenP
Hello,

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);
(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
Image
(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();
}
Jeroen

Posted: Wed Sep 02, 2009 2:37 pm
by PI
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:
Image

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!

Posted: Wed Sep 02, 2009 2:58 pm
by PI
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. :D

Posted: Wed Sep 02, 2009 5:55 pm
by Dorth
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 :)

Posted: Wed Sep 02, 2009 6:00 pm
by JeroenP
@ 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...

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

Posted: Wed Sep 02, 2009 6:13 pm
by sio2
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. :wink:

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. :D

Posted: Thu Sep 03, 2009 2:44 am
by bitplane
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 :)
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.

Posted: Thu Sep 03, 2009 4:57 am
by sRc
ah, the real world, our greatest enemy

Posted: Thu Sep 03, 2009 7:49 am
by xray
@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.
Can we have another math challenge after that one is concluded? This should go in the competition section or something
If the competition is just to get a solution and not a working code than I won ;)! Maple gave me a unhandy solution.

I will ask my math professor, I think he can tell me if there is a nice and simple solution to this problem.

Posted: Thu Sep 03, 2009 2:55 pm
by PI
@Dorth:
:D 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:
If the competition is just to get a solution and not a working code than I won Wink
True! :D I need a working code, though.
I will ask my math professor, I think he can tell me if there is a nice and simple solution to this problem.
That would be nice! Thanks!


--------------------------------
To answer my question: I wasn't right.

Because we want P to lay perp. on the tangent of CP, and not reversed:
Image
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 :D

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

Posted: Thu Sep 03, 2009 3:42 pm
by mk.1
google helps. there's no closed solution for the problem.