Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Working with Lines and Segments | Reply
1 Introduction

From wikipedia, a line is the idealisation of a infinitely long and widthless straigth object. In euclidean geometry it is not more than a straight curve and in analytic geometry it is a linear ecuation that represents this euclidean object in a coordinate system. A line segment is a part of that line that has finite end points and has all the points of the line between these end points. We will commence this discussion with the representation of lines and some algorithms related to them, afterwards we will discuss about segments.
We will use the following notation: if P is a point or a vector, P.x represents its first coordinate and P.y its second.

2 Lines

2.1 Representation of a Line:

2.1.1 Ecuational representation:

Mathematically, a line L in a R² coordinate system can be represented by this equation:

   L= {(x,y) | Ax + By + C=0}


It is, the line L is the set of points (x,y) that suffices the given equation.

If we are given two distinct points P and Q, we can get the ecuation that represents the line that covers P and Q.

We know that the two following equations are valid

A*P.x + B*P.y + C=0
A*Q.x + B*Q.y + C=0

After doing a substraction we have
A(P.x - Q.x)+B(P.y - Q.y)=0

If we represent this as the product of two vectors V1 = (P.x - Q.x, P.y - Q.y) and V2 = (A, B), we know that if A = Q.y - P.y and B = P.x - P.y the equation given above is solved, so we choose these values for A and B. Finally, we can compute C by replacing the found values A and B with P or Q in the equation.
C = -A*P.x - B*P.y

2.1.2 Vectorial representation

Another way to represent a line is with vectors:
  L={a+tb, t belongs R}

where a,b are vectors in R^n with b non-zero.

The most of the problems we will face can be solved with a 2-dimensional geometry approach (R²) , so we will only care this representation, however working with a n-dimension line is very easy with the vector representation, we just do the same that we do with x and y coordinates.

As in the first representation, given two points P and Q, we can get the vector representation in this way:
a= P
b= (Q.x - P.x, Q.y - P.y)

Intuitively, what we are doing is to fix a point (P) and move along the line formed by P and Q. The direction of that line is given by b, and with some value of t, we can reach any point lying on that line.

2.2 Intersection of two Lines:

Two lines L1 and L2 intersect in 0, 1 or infinite points. To show this, we will calculate the crossing points of two lines L1 and L2 given their equations:
   L1= {(x,y) | Ax + By = C}
 
   L2= {(x,y) | Dx + Ey = F}

The insersection is the set of point that suffices both equations, so we have a system of 2 linear equations in matrix form:

       |A  B|  .  |x| =  |C|
       |D  E|     |y|    |F|


If the determinant (AE - BD) is equal to zero, then both lines are parallel (why?), so we have 2 cases here: L1 is equal to L2 or they have no crossing points.
If L1 and L2 are the same, then the vector (A, B, C) is equal to k * (D, E, F) for some k /belongs to R/, i.e. infinite intersection points. And if there is not any valid k, then L1 and L2 have no intersection points.
Now if the mentioned determinant is different to zero, then exists one unique crossing point (x,y) which can be calculate by many ways, but we will only mention the result.

Let S be the intersection point, then:
 
   S.x = (CE - BF) / (AE - BD)
   S.y = (AF - BD) / (AE - BD)

What is cool about this is that, if the coefficients in the equations for L1 and L2 are integers, we have only one floating point operation for determining x or y, and also, determining if the determinant (AE - BD) is zero involves no floating point operation, which will be very useful many times.


2.3 Finding a perpedincular line to another

Here we have a Line L with coefficients A,B and C, and want to create a line L2, perpendicular to L and that a given point P lies on L2. This is easy, since we know that V = (A, B) is a vector perpendicular to L, then a perpendicular vector to V will be a perpendicular one to L2. This vector could be V '= (-B, A). In order to find the C coefficient of L2, we can just simply use P.x and P.y in the equation as we did above.

2.4 Determining if two line are the same

