Jump to content
  • Advertisement
Sign in to follow this  
Defeatist

Removing loops from a line / sef intersection

This topic is 3045 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

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 to coast[j+1]
                    }
                }

            }
        }
    }



Share this post


Link to post
Share on other sites
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!