loop without break in Python

Question

I try to write the fastest code that would select a point inside a contour. I need the point coordinates, not the pixels from the image. I wrote this definition OnePointInsideContour

Determine if a point is inside or outside of a shape with opencv

def OnePointInsideContour(contourArray, PointTuple, tol):
L = len(contourArray);
y0 = PointTuple[0]; # horizontal
x0 = PointTuple[1]; # vertical
ret = [];
inside = False;
counter = 0

for k in range(L):
    ycont = list(contourArray[k])[0];
    xcont = list(contourArray[k])[1];
    if ycont > y0 - tol and ycont < y0 + tol and xcont > x0: 
        p = (ycont, xcont); 
        counter += 1; 
        ret.append(p);
        break

for k in range(L):
    ycont = list(contourArray[k])[0];
    xcont = list(contourArray[k])[1];
    if ycont > y0 - tol and ycont < y0 + tol and xcont < x0: 
        p = (ycont, xcont); 
        counter += 1; 
        ret.append(p);
        break           

for k in range(L):
    ycont = list(contourArray[k])[0];
    xcont = list(contourArray[k])[1];
    if xcont > x0 - tol and xcont < x0 + tol and ycont < y0:
        p = (ycont, xcont); 
        counter += 1; 
        ret.append(p);
        break  

for k in range(L):
    ycont = list(contourArray[k])[0];
    xcont = list(contourArray[k])[1];
    if xcont > x0 - tol and xcont < x0 + tol and ycont > y0: 
        p = (ycont, xcont); 
        counter += 1; 
        ret.append(p);
        break

if counter == 4:
    inside = True

return inside, ret

but the fact that it uses 4 loops to iterate along contour each time a new point is tested, means that the execution time for 100 k points is about 1 hour! In the image below I show an example a successful confirmation that a given point (black dot) is inside the contour. This takes 0.012 seconds just for one point.

The problem is that there may be a few other dots on the contour near each of the North(red), South(green), East(cyan) and West(blue) points and for this reason once the first point is found the for loop is stopped with break and a new one starts, looking for the next condition.

Only if all four coloured dots are found on the contour, the test point is accepted as being inside.

Any suggestion how to make the execution faster?

Answer 1

You can surely reduce the computation time by improving the looping operations. For example, you can try something like:

found1, found2, found3, found4 = False, False, False, False
for k in range(L):
    ycont = list(contourArray[k])[0]
    xcont = list(contourArray[k])[1]
    
    if not found1 and (ycont > y0 - tol and ycont < y0 + tol and xcont > x0): 
        p = (ycont, xcont)
        counter += 1 
        ret.append(p)
        found1 = True
            
    if not found2 and (ycont > y0 - tol and ycont < y0 + tol and xcont < x0): 
        p = (ycont, xcont)
        counter += 1
        ret.append(p)
        found2 = True

    if not found3 and (xcont > x0 - tol and xcont < x0 + tol and ycont < y0):
        p = (ycont, xcont)
        counter += 1
        ret.append(p)
        found3 = True

    if not found4 and (xcont > x0 - tol and xcont < x0 + tol and ycont < y0):
        p = (ycont, xcont)
        counter += 1 
        ret.append(p)
        found4 = True

Note that you need to avoid breaking the loop since you're trying to iterate over L one time only. You seem to have some code replication that you can get rid of, all the parts below can be written as a function.

...
p = (ycont, xcont)
counter += 1 
ret.append(p)
...