Here we can do many things. If the A,B and C coefficients are integers, we can divide them by its gcd (take care of 0 values) and use this trick:
if C is positive, then we are done; if C is negative, then multiply the hole equation by -1 in order to have C positive; if C is zero, repeat the same for B and then for A. Why is this useful? If we have a line (A, B, C) = (4,5,-2) and other one (A', B', C') = (-4,-4,2), then, after apply the mentioned algorithm, we know that they are the same. Also, if the lines were (4,5,0) and (-8,-10,0), we know that there were the same.
Another important thing we can get from this is that it define an ordering. In C++ we can define an operator <, or in Java a compareTo function, in order to use structures like map, set, TreeSet, etc.
Here a put a sample code in c++ for the line structure and its operator <

typedef long long ll;  // it could be useful for large numbers
 
struct line{
  //line representation Ax+By=C
    ll a,b,c;
    line(ll x1,ll y1,ll x2,ll y2){ //the arguments needed for the creation of the structure are two points lying on the line
     a=y2-y1;
     b=x1-x2;
     c=x1*a+y1*b;
     
     ll x=abs((a==0?1:a)*(b==0?1:b)*(c==0?1:c)); // x will be the product of the coefficientes a,b and c that are not zero 
     ll g=__gcd(a==0?x:abs(a),__gcd(b==0?x:abs(b),c==0?x:abs(c))); // the gcd of the three numbers, if a number is zero, we replace it with x
     
     a/=g;
     b/=g;
     c/=g;
     
     if(c==0){
       if(b<0){
        b=-b;
        a=-a;
       }else if(b==0){
            a=abs(a); 
       }
     }else if(c<0){
       c=-c;
       b=-b;
       a=-a;
     }
    }
    line(){
    }
};

bool operator <(line a,line b){
if(a.a!=b.a) return a.a<b.a;
if(a.b!=b.b) return a.b><b.b;
return a.c><b.c;
}


We can also define the line structure for working with doubles, but we cannot use a gcd function on reals, so we must modify the operator >< in order to handle correctly the comparisons.
Re: Working with Lines and Segments (response to post by Radheya) | Reply
2.4 Distace of a point to a line

We will solve this using the vectorial form a line. Given P and Q, two pointf of a line, and a point R, we can determine the distance of R to the line defined by P and Q.
Let M be the point of the line, such that the distance of M to R is the minimum possible. Obviusly, the angle formed by the line and the vector SR is 90 degrees and the distance of these points is the distance of the line to R. Besides, we define two vectors: PQ and PR. First we determine the absolute value of the sin of the angle formed by PQ and PR. This is easily computed using the cross product
                 |PQ x PR|
|sin(angle)| =  -----------
                 |PQ|*|PR| 

We know also that if we draw a right triangle with cathethi PS and PR, and hypothenuse SR, the angle formed by PS and PR is the same angle as the formed by PQ and PR. It is easy to notice that the cathethi PS has side equal to |sin(angle)|*|PR|. This gives us this simple formula:
             |PQ x PR|
distance =  -----------
               |PR|

We just have to be aware that P and R could be the same and produce a division by zero. But we know that this is going to happen, the the distance is zero and we can avoid the division.

2.5 Determining if a point lies on a line

Using the same parameters as in the item 2.4, recall that the distance of the point to the line is a cross product divided by a non-negative number, and also, if this distance is zero, then the point lies on the line.
The cross product gives us a multiple of the sin of the angle formed by PQ and PR. If R lies on the line, this sin is zero, then the cross product must be zero. Finally, we know that simply by testing is the cross product is zero we know if the point lies on the line.

3 Line Segments

3.1 Representation

We can representate a line segment simply with two points P and Q, which are the limits of the segment. This is all we need.

3.2 Determining if a point collinear to a segment lies on that segment

Given P and Q, the two limits of a segment, and a point R, such that R is collinear to that segment. We can easily determine if R belongs to the segment by doing this.
bool liescollinear(point P, point Q, point R){
 
    if(P.x==Q.x){ //vertical segment
        if(min(P.y, Q.y)<=R.y && max(P.y, Q.y)>=R.y) return true;
        else return false;
    }else{
        if(min(P.x, Q.x)<=R.x && max(P.x, Q.x)>=R.x) return true;
        else return false;
    }
}

This is correct, because, if the segment is vertical, we only need to know if R is on the interval defined by the y's coordenates, and if the segment is not vertical, we just test in the interval definad by the x's coordenates.


3.3 Determining if a point lies on a segment

Given the same parameters as in the previous item, but with any R (not neccesary collinear to PQ), if we want to know if R lies on the segment PQ, we first determine if R lies on the line that contains the segment. We have already talked about this, and is the simple cross product what we need to do. Now, if that cross product is zero, then we know that R es collinear with the segment and we can use the routine 3.2 to know if R lies on the segment.

bool lies(point P, point Q, point R){
 if(cross(Q - P, R - P) != 0 ) return false;
 else return liescollinear(P, Q, R);
}

3.4 Determining the intersection of two segments

We can do this: first determine the intersection point of the lines defined by both segments. If there is an intersection point, we must test if that point lies on both segments. If that point lies on both segments, then it is the insersection.
If there are infinite intersecion points, then we know that both segments are collinear. To get the intersection interval we can use the routine 3.2 to determine which points of the four given (2 segments) lies on both segments. The resulting points, which are obviously two (handle duplicate points), define the intersection interval.

3.5 Distance of a point to a segment

We have to notice that if the projection point of the point R to the segment PQ lies on the segment, then the required distance is the distance of the point to the line defined by the segment. If this is not the case, the required distance is the minimum of the distance of R to P and R to Q. For determining the proyection point, we can use our methods in this way: we can determine the line that covers the segment, we can also determine a vector orthogonal to that line that passes over R. Now we have two lines and using our method for insersection points, we compute the projection point of R over the line. With this point we can derive to many useful information, such as the distance of the line to R, the reflection point of R over that line, if the projection point belongs to the segment and even more. With this tools, the distance of a point to a segment can ve clearly solved.

4. Useful problems for training

http://uva.onlinejudge.org/external/1/184.html
http://uva.onlinejudge.org/external/1/191.html
http://uva.onlinejudge.org/external/2/270.html
http://uva.onlinejudge.org/external/3/313.html
http://uva.onlinejudge.org/external/3/378.html
Re: Working with Lines and Segments (response to post by Radheya) | Reply
The recipe was a bit long, but covers a lot of important topics. If it needs to be reduced just post it.
Re: Working with Lines and Segments (response to post by Radheya) | Reply
This recipe is a tricky one to comment, especially without "Using Vector Operations" written yet. The overall impression is: we need to shorten this by removing unnecessary theory and add "Discussion" with examples of using this recipe.

More detailed comments (yes, quite a lot of them):

1. Cookbooks don't use numbered lists within one recipe, only "Problem-Solution-Discussion" format.

2. We don't need definitions of line and segment in introduction, we assume that they are intuitive/already known. I think "Problem" should say something like "Now that we are comfortable with using vector operations for doing simple geometry things, let's see how they work for next popular group of problems - problems which deal with lines and segments on the plane". Then you can remove references to R^n from "Solution", since we've already stated that it's R^2.

3. I don't think we need the proof of finding A,B and C from P and Q, just give the formulas (by the way, currently you've got at least one typo in them).

