# 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

×