maximum curvature of 2D Cubic Bezier
Given a 2D cubic Bezier segment defined by $P_0, P_1, P_2, P_3$, here's what I want:
A function that takes the segment and outputs the maximum curvature without using an iterative approach.
I have a function that finds the maximum curvature at the moment, but does this using Brent's Method to search a range of $t$ on $[0, 1]$. It fails to find the maximum curvature $5%$ of the time. In addition, I really need the Jacobian of the method to help my optimization algorithms. Brent's Method (or any kind of iterative search) makes this impossible.
I recognize that this is a difficult function to deal with by hand, but perhaps someone with access to some nice software and a fancy machine could crank out a function to find the maximum curvature of a cubic Bezier? Something that symbolically returns the roots of solving the derivative of the curvature? Thanks for your time.
derivatives curvature bezier-curve
edited Apr 24 '17 at 16:43
Widawensen
4,42121445
asked Jul 2 '14 at 21:03
Brannon
1205
add a comment |
Given a 2D cubic Bezier segment defined by $P_0, P_1, P_2, P_3$, here's what I want:
A function that takes the segment and outputs the maximum curvature without using an iterative approach.
I have a function that finds the maximum curvature at the moment, but does this using Brent's Method to search a range of $t$ on $[0, 1]$. It fails to find the maximum curvature $5%$ of the time. In addition, I really need the Jacobian of the method to help my optimization algorithms. Brent's Method (or any kind of iterative search) makes this impossible.
I recognize that this is a difficult function to deal with by hand, but perhaps someone with access to some nice software and a fancy machine could crank out a function to find the maximum curvature of a cubic Bezier? Something that symbolically returns the roots of solving the derivative of the curvature? Thanks for your time.
derivatives curvature bezier-curve
edited Apr 24 '17 at 16:43
Widawensen
4,42121445
asked Jul 2 '14 at 21:03
Brannon
1205
add a comment |
Given a 2D cubic Bezier segment defined by $P_0, P_1, P_2, P_3$, here's what I want:
A function that takes the segment and outputs the maximum curvature without using an iterative approach.
I have a function that finds the maximum curvature at the moment, but does this using Brent's Method to search a range of $t$ on $[0, 1]$. It fails to find the maximum curvature $5%$ of the time. In addition, I really need the Jacobian of the method to help my optimization algorithms. Brent's Method (or any kind of iterative search) makes this impossible.
I recognize that this is a difficult function to deal with by hand, but perhaps someone with access to some nice software and a fancy machine could crank out a function to find the maximum curvature of a cubic Bezier? Something that symbolically returns the roots of solving the derivative of the curvature? Thanks for your time.
derivatives curvature bezier-curve
edited Apr 24 '17 at 16:43
Widawensen
4,42121445
asked Jul 2 '14 at 21:03
Brannon
1205
Given a 2D cubic Bezier segment defined by $P_0, P_1, P_2, P_3$, here's what I want:
A function that takes the segment and outputs the maximum curvature without using an iterative approach.
I have a function that finds the maximum curvature at the moment, but does this using Brent's Method to search a range of $t$ on $[0, 1]$. It fails to find the maximum curvature $5%$ of the time. In addition, I really need the Jacobian of the method to help my optimization algorithms. Brent's Method (or any kind of iterative search) makes this impossible.
I recognize that this is a difficult function to deal with by hand, but perhaps someone with access to some nice software and a fancy machine could crank out a function to find the maximum curvature of a cubic Bezier? Something that symbolically returns the roots of solving the derivative of the curvature? Thanks for your time.
derivatives curvature bezier-curve
derivatives curvature bezier-curve
edited Apr 24 '17 at 16:43
Widawensen
4,42121445
asked Jul 2 '14 at 21:03
Brannon
1205
edited Apr 24 '17 at 16:43
Widawensen
4,42121445
asked Jul 2 '14 at 21:03
Brannon
1205
edited Apr 24 '17 at 16:43
Widawensen
4,42121445
edited Apr 24 '17 at 16:43
Widawensen
4,42121445
edited Apr 24 '17 at 16:43
Widawensen
4,42121445
4,42121445
asked Jul 2 '14 at 21:03
Brannon
1205
asked Jul 2 '14 at 21:03
Brannon
1205
asked Jul 2 '14 at 21:03
Brannon
1205
1205
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
I computed the curvature and its derivative symbolically. The numerator of the derivative expression is a polynomial of degree 5. So, unless there is some way to factor it or simplify it (which I don't see), there's no hope of finding formulae for its roots.
I'm surprised that Brent's method fails so often. I would have expected it to succeed almost always. Maybe you should do some more testing your root finder, before proceeding.
If the end goal is to minimise maximum curvature, the only option I see is to use a minimization algorithm that doesn't require derivatives. Actually, the ones that claim they don't need derivatives often have internal procedures that estimate derivatives numerically. But, no matter -- at least you don't have to provide derivatives.
answered Jul 3 '14 at 5:04
bubba
30k32986
We've had much better success with clothoids.
– Brannon
Jan 8 at 5:21
add a comment |
I found this while trying to solve similar problem:
PDF:Curvature extrema of planar parametric polynomial
cubic curves
Start reading from 8. Conclusion, they classify curves based on easy to check features like presence of loops & cusps, giving number and coarse positions of curvature extremes.
answered Apr 24 '17 at 15:29
Anonymous
1012
Perhaps this is more of a comment than an answer.
– mlc
Apr 24 '17 at 15:40
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%2f854757%2fmaximum-curvature-of-2d-cubic-bezier%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
I computed the curvature and its derivative symbolically. The numerator of the derivative expression is a polynomial of degree 5. So, unless there is some way to factor it or simplify it (which I don't see), there's no hope of finding formulae for its roots.
I'm surprised that Brent's method fails so often. I would have expected it to succeed almost always. Maybe you should do some more testing your root finder, before proceeding.
If the end goal is to minimise maximum curvature, the only option I see is to use a minimization algorithm that doesn't require derivatives. Actually, the ones that claim they don't need derivatives often have internal procedures that estimate derivatives numerically. But, no matter -- at least you don't have to provide derivatives.
answered Jul 3 '14 at 5:04
bubba
30k32986
We've had much better success with clothoids.
– Brannon
Jan 8 at 5:21
add a comment |
I computed the curvature and its derivative symbolically. The numerator of the derivative expression is a polynomial of degree 5. So, unless there is some way to factor it or simplify it (which I don't see), there's no hope of finding formulae for its roots.
I'm surprised that Brent's method fails so often. I would have expected it to succeed almost always. Maybe you should do some more testing your root finder, before proceeding.
If the end goal is to minimise maximum curvature, the only option I see is to use a minimization algorithm that doesn't require derivatives. Actually, the ones that claim they don't need derivatives often have internal procedures that estimate derivatives numerically. But, no matter -- at least you don't have to provide derivatives.
answered Jul 3 '14 at 5:04
bubba
30k32986
We've had much better success with clothoids.
– Brannon
Jan 8 at 5:21
add a comment |
I computed the curvature and its derivative symbolically. The numerator of the derivative expression is a polynomial of degree 5. So, unless there is some way to factor it or simplify it (which I don't see), there's no hope of finding formulae for its roots.
I'm surprised that Brent's method fails so often. I would have expected it to succeed almost always. Maybe you should do some more testing your root finder, before proceeding.
If the end goal is to minimise maximum curvature, the only option I see is to use a minimization algorithm that doesn't require derivatives. Actually, the ones that claim they don't need derivatives often have internal procedures that estimate derivatives numerically. But, no matter -- at least you don't have to provide derivatives.
answered Jul 3 '14 at 5:04
bubba
30k32986
I computed the curvature and its derivative symbolically. The numerator of the derivative expression is a polynomial of degree 5. So, unless there is some way to factor it or simplify it (which I don't see), there's no hope of finding formulae for its roots.
I'm surprised that Brent's method fails so often. I would have expected it to succeed almost always. Maybe you should do some more testing your root finder, before proceeding.
If the end goal is to minimise maximum curvature, the only option I see is to use a minimization algorithm that doesn't require derivatives. Actually, the ones that claim they don't need derivatives often have internal procedures that estimate derivatives numerically. But, no matter -- at least you don't have to provide derivatives.
answered Jul 3 '14 at 5:04
bubba
30k32986
answered Jul 3 '14 at 5:04
bubba
30k32986
answered Jul 3 '14 at 5:04
bubba
30k32986
answered Jul 3 '14 at 5:04
bubba
30k32986
30k32986
We've had much better success with clothoids.
– Brannon
Jan 8 at 5:21
add a comment |
We've had much better success with clothoids.
– Brannon
Jan 8 at 5:21
We've had much better success with clothoids.
– Brannon
Jan 8 at 5:21
We've had much better success with clothoids.
– Brannon
Jan 8 at 5:21
add a comment |
I found this while trying to solve similar problem:
PDF:Curvature extrema of planar parametric polynomial
cubic curves
Start reading from 8. Conclusion, they classify curves based on easy to check features like presence of loops & cusps, giving number and coarse positions of curvature extremes.
answered Apr 24 '17 at 15:29
Anonymous
1012
Perhaps this is more of a comment than an answer.
– mlc
Apr 24 '17 at 15:40
add a comment |
I found this while trying to solve similar problem:
PDF:Curvature extrema of planar parametric polynomial
cubic curves
Start reading from 8. Conclusion, they classify curves based on easy to check features like presence of loops & cusps, giving number and coarse positions of curvature extremes.
answered Apr 24 '17 at 15:29
Anonymous
1012
Perhaps this is more of a comment than an answer.
– mlc
Apr 24 '17 at 15:40
add a comment |
I found this while trying to solve similar problem:
PDF:Curvature extrema of planar parametric polynomial
cubic curves
Start reading from 8. Conclusion, they classify curves based on easy to check features like presence of loops & cusps, giving number and coarse positions of curvature extremes.
answered Apr 24 '17 at 15:29
Anonymous
1012
I found this while trying to solve similar problem:
PDF:Curvature extrema of planar parametric polynomial
cubic curves
Start reading from 8. Conclusion, they classify curves based on easy to check features like presence of loops & cusps, giving number and coarse positions of curvature extremes.
answered Apr 24 '17 at 15:29
Anonymous
1012
answered Apr 24 '17 at 15:29
Anonymous
1012
answered Apr 24 '17 at 15:29
Anonymous
1012
answered Apr 24 '17 at 15:29
Anonymous
1012
1012
Perhaps this is more of a comment than an answer.
– mlc
Apr 24 '17 at 15:40
add a comment |
Perhaps this is more of a comment than an answer.
– mlc
Apr 24 '17 at 15:40
Perhaps this is more of a comment than an answer.
– mlc
Apr 24 '17 at 15:40
Perhaps this is more of a comment than an answer.
– mlc
Apr 24 '17 at 15:40
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f854757%2fmaximum-curvature-of-2d-cubic-bezier%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