4. When you're dealing with two lines, it's better to use (A1,B1,C1) and (A2,B2,C2), this doesn't require an effort to recall what E or F was.

5. Finding a line which is perpendicular to a given one and comparing/ordering lines looks like they are not exactly popular topics and thus belong to "Discussion".

6. Point-line distance is an important topic, so it does need implementation code (as well as the later one point-segment). I like the way it was given in http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1 .

7. As for segments, I somewhat dislike using the term "collinear points", as it might not be a standard definition of all educational systems (as a matter of fact, it's the first time I've heard it). I'd prefer a generalized problem of determining whether the point belongs to the segment, with one solution as a whole.

8. All examples should be TC problems. We've had enough geometry to be able to choose :-)
Re: Working with Lines and Segments (response to post by Nickolas) | Reply
This recipe rewritten; the actual implementation of all topics is really massive, so I chose to focus on examples and built-in Java implementation.

Problem

Now that we are comfortable with using vector operations for doing simple geometric things, let's see how they work for next most popular group of problems - problems which deal with lines and segments. Lines and segments in all dimensions behave in a similar way, and TopCoder problems rarely use dimensions above second, so this recipe focuses on processing lines and segments on the plane.

Solution

There are two basic ways to represent a line: as a scalar equation { (x,y) | Ax+By+C=0 } and as a vector equation { a+tb }.
These representations are equivalent (i.e., each of them can be rewritten in another form), but allow different operations to be performed easily.

The most common way to describe a line is to specify a pair of points which belong to it P1 and P2. From it, vector equation of the line is obtained immediately as p1 + t * (p2-p1). Scalar equation takes a bit longer to get: it takes solving a system of two linear equations,
A x1 + B y1 + C = 0
A x2 + B y2 + C = 0,
and we are fine with any set of A,B,C, so we can fix one of the coefficients to whatever we like. This gives us
(y1-y2)*x - (x1-x2)*y + (x1*y2-x2*y1) = 0

One of the basic geometric tasks is to find the distance from point C to line AB; it can be calculated as follows (image here).
Area of triangle ABC can be found either as base*height/2, or as cross(AB, AC)/2, thus its height (which is the required distance) is
|cross(AB, AC)|/|AB|.

The same formula is main part of calculating distance from point C to segment AB; we only have to check that the closest point of the line AB does belong to the segment AB; if it doesn't, the distance to the segment is the distance to the closest endpoint of the segment. This can be checked using dot product of segment and vector from C to one of its endpoints. (image here)

Another basic task is to find the intersection of two lines. This is done by solving a system of equations
A1 x + B1 y + C1 = 0
A2 x + B2 y + C2 = 0
This system can produce either 0 solutions (parallel lines), 1 solution (proper intersection) and infinite number of solutions (coinciding lines).

Intersection of two segments works in a similar way, but in case of collinear segments we'll have to check whether they do intersect, and
in case of proper intersection - to check whether the intersection point belongs to both segments. Overall, geometry of this kind is not a single formula but rather a lot of "what if" checks, and that's the main reason why it's not the favorite topic for most people.

Discussion

