[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-kimageshop
Subject: Re: Perspective Ellipse Math for SoK'22
From: Tymon_Dąbrowski <tamtamy.tymona () gmail ! com>
Date: 2022-03-14 7:00:00
Message-ID: CAL5LU_9s4xfmeKBk8sCVG=VApWri3Z-1iobq2SkKgA_6Ht-W4Q () mail ! gmail ! com
[Download RAW message or body]
Hi @Srirupa,
***Method 1***
I checked your PDF and in my opinion, the result you got from Wolfram Alpha
is consistent with your data and your approach. If you use the values for
a, b, c,..., into the generic ellipse equation, you'll see that it results
in an equation:
a*x^2 + a*y^2 - a = 0
which is the same as:
a*(x^2 + y^2 - 1) = 0
And you can see that no matter what value "a" is, it represents the same
points on the plane (except when a is equal to 0, then it represents the
whole plane and not just the ellipse).
The problem in your equation is that every part of the equation has a
parameter/variable next to it. It's probably easiest to see if you reduce
by *f *(here, with the assumption that *f* != 0):
f * (a/f * x^2 + b/f * xy + c/f * y^2 + d/f * x + e/f * y + 1) = 0
as you can see, no matter what value f is, it will represent the exact same
ellipse. So you could represent it this way:
a/f * x^2 + b/f * xy + c/f * y^2 + d/f * x + e/f * y + 1 = 0
or, since *a/f* is just as unknown as *a*, this way:
a * x^2 + b * xy + c * y^2 + d * x + e * y + 1 = 0
and this reduces the dimension of the linear equations system to just 5.
NOW, I'm not 100% sure if you can just reduce *f* like that, because I'm
not sure whether *f* (in the original equation) can or cannot be 0. I
haven't explored that possibility before writing this mail. If* f* *can* be
0, it would have to be considered somewhere separately.
Thinking about it, while I'm not sure whether we can reduce *f*, we
*probably* could reduce for example *a*.
I'm not 100% sure about it either, you'd have to check that, but I'm
somewhat quite sure you couldn't have an ellipse with equation like that:
0*x^2 + ... = 0
so I think it would be fine if you reduce by *a* and change the original
equation to be:
a * (1 * x^2 + b/a * xy + c/a * y^2 + d/a * x + e/a * y + f/a) = 0
which means you could make an equation like that:
*1 * x^2 + a * xy + b * y^2 + c * x + d * y + e = 0*
which also means just 5 variables/equations, not 6, and less chance of
infinite solutions.
Think about it this way: it's similar to as if you had an equation for a
line looking like this: "ax + by + c = 0", which looks correct, but then
you'd try having three equations to find all three a, b and c, while the
line only needs two points to be defined, which means just two equations.
To represent a line, at least one of a, b, or c must not be 0, so there is
always a way to reduce the number of equations to 2 (though it depends on
the data in that case because sometimes you'd have "y = 0" (so a = 0, b =
1, c = 0) and sometimes you'd have "x = 0" (a = 1, b = 0, c = 0)).
-----
Also
> I need to solve a system of linear equations for six variables and this
is *probably* complicated.
Actually, you'd probably just have to put it all into a matrix and a vector
and ask Eigen to solve it for you. It's a very basic operation (it's not
trivial to write yourself, though it wouldn't be very difficult either, but
it's so common of a need that I would be surprised to learn that some
library offering matrix operations doesn't provide it out of the box. As an
example, in languages "octave" (foss) and "matlab" (proprietary) you can
solve a system of linear equations just by writing a few characters: "x =
A\b" (note the backslash instead of slash) when A is the matrix of
coefficients and b is the vector of constant terms. And x is the solution
vector. The original equation system is Ax = b).
In Eigen you'll probably have to write a few more characters than that, but
it should be fairly easy, too :)
For Eigen, here you have documentation that explains what needs to be
written: https://eigen.tuxfamily.org/dox/group__TutorialLinearAlgebra.html
And for usage of Eigen in Krita, you can refer to the file:
libs/global/kis_algebra_2d.cpp
***Method 2***
I think there should be a way, but I don't know yet, but also you have
Method 1 already figured out, so maybe it's not necessarily needed.
---
Hope that helps,
Tiar
PS. If anything is unclear, feel free to ask, either here or on IRC (tiar).
niedz., 13 mar 2022 o 19:04 Srirupa Datta <srirupa.sps@gmail.com>
napisał(a):
> I have a quadrilateral, whose 4 corners are known, and an inscribed
> ellipse whose touching points with the quadrilateral and also known. I need
> to find out the extreme points of the major axis of that ellipse.
>
> *Method 1*
> I decided to first find out the equation of the inscribed ellipse. This
> <https://drive.google.com/file/d/1mMT9to50lJN1eo2SPQh3jJB_puvb-SBj/view?usp=sharing>
> is what I did so far. However this approach has a challenge. I need to
> solve a system of linear equations for six variables and this is
> *probably* complicated. So I'm not sure if this is at all the right
> approach.
>
> Also, I got stuck since I expected the solution to be a unique one.
>
> *Method 2*
> I have the transformation matrix that maps a unit square to my
> quadrilateral. Is there any way I can use transformation mathematics to
> solve this problem easily?
>
> Thanks,
> Srirupa
>
>
>
[Attachment #3 (text/html)]
<div dir="ltr"><div>Hi @Srirupa,</div><div><br></div><div>**<b>Method \
1</b>**<br></div><div>I checked your PDF and in my opinion, the result you got from \
Wolfram Alpha is consistent with your data and your approach. If you use the values \
for a, b, c,..., into the generic ellipse equation, you'll see that it results in \
an equation:<br></div><div>a*x^2 + a*y^2 - a = 0<br></div><div>which is the same \
as:<br></div><div>a*(x^2 + y^2 - 1) = 0<br></div><div>And you can see that no matter \
what value "a" is, it represents the same points on the plane (except when \
a is equal to 0, then it represents the whole plane and not just the \
ellipse).<br></div><div><br></div><div>The problem in your equation is that every \
part of the equation has a parameter/variable next to it. It's probably easiest \
to see if you reduce by <b>f </b>(here, with the assumption that <b>f</b> != \
0):</div><div>f * (a/f * x^2 + b/f * xy + c/f * y^2 + d/f * x + e/f * y + 1) = \
0<br></div><div>as you can see, no matter what value f is, it will represent the \
exact same ellipse. So you could represent it this way:<br><div>a/f * x^2 + b/f * xy \
+ c/f * y^2 + d/f * x + e/f * y + 1 = 0<br></div><div>or, since <b>a/f</b> is just as \
unknown as <b>a</b>, this way:<br><div>a * x^2 + b * xy + c * y^2 + d * x + e * y + 1 \
= 0<br></div><div>and this reduces the dimension of the linear equations system to \
just 5.</div><div><br></div><div>NOW, I'm not 100% sure if you can just reduce \
<b>f</b> like that, because I'm not sure whether <b>f</b> (in the original \
equation) can or cannot be 0. I haven't explored that possibility before writing \
this mail. If<b> f</b> *can* be 0, it would have to be considered somewhere \
separately.</div><div>Thinking about it, while I'm not sure whether we can reduce \
<b>f</b>, we *probably* could reduce for example <b>a</b>.<br></div><div>I'm not \
100% sure about it either, you'd have to check that, but I'm somewhat quite \
sure you couldn't have an ellipse with equation like that:<br></div><div>0*x^2 + \
... = 0<br></div><div>so I think it would be fine if you reduce by <b>a</b> and \
change the original equation to be:<br>a * (1 * x^2 + b/a * xy + c/a * y^2 + d/a * x \
+ e/a * y + f/a) = 0<br></div><div>which means you could make an equation like \
that:</div><div><br><b>1 * x^2 + a * xy + b * y^2 + c * x + d * y + e = \
0</b><br></div><div><br></div><div>which also means just 5 variables/equations, not \
6, and less chance of infinite solutions.<br></div><div><br></div><div>Think about it \
this way: it's similar to as if you had an equation for a line looking like this: \
"ax + by + c = 0", which looks correct, but then you'd try having three \
equations to find all three a, b and c, while the line only needs two points to be \
defined, which means just two equations. To represent a line, at least one of a, b, \
or c must not be 0, so there is always a way to reduce the number of equations to 2 \
(though it depends on the data in that case because sometimes you'd have "y \
= 0" (so a = 0, b = 1, c = 0) and sometimes you'd have "x = 0" (a \
= 1, b = 0, c = 0)).</div><div><br></div><div>-----<br></div><div><br></div></div>Also<br>> \
I need to solve a system of linear equations for six variables and this is \
<b>probably</b> complicated.<br></div><div>Actually, you'd probably just have to \
put it all into a matrix and a vector and ask Eigen to solve it for you. It's a \
very basic operation (it's not trivial to write yourself, though it wouldn't \
be very difficult either, but it's so common of a need that I would be surprised \
to learn that some library offering matrix operations doesn't provide it out of \
the box. As an example, in languages "octave" (foss) and "matlab" \
(proprietary) you can solve a system of linear equations just by writing a few \
characters: "x = A\b" (note the backslash instead of slash) when A is the \
matrix of coefficients and b is the vector of constant terms. And x is the solution \
vector. The original equation system is Ax = b).<br></div><div>In Eigen you'll \
probably have to write a few more characters than that, but it should be fairly easy, \
too :)<br></div><div>For Eigen, here you have documentation that explains what needs \
to be written: <a href="https://eigen.tuxfamily.org/dox/group__TutorialLinearAlgebra.html" \
target="_blank">https://eigen.tuxfamily.org/dox/group__TutorialLinearAlgebra.html</a><br></div><div>And \
for usage of Eigen in Krita, you can refer to the \
file:<br>libs/global/kis_algebra_2d.cpp<br></div><div><br></div><div>**<b>Method \
2</b>**<br></div><div>I think there should be a way, but I don't know yet, but \
also you have Method 1 already figured out, so maybe it's not necessarily \
needed.<br></div><div><br>---</div><div><br></div><div>Hope that \
helps,</div><div>Tiar</div><div><br></div><div>PS. If anything is unclear, feel free \
to ask, either here or on IRC (tiar). \
<br></div><div><br></div><div><br></div></div><br><div class="gmail_quote"><div \
dir="ltr" class="gmail_attr">niedz., 13 mar 2022 o 19:04 Srirupa Datta <<a \
href="mailto:srirupa.sps@gmail.com" target="_blank">srirupa.sps@gmail.com</a>> \
napisał(a):<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px \
0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">I have \
a quadrilateral, whose 4 corners are known, and an inscribed ellipse whose touching \
points with the quadrilateral and also known. I need to find out the extreme points \
of the major axis of that ellipse. <div><br></div><div><b>Method 1</b></div><div>I \
decided to first find out the equation of the inscribed ellipse. <a \
href="https://drive.google.com/file/d/1mMT9to50lJN1eo2SPQh3jJB_puvb-SBj/view?usp=sharing" \
target="_blank">This</a> is what I did so far. However this approach has a challenge. \
I need to solve a system of linear equations for six variables and this is \
<b>probably</b> complicated. So I'm not sure if this is at all the right \
approach. <br></div><div><br></div><div>Also, I got stuck since I expected the \
solution to be a unique one. </div><div><br></div><div><b>Method 2</b></div><div>I \
have the transformation matrix that maps a unit square to my quadrilateral. Is there \
any way I can use transformation mathematics to solve this problem easily? \
</div><div><br></div><div>Thanks,</div><div>Srirupa</div><div><br></div><div><br></div></div>
</blockquote></div>
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic