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.

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)

Anyone?

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,

what is: "sort the array by increasing line first points" ?
Thanks.

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,