current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Join the Stack Overflow Community
Stack Overflow is a community of 6.5 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up
up vote 0 down vote favorite

Say I have an MxN binary matrix. It is not necessarily sparse. I'm interested in finding the coordinates of the apexes of all of the right triangles in the array. By right triangle, I mean: pretend that the 1 or True values in the matrix are vertices of triangles, and the 0's or False elements are null. Then a right triangle is an arrangement that visually forms a right triangle. By apex I mean the vertex which corresponds to the right angle of the triangle. E.g. in the following 5x6 array:

0 0 1 0 1 0
0 1 0 0 0 0
1 0 0 1 0 1
0 0 1 0 0 0
0 0 0 0 0 0

There is only 1 right triangle. It is the triangle with vertices at: (0,2) is the apex, (3,2) is the lower left, (0,4) is the upper right, where I'm indexing from 0, starting at the top left [Python indexing].

For a given MxN array, I want a Python function F(A) that returns an array L of subarrays, where each subarray is the coordinate pair of the apex of the right triangles in the array. For the case where the same element of the array is the apex of multiple triangles, ultimately I'll just want unique subarrays, but for now the function can duplicate them. As an example, for the array A above, F(A) would return the array L = [[0,2]]

My first thought would be to use row and column sums. Those rows with a row sum >= 2 are worth exploring, and then use the columns sum >=2. Then you would need an efficient way to find the intersections. I would be interested in a function using this method or any other method which might be better and faster.

{E.g. as an alternative, you could think about this from a graph theory perspective. The rows and columns would be nodes of a bipartite graph [the rows would be one set, the columns the other set]. Then the matrix shown here would be one quadrant of the adjacency matrix of the full bipartite graph. In other words, it would be the part of only the cross terms between the row and column sets, since the within set parts would all be 0 since the row nodes don't connect to other row nodes; only to column nodes. From this perspective, a right triangle would look like a path of length 3 on the bipartite graph. I think the matrix approach is simpler, but I'm open to any algorithms here.}

share|improve this question
1  
Are you restricted to triangles whose sides are orthogonal to the axes? If not, you have another right triangle at (2,3) (0,4) (1,1), with legs of length sqrt(5). In this case, the problem gets harder. – Prune 2 days ago
1  
Yes, restricted to triangles with 2 sides orthogonal to axes. So a better way to define right triangle is a set of 3 elements such that 2 of the elements share a row and 2 of the elements share a column. So one side will be horizontal, another vertical, and the hypotenuse will be diagonal (not aligned with either axis). – sambajetson 2 days ago
    
Is the matrix particularly large and sparse, that we have to consider alternate methods of checking the elements? Simple brute force with a couple of any checks will do the job. – Prune 2 days ago
    
Yeah, it will probably be sparse and large but not huge (10's of thousands in both dimensions). – sambajetson 2 days ago
    
Generate the row and column sums. Then for every 1 in the array, it's an apex if the corresponding row and column sums are both >1. – user3386109 2 days ago
up vote 1 down vote

Yes, I believe that you're over-thinking this. Generate the row and column sums, and check each array location for intersection.

I haven't tested the syntax, but it will be something like this:

# Generate row and column sums
row_sums = (sum(A[M]) for M in range(len(A)))
col_sums = (sum([A[M, N] for M in range(len(A))] for N in range len(A[0]))

# Now, check each element in the array for being a vertex
vertices = 
    [(row, col) if A[row, col] and row_sums[row] > 1
                               and col_sums[col] > 1
          for row in range(len(A)) for col in range(len(A[0]))]

# You now have a list of all solutions, with no duplicates.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.