mat64: implement triangle shadow detection

[kortschak]

Fixes #357.

Needs proper tests for triangle cases. Still thinking.

[vladimir-ch]

The notion of projecting the corners on the top row (or left column) of a is making the reasoning more difficult, at least for me. I'm not sure about this but, taking the situation aUpper and bUpper as an example, wouldn't testing the upper right corner of b against the diagonal of a and the upper left corner against the right column of a on a given row of a work equally well? In other words, translate the top corners of b into the index space of a and test it there. For me it would make the test clearer.

Thinking about it, since you check overlap of the rectangles, in the above situation we could even skip testing the upper left corner of b. Or skip the rectangle overlap, and just check the two corners.

Isn't there a catch that I might be missing?

[kortschak]

The notion of projecting the corners on the top row (or left column) of a is making the reasoning more difficult, at least for me. I'm not sure about this but, taking the situation aUpper and bUpper as an example, wouldn't testing the upper right corner of b against the diagonal of a and the upper left corner against the right column of a on a given row of a work equally well? In other words, translate the top corners of b into the index space of a and test it there. For me it would make the test clearer.

I find this very difficult to reason about. Can you show me what you're saying in code?

Thinking about it, since you check overlap of the rectangles, in the above situation we could even skip testing the upper left corner of b. Or skip the rectangle overlap, and just check the two corners.

That is true. This is the converse of the other case. Nice.

[kortschak]

That is true. This is the converse of the other case. Nice.

Sorry. No.

 a
 aa
 a a
 a  a  bbbbbbbbbb
 a   a  b       b
 a    a  b      b
 a     a  b     b
 a      a  b    b
 aaaaaaaaa  b   b
             b  b
              b b
               bb
                b

[vladimir-ch]

Can you show me what you're saying in code?

I'll try to but I think that in the end it will boil down to a similar set of checks.

That is true. This is the converse of the other case. Nice.

Sorry. No.

In the comment I was considering just the case of aUpper to simplify the reasoning. At any case, don't take me too seriously.

[kortschak]

In the comment I was considering just the case of aUpper to simplify the reasoning.

Ahh, sorry. Yes, I think you are right.

[kortschak]

Though I'm not sure it simplifies anything.

[vladimir-ch]

Ok, no code is necessary. We are not thinking the same thing but almost and my concept does not simplify anything. But maybe we can remove the rectangles overlap check without complicating anything. I'll comment in the code.

[vladimir-ch]

Being a true pioneer of dead ends, I've come to the conclusion that projecting onto the first row or column makes more sense, especially because of the !aUpper case. Sorry for the noise :-)

[kortschak]

@vladimir-ch I have complete tests now. It's clear now that the conditions are not quite right, though the geometry is subtle. I'm going to leave it for a while, but if you feel like having a play and suggesting changes, please do.

[kortschak]

The issue seems to be that I'm not properly accounting for the modular nature of the space I'm working in, but I've not figured out a good way of handling it.

[kortschak]

The idea is to only work in mod space to get relative positions and then do all the comparisons in normal space. The stanza required to get offsets is as follows:

    // Find location of b relative to a.
    rowOffset := off / stride
    colOffset := off % stride
    if (off+bSize)%stride < colOffset {
        // We have wrapped, so readjust offsets.
        rowOffset++
        colOffset -= stride
    }

[kortschak]

This works now. The conditions are inelegant and I'm sure that there are redundant checks, but this is reviewable.

PTAL

[kortschak]

This fails on tip (as does rectangle overlap). I'll bisect that tomorrow.

[kortschak]

Failure issue filed: https://github.com/golang/go/issues/15042.

[btracey]

This looks correct to me. I'll let @vladimir-ch give the official goahead

[vladimir-ch]

LGTM