Register Now
Member Count: 627,716 - April 23, 2014  [Get Time]
Login
forums   
Round Tables
News Discussions
Algorithm Matches
Marathon Matches
NASA Tournament Lab
Software Forums
TopCoder Cookbook
High School Matches
Sponsor Discussions
Search Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase 2.2. Using Vectors in Geometry Problems
2.2. Using Vectors in Geometry Problems | Reply
This is a new recipe, but based on more specific recipe by bmerry.

Problem

Geometry problems are quite frequent at TopCoder - at least way more frequent than a lot of people would like them to be.

A lot of 2D computational geometry problems can be solved using concept of vector - an object which has length and direction but not start and end points. It can be thought of as directed line segment, but in calculations it's usually represented as a pair of numeric coordinates in Cartesian system (the coordinates of vector endpoint if its start was placed in (0,0)). Let's have a look at the main properties of vectors and their application to solving TopCoder problems.

Solution

The main operations that can be performed with vectors in coordinates-based representation are:
- length: |(x, y)| = sqrt(x*x+y*y)
- multiplication by scalar: a * (x, y) = (a*x, a*y)
- sum and difference: (x1, y1) +- (x2, y2) = (x1 +- x2, y1 +- y2)
- dot product: (x1, y1) * (x2, y2) = x1*x2 + y1*y2 = |(x1, y1)| * |(x2, y2)| * cos theta.
- cross product: (x1, y1) x (x2, y2) = x1*y2 - x2*y1 = |(x1, y1)| * |(x2, y2)| * sin theta.
Here theta is the angle between vectors, calculated counterclockwise from (x1,y1) to (x2,y2).

These operations are the basics for building more complicated algorithms and processing more complex geometrical entities, which will be discussed in later recipes. However, even this level of detail can be used for solving problems. One of the most common applications is calculating area of a triangle built on two vectors as half of their cross product.

Discussion

Vectors are the kind of object that really should be pre-written beforehand; same as common fractions, one or two operations on them can be done without corresponding class, but for a problem with lots of calculations a pre-written class is much more convenient. The exact implementation is really simple and can vary depending on your preferred style of classes definition.

An interesting C++ implementation of vectors involves using complex<> class. It already provides some of the required operations (addition, subtraction, multiplication by scalar and length), and the others are easy to implement (remember that conj() negates second coordinate):

#include <complex>
using namespace std;
 
typedef complex<double> point;
 
double dot(const point &a, const point &b)
{ return real(conj(a) * b); }
 
double cross(const point &a, const point &b)
{ return imag(conj(a) * b); }
 
double signed_area(const point &a, const point &b, const point &c)
{ return cross(b - a, c - a) * 0.5; }


One could also overload operators for products; a possible convention is to use operator | for dot product (this way (a|b) looks quite like the inner product in the bra-ket notation), and operator ^ for cross product.

Thinking in terms of angles makes it possible to compactly represent some operations that would be more difficult in conventional vector algebra. For example, consider reflecting a point in a line through the origin. First, we can rotate the problem so that it becomes a case of reflecting about the real axis; this is achieved by division. The reflection itself can then by achieved by conj, after which we just have to reverse the rotation to obtain the original coordinate system. This leads to the example code above; it just so happens that the operations on the length all cancel out, so it is not even necessary for line to be unit-length.

/ Rotate p by theta radians
p *= exp(point(0, theta));
 
// Reflect p in the line (0, 0) - line
p = conj(p / line) * line;


The examples above use complex<double>, but it's also possible to use integer types e.g. complex<long long>. Working in integers is often a good idea in contest problems since it eliminates the dangers of floating-point rounding. Of course, this can introduce some additional work, like working with the double-area rather than the area of triangles, since the area can be a half-integer; and to find the squared length of a vector, it's better to use dot(x, x) than the actual square of length.

The functions as written above are short and easy to remember, but they're not optimal. For example, the dot- and cross-product functions each compute a complex product and then discard half the result. If you find that performance is just not quite there, you can always modify them later to work directly with the real and imaginary components.

Now, to the examples. Calculation of triangle's area via vector product of its sides is a really common way to avoid floating-point errors introduced by Heron's formula. For example, in FindTriangle after parsing the input one had simply to iterate over all triples of points, check whether they all are either of the same color or of different colors and choose the maximum area of properly colored triangles. The only thing to note is that this problem uses 3D geometry instead of 2D discussed in this recipe, but the cross-product-based formula for triangle area still holds, even though in 3D it looks a bit different. Java solution follows:

class Vector3D {
    public long x,y,z;
    Vector3D(long x1, long y1, long z1)
    {   x=x1;
        y=y1;
        z=z1;
    }
    public Vector3D subtract(Vector3D other)
    {   return new Vector3D(x-other.x, y-other.y, z-other.z);   }
    public long length2()
    {   return x*x+y*y+z*z; }
    public Vector3D cross(Vector3D other)
    {   return new Vector3D(y*other.z - z*other.y, 
                            z*other.x - x*other.z, 
                            x*other.y - y*other.x);   }
}
 
public class FindTriangle {
    public double largestArea(String[] points)
    {   int i,j,k,n=points.length;
        long maxarea=0;
        String[] col = new String[n],t;
        Vector3D[] p = new Vector3D[n];
        Vector3D v1,v2;
        for (i=0; i<n; i++)
        {   t = points[i].split(" ");
            col[i] = t[0];
            p[i] = new Vector3D(Integer.parseInt(t[1]), 
                                Integer.parseInt(t[2]), 
                                Integer.parseInt(t[3]));
        }
        for (i=0; i<n; i++)
        for (j=i+1; j<n; j++)
        for (k=j+1; k<n; k++)
            if (col[i].equals(col[j]) && col[j].equals(col[k]) || 
                !col[i].equals(col[j]) && !col[j].equals(col[k]) && !col[k].equals(col[i]))
            {   v1 = p[i].subtract(p[j]);
                v2 = p[i].subtract(p[k]);
                maxarea = Math.max(maxarea, (v1.cross(v2)).length2());
            }
        return Math.sqrt(maxarea)*0.5;
    }
}


The same trick allows to check whether three points with integer coordinates belong to the same line, as required in DreamingAboutCarrots. Points A, B and C belong to the same line if vectors AB and AC are collinear, i.e., their cross product is 0. C++ solution follows:

#include <algorithm>
 
class DreamingAboutCarrots {
    public:
    int carrotsBetweenCarrots(int x1, int y1, int x2, int y2)
    {   int x,y,n=0;
        if (x1>x2) std::swap(x1,x2);
        if (y1>y2) std::swap(y1,y2);
        for (x=x1; x<=x2; x++)
        for (y=y1; y<=y2; y++)
            if ((x!=x1 || y!=y1) && (x!=x2 || y!=y2) && (x-x1)*(y-y2)-(x-x2)*(y-y1)==0)
                n++;
        return n;
    }
};
Re: 2.2. Using Vectors in Geometry Problems (response to post by Nickolas) | Reply
typedef complex<double> vect;



This is a typo. Or maybe it will be more appropriate to use vect everywhere in this recipe.
Re: 2.2. Using Vectors in Geometry Problems (response to post by wasi.ahmed) | Reply
Right - meant to change it to vect everywhere but got distracted mid-change.
Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase 2.2. Using Vectors in Geometry Problems
Previous Thread  |  Next Thread
RSS