Segment/Polyline intersection

beginners
#1

Hi,
I’m using a ofPath as a container for obstacles. The point in the center is supposed to find a way to go to some coordinates, dodging those obstacles.

I going to “shoot” rays from the point to see if a the way is obstructed in the ray direction. How can i check if the ray intersect one of the subpaths ?

Cheers,
Hippolyte.

#2

You should check ray intersection with line segments, each line segment being the obstacle subpaths.

To get the subpaths for each ofPath obstacle you can use obstacle.getOutline(), which will give you a vector of ofPolylines. Intersect those ofPolylines with the ray your generate

#3

I did the following : i have a vector of Segments (a class with nothing but the origin of the segment and its vector), for each subpaths i check if those segments intersects one of the sides. If there’s no intersection, I draw the segment. The thing is, so far every single segments is drawn, all the time.

Here’s my code :

//Search for intersections
        ofSetColor(220,0,0);
        std::vector<ofPolyline> outline = shapes.getOutline();
        for(ofPolyline line : outline){
            auto iterator = line.getVertices().begin();
            while(iterator != line.getVertices().end()){
                Segment s(*iterator, ofVec2f(*std::next(iterator,1) - *iterator));
                for(Segment ray : segments){
                    if(!ray.intersect(s)){
                        ofDrawLine(ray.origin, ray.origin + ray.v);
                    }
                }
                iterator = next(iterator,1);
            }
        }

Segments::intersect function :

bool Segment::intersect(Segment otherSegment){
    
    float s, t;
    s = -this->v.y * (this->origin.x - otherSegment.origin.x);
    s += this->v.x * (this->origin.y - otherSegment.origin.y);
    s /= (-otherSegment.v.x * this->v.y + this->v.x * otherSegment.v.y);
    
    t = otherSegment.v.x * (this->origin.y - otherSegment.origin.y);
    t -= otherSegment.v.y * (this->origin.x - otherSegment.origin.x);
    t /= (-otherSegment.v.x * this->v.y + this->v.x * otherSegment.v.y);
    
    return (s >= 0 && s <= 1 && t >= 0 && t <= 1);
}
#4

Can’t debug the code for you, I just can tip with links about segment and ray intersection: http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/565282#565282

Make sure you are not intersecting ray with ray!