Thread Tools Display Modes
02-11-14, 12:11 PM   #1
Duugu
Premium Member
 
Duugu's Avatar
AddOn Author - Click to view addons
Join Date: Nov 2006
Posts: 851
I need an idea, approach or algorithm to solve a development issue

I'm stuck on a developing issue and desperately looking for some help or ideas.

The setup:
  • I have an array of x degree-values (each of them has a value between 0 and 360).
  • My goal is to 'normalize' each of the values using its two neighbors. To get more 'smoothe' degree values.

Don't know if this is clear to everyone. I can't explain it better. :/ So here's an

Example:

Let's say an array is
Lua Code:
  1. degrees = {
  2. [1] = 39,
  3. [2] = 25,
  4. [3] = 18,
  5. [4] = 6,
  6. [5] = 353,
  7. [6] = 320,
  8. [7] = 333,
  9. [8] = 342,
  10. [9] = 338,
  11. [10] = 318,
  12. [11] = 350,
  13. [12] = 359,
  14. [13] = 340,
  15. [14] = 329,
  16. [15] = 320,
  17. [16] = 313
  18. }

I'm starting my 'normalization' with the second value ([2]). (The first one is my reference and is not modified.)
Lua Code:
  1. [1] = 38,
  2. [2] = 25,
  3. [3] = 18,

I'm calculating a new 'normalized' value for [2] using the value of [1] and [3]:
38 - 18 / 2 = 10
38 - 10 = 28
So the normalized value of [2] is 28

Now I'm doing the same with the remaining values.

That means, the next step would be to normalize value [3]
Lua Code:
  1. [2] = 25,
  2. [3] = 18,
  3. [4] = 6,
which is
25 - 6 / 2 = 9.5
25 – 9.5 = 15.5
Normalized value of [3] = 15.5

