• Advertisement
Sign in to follow this  

smoothing algorithm

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

If you intended to correct an error in the post then please contact us.

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.

Share this post


Link to post
Share on other sites
Advertisement
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?
Thanks (please ask if the question isn't clear)

Share this post


Link to post
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 points
for 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 of
end of


The hard part is the i_can_combine test - well, it is not as hard as it seems:

v = vector of L
v' = 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 if
end if
return false


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

HTH,

Share this post


Link to post
Share on other sites
Quote:
Original post by daniel_i_l
what 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,

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement