Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Area of a Convex Polygon by Kurush
def checkio(data):
x, y = zip(*data)
pairs = []
for i, elem in enumerate(data):
pairs.append((tuple(data[i]), tuple(data[(i+1) % len(data)])))
lines = {}
for pair in pairs:
A, B, C, Res = get_line_equation(pair[0][0], pair[0][1], pair[1][0], pair[1][1])
AD, BD, CD = round(A, 5), round(B, 5), round(C, 5)
lines[(AD, BD, CD)] = [pair[0], pair[1]]
number_inside = 0
number_border = 0
for i in range(min(x), max(x) + 1):
for j in range(min(y), max(y) + 1):
if is_border((i, j), lines): number_border += 1
else:
if is_inside((i, j), pairs): number_inside += 1
area = round(number_inside + number_border / 2 - 1, 1) # Pick's theorem
if area.is_integer(): area = int(area)
print(number_border, number_inside, area)
return area
def is_border(point, lines):
for line, pairs in lines.items():
if abs(line[0] * point[0] + line[1] * point[1] + line[2]) < 0.01:
if (
(min(pairs[0][0], pairs[1][0]) <= point[0]) and
(max(pairs[0][0], pairs[1][0]) >= point[0]) and
(min(pairs[0][1], pairs[1][1]) <= point[1]) and
(max(pairs[0][1], pairs[1][1]) >= point[1])
):
return True
return False
def is_inside(point, pairs):
changes = 0
for pair in pairs:
A, B, C, Res = get_line_equation(pair[0][0], pair[0][1], pair[1][0], pair[1][1])
AD, BD, CD = round(A, 5), round(B, 5), round(C, 5)
if AD == 0: continue
x = -(BD * point[1] + CD) / AD
if x < point[0]: continue
val_prev = pair[0][1] - point[1] > 0
val_cur = pair[1][1] - point[1] > 0
if (val_prev != val_cur):
changes += 1
if changes % 2 == 0: return False
else:
return True
# Get line equation Ax + By + C = 0 given two points (xa, ya) and (xb, yb).
def get_line_equation(xa, ya, xb, yb):
if (xb - xa != 0) and (yb - ya != 0):
A = 1. / (xb - xa)
B = 1. / (ya - yb)
C = 1. * ya / (yb - ya) - 1. * xa / (xb - xa)
# normalization of koefficients
B = B / A
C = C / A
A = 1.
return A, B, C, True
elif (xb - xa == 0) and (yb - ya != 0):
A = 1.
B = 0.
C = -xa
return A, B, C, True
elif (xb - xa != 0) and (yb - ya == 0):
A = 0.
B = 1.
C = -ya
return A, B, C, True
elif (xb - xa == 0) and (yb - ya == 0):
return 0, 0, 0, False
if __name__ == '__main__':
#This part is using only for self-checking and not necessary for auto-testing
def almost_equal(checked, correct, significant_digits=1):
precision = 0.1 ** significant_digits
return correct - precision < checked < correct + precision
assert almost_equal(checkio([[2, 2], [2, 4], [4, 4], [4, 2]]), 4), "Additional example"
assert almost_equal(checkio([[1, 1], [9, 9], [9, 1]]), 32), "The half of the square"
assert almost_equal(checkio([[4, 10], [7, 1], [1, 4]]), 22.5), "Triangle"
assert almost_equal(checkio([[1, 2], [3, 8], [9, 8], [7, 1]]), 40), "Quadrilateral"
assert almost_equal(checkio([[3, 3], [2, 7], [5, 9], [8, 7], [7, 3]]), 26), "Pentagon"
assert almost_equal(checkio([[7, 2], [3, 2], [1, 5], [3, 9], [7, 9], [9, 6]]), 42), "Hexagon"
assert almost_equal(checkio([[4, 1], [3, 4], [3, 7], [4, 8], [7, 9], [9, 6], [7, 1]]), 35.5), "Heptagon"
Feb. 21, 2019