[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-kimageshop
Subject: Re: Perspective Ellipse Math for SoK'22
From: Srirupa Datta <srirupa.sps () gmail ! com>
Date: 2022-03-18 9:25:18
Message-ID: CAN9L-CEQvOdv00J2PPDeSM4AFcxQtEnHkOn2MB2C0BcVoRuBHg () mail ! gmail ! com
[Download RAW message or body]
Hey Tiar,
Sorry it took me some time to respond back. Thanks for helping out, your
answer was pretty detailed! I went through your explanation, and the
reduction by *a *(*1 * x^2 + a * xy + b * y^2 + c * x + d * y + e = 0*)
seems convincing. I will try this out.
Thanks,
Srirupa
On Mon, Mar 14, 2022 at 12:32 PM Tymon Dąbrowski <tamtamy.tymona@gmail.com>
wrote:
> 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">Hey Tiar, <div><br><div>Sorry it took me some time to respond back. \
Thanks for helping out, your answer was pretty detailed! I went through your \
explanation, and the reduction by <b>a </b>(<b>1 * x^2 + a * xy + b * y^2 + c * x + d \
* y + e = 0</b>) seems convincing. I will try this out. \
</div><div><br></div><div>Thanks,</div><div>Srirupa</div><div></div><div><br></div></div></div><br><div \
class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Mar 14, 2022 at 12:32 \
PM Tymon Dąbrowski <<a \
href="mailto:tamtamy.tymona@gmail.com">tamtamy.tymona@gmail.com</a>> \
wrote:<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"><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>
</blockquote></div>
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic