# Removing loops from a line / sef intersection

## Recommended Posts

Defeatist    100
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 on other sites
Alrecenk    400
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