What is the name of this geometrical function?

Question

In a two dimentional integer space, you have two points, A and B. This function returns an enumeration of the points in the quadrilateral subset bounded by A and B.

A = {1,1} B = {2,3}

Fn(A,B) = {{1,1},{1,2},{1,3},{2,1},{2,2},{2,3}}

I can implement it in a few lines of LINQ.

private void UnknownFunction(Point to, Point from, List<Point> list)
{
    var vectorX = Enumerable.Range(Math.Min(to.X, from.X), Math.Abs(to.X - from.Y) + 1);
    var vectorY = Enumerable.Range(Math.Min(to.Y, from.Y), Math.Abs(to.Y - from.Y) + 1);
    foreach (var x in vectorX)
        foreach (var y in vectorY)
            list.Add(new Point(x, y));
}

I'm fairly sure that this is a standard mathematical operation, but I can't think what it is. Feel free to tell me that it's one line of code in your language of choice. Or to give me a cunning implementation with lambdas or some such.

But mostly I just want to know what it's called. It's driving me nuts. It feels a little like a convolution, but it's been too long since I was at school for me to be sure.

Answer 1

It's the Cartesian product of the sets {1,2} and {1,2,3} in your specific example, or generally the Cartesian product of the vectorX and vectorY in your code example.

Answer 2

I don't know that this is a standard mathematical operation, if you wanted to describe it mathematically it would be described as such.

Given two points, (x_1,x_2) and (y_1,y_2) in N^2. Then take min_1 to be min(x_1,y_1) and max_1 to be max(x_1,y_1) and symetric operations for min_2 and max_2. Then the set is defined as:

Enum = { (a,b) : a,b in N^2 and min_1 <= a <= max_1 and min_2 <= b <= max_2 }

Which seems pretty arbitrary to me and I would say that it doesn't seem like a fairly standard mathematical operation to me.

Solving it using the Cartesian product becomes, trickier. It was simple to use the cartesian product when you have points that are so close together, but what about when you have {1,1} and {8,8}. Then the problem is a little more involved. You take the two sets:

{ a: min(x_1,y_1) <= a <= max(x_1,y_1) } and {b : min(x_2,y_2) <= b <= max(x_2,y_2) }

In both instances you're simply taking all the values in the range and enumerating across the space. Once again though, it feels like an arbitrary operation and maybe I'm wrong, but I don't think this has a well-known name. Besides enumerating the points in a rectangle.

Answer 3

Integer / lattice points in bounds / rectangle.

(Similar to the name of http://en.wikipedia.org/wiki/Integer_points_in_convex_polyhedra)

Answer 4

Cartesian Product using list comprehensions in

Python

[(x,y) for x in [1,2] for y in [1,2,3] ]

and Haskell

[(x,y) | x <- [1,2] , y <- [1,2,3] ]