• Create Account

#ActualBacterius

Posted 24 August 2012 - 11:24 PM

OK, I think I got it. I would expect the length of the parabola to increase monotonically as the height increases, for a same base width. In this case, you can use good old bisection. This will allow you to converge on the correct height required to obtain a given arc length, knowing the base width. I would expect the algorithm to converge pretty quickly on the solution, which means it should be fast if you only need, say, 5 digits of precision, but I can't say anything about performance. I believe it would be correct though.

The code would look something like this (may have some edge cases but it's the idea):

input: base length W, required length L.
output: approximate correct H such that Length(W, H) = L

1. Let lo = 0, hi = 4h + c (twice the limit form plus some constant, try various c)
2. Compute H_mid = (lo + hi) / 2
3. Compute L' = Length(W, H_mid)
4. If L' < L, let lo = H_mid and goto 2
5. If L' > L, let hi = H_mid and goto 2
6. If L' is close to L, return H_mid


Though note that if arc length doesn't strictly increase with height with constant base width as I think it does, this might not work.

EDIT:

If w is a constant, then:

O(0.5√16h²+w² + [w²/(8h)][ln(4h + √16h²+w²) - ln(w)]) = O(0.5√16h² + [1/(8h)][ln(4h + √16h²)]) = O(2h + ln(8h)/(8h)) = O(2h + ln(8h)/(8h))

Which tends to 2h in the limit, so the arc length does increase monotonically with h, this should work.

You can also use Newton-Raphson instead by differentiating (have you seen this method at high school?), it would converge faster but each iteration takes more work, and the differentiated expression may not be so nice to compute.

#4Bacterius

Posted 24 August 2012 - 06:24 PM

OK, I think I got it. I would expect the length of the parabola to increase monotonically as the height increases, for a same base width. In this case, you can use good old bisection. This will allow you to converge on the correct height required to obtain a given arc length, knowing the base width. I would expect the algorithm to converge pretty quickly on the solution, which means it should be fast if you only need, say, 5 digits of precision, but I can't say anything about performance. I believe it would be correct though.

The code would look something like this (may have some edge cases but it's the idea):

input: base length W, required length L.
output: approximate correct H such that Length(W, H) = L

1. Let lo = 0, hi = *some number bigger than the required height*
2. Compute H_mid = (lo + hi) / 2
3. Compute L' = Length(W, H_mid)
4. If L' < L, let lo = H_mid and goto 2
5. If L' > L, let hi = H_mid and goto 2
6. If L' is close to L, return H_mid


Though note that if arc length doesn't strictly increase with height with constant base width as I think it does, this might not work.

EDIT:

If w is a constant, then:

O(0.5√16h²+w² + [w²/(8h)][ln(4h + √16h²+w²) - ln(w)]) = O(0.5√16h² + [1/(8h)][ln(4h + √16h²)]) = O(2h + ln(8h)/(8h)) = O(2h + ln(8h)/(8h))

Which tends to 2h in the limit, so the arc length does increase monotonically with h, this should work.

#3Bacterius

Posted 24 August 2012 - 06:22 PM

OK, I think I got it. I would expect the length of the parabola to increase monotonically as the height increases, for a same base width. In this case, you can use good old bisection. This will allow you to converge on the correct height required to obtain a given arc length, knowing the base width. I would expect the algorithm to converge pretty quickly on the solution, which means it should be fast if you only need, say, 5 digits of precision, but I can't say anything about performance. I believe it would be correct though.

The code would look something like this (may have some edge cases but it's the idea):

input: base length W, required length L.
output: approximate correct H such that Length(W, H) = L

1. Let lo = 0, hi = *some number bigger than the required height*
2. Compute H_mid = (lo + hi) / 2
3. Compute L' = Length(W, H_mid)
4. If L' < L, let lo = H_mid and goto 2
5. If L' > L, let hi = H_mid and goto 2
6. If L' is close to L, return H_mid


Though note that if arc length doesn't strictly increase with height with constant base width as I think it does, this might not work.

EDIT:

If w is a constant, then:

O(0.5√16h²+w² + [w²/(8h)][ln(4h + √16h²+w²) - ln(w)]) = O(0.5√16h² + [1/(8h)][ln(4h + √16h²)]) = O(2h + ln(8h)/(8h)) = O(2h + ln(8h)/(8h)) = O(ln(h))

so the arc length does increase monotonically with h, this should work.

#2Bacterius

Posted 24 August 2012 - 06:06 PM

OK, I think I got it. I would expect the length of the parabola to increase monotonically as the height increases, for a same base width. In this case, you can use good old bisection. This will allow you to converge on the correct height required to obtain a given arc length, knowing the base width. I would expect the algorithm to converge pretty quickly on the solution, which means it should be fast if you only need, say, 5 digits of precision, but I can't say anything about performance. I believe it would be correct though.

The code would look something like this (may have some edge cases but it's the idea):

input: base length W, required length L.
output: approximate correct H such that Length(W, H) = L

1. Let lo = 0, hi = *some number bigger than the required height*
2. Compute H_mid = (lo + hi) / 2
3. Compute L' = Length(W, H_mid)
4. If L' < L, let lo = H_mid and goto 2
5. If L' > L, let hi = H_mid and goto 2
6. If L' is close to L, return H_mid


Though note that if arc length doesn't strictly increase with height with constant base width as I think it does, this might not work.

#1Bacterius

Posted 24 August 2012 - 06:04 PM

OK, I think I got it. I would expect the length of the parabola to increase monotonically as the height increases, for a same base width. In this case, you can use good old bisection. This will allow you to converge on the correct height required to obtain a given arc length, knowing the base width. I would expect the algorithm to converge pretty quickly on the solution, which means it should be fast if you only need, say, 5 digits of precision, but I can't say anything about performance. I believe it would be correct though.

The code would look something like this (may not be correct but it's the idea):

input: base length W, required length L.
output: approximate correct H such that Length(W, H) = L

1. Let lo = 0, hi = *some number bigger than the required height*
2. Compute H_mid = (lo + hi) / 2
3. Compute L' = Length(W, H_mid)
4. If L' < L, let lo = H_mid and goto 2
5. If L' > L, let hi = H_mid and goto 2
6. If L' is close to L, return H_mid


Though note that if arc length doesn't strictly increase with height with constant base width as I think it does, this might not work.

PARTNERS