Why are we sorting vertices to calculate 2D intersection? about rotated_iou HOT 3 CLOSED

The formula is called "shoelace formula". This formula requires that all vertices must be sorted in clockwise or counter-clockwise order.

For the intersection of boxes, there are two types of vertices. "intersections of edges" and "corners in boxes", as the green ones and red ones in this Picture show. The basic idea of my code is:

1. find these two types of vertices, respectively
2. sort them in clockwise/counter-clockwise order
3. use the shoelace formula to get the area.

My implementation needs this sort() because it finds the two types of vertices separately, which is intuitive and naive. The other implementations use a more elegant "sequential cutting" algorithm to find all vertices at once. To be honest, I'm not an expert in geometry. But this algorithm seems to provide sorted vertices directly so that there is no need to sort them afterward.

I think the "sequential cutting" is probably faster than my implementation but the result should be the same.

from rotated_iou.

ok that makes sense. My only concern is how that sort will affect the backwards pass when differentiating.

from rotated_iou.

The back-propagation is explained in issue #7. The trick is to use torch.gather() and the sorting itself doesn't need a backward pass.

from rotated_iou.