I'm writing a program using opencv libraries that is performance is critical. I have found a solution to this problem, but the performance is very slow, so I'm hoping a mathematical approach may present a solution with better performance. The closest I've seen is
Problem: Given two polygons (ALWAYS trapezoids that are parallel to the X axis), I would like to calculate by some means how much they match up. By this, I mean overlapping area is not sufficient, because if one polygon has excess area, somehow that needs to count against it. Optimally, I would like to know what percent of the area created by both polygons is common. See image for example as what is desired.
A working (but slow) solution:
- Draw polygon one on an empty image (cv::fillConvexPoly)
- Draw polygon two on an empty image (cv::fillConvexPoly)
- Perform a bitwise and to create an image of all the pixels that overlapped
- Count all nonzero pixels --> overlapped Pixels
- Invert the first image and repeat with non-inverted second --> excessive pixels
- Invert the second image and repeat with non-inverted first --> more excessive pixels
- Take the 'overlapped pixels' over the sum of the 'excessive pixels'
As you can see the current solution is computationally intensive because it is evaluating/ operating on every single pixel of an image ~12 times or so. I would rather a solution that calculates this area that goes through the tedious construction and evaluation of several images.
Given:
(x11, y11, x12, y12, x13, y13, x14, y14) where y11 = y12, y13 = y14
(x21, y21, x22, y22, x23, y23, x24, y24) where y21 = y22, y23 = y24
Desired:
Percentage match