# smoothing algorithm

This topic is 4608 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm loading a map of trees from a picture were a red pixel is a tree and want every group of trees to be defined by an array of lines that surround the group. So far I thought of looking at every pixel: If the pixel to the right of it is clear, make a line to the right of the pixel, same for the top, bottom, and left. So that gives me a lot of little lines (vert and hoiz) surrounding the groups of trees. But I don't want lots of little lines, many of the small lines like this: -------- could be combined into one long line, that would save a lot of collision detection time. So my question is, what is a good way to go through the line array (an array of structures were each structure holds two points) and combine lines. Or to go through the pixel data (stored in a 2D array) and do the same thing? Thanks.

0,0 1,0
1,0 2,0

0,0 2,0

Correct?

Kuphryn

##### Share on other sites
Yes thats correct (Also:
(0,0),(1,0)/(1,0),(2,0)/(2,0),(3,0) => (0,0),(3,0) )
, but how do I combine all of the little lines in the array, to bigger ones?

Anyone?

##### Share on other sites
Ouch. I was unable to understand the post when I read it first. Then I understood your answer to kuphryn and everything was suddenly clearer.

The basic algorithm to do the job is
sort the array by increasing line first pointsfor each line L in my array  for each line L' after L in my array    if i_can_combine(L,L')      L = combine(L, L') // L endpoint is now L' endpoint      remove L'    end if  end ofend of

The hard part is the i_can_combine test - well, it is not as hard as it seems:
v = vector of Lv' = vector of L'if the begin point of L' is on the L segment  // any other method that will prove that v and v' are colinear is ok  are_colinear = (length(cross_product(v, v')) == 0)  if are_parrallel    return true  end ifend ifreturn false

This is a greedy, O(n2) algorithm, but I believe it should do the job

HTH,

##### Share on other sites
what is: "sort the array by increasing line first points" ?
Thanks.

##### Share on other sites
Quote:
 Original post by daniel_i_lwhat is: "sort the array by increasing line first points" ?Thanks.

I'm rather bad at english. I just wanted to say that the algorithm needs to have an ordered set of lines as the input. This way, I'll be sure that if a line A begins at point a1 and ends at point a2, any subsequent line in the set will begin after point a1. It allows me to introduce another small optimization - but I left this as an exercise for the reader :)

Regards,

1. 1
Rutin
40
2. 2
3. 3
4. 4
5. 5

• 16
• 18
• 12
• 14
• 9
• ### Forum Statistics

• Total Topics
633360
• Total Posts
3011524
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!