Sign in to follow this  
Defeatist

Removing loops from a line / sef intersection

Recommended Posts

Hi! I have a line that is composed of points with a x,y,z coordinate. I treat the line as a 2D line and ignore the Y value (looking top-down). I want to remove loops( self intersections) from the line. http://img535.imageshack.us/img535/3449/loop.png This is what I have for now:
for each line-segment line(I) to line(I+1) in line
   for each line-segment line(J) to line(J+1) in line
       if im not testing the segment against itself (i!=j)
           get the intersection point
              if the intersection point falls on one of the line-segments and is not one of its corners
                 erase I to J+1 from line



I get the intersection point using this article found on wikipedia wikipedia http://en.wikipedia.org/wiki/Line-line_intersection my c++ implementation however returns a lot of intersections points( way too many, most of them on top of a single line ). There must be some things Im not taking into account: - the line contains no duplicate points - I check wether the intersection point is on one of the segments or not - I check wether the intersection point is one of the segments corners (it shouldnt be) http://img15.imageshack.us/img15/6205/errorsn.png any help? :)
for(int i = 0; i < coast->size()-1; i++)
    {
        float x_1 = coast->at(i).x;
        float x_2 = coast->at(i+1).x;
        float y_1 = coast->at(i).z;
        float y_2 = coast->at(i+1).z;

        for(int j = 0; j < coast->size()-1; j++)
        {
            if( i != j)
            {
                float x_3 = coast->at(j).x;
                float x_4 = coast->at(j+1).x;
                float y_3 = coast->at(j).z;
                float y_4 = coast->at(j+1).z;

                /// Wikipedia method to intersection
                float x = ((x_1*y_2 - y_1*x_2)*(x_3-x_4)-(x_1-x_2)*(x_3*y_4-y_3*x_4)) / ((x_1-x_2)*(y_3-y_4)-(y_1-y_2)*(x_3-x_4));
                float y = ((x_1*y_2-y_1*x_2)*(y_3-y_4)-(y_1-y_2)*(x_3*y_4-y_3*x_4)) /  ((x_1-x_2)*(y_3-y_4)-(y_1-y_2)*(x_3-x_4));

                // check wether the intersection point is in the domain of linesegment i
                // but is not its corner
                if( (x < max(coast->at(i).x, coast->at(i+1).x))&&(x > min(coast->at(i).x, coast->at(i+1).x)) )
                {
                    // check wether the intersection point is in the domain of linesegment i
                    // but is not its corner
                    if((y > min(coast->at(i).z, coast->at(i+1).z))&&(y < max(coast->at(i).z, coast->at(i+1).z)) )
                    {
                        dev->push_back( mPoint( x, 0, y) );         // debug visualisation

                        // remove coast[i] to coast[j+1]
                    }
                }

            }
        }
    }



Share this post


Link to post
Share on other sites
Well, for starters, you're testing every pair of lines twice. Then you're comparing the result to the bounding box of line i but not comparing it to the bounding box of j(it has to be within both). Also, you'll probably want to replace the removed part with the intersection point to avoid cutting off the corners with the loops.


for each line-segment line(I) to line(I+1) in line
for each line-segment line(J) to line(J+1) in line
if j < i
get the intersection point
if the intersection point falls on both of the line-segments
replace j to i with intersection point
if intersection point is too close to one of the points it's connected to
remove it


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this