2
$\begingroup$

I'm trying to find a mathematical formula that will return the number of vertices for an $m x n$ grid of elements. The tricky part is that any grid element is allowed to span multiple rows or columns.

Let's define the bottom left corner of a grid element as it's position and say that the origin [x=0,y=0] of any grid is the bottom left corner, where +x is to the right and +y is up.

Here are some examples to help one visualize the problem:

enter image description here

The description grids 1, 2, and 3 are:

  1. 2x2 Grid - comprised of (2) 1x1 elements at positions [0,0] and [0,1] (1) 2x1 element at position [1,0]
  2. 2x3 Grid - comprised of (4) 1x1 elements at positions [0,1] [1,1] [2,1] [0,2] and (1) 1x2 element at position [0,0]
  3. 2x4 Grid - comprised of (3) 1x1 elements at positions [0,0] [2,1] [3,1], (1) 1x2 element at position [0,1], and (1) 1x3 element at position [1,0]

If for an $mxn$ grid we know the total number of grid elements ($cnt$) and for each grid element we know it's position ($[x , y]$) and size ($l$ x $w]$), is there a formula that we may derive to calculate the number of unique vertices in said grid?

*** Note that unique vertices are shown as blue dots in the aforementioned Example Image

Thank you

01/16/2015 EDIT: I came up with a new example (4.) that is missing a grid element, it is desired for the formula to be able to calculate the number of unique vertices for an incomplete grid as well Click here to see new example #4

$\endgroup$
1
  • $\begingroup$ So the input to your function would be, effectively, a finite list of non-overlapping rectangles? I can think of a computer algorithm to solve that, which is a function of sorts, but I'm not sure how a purely mathematical description of the function would look like. It's effectively the cardinality of the set of all corner points for all of the rectangles. $\endgroup$
    – user2469
    Commented Jan 15, 2016 at 3:13

3 Answers 3

1
$\begingroup$

I think from your input you can simply calculate the position of each of the four vertex. It is going to be:

[x,y] , [x+l,y] , [x,y+w] , [x+l,y+w]

Then you sort this list of 4*cnt elements and remove duplicates and count the cardinality. I don't think you can have a closed formula because the domain of your function depends on how many grids you have:

vertex = $f(g_1,g_2,....,g_{cnt})$

where $g \in N^4$ (4 dimension arrays of natural numbers)

$\endgroup$
3
  • $\begingroup$ As @barrycarter pointed out, the context of this problem in indeed a computer algorithm. Maurizio De Leo, I appreciate this method, as it's easy to sort and remove duplicates in code. I have tried it on a few new shapes that I imagined and am happy to say that it works very well! Thank you very much! $\endgroup$
    – brio50
    Commented Jan 16, 2016 at 18:04
  • $\begingroup$ Wait, I may have jumped the gun here: It doesn't work on the example that I gave Alex, "take the grid in example image 1 and remove the bottom left element." Sorry for not including this gotcha in the original post. Using your method I get 6 unique vertices, when it should be 7. Is it as simple as just subtracting the # of elements missing from your method? I edited the original post to include an example image. Thanks $\endgroup$
    – brio50
    Commented Jan 16, 2016 at 18:37
  • $\begingroup$ It may be an issue with the implementation. The grid has 2 elements, so the input [x,y],(l,w) is [0,1], (1,1) and [1,0], (2,1). The list of vertices that we obtain is {0,1},{1,1},{0,2},{1,2} and {1,0},{3,0},{1,1},{3,1}. Sorting we get {0,1},{0,2},{1,0},{1,1},{1,1},{1,2},{3,0},{3,1} and eliminating the duplicate {1,1} we are left with the correct 7. Sorting a 2 element array must be done first on one element, then on the other. $\endgroup$ Commented Jan 18, 2016 at 5:36
1
$\begingroup$

Let $f$ be the number of "elements", $v$ be the number of interior full nodes, and $h$ be the number of half nodes. Then counting right angles we obtain $$4f=4v+2h+4\ ,$$ which is essentially Euler's formula in this situation. Now one can refine this by taking the size of the "elements" into account, and counting the "null nodes" as well.

$\endgroup$
1
  • $\begingroup$ Thank you very much Christian, I think Maurizio's solution is easiest for me to implement since it's being handled by computer code. I appreciate your answer. In trying to understand it however, it was not clear to me what a full or half node is. Can you clarify please? Is a full node where four corners meet, half node where two or three corners meet, and null where no corners meet? $\endgroup$
    – brio50
    Commented Jan 16, 2016 at 18:08
1
$\begingroup$

If you know the number of vertices where $4$ rectangles meet then here's a formula.

e.g. in Example 1 there are none, in Example 2 there is one vertex (2,1) and in example 3 there are none.

Let $r$ be the number of rectangles and $s$ be the number of vertices where $4$ rectangles meet, then the number of unique vertices is

$$2\cdot (r+1)-s$$

This gives $2\cdot 4-0=8$, $2\cdot 6-1=11$ and $2\cdot 6-0=12$ correctly.

EDIT: I assumed that the region is rectangular. To make this formula work for more complicated shapes it becomes more complicated. Define:

  • $s_1 = $ number of vertices that have $1$ corner of a rectangle.
  • $s_2 = $ number of vertices that have $2$ corners of a rectangle.
  • $s_3 = $ number of vertices that have $3$ corners of a rectangle.
  • $s_4 = $ number of vertices that have $4$ corners of a rectangle.

Anyhow, the formula for unique vertices is

$$\begin{align} v&=s_1+s_2+s_3+s_4\\ &=4r-s_2-2s_3-3s_4 \\ &=2r+\frac{s_1-s_3}{2}-s_4 \\ &=\frac{4r+2s_1+s_2-s_4}{3} \\ &=r+\frac{3s_1+2s_2+s_3}{4} \end{align}$$

Previously I chose to give you the middle equation with $s_1=4, s_3=0$, but we can't make these assumptions if the region isn't necessarily rectangular.

e.g. This works for the new example $4$ with $r=2,s_1=6,s_2=1,s_3=0,s_4=0,v=7$.

$\endgroup$
4
  • $\begingroup$ Alex, this formula works very well for the three examples shown in the example image, however I came up with a new example where a grid element is missing and it does not work. For instance, take the grid in example image 1 and remove the bottom left element, $2(r+1) - s = 2(2+1) - 0 = 6$, which should be $7$. I realize that's not one of the examples I offered, but I would like the formula to be able to work for scenarios where the grid of elements is not entirely filled. Thanks for your help! $\endgroup$
    – brio50
    Commented Jan 16, 2016 at 18:23
  • $\begingroup$ @brio50 yes, I assumed that the grids are rectangular. It's possible to adjust it, but the formula will get more complicated. $\endgroup$
    – Alex
    Commented Jan 16, 2016 at 19:54
  • $\begingroup$ I'm interested if you have any thoughts! $\endgroup$
    – brio50
    Commented Jan 18, 2016 at 4:23
  • $\begingroup$ Thank you so much Alex - its easiest for me to think of $s_1$ as grid vertices with unique coordinate value, $s_2$ as grid vertices with two duplicate values, $s_3$ as grid vertices with three duplicate values, and so on. What I'm getting at, is that I think I can still collect all of the vertex coordinates, like @Maurizio De Leo 's method, and find $s_n$ based on the unique, pairs of duplicates, triples of duplicates, and quadruples duplicates (hope this makes sense). Again I'm trying to implement this in code, so I want to leverage sorting and duplicate finding! $\endgroup$
    – brio50
    Commented Jan 21, 2016 at 6:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .