Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
No numpy solution in Uncategorized category for Inscribe a Contour by alterGNU
from math import pow, sqrt, degrees, acos
# From points a:(xa, ya) and b:(xb, yb) return vector ab:(xab, yab)
vect=lambda a,b: (b[0]-a[0], b[1]-a[1])
# Return norm of x vector
norme=lambda x: sqrt(pow(x[0],2)+pow(x[1],2))
# Return angle:(u^v) (°degrees) made by vect:u and vect:v
angle=lambda u,v: degrees(acos((u[0]*v[0]+u[1]*v[1])/(norme(u)*norme(v))))
def coord_H(a,b,c):
"""
Calculate and return the point H, orthogonal projection of the line passing through c and
cutting (ab)
"""
t = ((-1)*((a[1]-b[1])*(b[1]-c[1])+(a[0]-b[0])*(b[0]-c[0])))/(pow((a[0]-b[0]),2)+pow((a[1]-b[1]),2))
hx= b[0] + (a[0]-b[0])*t
hy= b[1] + (a[1]-b[1])*t
return (hx, hy)
def extremums(points: list) -> list:
"""
Return extremum list : [xmin,ymax,xmax,ymin]
"""
x_list=[ x for (x, y) in points ]
y_list=[ y for (x, y) in points ]
return [min(x_list),max(y_list),max(x_list),min(y_list)]
def addA(LA,pt1,pt2,points):
"""
Insert next contour_point between pt1 and pt2 in list of contour point LA
"""
candidats = [c for c in points if ((pt1[0]0]
if angle_point_list != []:
maximum=angle_point_list[0]
for i in angle_point_list:
if (i[0]>maximum[0]):
maximum = i
elif (i[0]==maximum[0])and(i[1][1]>maximum[1][1]):
maximum = i
newA = angle_point_list.pop(angle_point_list.index(maximum))
LA.append(newA[1])
newPoints=[y for (x,y) in angle_point_list]
addA(LA,newA[1],pt2,newPoints)
def addB(LB,pt1,pt2,points):
"""
Insert next contour_point between pt1 and pt2 in list of contour point LB
"""
candidats = [c for c in points if ((pt1[0]0]
if angle_point_list != []:
maximum=angle_point_list[0]
for i in angle_point_list:
if (i[0]>maximum[0]):
maximum = i
elif (i[0]==maximum[0])and(i[1][0]>maximum[1][0]):
maximum = i
newB = angle_point_list.pop(angle_point_list.index(maximum))
LB.append(newB[1])
newPoints=[y for (x,y) in angle_point_list]
addB(LB,newB[1],pt2,newPoints)
def addC(LC,pt1,pt2,points):
"""
Insert next contour_point between pt1 and pt2 in list of contour point LC
"""
candidats = [c for c in points if ((pt2[0]0]
if angle_point_list != []:
maximum=angle_point_list[0]
for i in angle_point_list:
if (i[0]>maximum[0]):
maximum = i
elif (i[0]==maximum[0])and(i[1][0]0]
if angle_point_list != []:
maximum=angle_point_list[0]
for i in angle_point_list:
if (i[0]>maximum[0]):
maximum = i
elif (i[0]==maximum[0])and(i[1][1]>maximum[1][1]):
maximum = i
newD = angle_point_list.pop(angle_point_list.index(maximum))
LD.append(newD[1])
newPoints=[y for (x,y) in angle_point_list]
addD(LD,newD[1],pt2,points)
def contour(points: list)-> list:
"""
Return contour point list
"""
# 3 points case : they're all contour point
if len(points) == 3 :
return points
# extremums
ext=extremums(points)
# Immuable octagon's portions
s1 = [(x, y) for (x, y) in points if x==ext[0]] # xmin
s2 = [(x, y) for (x, y) in points if y==ext[1]] # ymax
s3 = [(x, y) for (x, y) in points if x==ext[2]] # xmax
s4 = [(x, y) for (x, y) in points if y==ext[3]] # ymin
# Octagon's portions where contour points can be add
pA = [max(s1),min(s2)] # Portion A
pB = [max(s2),min(s3)] # Portion B
pC = [min(s3),max(s4)] # Portion C
pD = [min(s4),min(s1)] # Portion D
# add contour point to Portion A
LA=[pA[0]]
addA(LA,pA[0],pA[1],points)
LA.append(pA[1])
# add contour point to Portion B
LB=[pB[0]]
addB(LB,pB[0],pB[1],points)
LB.append(pB[1])
# add contour point to Portion C
LC=[pC[0]]
addC(LC,pC[0],pC[1],points)
LC.append(pC[1])
# add contour point to Portion D
LD=[pD[0]]
addD(LD,pD[0],pD[1],points)
LD.append(pD[1])
# Creation of the ordered list of contour points:
raw_list = LA + LB + LC + LD
# No duplicate point
final_list = [ raw_list[i] for i in range(len(raw_list)-1) if raw_list[i]!=raw_list[i+1] ]
# Make shure to add last point of raw_list if it ands with a duplicate point
if raw_list[-2] == raw_list[-1]:
final_list.append(raw_list[-1])
# buckle closure
if final_list[0] != final_list[-1]:
final_list.append(final_list[0])
return final_list
def min_air(bordure: list)->float:
"""
Go through the list of contour points, then for each segment they form, determine the air of the
minimum rectangle in which all the points are inscribed.
Returns the minimum calculated air value.
"""
bords = bordure
seg=[(bords[i],bords[i+1]) for i in range(len(bords)-1)]
air=[]
for s in seg:
other = {o for o in set(bordure)}-{s[0],s[1]}
list_c=[ (coord_H(s[0],s[1],c),c) for c in other ]
largeur=max([norme(vect(v[0],v[1]) )for v in list_c])
list_p=[s[0],s[1]]+[ p[0] for p in list_c]
longueur=[]
for i1 in range(len(list_p)):
for i2 in range(len(list_p)):
longueur.append(norme(vect(list_p[i1],list_p[i2])))
air.append(max(longueur)*largeur)
return min(air)
def inscribe(points):
liste_contour=contour(points)
return min_air(liste_contour)
if __name__ == '__main__':
def close_enough(contour, answer):
result = inscribe(contour)
assert abs(result - answer) <= 1e-3, \
f'inscribe({contour}) == {answer}, and not {result}'
# These "asserts" are used for self-checking and not for an auto-testing
close_enough([(1, 1), (1, 2), (0, 2), (3, 5), (3, 4), (4, 4)], 6.0)
close_enough([(6, 5), (10, 7), (2, 8)], 20.0)
close_enough([(2, 3), (3, 8), (8, 7), (9, 2), (3, 2), (4, 4), (6, 6), (7, 3), (5, 3)], 41.538)
close_enough([(10, 250), (60, 300), (300, 60), (250, 10)], 24000.0)
close_enough([(10, 250), (60, 300), (110, 250), (160, 300), (210, 250), (160, 200), (300, 60), (250, 10)], 48000.0)
close_enough([(5,0),(0,5),(50,55),(55,50),(70,105),(105,70),(120,125),(125,120),(170,175),(175,170)], 11600.503)
close_enough([(10,250),(60,300),(110,250),(160,300),(210,250),(160,200),(300,60),(250,10)], 48000)
close_enough([(282,212),(160,290),(90,276),(288,140),(89,23),(46,252),(141,3),(183,284),(291,186),(7,171),(263,240),(191,21),(214,30),(17,208),(52,41),(32,223),(251,249),(24,88),(30,62),(107,20),(0,146),(107,284),(129,279),(16,115),(253,43),(289,128),(280,88),(272,60),(216,275),(162,9)], 79849.548)
close_enough([(0, 0), (0, 10), (0, 20), (100, 20), (100, 30), (120, 30), (120, 20), (120, 10), (20, 10), (20, 0)], 2679.208)
print("Coding complete? Click 'Check' to earn cool rewards!")
May 26, 2021