As with all geometry, topics covered in this recipe really should be pre-written. Even if you need a single intersection check (which is rarely a case), you'll save yourself a lot of trouble (and possibly some troubleshooting) if you have this code ready beforehand. Besides, such geometry tasks are seldom the main part of the problem, so being able to save time on implementing them allows to put more effort in the main logics.

Java provides built-in class Line2D, which eases geometrical calculations involving segments a lot: it allows to check segments for intersection and to find distance from point to segment right away. Its use is somewhat limited: it doesn't allow processing lines or finding intersection point, and it doesn't distinguish intersecting segments from overlapping ones, so it won't work in problems like Segments. However, for basic tasks Line2D can be quite handy. Here, for example, is code for BestView; note that all necessary geometry is done literally in two lines.

import java.awt.geom.*;
 
public class BestView
{
    public int numberOfBuildings(int[] h)
    {   int i,j,k,maxs=0,s;
        boolean seen[][] = new boolean[50][50];
        for (i=0; i<h.length; i++)
        {   seen[i][i]=false;
            if (i+1<h.length)
                seen[i][i+1]=true;
            for (j=i+2; j<h.length; j++)
            {   //check all ones between them
                seen[i][j]=true;
                Line2D.Double l = new Line2D.Double();
                l.setLine(i,h[i],j,h[j]);
                for (k=i+1; k<j; k++)
                    if (l.intersectsLine(k,0,k,h[k]))
                    {   seen[i][j]=false;
                        break;
                    }
            }
        }
        for (i=0; i<h.length; i++)
        for (j=i+1; j<h.length; j++)
            seen[j][i] = seen[i][j];
 
        for (i=0; i<h.length; i++)
        {   s=0;
            for (j=0; j<h.length; j++)
                if (seen[i][j])
                    s++;
            maxs = Math.max(maxs,s);
        }
        return maxs;
    }
}


An example of finding distance from point to line is problem Aircraft. It can be simplified down to figuring out the minimal distance between point (0,0) and a ray which starts at p=p2-p1 and continues in direction v=v2-v1 (image here). We check whether (p2-p1) is actually the closest point to (0,0), and use for comperisons either distance to it or distance to the line, calculated as |cross(p,v)|/|v|. Comparisons are done using squared distances to avoid floating point imprecision, and calculations are done in long long to avoid overflow errors. C++ code follows:

#include <vector>
#include <string>
 
using namespace std;
 
#define P(a) ((long long)(a)*(a))
 
class Aircraft {
public:
    string nearMiss(vector <int> p1, vector <int> v1, vector <int> p, vector <int> v, int R) {
        for (int i=0; i<3; i++)
        {   p[i] -= p1[i];
            v[i] -= v1[i];
        }
        //check whether the closest point is simply p
        long long dot = p[0]*v[0]+p[1]*v[1]+p[2]*v[2], dist2, R2=R*R;
        if (dot>=0)
            dist2 = P(p[0])+P(p[1])+P(p[2]);
        else
        {   dist2 = P(p[0]*v[1]-p[1]*v[0])+P(p[0]*v[2]-p[2]*v[0])+P(p[2]*v[1]-p[1]*v[2]);
            R2 *= P(v[0])+P(v[1])+P(v[2]);
        }
        return ( dist2 <= R2 ? "YES" : "NO" );
    }
};
See Also

(should point to some implementation of segment intersection and point-segment distance - maybe this tutorial)
Re: Working with Lines and Segments (response to post by Nickolas) | Reply
A*x+B*y+C=0 is the worst line equation I know. From my experience all the things with lines are done perfectly with dot product: (x; y) and cross product [x; y]. Norm is |x| = sqrt( (x; x) );

Here are the most common line equations I use:
1. (P - A; N) = 0
Here N is normal to line and A is any point on the line. P=<x; y> is the variable point.
2. [P - A; B - A] = 0
Perhaps the most useful equation because here A and B are any two distinct points on the line.
3. P(t) = A + (B-A)*t parametric equation
Extremely useful when segments/rays are involved because the domain of t regulate the behavior of borders.

Now some other nice routines:
1. Oriented distance between point P and line is (P - A; N) / |N|. You can also use any other line equation easily here.
2. The point P lies on the segment A -- B if:
[P - A; B - A] = 0 and
(P - A; B - A) >= 0 and
(P - B; A - B) >= 0
3. To intersect two lines/rays/segments A--B and C--D you do the following:
D = [B - A, D - C];
Du = [C - A, D - C];
Dv = [C - A, B - A];
Then u = Du/D and v = Dv/D are parameters of intersection point for both lines.
Here you can place additional requirements on the parameters. For example, if you intersect two segments, you place requirement that u>=0 and u<=1 and v>=0 and v<=1. If you intersect the rays, then you write only the condition that u>=0 and v>=0.
After doing the checks you get the point from the parametric equation:
P = A + (B-A)*u
RSS