“fastest” curve through n points
I'm programming an AI for a race game, where my car has to drive through some checkpoints. If I let it drive straight in direction of the checkpoints, it has to slow down and make a huge turn after each checkpoint.
So I thought, I could calculate a curve through this checkpoints, which should be a trade-off between having the least possible curvature and being as short as possible.
If I have for example this 4 checkpoints:
begin{align*}
&A(6,8)\
&B(10,2)\
&C(6,3)\
&D(2,2)
end{align*}
Then the curve should look approximately like this.
How can I calculate this? It has something to do with splines, but I'm not a mathematician and it's quite hard for me to find some understandable sources.
I think the easiest for me, would be, if somebody could provide an example, how to calculate the curve in my example?
curves spline
asked Nov 25 at 14:45
Josef Zoller
143
|
show 2 more comments
I'm programming an AI for a race game, where my car has to drive through some checkpoints. If I let it drive straight in direction of the checkpoints, it has to slow down and make a huge turn after each checkpoint.
So I thought, I could calculate a curve through this checkpoints, which should be a trade-off between having the least possible curvature and being as short as possible.
If I have for example this 4 checkpoints:
begin{align*}
&A(6,8)\
&B(10,2)\
&C(6,3)\
&D(2,2)
end{align*}
Then the curve should look approximately like this.
How can I calculate this? It has something to do with splines, but I'm not a mathematician and it's quite hard for me to find some understandable sources.
I think the easiest for me, would be, if somebody could provide an example, how to calculate the curve in my example?
curves spline
asked Nov 25 at 14:45
Josef Zoller
143
1
please say me, why my question gets downvoted after one minute. I have no idea what I could have done wrong
– Josef Zoller
Nov 25 at 14:48
1
I didn't downvote but the criterion "least possible curvature" is meaningless as the curvature varies along the curve. In addition, least curvature and short length are contradictory goals. Finally, you have no reason to believe that Adobe Illustrator uses this criteria at all.
– Yves Daoust
Nov 25 at 14:58
3
I think the downvotes are wrong. This is a perfectly reasonable question from a nonmathematician asking for help where mathematics may come into play. The way it's asked makes no literal sense mathematically, but that's no surprise given the source.
– Ethan Bolker
Nov 25 at 15:00
From other comments, I infer that what you are after is a "fastest curve". You fell deep in an XY problem I am afraid.
– Yves Daoust
Nov 25 at 15:00
I'm sorry, when my explanation was bad, but i'm not a native english speaker and It's really hard for me to find the right words, especially describing a hard problem in maths
– Josef Zoller
Nov 25 at 15:01
|
show 2 more comments
I'm programming an AI for a race game, where my car has to drive through some checkpoints. If I let it drive straight in direction of the checkpoints, it has to slow down and make a huge turn after each checkpoint.
So I thought, I could calculate a curve through this checkpoints, which should be a trade-off between having the least possible curvature and being as short as possible.
If I have for example this 4 checkpoints:
begin{align*}
&A(6,8)\
&B(10,2)\
&C(6,3)\
&D(2,2)
end{align*}
Then the curve should look approximately like this.
How can I calculate this? It has something to do with splines, but I'm not a mathematician and it's quite hard for me to find some understandable sources.
I think the easiest for me, would be, if somebody could provide an example, how to calculate the curve in my example?
curves spline
asked Nov 25 at 14:45
Josef Zoller
143
I'm programming an AI for a race game, where my car has to drive through some checkpoints. If I let it drive straight in direction of the checkpoints, it has to slow down and make a huge turn after each checkpoint.
So I thought, I could calculate a curve through this checkpoints, which should be a trade-off between having the least possible curvature and being as short as possible.
If I have for example this 4 checkpoints:
begin{align*}
&A(6,8)\
&B(10,2)\
&C(6,3)\
&D(2,2)
end{align*}
Then the curve should look approximately like this.
How can I calculate this? It has something to do with splines, but I'm not a mathematician and it's quite hard for me to find some understandable sources.
I think the easiest for me, would be, if somebody could provide an example, how to calculate the curve in my example?
curves spline
curves spline
asked Nov 25 at 14:45
Josef Zoller
143
asked Nov 25 at 14:45
Josef Zoller
143
edited Nov 25 at 15:30
asked Nov 25 at 14:45
Josef Zoller
143
asked Nov 25 at 14:45
Josef Zoller
143
asked Nov 25 at 14:45
Josef Zoller
143
143
1
please say me, why my question gets downvoted after one minute. I have no idea what I could have done wrong
– Josef Zoller
Nov 25 at 14:48
1
I didn't downvote but the criterion "least possible curvature" is meaningless as the curvature varies along the curve. In addition, least curvature and short length are contradictory goals. Finally, you have no reason to believe that Adobe Illustrator uses this criteria at all.
– Yves Daoust
Nov 25 at 14:58
3
I think the downvotes are wrong. This is a perfectly reasonable question from a nonmathematician asking for help where mathematics may come into play. The way it's asked makes no literal sense mathematically, but that's no surprise given the source.
– Ethan Bolker
Nov 25 at 15:00
From other comments, I infer that what you are after is a "fastest curve". You fell deep in an XY problem I am afraid.
– Yves Daoust
Nov 25 at 15:00
I'm sorry, when my explanation was bad, but i'm not a native english speaker and It's really hard for me to find the right words, especially describing a hard problem in maths
– Josef Zoller
Nov 25 at 15:01
|
show 2 more comments
1
please say me, why my question gets downvoted after one minute. I have no idea what I could have done wrong
– Josef Zoller
Nov 25 at 14:48
1
I didn't downvote but the criterion "least possible curvature" is meaningless as the curvature varies along the curve. In addition, least curvature and short length are contradictory goals. Finally, you have no reason to believe that Adobe Illustrator uses this criteria at all.
– Yves Daoust
Nov 25 at 14:58
3
I think the downvotes are wrong. This is a perfectly reasonable question from a nonmathematician asking for help where mathematics may come into play. The way it's asked makes no literal sense mathematically, but that's no surprise given the source.
– Ethan Bolker
Nov 25 at 15:00
From other comments, I infer that what you are after is a "fastest curve". You fell deep in an XY problem I am afraid.
– Yves Daoust
Nov 25 at 15:00
I'm sorry, when my explanation was bad, but i'm not a native english speaker and It's really hard for me to find the right words, especially describing a hard problem in maths
– Josef Zoller
Nov 25 at 15:01
1
1
please say me, why my question gets downvoted after one minute. I have no idea what I could have done wrong
– Josef Zoller
Nov 25 at 14:48
please say me, why my question gets downvoted after one minute. I have no idea what I could have done wrong
– Josef Zoller
Nov 25 at 14:48
1
1
I didn't downvote but the criterion "least possible curvature" is meaningless as the curvature varies along the curve. In addition, least curvature and short length are contradictory goals. Finally, you have no reason to believe that Adobe Illustrator uses this criteria at all.
– Yves Daoust
Nov 25 at 14:58
I didn't downvote but the criterion "least possible curvature" is meaningless as the curvature varies along the curve. In addition, least curvature and short length are contradictory goals. Finally, you have no reason to believe that Adobe Illustrator uses this criteria at all.
– Yves Daoust
Nov 25 at 14:58
3
3
I think the downvotes are wrong. This is a perfectly reasonable question from a nonmathematician asking for help where mathematics may come into play. The way it's asked makes no literal sense mathematically, but that's no surprise given the source.
– Ethan Bolker
Nov 25 at 15:00
I think the downvotes are wrong. This is a perfectly reasonable question from a nonmathematician asking for help where mathematics may come into play. The way it's asked makes no literal sense mathematically, but that's no surprise given the source.
– Ethan Bolker
Nov 25 at 15:00
From other comments, I infer that what you are after is a "fastest curve". You fell deep in an XY problem I am afraid.
– Yves Daoust
Nov 25 at 15:00
From other comments, I infer that what you are after is a "fastest curve". You fell deep in an XY problem I am afraid.
– Yves Daoust
Nov 25 at 15:00
I'm sorry, when my explanation was bad, but i'm not a native english speaker and It's really hard for me to find the right words, especially describing a hard problem in maths
– Josef Zoller
Nov 25 at 15:01
I'm sorry, when my explanation was bad, but i'm not a native english speaker and It's really hard for me to find the right words, especially describing a hard problem in maths
– Josef Zoller
Nov 25 at 15:01
|
show 2 more comments
2 Answers
2
active
oldest
votes
The shortest possible curve would connect the points with straight lines. But that would mean essentially infinite curvature when you suddenly change direction. To smooth out the transition you have to lengthen the curve.
That means you have to specify some kind of tradeoff between length and curvature. You are right that various kinds of splines or bezier curves will do that. It's probably what Adobe has done; they keep their calculation under the hood in the software.
Why do you need to do the calculation yourself?
answered Nov 25 at 14:52
Ethan Bolker
40.9k546108
1
I'm programming an AI for a race game through a couple of checkpoints. If my car goes straight in direction of the checkpoint, then it has to slow down and make a huge turn there, so I wanted it to drive on such a curve, which I tried to explain (It seems, that my explanation was very bad)
– Josef Zoller
Nov 25 at 14:57
@JosefZoller That clarifies a lot. You have indeed asked an x-y question: meta.stackexchange.com/questions/66377/what-is-the-xy-problem . I think the real question is finding the fastest track, given the physical characteristics of the car - how fast can it accelerate or decelerate, how fast can it take turns. That's a hard problem. Programmng a bezier curve might give you a good enough answer. You could post it here in much more detail and hope for help.
– Ethan Bolker
Nov 25 at 15:05
Thanks for explaining to me the downvotes. I'll try to improve my question
– Josef Zoller
Nov 25 at 15:08
I think the official name for the area your problem lives in is :"calculus of variations". I doubt that there's a neat solution, but you can post it and hope.
– Ethan Bolker
Nov 25 at 15:12
@Rahul What lovely links - particularly the second one. I hope the OP appreciates them.
– Ethan Bolker
Nov 25 at 15:26
|
show 2 more comments
I think what you are looking for is the so called Minimum Energy Curve (or Minimum Energy Spline), which is constructed by minimizing a certain energy functional of the curve while treating the interpolated points as constraint.
The following shows a typical energy functional
$$E(t) = (1-w)int_0^1{||c'(t)||^2dt} + wint_0^1{kappa(t)^2dt} $$
where $c'(t)$ is the first derivative of the curve $c(t)$, $kappa(t)$ is the curvature of the curve and $0.0 le w le 1.0$. The first integral term represents the stretch energy and the second integral the bending energy of the curve. You can choose to minimize the stretch energy or the bending energy alone by using $w=0.0$ or $1.0$ respectively or you can choose to minimize a combination of both.
Because the existence of the nonlinear term $kappa(t)$, it is often desired to replace the curvature by the second derivative as
$$E_s(t) = (1-w)int_0^1{||c'(t)||^2dt} + wint_0^1{||c''(t)||^2dt} $$
so that the solution can be easily found by solving a linear equation set.
answered Nov 30 at 7:22
fang
2,462166
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%2f3012923%2ffastest-curve-through-n-points%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
The shortest possible curve would connect the points with straight lines. But that would mean essentially infinite curvature when you suddenly change direction. To smooth out the transition you have to lengthen the curve.
That means you have to specify some kind of tradeoff between length and curvature. You are right that various kinds of splines or bezier curves will do that. It's probably what Adobe has done; they keep their calculation under the hood in the software.
Why do you need to do the calculation yourself?
answered Nov 25 at 14:52
Ethan Bolker
40.9k546108
1
I'm programming an AI for a race game through a couple of checkpoints. If my car goes straight in direction of the checkpoint, then it has to slow down and make a huge turn there, so I wanted it to drive on such a curve, which I tried to explain (It seems, that my explanation was very bad)
– Josef Zoller
Nov 25 at 14:57
@JosefZoller That clarifies a lot. You have indeed asked an x-y question: meta.stackexchange.com/questions/66377/what-is-the-xy-problem . I think the real question is finding the fastest track, given the physical characteristics of the car - how fast can it accelerate or decelerate, how fast can it take turns. That's a hard problem. Programmng a bezier curve might give you a good enough answer. You could post it here in much more detail and hope for help.
– Ethan Bolker
Nov 25 at 15:05
Thanks for explaining to me the downvotes. I'll try to improve my question
– Josef Zoller
Nov 25 at 15:08
I think the official name for the area your problem lives in is :"calculus of variations". I doubt that there's a neat solution, but you can post it and hope.
– Ethan Bolker
Nov 25 at 15:12
@Rahul What lovely links - particularly the second one. I hope the OP appreciates them.
– Ethan Bolker
Nov 25 at 15:26
|
show 2 more comments
The shortest possible curve would connect the points with straight lines. But that would mean essentially infinite curvature when you suddenly change direction. To smooth out the transition you have to lengthen the curve.
That means you have to specify some kind of tradeoff between length and curvature. You are right that various kinds of splines or bezier curves will do that. It's probably what Adobe has done; they keep their calculation under the hood in the software.
Why do you need to do the calculation yourself?
answered Nov 25 at 14:52
Ethan Bolker
40.9k546108
1
I'm programming an AI for a race game through a couple of checkpoints. If my car goes straight in direction of the checkpoint, then it has to slow down and make a huge turn there, so I wanted it to drive on such a curve, which I tried to explain (It seems, that my explanation was very bad)
– Josef Zoller
Nov 25 at 14:57
@JosefZoller That clarifies a lot. You have indeed asked an x-y question: meta.stackexchange.com/questions/66377/what-is-the-xy-problem . I think the real question is finding the fastest track, given the physical characteristics of the car - how fast can it accelerate or decelerate, how fast can it take turns. That's a hard problem. Programmng a bezier curve might give you a good enough answer. You could post it here in much more detail and hope for help.
– Ethan Bolker
Nov 25 at 15:05
Thanks for explaining to me the downvotes. I'll try to improve my question
– Josef Zoller
Nov 25 at 15:08
I think the official name for the area your problem lives in is :"calculus of variations". I doubt that there's a neat solution, but you can post it and hope.
– Ethan Bolker
Nov 25 at 15:12
@Rahul What lovely links - particularly the second one. I hope the OP appreciates them.
– Ethan Bolker
Nov 25 at 15:26
|
show 2 more comments
The shortest possible curve would connect the points with straight lines. But that would mean essentially infinite curvature when you suddenly change direction. To smooth out the transition you have to lengthen the curve.
That means you have to specify some kind of tradeoff between length and curvature. You are right that various kinds of splines or bezier curves will do that. It's probably what Adobe has done; they keep their calculation under the hood in the software.
Why do you need to do the calculation yourself?
answered Nov 25 at 14:52
Ethan Bolker
40.9k546108
The shortest possible curve would connect the points with straight lines. But that would mean essentially infinite curvature when you suddenly change direction. To smooth out the transition you have to lengthen the curve.
That means you have to specify some kind of tradeoff between length and curvature. You are right that various kinds of splines or bezier curves will do that. It's probably what Adobe has done; they keep their calculation under the hood in the software.
Why do you need to do the calculation yourself?
answered Nov 25 at 14:52
Ethan Bolker
40.9k546108
answered Nov 25 at 14:52
Ethan Bolker
40.9k546108
answered Nov 25 at 14:52
Ethan Bolker
40.9k546108
answered Nov 25 at 14:52
Ethan Bolker
40.9k546108
40.9k546108
1
I'm programming an AI for a race game through a couple of checkpoints. If my car goes straight in direction of the checkpoint, then it has to slow down and make a huge turn there, so I wanted it to drive on such a curve, which I tried to explain (It seems, that my explanation was very bad)
– Josef Zoller
Nov 25 at 14:57
@JosefZoller That clarifies a lot. You have indeed asked an x-y question: meta.stackexchange.com/questions/66377/what-is-the-xy-problem . I think the real question is finding the fastest track, given the physical characteristics of the car - how fast can it accelerate or decelerate, how fast can it take turns. That's a hard problem. Programmng a bezier curve might give you a good enough answer. You could post it here in much more detail and hope for help.
– Ethan Bolker
Nov 25 at 15:05
Thanks for explaining to me the downvotes. I'll try to improve my question
– Josef Zoller
Nov 25 at 15:08
I think the official name for the area your problem lives in is :"calculus of variations". I doubt that there's a neat solution, but you can post it and hope.
– Ethan Bolker
Nov 25 at 15:12
@Rahul What lovely links - particularly the second one. I hope the OP appreciates them.
– Ethan Bolker
Nov 25 at 15:26
|
show 2 more comments
1
I'm programming an AI for a race game through a couple of checkpoints. If my car goes straight in direction of the checkpoint, then it has to slow down and make a huge turn there, so I wanted it to drive on such a curve, which I tried to explain (It seems, that my explanation was very bad)
– Josef Zoller
Nov 25 at 14:57
@JosefZoller That clarifies a lot. You have indeed asked an x-y question: meta.stackexchange.com/questions/66377/what-is-the-xy-problem . I think the real question is finding the fastest track, given the physical characteristics of the car - how fast can it accelerate or decelerate, how fast can it take turns. That's a hard problem. Programmng a bezier curve might give you a good enough answer. You could post it here in much more detail and hope for help.
– Ethan Bolker
Nov 25 at 15:05
Thanks for explaining to me the downvotes. I'll try to improve my question
– Josef Zoller
Nov 25 at 15:08
I think the official name for the area your problem lives in is :"calculus of variations". I doubt that there's a neat solution, but you can post it and hope.
– Ethan Bolker
Nov 25 at 15:12
@Rahul What lovely links - particularly the second one. I hope the OP appreciates them.
– Ethan Bolker
Nov 25 at 15:26
1
1
I'm programming an AI for a race game through a couple of checkpoints. If my car goes straight in direction of the checkpoint, then it has to slow down and make a huge turn there, so I wanted it to drive on such a curve, which I tried to explain (It seems, that my explanation was very bad)
– Josef Zoller
Nov 25 at 14:57
I'm programming an AI for a race game through a couple of checkpoints. If my car goes straight in direction of the checkpoint, then it has to slow down and make a huge turn there, so I wanted it to drive on such a curve, which I tried to explain (It seems, that my explanation was very bad)
– Josef Zoller
Nov 25 at 14:57
@JosefZoller That clarifies a lot. You have indeed asked an x-y question: meta.stackexchange.com/questions/66377/what-is-the-xy-problem . I think the real question is finding the fastest track, given the physical characteristics of the car - how fast can it accelerate or decelerate, how fast can it take turns. That's a hard problem. Programmng a bezier curve might give you a good enough answer. You could post it here in much more detail and hope for help.
– Ethan Bolker
Nov 25 at 15:05
@JosefZoller That clarifies a lot. You have indeed asked an x-y question: meta.stackexchange.com/questions/66377/what-is-the-xy-problem . I think the real question is finding the fastest track, given the physical characteristics of the car - how fast can it accelerate or decelerate, how fast can it take turns. That's a hard problem. Programmng a bezier curve might give you a good enough answer. You could post it here in much more detail and hope for help.
– Ethan Bolker
Nov 25 at 15:05
Thanks for explaining to me the downvotes. I'll try to improve my question
– Josef Zoller
Nov 25 at 15:08
Thanks for explaining to me the downvotes. I'll try to improve my question
– Josef Zoller
Nov 25 at 15:08
I think the official name for the area your problem lives in is :"calculus of variations". I doubt that there's a neat solution, but you can post it and hope.
– Ethan Bolker
Nov 25 at 15:12
I think the official name for the area your problem lives in is :"calculus of variations". I doubt that there's a neat solution, but you can post it and hope.
– Ethan Bolker
Nov 25 at 15:12
@Rahul What lovely links - particularly the second one. I hope the OP appreciates them.
– Ethan Bolker
Nov 25 at 15:26
@Rahul What lovely links - particularly the second one. I hope the OP appreciates them.
– Ethan Bolker
Nov 25 at 15:26
|
show 2 more comments
I think what you are looking for is the so called Minimum Energy Curve (or Minimum Energy Spline), which is constructed by minimizing a certain energy functional of the curve while treating the interpolated points as constraint.
The following shows a typical energy functional
$$E(t) = (1-w)int_0^1{||c'(t)||^2dt} + wint_0^1{kappa(t)^2dt} $$
where $c'(t)$ is the first derivative of the curve $c(t)$, $kappa(t)$ is the curvature of the curve and $0.0 le w le 1.0$. The first integral term represents the stretch energy and the second integral the bending energy of the curve. You can choose to minimize the stretch energy or the bending energy alone by using $w=0.0$ or $1.0$ respectively or you can choose to minimize a combination of both.
Because the existence of the nonlinear term $kappa(t)$, it is often desired to replace the curvature by the second derivative as
$$E_s(t) = (1-w)int_0^1{||c'(t)||^2dt} + wint_0^1{||c''(t)||^2dt} $$
so that the solution can be easily found by solving a linear equation set.
answered Nov 30 at 7:22
fang
2,462166
add a comment |
I think what you are looking for is the so called Minimum Energy Curve (or Minimum Energy Spline), which is constructed by minimizing a certain energy functional of the curve while treating the interpolated points as constraint.
The following shows a typical energy functional
$$E(t) = (1-w)int_0^1{||c'(t)||^2dt} + wint_0^1{kappa(t)^2dt} $$
where $c'(t)$ is the first derivative of the curve $c(t)$, $kappa(t)$ is the curvature of the curve and $0.0 le w le 1.0$. The first integral term represents the stretch energy and the second integral the bending energy of the curve. You can choose to minimize the stretch energy or the bending energy alone by using $w=0.0$ or $1.0$ respectively or you can choose to minimize a combination of both.
Because the existence of the nonlinear term $kappa(t)$, it is often desired to replace the curvature by the second derivative as
$$E_s(t) = (1-w)int_0^1{||c'(t)||^2dt} + wint_0^1{||c''(t)||^2dt} $$
so that the solution can be easily found by solving a linear equation set.
answered Nov 30 at 7:22
fang
2,462166
add a comment |
I think what you are looking for is the so called Minimum Energy Curve (or Minimum Energy Spline), which is constructed by minimizing a certain energy functional of the curve while treating the interpolated points as constraint.
The following shows a typical energy functional
$$E(t) = (1-w)int_0^1{||c'(t)||^2dt} + wint_0^1{kappa(t)^2dt} $$
where $c'(t)$ is the first derivative of the curve $c(t)$, $kappa(t)$ is the curvature of the curve and $0.0 le w le 1.0$. The first integral term represents the stretch energy and the second integral the bending energy of the curve. You can choose to minimize the stretch energy or the bending energy alone by using $w=0.0$ or $1.0$ respectively or you can choose to minimize a combination of both.
Because the existence of the nonlinear term $kappa(t)$, it is often desired to replace the curvature by the second derivative as
$$E_s(t) = (1-w)int_0^1{||c'(t)||^2dt} + wint_0^1{||c''(t)||^2dt} $$
so that the solution can be easily found by solving a linear equation set.
answered Nov 30 at 7:22
fang
2,462166
I think what you are looking for is the so called Minimum Energy Curve (or Minimum Energy Spline), which is constructed by minimizing a certain energy functional of the curve while treating the interpolated points as constraint.
The following shows a typical energy functional
$$E(t) = (1-w)int_0^1{||c'(t)||^2dt} + wint_0^1{kappa(t)^2dt} $$
where $c'(t)$ is the first derivative of the curve $c(t)$, $kappa(t)$ is the curvature of the curve and $0.0 le w le 1.0$. The first integral term represents the stretch energy and the second integral the bending energy of the curve. You can choose to minimize the stretch energy or the bending energy alone by using $w=0.0$ or $1.0$ respectively or you can choose to minimize a combination of both.
Because the existence of the nonlinear term $kappa(t)$, it is often desired to replace the curvature by the second derivative as
$$E_s(t) = (1-w)int_0^1{||c'(t)||^2dt} + wint_0^1{||c''(t)||^2dt} $$
so that the solution can be easily found by solving a linear equation set.
answered Nov 30 at 7:22
fang
2,462166
answered Nov 30 at 7:22
fang
2,462166
answered Nov 30 at 7:22
fang
2,462166
answered Nov 30 at 7:22
fang
2,462166
2,462166
add a comment |
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%2f3012923%2ffastest-curve-through-n-points%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
1
please say me, why my question gets downvoted after one minute. I have no idea what I could have done wrong
– Josef Zoller
Nov 25 at 14:48
1
I didn't downvote but the criterion "least possible curvature" is meaningless as the curvature varies along the curve. In addition, least curvature and short length are contradictory goals. Finally, you have no reason to believe that Adobe Illustrator uses this criteria at all.
– Yves Daoust
Nov 25 at 14:58
3
I think the downvotes are wrong. This is a perfectly reasonable question from a nonmathematician asking for help where mathematics may come into play. The way it's asked makes no literal sense mathematically, but that's no surprise given the source.
– Ethan Bolker
Nov 25 at 15:00
From other comments, I infer that what you are after is a "fastest curve". You fell deep in an XY problem I am afraid.
– Yves Daoust
Nov 25 at 15:00
I'm sorry, when my explanation was bad, but i'm not a native english speaker and It's really hard for me to find the right words, especially describing a hard problem in maths
– Josef Zoller
Nov 25 at 15:01