import numpy.linalg
import numpy.random
from matplotlib import pyplot as plt
import numpy as np
from scipy.spatial import ConvexHull
from sympy import *
import matplotlib.path as path
def calculate_b_c(p):
A = [[p[0][0] * p[0][1], p[0][1] * p[0][1], p[0][0], p[0][1], 1],
[p[1][0] * p[1][1], p[1][1] * p[1][1], p[1][0], p[1][1], 1],
[p[2][0] * p[2][1], p[2][1] * p[2][1], p[2][0], p[2][1], 1],
[p[3][0] * p[3][1], p[3][1] * p[3][1], p[3][0], p[3][1], 1],
[p[4][0] * p[4][1], p[4][1] * p[4][1], p[4][0], p[4][1], 1]]
B = [[p[0][0] * p[0][0], p[0][1] * p[0][1], p[0][0], p[0][1], 1],
[p[1][0] * p[1][0], p[1][1] * p[1][1], p[1][0], p[1][1], 1],
[p[2][0] * p[2][0], p[2][1] * p[2][1], p[2][0], p[2][1], 1],
[p[3][0] * p[3][0], p[3][1] * p[3][1], p[3][0], p[3][1], 1],
[p[4][0] * p[4][0], p[4][1] * p[4][1], p[4][0], p[4][1], 1]]
C = [[p[0][0] * p[0][0], p[0][0] * p[0][1], p[0][0], p[0][1], 1],
[p[1][0] * p[1][0], p[1][0] * p[1][1], p[1][0], p[1][1], 1],
[p[2][0] * p[2][0], p[2][0] * p[2][1], p[2][0], p[2][1], 1],
[p[3][0] * p[3][0], p[3][0] * p[3][1], p[3][0], p[3][1], 1],
[p[4][0] * p[4][0], p[4][0] * p[4][1], p[4][0], p[4][1], 1]]
D = [[p[0][0] * p[0][0], p[0][0] * p[0][1], p[0][1] * p[0][1], p[0][1], 1],
[p[1][0] * p[1][0], p[1][0] * p[1][1], p[1][1] * p[1][1], p[1][1], 1],
[p[2][0] * p[2][0], p[2][0] * p[2][1], p[2][1] * p[2][1], p[2][1], 1],
[p[3][0] * p[3][0], p[3][0] * p[3][1], p[3][1] * p[3][1], p[3][1], 1],
[p[4][0] * p[4][0], p[4][0] * p[4][1], p[4][1] * p[4][1], p[4][1], 1]]
E = [[p[0][0] * p[0][0], p[0][0] * p[0][1], p[0][1] * p[0][1], p[0][0], 1],
[p[1][0] * p[1][0], p[1][0] * p[1][1], p[1][1] * p[1][1], p[1][0], 1],
[p[2][0] * p[2][0], p[2][0] * p[2][1], p[2][1] * p[2][1], p[2][0], 1],
[p[3][0] * p[3][0], p[3][0] * p[3][1], p[3][1] * p[3][1], p[3][0], 1],
[p[4][0] * p[4][0], p[4][0] * p[4][1], p[4][1] * p[4][1], p[4][0], 1]]
F = [[p[0][0] * p[0][0], p[0][0] * p[0][1], p[0][1] * p[0][1], p[0][0], p[0][1]],
[p[1][0] * p[1][0], p[1][0] * p[1][1], p[1][1] * p[1][1], p[1][0], p[1][1]],
[p[2][0] * p[2][0], p[2][0] * p[2][1], p[2][1] * p[2][1], p[2][0], p[2][1]],
[p[3][0] * p[3][0], p[3][0] * p[3][1], p[3][1] * p[3][1], p[3][0], p[3][1]],
[p[4][0] * p[4][0], p[4][0] * p[4][1], p[4][1] * p[4][1], p[4][0], p[4][1]]]
a = numpy.linalg.det(A)
b = (-1) * numpy.linalg.det(B)
c = numpy.linalg.det(C)
d = (-1) * numpy.linalg.det(D)
e = numpy.linalg.det(E)
f = (-1) * numpy.linalg.det(F)
return a, b, c, d, e, f
def in_ellipse(p, koef):
x = p[0]
y = p[1]
d = koef[0] * x**2 + koef[1]*x*y + koef[2]*y**2 + koef[3]*x + koef[4]*y + koef[5]
if d < 0:
return True
else:
return False
def rotate(A,B,C):
return (B[0]-A[0])*(C[1]-B[1])-(B[1]-A[1])*(C[0]-B[0])
def jarvismarch(A):
n = len(A)
P = range(n)
for i in range(1,n):
if A[P[i]][0]<A[P[0]][0]:
P[i], P[0] = P[0], P[i]
H = [P[0]]
del P[0]
P.append(H[0])
while True:
right = 0
for i in range(1,len(P)):
if rotate(A[H[-1]],A[P[right]],A[P[i]])<0:
right = i
if P[right]==H[0]:
break
else:
H.append(P[right])
del P[right]
H = [A[H[i]] for i in range(len(H))]
return np.array(H)
def empty_poligon(p, points):
bbPath = path.Path(p)
new_p = [[i[0],i[1]] for i in p]
for i in points:
if [i[0],i[1]] not in new_p:
if bbPath.contains_point(i, radius=0.0):
return False
else:
a,b,c,d,e,f = calculate_b_c(p)
if in_ellipse(i, [ a,b,c,d,e,f]):
return False
return True
points = []
while len(points) < 10:
new_p = [numpy.random.randint(-5, 5), numpy.random.randint(-5, 5)]
if new_p not in points:
points.append(new_p)
points = np.array(points)
print(points)
k = 0
for i in points:
plt.plot(i[0], i[1], '.')
plt.annotate(str("%d" % k), [i[0], i[1]])
k = k + 1
plt.grid()
plt.plot(points[:, 0], points[:, 1], 'o')
plt.show()
#plt.savefig('/home/kate/Рабочий стол/Figure_1.png')
for i1 in range(len(points)):
for i2 in range(i1 + 1, len(points)):
for i3 in range(i2 + 1, len(points)):
for i4 in range(i3 + 1, len(points)):
for i5 in range(i4 + 1, len(points)):
conv = jarvismarch([points[i1], points[i2], points[i3], points[i4], points[i5]])
if (len(conv) == 5):
if empty_poligon(conv, points):
print(i1, i2, i3, i4, i5)
a, b, c, d, e, f = calculate_b_c(points)
# print(a, b, c, d, e, f)
# x = symbols('x')
# y = symbols('y')
# plot_implicit(Eq(a * x ** 2 + b * x * y + c * y ** 2 + d * x + e * y + f))