CODEWITHSUNDEEP
algorithmmathgeometry
Spike
Spike

Reputation: 2027

What is the name of this geometrical function?

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.

Upvotes: 2

Views: 237

Answers (4)

Pratik Deoghare
Pratik Deoghare

Reputation: 37172

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] ]

Upvotes: 1

kennytm
kennytm

Reputation: 523254

Integer / lattice points in bounds / rectangle.

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

Upvotes: 1

JSchlather
JSchlather

Reputation: 1603

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.

Upvotes: 1

brainjam
brainjam

Reputation: 19005

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.

Upvotes: 5

Related Questions