Mixing
Determine if a point is in a rotated hyperellipsoid
$begingroup$
I asked this question a few days ago. I am implementing an algorithm to test whether a set of points is within an hyper-ellipsoid (HE). That post provided the correct answer for a non-rotated HE centered at the origin. However, I need a solution for an HE that is not at the origin and may be rotated in any dimension.
So, either I rotate all my data points (I assume, relative to the center of the HE?) or I account for the position and rotation of the HE. In either case, I am unsure of how to proceed.
From the answer to my previous question I get that there is a pattern that generalizes to n-dimensions:
$$
left( {x over a} right) ^2 + left({y over b}right) ^2 + left({z over c}right) ^2 + ldots left( {n over d_n }right) ^2 le 1
$$
And, after a bit more research, I see for the 2-dimensional case that rotations and translations can be accounted for by the following:
$$
cfrac{
left(
cos (alpha)(x_p - x_0) +
sin (alpha)(y_p - y_0)
right)^2
}{a^2} +
cfrac{
left(
sin (alpha)(x_p - x_0) -
cos (alpha)(y_p - y_0)
right)^2
}{b^2}
le 1
$$
where:
$x_p$, $y_p$ are the data point coordinates
$x_0$, $y_0$ are the coordinates of the HE center
$alpha$ is the rotation angle in x, y of the HE
$a$, $b$ are the half-length axes of the HE
So, how does this generalize to the n-dimensional case? Is there a similar predictable pattern that emerges in the trigonometry?
geometry trigonometry
asked Feb 1 at 0:00
FiverFiver
1105
$endgroup$
add a comment |
$begingroup$
I asked this question a few days ago. I am implementing an algorithm to test whether a set of points is within an hyper-ellipsoid (HE). That post provided the correct answer for a non-rotated HE centered at the origin. However, I need a solution for an HE that is not at the origin and may be rotated in any dimension.
So, either I rotate all my data points (I assume, relative to the center of the HE?) or I account for the position and rotation of the HE. In either case, I am unsure of how to proceed.
From the answer to my previous question I get that there is a pattern that generalizes to n-dimensions:
$$
left( {x over a} right) ^2 + left({y over b}right) ^2 + left({z over c}right) ^2 + ldots left( {n over d_n }right) ^2 le 1
$$
And, after a bit more research, I see for the 2-dimensional case that rotations and translations can be accounted for by the following:
$$
cfrac{
left(
cos (alpha)(x_p - x_0) +
sin (alpha)(y_p - y_0)
right)^2
}{a^2} +
cfrac{
left(
sin (alpha)(x_p - x_0) -
cos (alpha)(y_p - y_0)
right)^2
}{b^2}
le 1
$$
where:
$x_p$, $y_p$ are the data point coordinates
$x_0$, $y_0$ are the coordinates of the HE center
$alpha$ is the rotation angle in x, y of the HE
$a$, $b$ are the half-length axes of the HE
So, how does this generalize to the n-dimensional case? Is there a similar predictable pattern that emerges in the trigonometry?
geometry trigonometry
asked Feb 1 at 0:00
FiverFiver
1105
$endgroup$
add a comment |
$begingroup$
I asked this question a few days ago. I am implementing an algorithm to test whether a set of points is within an hyper-ellipsoid (HE). That post provided the correct answer for a non-rotated HE centered at the origin. However, I need a solution for an HE that is not at the origin and may be rotated in any dimension.
So, either I rotate all my data points (I assume, relative to the center of the HE?) or I account for the position and rotation of the HE. In either case, I am unsure of how to proceed.
From the answer to my previous question I get that there is a pattern that generalizes to n-dimensions:
$$
left( {x over a} right) ^2 + left({y over b}right) ^2 + left({z over c}right) ^2 + ldots left( {n over d_n }right) ^2 le 1
$$
And, after a bit more research, I see for the 2-dimensional case that rotations and translations can be accounted for by the following:
$$
cfrac{
left(
cos (alpha)(x_p - x_0) +
sin (alpha)(y_p - y_0)
right)^2
}{a^2} +
cfrac{
left(
sin (alpha)(x_p - x_0) -
cos (alpha)(y_p - y_0)
right)^2
}{b^2}
le 1
$$
where:
$x_p$, $y_p$ are the data point coordinates
$x_0$, $y_0$ are the coordinates of the HE center
$alpha$ is the rotation angle in x, y of the HE
$a$, $b$ are the half-length axes of the HE
So, how does this generalize to the n-dimensional case? Is there a similar predictable pattern that emerges in the trigonometry?
geometry trigonometry
asked Feb 1 at 0:00
FiverFiver
1105
$endgroup$
I asked this question a few days ago. I am implementing an algorithm to test whether a set of points is within an hyper-ellipsoid (HE). That post provided the correct answer for a non-rotated HE centered at the origin. However, I need a solution for an HE that is not at the origin and may be rotated in any dimension.
So, either I rotate all my data points (I assume, relative to the center of the HE?) or I account for the position and rotation of the HE. In either case, I am unsure of how to proceed.
From the answer to my previous question I get that there is a pattern that generalizes to n-dimensions:
$$
left( {x over a} right) ^2 + left({y over b}right) ^2 + left({z over c}right) ^2 + ldots left( {n over d_n }right) ^2 le 1
$$
And, after a bit more research, I see for the 2-dimensional case that rotations and translations can be accounted for by the following:
$$
cfrac{
left(
cos (alpha)(x_p - x_0) +
sin (alpha)(y_p - y_0)
right)^2
}{a^2} +
cfrac{
left(
sin (alpha)(x_p - x_0) -
cos (alpha)(y_p - y_0)
right)^2
}{b^2}
le 1
$$
where:
$x_p$, $y_p$ are the data point coordinates
$x_0$, $y_0$ are the coordinates of the HE center
$alpha$ is the rotation angle in x, y of the HE
$a$, $b$ are the half-length axes of the HE
So, how does this generalize to the n-dimensional case? Is there a similar predictable pattern that emerges in the trigonometry?
geometry trigonometry
geometry trigonometry
asked Feb 1 at 0:00
FiverFiver
1105
asked Feb 1 at 0:00
FiverFiver
1105
edited Feb 1 at 0:06
Fiver
asked Feb 1 at 0:00
FiverFiver
1105
asked Feb 1 at 0:00
FiverFiver
1105
asked Feb 1 at 0:00
FiverFiver
1105
1105
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
First, rewrite your original test slightly as $${x_1^2over a_1^2}+cdots+{x_n^2over a_n^2}-1le0.$$ Any orientation-preserving affine transformation will preserve the direction of the inequality, so you can either transform all of your points into this “standard” coordinate system and test them against this relatively simple inequality or transform the ellipsoid into the coordinate system of the data and test the points against a potentially more complex expression. I suspect that doing the former will be more efficient.
As for how to transform the equation of the ellipsoid, it’s easiest for me to describe in matrix form. Any quadric can be expressed by an equation of the form $mathbf x^TQmathbf x=0$, where $Q$ is a symmetric matrix and $mathbf x^T=(x_1,dots,x_n,1)$. Under the point transformation $mathbf x'=Mmathbf x$, substituting for $mathbf x$ gives $(M^{-1}mathbf x')^TQ(M^{-1}mathbf x')={mathbf x'}^T(M^{-T}QM^{-1})mathbf x'$, so the matrix of the transformed quadric is $Q'=M^{-T}QM^{-1}$. For your application, the standardized ellipsoid that you’d be starting with has the matrix $Q = operatorname{diag}(1/a_1^2,dots,1/a_n^2,-1)$.
answered Feb 1 at 1:08
amdamd
31.6k21052
$endgroup$
$begingroup$
Thanks! One more clarification...the ellipsoids are defined as a set of center co-ords w/ a covariance matrix. My plan: 1) Get the half-lengths from the eigenvalues to construct the non-rotated ellipsoid at the origin. 2) Translate the data points by the center coordinates. 3) Apply the inverse of the covariance to the points. 4) Do the inequality check you've given. Does that sound correct?
$endgroup$
– Fiver
Feb 1 at 22:08
$begingroup$
@Fiver Not quite. You’re going to need the principal components (axes) of the ellipsoid in order to construct the correct rotation. Inverting the covariance matrix produces the dual to the ellipsoid, which is not at all what you want for this.
$endgroup$
– amd
Feb 2 at 0:13
$begingroup$
Does the eigenvector provide the principal components? If not, how do I derive them?
$endgroup$
– Fiver
Feb 2 at 2:40
$begingroup$
@Fiver Yes, though if there are repeated eigenvalues you might need to orthogonalize.
$endgroup$
– amd
Feb 2 at 3:01
$begingroup$
Got it, it's working now for n-dimensions! Thank you!
$endgroup$
– Fiver
Feb 3 at 0:05
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3095651%2fdetermine-if-a-point-is-in-a-rotated-hyperellipsoid%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
First, rewrite your original test slightly as $${x_1^2over a_1^2}+cdots+{x_n^2over a_n^2}-1le0.$$ Any orientation-preserving affine transformation will preserve the direction of the inequality, so you can either transform all of your points into this “standard” coordinate system and test them against this relatively simple inequality or transform the ellipsoid into the coordinate system of the data and test the points against a potentially more complex expression. I suspect that doing the former will be more efficient.
As for how to transform the equation of the ellipsoid, it’s easiest for me to describe in matrix form. Any quadric can be expressed by an equation of the form $mathbf x^TQmathbf x=0$, where $Q$ is a symmetric matrix and $mathbf x^T=(x_1,dots,x_n,1)$. Under the point transformation $mathbf x'=Mmathbf x$, substituting for $mathbf x$ gives $(M^{-1}mathbf x')^TQ(M^{-1}mathbf x')={mathbf x'}^T(M^{-T}QM^{-1})mathbf x'$, so the matrix of the transformed quadric is $Q'=M^{-T}QM^{-1}$. For your application, the standardized ellipsoid that you’d be starting with has the matrix $Q = operatorname{diag}(1/a_1^2,dots,1/a_n^2,-1)$.
answered Feb 1 at 1:08
amdamd
31.6k21052
$endgroup$
$begingroup$
Thanks! One more clarification...the ellipsoids are defined as a set of center co-ords w/ a covariance matrix. My plan: 1) Get the half-lengths from the eigenvalues to construct the non-rotated ellipsoid at the origin. 2) Translate the data points by the center coordinates. 3) Apply the inverse of the covariance to the points. 4) Do the inequality check you've given. Does that sound correct?
$endgroup$
– Fiver
Feb 1 at 22:08
$begingroup$
@Fiver Not quite. You’re going to need the principal components (axes) of the ellipsoid in order to construct the correct rotation. Inverting the covariance matrix produces the dual to the ellipsoid, which is not at all what you want for this.
$endgroup$
– amd
Feb 2 at 0:13
$begingroup$
Does the eigenvector provide the principal components? If not, how do I derive them?
$endgroup$
– Fiver
Feb 2 at 2:40
$begingroup$
@Fiver Yes, though if there are repeated eigenvalues you might need to orthogonalize.
$endgroup$
– amd
Feb 2 at 3:01
$begingroup$
Got it, it's working now for n-dimensions! Thank you!
$endgroup$
– Fiver
Feb 3 at 0:05
add a comment |
$begingroup$
First, rewrite your original test slightly as $${x_1^2over a_1^2}+cdots+{x_n^2over a_n^2}-1le0.$$ Any orientation-preserving affine transformation will preserve the direction of the inequality, so you can either transform all of your points into this “standard” coordinate system and test them against this relatively simple inequality or transform the ellipsoid into the coordinate system of the data and test the points against a potentially more complex expression. I suspect that doing the former will be more efficient.
As for how to transform the equation of the ellipsoid, it’s easiest for me to describe in matrix form. Any quadric can be expressed by an equation of the form $mathbf x^TQmathbf x=0$, where $Q$ is a symmetric matrix and $mathbf x^T=(x_1,dots,x_n,1)$. Under the point transformation $mathbf x'=Mmathbf x$, substituting for $mathbf x$ gives $(M^{-1}mathbf x')^TQ(M^{-1}mathbf x')={mathbf x'}^T(M^{-T}QM^{-1})mathbf x'$, so the matrix of the transformed quadric is $Q'=M^{-T}QM^{-1}$. For your application, the standardized ellipsoid that you’d be starting with has the matrix $Q = operatorname{diag}(1/a_1^2,dots,1/a_n^2,-1)$.
answered Feb 1 at 1:08
amdamd
31.6k21052
$endgroup$
$begingroup$
Thanks! One more clarification...the ellipsoids are defined as a set of center co-ords w/ a covariance matrix. My plan: 1) Get the half-lengths from the eigenvalues to construct the non-rotated ellipsoid at the origin. 2) Translate the data points by the center coordinates. 3) Apply the inverse of the covariance to the points. 4) Do the inequality check you've given. Does that sound correct?
$endgroup$
– Fiver
Feb 1 at 22:08
$begingroup$
@Fiver Not quite. You’re going to need the principal components (axes) of the ellipsoid in order to construct the correct rotation. Inverting the covariance matrix produces the dual to the ellipsoid, which is not at all what you want for this.
$endgroup$
– amd
Feb 2 at 0:13
$begingroup$
Does the eigenvector provide the principal components? If not, how do I derive them?
$endgroup$
– Fiver
Feb 2 at 2:40
$begingroup$
@Fiver Yes, though if there are repeated eigenvalues you might need to orthogonalize.
$endgroup$
– amd
Feb 2 at 3:01
$begingroup$
Got it, it's working now for n-dimensions! Thank you!
$endgroup$
– Fiver
Feb 3 at 0:05
add a comment |
$begingroup$
First, rewrite your original test slightly as $${x_1^2over a_1^2}+cdots+{x_n^2over a_n^2}-1le0.$$ Any orientation-preserving affine transformation will preserve the direction of the inequality, so you can either transform all of your points into this “standard” coordinate system and test them against this relatively simple inequality or transform the ellipsoid into the coordinate system of the data and test the points against a potentially more complex expression. I suspect that doing the former will be more efficient.
As for how to transform the equation of the ellipsoid, it’s easiest for me to describe in matrix form. Any quadric can be expressed by an equation of the form $mathbf x^TQmathbf x=0$, where $Q$ is a symmetric matrix and $mathbf x^T=(x_1,dots,x_n,1)$. Under the point transformation $mathbf x'=Mmathbf x$, substituting for $mathbf x$ gives $(M^{-1}mathbf x')^TQ(M^{-1}mathbf x')={mathbf x'}^T(M^{-T}QM^{-1})mathbf x'$, so the matrix of the transformed quadric is $Q'=M^{-T}QM^{-1}$. For your application, the standardized ellipsoid that you’d be starting with has the matrix $Q = operatorname{diag}(1/a_1^2,dots,1/a_n^2,-1)$.
answered Feb 1 at 1:08
amdamd
31.6k21052
$endgroup$
First, rewrite your original test slightly as $${x_1^2over a_1^2}+cdots+{x_n^2over a_n^2}-1le0.$$ Any orientation-preserving affine transformation will preserve the direction of the inequality, so you can either transform all of your points into this “standard” coordinate system and test them against this relatively simple inequality or transform the ellipsoid into the coordinate system of the data and test the points against a potentially more complex expression. I suspect that doing the former will be more efficient.
As for how to transform the equation of the ellipsoid, it’s easiest for me to describe in matrix form. Any quadric can be expressed by an equation of the form $mathbf x^TQmathbf x=0$, where $Q$ is a symmetric matrix and $mathbf x^T=(x_1,dots,x_n,1)$. Under the point transformation $mathbf x'=Mmathbf x$, substituting for $mathbf x$ gives $(M^{-1}mathbf x')^TQ(M^{-1}mathbf x')={mathbf x'}^T(M^{-T}QM^{-1})mathbf x'$, so the matrix of the transformed quadric is $Q'=M^{-T}QM^{-1}$. For your application, the standardized ellipsoid that you’d be starting with has the matrix $Q = operatorname{diag}(1/a_1^2,dots,1/a_n^2,-1)$.
answered Feb 1 at 1:08
amdamd
31.6k21052
answered Feb 1 at 1:08
amdamd
31.6k21052
answered Feb 1 at 1:08
amdamd
31.6k21052
answered Feb 1 at 1:08
amdamd
31.6k21052
31.6k21052
$begingroup$
Thanks! One more clarification...the ellipsoids are defined as a set of center co-ords w/ a covariance matrix. My plan: 1) Get the half-lengths from the eigenvalues to construct the non-rotated ellipsoid at the origin. 2) Translate the data points by the center coordinates. 3) Apply the inverse of the covariance to the points. 4) Do the inequality check you've given. Does that sound correct?
$endgroup$
– Fiver
Feb 1 at 22:08
$begingroup$
@Fiver Not quite. You’re going to need the principal components (axes) of the ellipsoid in order to construct the correct rotation. Inverting the covariance matrix produces the dual to the ellipsoid, which is not at all what you want for this.
$endgroup$
– amd
Feb 2 at 0:13
$begingroup$
Does the eigenvector provide the principal components? If not, how do I derive them?
$endgroup$
– Fiver
Feb 2 at 2:40
$begingroup$
@Fiver Yes, though if there are repeated eigenvalues you might need to orthogonalize.
$endgroup$
– amd
Feb 2 at 3:01
$begingroup$
Got it, it's working now for n-dimensions! Thank you!
$endgroup$
– Fiver
Feb 3 at 0:05
add a comment |
$begingroup$
Thanks! One more clarification...the ellipsoids are defined as a set of center co-ords w/ a covariance matrix. My plan: 1) Get the half-lengths from the eigenvalues to construct the non-rotated ellipsoid at the origin. 2) Translate the data points by the center coordinates. 3) Apply the inverse of the covariance to the points. 4) Do the inequality check you've given. Does that sound correct?
$endgroup$
– Fiver
Feb 1 at 22:08
$begingroup$
@Fiver Not quite. You’re going to need the principal components (axes) of the ellipsoid in order to construct the correct rotation. Inverting the covariance matrix produces the dual to the ellipsoid, which is not at all what you want for this.
$endgroup$
– amd
Feb 2 at 0:13
$begingroup$
Does the eigenvector provide the principal components? If not, how do I derive them?
$endgroup$
– Fiver
Feb 2 at 2:40
$begingroup$
@Fiver Yes, though if there are repeated eigenvalues you might need to orthogonalize.
$endgroup$
– amd
Feb 2 at 3:01
$begingroup$
Got it, it's working now for n-dimensions! Thank you!
$endgroup$
– Fiver
Feb 3 at 0:05
$begingroup$
Thanks! One more clarification...the ellipsoids are defined as a set of center co-ords w/ a covariance matrix. My plan: 1) Get the half-lengths from the eigenvalues to construct the non-rotated ellipsoid at the origin. 2) Translate the data points by the center coordinates. 3) Apply the inverse of the covariance to the points. 4) Do the inequality check you've given. Does that sound correct?
$endgroup$
– Fiver
Feb 1 at 22:08
$begingroup$
Thanks! One more clarification...the ellipsoids are defined as a set of center co-ords w/ a covariance matrix. My plan: 1) Get the half-lengths from the eigenvalues to construct the non-rotated ellipsoid at the origin. 2) Translate the data points by the center coordinates. 3) Apply the inverse of the covariance to the points. 4) Do the inequality check you've given. Does that sound correct?
$endgroup$
– Fiver
Feb 1 at 22:08
$begingroup$
@Fiver Not quite. You’re going to need the principal components (axes) of the ellipsoid in order to construct the correct rotation. Inverting the covariance matrix produces the dual to the ellipsoid, which is not at all what you want for this.
$endgroup$
– amd
Feb 2 at 0:13
$begingroup$
@Fiver Not quite. You’re going to need the principal components (axes) of the ellipsoid in order to construct the correct rotation. Inverting the covariance matrix produces the dual to the ellipsoid, which is not at all what you want for this.
$endgroup$
– amd
Feb 2 at 0:13
$begingroup$
Does the eigenvector provide the principal components? If not, how do I derive them?
$endgroup$
– Fiver
Feb 2 at 2:40
$begingroup$
Does the eigenvector provide the principal components? If not, how do I derive them?
$endgroup$
– Fiver
Feb 2 at 2:40
$begingroup$
@Fiver Yes, though if there are repeated eigenvalues you might need to orthogonalize.
$endgroup$
– amd
Feb 2 at 3:01
$begingroup$
@Fiver Yes, though if there are repeated eigenvalues you might need to orthogonalize.
$endgroup$
– amd
Feb 2 at 3:01
$begingroup$
Got it, it's working now for n-dimensions! Thank you!
$endgroup$
– Fiver
Feb 3 at 0:05
$begingroup$
Got it, it's working now for n-dimensions! Thank you!
$endgroup$
– Fiver
Feb 3 at 0:05
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3095651%2fdetermine-if-a-point-is-in-a-rotated-hyperellipsoid%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
