SC-RAY Project

Street Crossing Ray Algorithm
by
Greg Reshko

This program solves the street crossing problem for arbitrary configuration of obstacles. Obstacles are described in the List of Obstacles text box on the right. Click run to execute the algorithm. The algorithm will dequeue a point from a queue every 100ms in order for the user to see the region being constructed. Actions Taken by Solver displays a list of steps taken by the solver algorithm in order to construct the region. Run Time Queue Status displays the current status of the queue when the algorithm is running. Various interesting obstacle configuration examples are given at the bottom of this page.

Table of Contents:

Problem Description
Data Structures
High-Level Algorithm Description
Data Structures Implementation
Algorithm Implementation
Copyright Statement

Problem Description:

A path crossing a street is simply a line segment AB, where point A is on one side of the street, and point B on the other. (jaywalking is not allowed). A robot is sitting at point A and wants to move to point B. Being a robot, it can move only in three different speeds: +1, 0 and -1. For simplicity we assume that transitions from one speed to another are instantaneous.

The problem is that there are cars moving along the street. At each time t, one or more cars may be obstructing parts of the line AB.

The problem can be modeled in space-time (one space dimension, one time dimension). The robot tries to move from position (0, 0) to (1, t) for the smallest possible value of t. The moving obstacles are given as rectangular regions in space-time specified by the lower left corner (xl, tl) and the upper right corner (xr, tr) (where 0 <= xl < xr <= 1 and 0 <= tl < tr.

Suppose that there are n obstacles C1, . . . ,Cn. A collision occurs only when the trajectory of the robot contains an interior point of an obstacle (the boundary is still safe). A position (x, t) is reachable if the robot can move from (0, 0) to (x, t) given the velocity constraints and without colliding with an obstacle.

- - - - -

Data Structures:

Point
Stores direction, t, x, object on which it is located if any, activity, type, and t and x coordinates of the point from which it is derived (if any).
Point class can compute an intersection point c given the point from which a ray is fired, direction of the ray and a line segment. Intersection point computation is performed by the following fast algorithm:

Obstacles
    This is the obstacle database.
    It can return t or x coordinates of the given obstacle.
    It can also determine if the given ray intersect with any of the obstacles before reaching the next event point.

Event Queue:
    Maintains a priority queue of points arranged by t and then by x.
    Obvious methods include insertion, retrieval, and removal of points.
    The class can also return the time of the next event line and activate all points with x coordinate lower than maximum possible x so far.

- - - - -

General High-Level Algorithm Description:

Some definitions:
Activity:
    Point is considered active, if we will fire a ray from this point when it is dequeued.
    Point is considered inactive, if we will not fire a ray from it when it is dequeued.
Type:
    There are five types of points – upper beginning, upper ending, lower beginning, lower ending of rectangle, and free points. Free points are the ones that are not on rectangle.

Initially all points, except for the starting point, are inactive.
Event queue contains beginning and end points of all rectangles (all inactive) and the active starting point set to the origin.

Loop:
    Activate all end points of rectangles that are in the max reachable x region – that is the x region that we can potentially reach at any given time before that point.

    Fire a ray for all active points on the current event line towards the next event line. Ray direction is determined as follows:
    Free point – same direction as the point that created it
    Upper endpoint of obstacle – diagonally downward
    Lower endpoint of obstacle – diagonally upward

    If two rays are fired from the same obstacle, compute their intersection point. If the intersection point is before any other event, add that point as inactive to the event queue and remove the ray. Remove both endpoints from which the rays are fired from the queue and continue loop.

    Compute finishing points for fired rays:
    If the resulting point is a free point it will be active.
    If the resulting point is on an obstacle it will be inactive and we create a new event E and insert it into priority queue of events.

    Advance to the next event.

The algorithm terminates when the queue is empty. When the algorithm is done, we will have a picture of reachable region.

- - - - -

Data Structures Implementation:

The following classes are used:

class Point
{
public:
    enum enumDirection {dir_down, dir_horiz, dir_up};
    enum enumType {type_free, type_upper_begin, type_lower_begin, type_lower_end, type_upper_end};

    void SetPrev(double t, double x);
    void Set(double setT, double setX, int setObject, int setDirection, int setType, bool setActive);
    Point Intersection(Point point);
    void RayFromPoint(Point point);
    Point();
    virtual ~Point();
    Point & operator =(const Point &p);

    enumDirection direction; // direction
    double t; // time
    double x; // position
    int object; // object id
    int active; // active or not
    enumType type; // type of point
    double prevt, prevx; // previous point
};

class Obstacles
{
public:

    struct LineSegment
    {
        double t1, t2, x1, x2;
    };

    CList <LineSegment, LineSegment&> segmentList;
    CList <LineSegment, LineSegment&> obstacleList;

    double GetObstacleT(int id, int v);
    double GetObstacleX(int id, int v);
    int GetCount();
    bool RayHitsObstacle(Point point, double targetTime, Point * hitPoint);
    void Add(double t1, double x1, double t2, double x2);
    Obstacles();
    virtual ~Obstacles();
};

class EventQueue
{
public:
    int GetCount();
    Point GetPoint(int count);
    double NextEventTime();
    bool IsEmpty();
    void ActivateObstaclePoints(double maxX, double nextEventTime);
    void RemoveFirstPoint();
    Point GetFirstPoint();
    void AddPoint(Point p);
    EventQueue();
    virtual ~EventQueue();

private:
    CList <Point, Point&> eventList;
    double currentMaxX;
};

- - - - -

Algorithm Implementation:

The algorithm is implemented using highly object-oriented code written in Visual C++ and Microsoft Foundation Classes.
MFC is used primarily for graphics as well as most basic data structures such as Lists.

Various Obstacle Configurations:

Feel free to just cut and paste these into List of Obstacles text box. Somes notes -- due to the size of the screen being finite, obstacles must have t less than 2.0 and x less than 1.0. Obstacles are described by

lower left t lower left x upper right t upper right x

Some examples:

0.1 0.2 0.5 0.25
0.3 0.3 0.7 0.35
0.5 0.4 0.9 0.45
0.7 0.5 1.1 0.55
0.9 0.6 1.3 0.65

0.3 0.4 0.7 0.9
0.3 0.1 0.7 0.2
0.8 0.4 1.1 0.9

0.3 0.4 0.7 0.6
0.3 0.05 0.7 0.25
0.75 0.05 1.1 0.9

0.1 0.4 0.3 0.45
0.2 0.5 0.4 0.55
0.3 0.6 0.5 0.65
0.4 0.7 0.6 0.75
0.5 0.8 0.7 0.85

0.1 0.2 0.5 0.25
0.3 0.3 0.7 0.35
0.5 0.4 0.9 0.45
0.7 0.5 1.1 0.55
0.9 0.6 1.8 0.65
1.0 0.1 1.3 0.4
1.35 0.1 1.7 0.2
0.5 0.05 0.6 0.15
0.63 0.05 0.8 0.15
0.2 0.8 0.6 0.9
0.45 0.6 0.55 0.7
1.15 0.75 1.25 0.85