(To be accurate: the value of [2] would be 28 and not 25 as it was normalized it in the previous step. But to keep the example as simple as possible I'm using the original value.)

Works nice so far. But now it's starting to get dirty. The next value is
Lua Code:
  1. [3] = 18,
  2. [4] = 6,
  3. [5] = 353,

So I'll have to consider the 0 threshold with this one.
18 + (360 - 353) / 2 = 12.5
18 - 12.5 = 5.5

And the next value makes it really worse:
Lua Code:
  1. [4] = 6,
  2. [5] = 353,
  3. [6] = 320,
Which translates into
6 + (360 - 320) / 2 = 23
360 + (6 – 23) = 343


The Problem

The degree values could be in any order/sequence. The array could be reversed for example. The values could be decreasing, then increasing and decreasing again. They could pass the 0 threshold never, once or multiple times. :/

I just can't imagine a way or an algorithm to do what I want. I really would appreciate any idea, hint, or approach that helps me solve this development issue.

How would you do it?

btw: Thanks a lot for reading all the way down to this.

Last edited by Duugu : 02-11-14 at 12:21 PM.
  Reply With Quote
02-11-14, 01:01 PM   #2
Malsomnus
A Cobalt Mageweaver
AddOn Author - Click to view addons
Join Date: Apr 2013
Posts: 203
I don't understand why you use this algorithm.
Averaging the two neighboring numbers - fine.
Substracting the result from the current number - wtf?
__________________
SanityCheck - If you've ever said the words "Sorry, I forgot" then you need this add-on.

Remember, every time you post a comment on an add-on, a kitten gets its wings!
  Reply With Quote
02-11-14, 01:18 PM   #3
Duugu
Premium Member
 
Duugu's Avatar
AddOn Author - Click to view addons
Join Date: Nov 2006
Posts: 851
Hm. My goal is to get more "smoothe" degree values.

Lets say an ideal set of values would be:
10 , 20 , 30 , 40 , 50 , 40 , 30 , 20 , 10

A real world set of values I have to deal with is:
10 , 20 , 40 , 50 , 40 , 30 , 20 , 10

Now I'm trying to 'smoothe' or 'flatten' the second one. To get something like
10 , 25 , 40 , 50 , 40 , 30 , 20 , 10

Last edited by Duugu : 02-11-14 at 01:21 PM.
  Reply With Quote
02-11-14, 01:26 PM   #4
elcius
A Cliff Giant
AddOn Author - Click to view addons
Join Date: Sep 2011
Posts: 75
Lua Code:
  1. local a = {38,25,18,6,353,320,333,342,338}
  2. for i = 2,#a-1 do
  3.     a[i] = ((a[i-1]+a[i+1])/2+(abs(a[i-1]-a[i+1])>180 and 180 or 0))%360
  4. end
?
  Reply With Quote
02-11-14, 01:28 PM   #5
Resike
A Pyroguard Emberseer
AddOn Author - Click to view addons
Join Date: Mar 2010
Posts: 1,290
Like this?

Lua Code:
  1. for i = 2, #degrees - 1 do
  2.     degrees[i] = (degrees[i - 1] + degrees[i + 1]) / 2
  3. end
  Reply With Quote
02-11-14, 01:45 PM   #6
Malsomnus
A Cobalt Mageweaver
AddOn Author - Click to view addons
Join Date: Apr 2013
Posts: 203
What I'd do is a weighted average of each number with its 2 closest neighbours. Preferably put the whole thing into a brand new array so that you actually work with the original numbers
__________________
SanityCheck - If you've ever said the words "Sorry, I forgot" then you need this add-on.

Remember, every time you post a comment on an add-on, a kitten gets its wings!
  Reply With Quote
02-11-14, 01:52 PM   #7
Duugu
Premium Member
 
Duugu's Avatar
AddOn Author - Click to view addons
Join Date: Nov 2006
Posts: 851
Originally Posted by elcius View Post
What I'd do is a weighted average of each number with its 2 closest neighbours. Preferably put the whole thing into a brand new array so that you actually work with the original numbers
:O
Thank you elcius.

I'm still trying to understand what exactly you're doing with this. ;D

I'll report back in a few minutes.

Last edited by Duugu : 02-11-14 at 03:10 PM.
  Reply With Quote
02-11-14, 01:54 PM   #8
Malsomnus
A Cobalt Mageweaver
AddOn Author - Click to view addons
Join Date: Apr 2013
Posts: 203
Now that the raid is over, I'll try to write a piece of code for this
__________________
SanityCheck - If you've ever said the words "Sorry, I forgot" then you need this add-on.

Remember, every time you post a comment on an add-on, a kitten gets its wings!
  Reply With Quote
02-11-14, 02:05 PM   #9
Nimhfree
A Frostmaul Preserver
AddOn Author - Click to view addons
Join Date: Aug 2006
Posts: 267
I don't understand the problem the OP is having. Basically my understanding is from a group of three degree values, take the middle one and replace it with the average of the two outer ones. The math is easy, and if the resulting value < 360 just add 360 to it. However, this math does not take into account the original value of the middle number. So, with an array like:

10, 80, 20, 95, 30, 160, 40

you would get an array of:

10, 15, 55, 42.5, 101.25, 70.625, 40

(assuming the end value of 40 does not change, like the first value does not change).

I have no idea what this is supposed to be for, but I think it is not the proper solution based on the fact that the OP says the numbers can come in any order, etc.
  Reply With Quote
02-11-14, 02:07 PM   #10
Malsomnus
A Cobalt Mageweaver
AddOn Author - Click to view addons
Join Date: Apr 2013
Posts: 203
I assumed that averaging would be easy despite the fact we're talking about degrees. I was wrong. Going to have to work on it a bit more
__________________
SanityCheck - If you've ever said the words "Sorry, I forgot" then you need this add-on.

Remember, every time you post a comment on an add-on, a kitten gets its wings!
  Reply With Quote
02-11-14, 02:30 PM   #11
Dridzt
A Pyroguard Emberseer
 
Dridzt's Avatar
AddOn Author - Click to view addons
Join Date: Nov 2005
Posts: 1,359
Is this a curve fitting problem or am I misunderstanding what you're trying to do?
  Reply With Quote
02-11-14, 03:06 PM   #12
Phanx
Cat.
 
Phanx's Avatar
AddOn Author - Click to view addons
Join Date: Mar 2006
Posts: 5,617
I think OP needs to describe the end result they're looking to achieve, rather than just the means they're trying to use to achieve it... the only thing I can think of is trying to evenly space minimap buttons, but nobody uses those things anymore, so it must be something else...
__________________
Retired author of too many addons.
Message me if you're interested in taking over one of my addons.
Don’t message me about addon bugs or programming questions.
  Reply With Quote
02-11-14, 03:06 PM   #13
Duugu
Premium Member
 
Duugu's Avatar
AddOn Author - Click to view addons
Join Date: Nov 2006
Posts: 851
Originally Posted by Dridzt View Post
Is this a curve fitting problem or am I misunderstanding what you're trying to do?
No exactly.

I have some frames that are lined up on a curve and that are rotated according to their position.
In some cases the calculated rotation angle does not perfectly fit. And I'm trying to fix this.



Button 5 (starting from the left) needs one degree more, button 6 one less.

I know it's hard to see. It is getting more visible in action if the curve knots are moving. But I don't have the time to make a video of it.
  Reply With Quote
02-11-14, 03:11 PM   #14
Malsomnus
A Cobalt Mageweaver
AddOn Author - Click to view addons
Join Date: Apr 2013
Posts: 203
This was bloody annoying to do... I shouldn't have neglected my math studies... but this seems to work, generally speaking, even though it's not perfect mathematically, and the code is a bit ugly as well.

Lua Code:
  1. function smooth_helper (a, b, weight)
  2.    -- Assuming both a and b are in 0..359 range
  3.    local direction = 1
  4.    if (a-b)%360 < 180 then
  5.       direction = -1
  6.    end
  7.    
  8.    local delta = math.abs(a-b) % 360
  9.    if delta > 180 then
  10.       delta = 360 - delta
  11.    end
  12.    
  13.    return (a + direction * delta * weight) % 360
  14. end
  15.  
  16. function round (n)
  17.    return math.floor(n+0.5)
  18. end
  19.  
  20. function smooth (tbl)
  21.    ret =  {}
  22.    local avg = 0
  23.    
  24.    -- To make the averaging less ugly, make a padded copy of tbl
  25.    local tmp = {tbl[1], tbl[1]}
  26.    for i=1,#tbl do
  27.       table.insert (tmp, tbl[i])
  28.    end
  29.    table.insert (tmp, tbl[#tbl])
  30.    table.insert (tmp, tbl[#tbl])
  31.    
  32.    for i=3,#tbl+2 do
  33.       avg = tmp[i]
  34.       avg = smooth_helper (avg, tmp[i-1], 0.15)
  35.       avg = smooth_helper (avg, tmp[i+1], 0.15)
  36.       avg = smooth_helper (avg, tmp[i-2], 0.05)
  37.       avg = smooth_helper (avg, tmp[i+2], 0.05)
  38.      
  39.       table.insert (ret, round(avg))
  40.    end
  41.    
  42.    return ret
  43. end

You can play around with the weights, naturally, and I suspect that changing the order of those smoothing lines would change the outcome in a way that would make a mathematician cringe

[Edit]
A mathematician, or someone who takes their computer graphics seriously, would have done it with vectors
__________________
SanityCheck - If you've ever said the words "Sorry, I forgot" then you need this add-on.

Remember, every time you post a comment on an add-on, a kitten gets its wings!

Last edited by Malsomnus : 02-11-14 at 03:22 PM.
  Reply With Quote
02-11-14, 03:31 PM   #15
Duugu
Premium Member
 
Duugu's Avatar
AddOn Author - Click to view addons
Join Date: Nov 2006
Posts: 851
Thank you Elcius and Malsomnus for the code (mixed you up below, sorry :/) and to everyone else to pointing me into the right direction. That was exactly what I was looking for.

I was so locked into my approach that it just did not came to my mind that taking the average is the solution. Don't ask. Can't believe it myself. That was one of those situations where I lost the ability to think after unsuccessfully trying to solve a problem for hours.
  Reply With Quote
02-11-14, 03:44 PM   #16
Vrul
A Scalebane Royal Guard
 
Vrul's Avatar
AddOn Author - Click to view addons
Join Date: Nov 2007
Posts: 404
Originally Posted by Duugu View Post
In some cases the calculated rotation angle does not perfectly fit. And I'm trying to fix this.
So post the function that calculates the rotation angle and some examples of inputs that give bad outputs and what those outputs should be and maybe we can fix that.

Originally Posted by Duugu View Post
Thank you Elcius and Malsomnus for the code
Resike's code does exactly what you asked for without a bunch of extra crap.
  Reply With Quote
02-11-14, 03:58 PM   #17
Duugu
Premium Member
 
Duugu's Avatar
AddOn Author - Click to view addons
Join Date: Nov 2006
Posts: 851
Originally Posted by Vrul View Post
Resike's code does exactly what you asked for without a bunch of extra crap.
Skiping it was not meant as an offense. Sorry for that.
Actually it does not exactly the same as it doesn't takes the 0/360 degree threshold into account.
  Reply With Quote
02-11-14, 04:09 PM   #18
Vrul
A Scalebane Royal Guard
 
Vrul's Avatar
AddOn Author - Click to view addons
Join Date: Nov 2007
Posts: 404
Originally Posted by Duugu View Post
Skiping it was not meant as an offense. Sorry for that.
Actually it does not exactly the same as it doesn't takes the 0/360 degree threshold into account.
Based off your intended use your values should not exceed the +/-90 degree range, so if your array contained -7 instead of 353 it would work just fine. That pushes the problem boundary to the 180 degree area where your values should never realistically be. You're not taking full advantage of the available ways to store what you have and are trying to create a needlessly complex system to compensate for it.
  Reply With Quote
02-11-14, 04:14 PM   #19
Seerah
Fishing Trainer
 
Seerah's Avatar
WoWInterface Super Mod
Featured
Join Date: Oct 2006
Posts: 10,860
Originally Posted by Duugu View Post
Skiping it was not meant as an offense. Sorry for that.
Actually it does not exactly the same as it doesn't takes the 0/360 degree threshold into account.
How does it not? It's just taking the average of the two values on either side. Your values are all in that 0-360 range. The averages will be also.
__________________
"You'd be surprised how many people violate this simple principle every day of their lives and try to fit square pegs into round holes, ignoring the clear reality that Things Are As They Are." -Benjamin Hoff, The Tao of Pooh

  Reply With Quote
02-11-14, 04:22 PM   #20
Duugu
Premium Member
 
Duugu's Avatar
AddOn Author - Click to view addons
Join Date: Nov 2006
Posts: 851
Lets say the values are 14, 6, 340

The intented result for the second value would be 357.

Using Resike's code
Lua Code:
  1. degrees[i] = (degrees[i - 1] + degrees[i + 1]) / 2
the value would be

(14 + 340) / 2 = 177

Last edited by Duugu : 02-11-14 at 04:30 PM.
  Reply With Quote

WoWInterface » Developer Discussions » General Authoring Discussion » I need an idea, approach or algorithm to solve an development issue

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off