import numpy as np
import shed
import matplotlib.pyplot as plt
from scipy.spatial import Delaunay
import networkx as nx
from collections import Counter
def divide_on_convex_polygon(p):
tri = Delaunay(p)
e, face = shed.getEdgesDelaunay(tri)
G = nx.Graph()
G.add_edges_from(e)
nx.draw_networkx(G, p, node_size=150, font_size=10, node_color='skyblue')
plt.show()
print("Грани триангуляции\n", face)
for i in e:
av_faces = []
# print("=====\n", i)
for f in face:
if set(i).issubset(f):
# print (f)
av_faces.append(f)
if len(av_faces) == 2:
a = shed.mergeTwoPolygons(av_faces[0], av_faces[1], p)
# print(a)
if a is not None:
face.remove(av_faces[0])
face.remove(av_faces[1])
face.append(a)
# print ("ggg", a)
print("Итоговые грани\n", face)
return face
def koef(x, y, points, edges, show=False):
points.append([x, y])
p = [i for i in range(len(points))]
for j in p:
edges.append([j, len(points) - 1])
if show:
shed.show(np.array(points), edges)
k = shed.calculateStretchFactor(points, edges)
for j in p:
edges.remove([j, len(points) - 1])
points.remove([x, y])
return k
def gs_y(points, edges, x, a, b):
eps = 0.1
y1 = a + 0.382 * (b - a)
y2 = b - 0.382 * (b - a)
f1 = koef(x, y1, points, edges)
f2 = koef(x, y2, points, edges)
while(True):
if f1 < f2:
b = y2
else:
a = y1
if abs(b - a) < eps:
return (y1 + y2) / 2
else:
if b == y2:
y2 = y1
f2 = f1
y1 = a + 0.382 * (b - a)
f1 = koef(x, y1, points, edges)
if a == y1:
y1 = y2
f1 = f2
y2 = b - 0.382 * (b - a)
f2 = koef(x, y2, points, edges)
def gs_x(points, edges, y, a, b):
eps = 0.1
x1 = a + 0.382 * (b - a)
x2 = b - 0.382 * (b - a)
f1 = koef(x1, y, points, edges)
f2 = koef(x2, y, points, edges)
while (True):
if f1 < f2:
b = x2
else:
a = x1
if (abs(b - a) < eps):
return (x1 + x2) / 2
else:
if b == x2:
x2 = x1
f2 = f1
x1 = a + 0.382 * (b - a)
f1 = koef(x1, y, points, edges)
if a == x1:
x1 = x2
f1 = f2
x2 = b - 0.382 * (b - a)
f2 = koef(x2, y, points, edges)
def gold_method(p, epsilon=0.01):
if len(p) == 4:
x1 = p[0][0]
x2 = p[2][0]
x3 = p[1][0]
x4 = p[3][0]
y1 = p[0][1]
y2 = p[2][1]
y3 = p[1][1]
y4 = p[3][1]
xr = -((x1*y2-x2*y1)*(x4-x3)-(x3*y4-x4*y3)*(x2-x1))/((y1-y2)*(x4-x3)-(y3-y4)*(x2-x1))
yr = ((y3-y4)*(-xr)-(x3*y4-x4*y3))/(x4-x3)
k = 1
else:
e = [[i, i+1]for i in range(0, len(p) - 1)]
e.append([len(p)-1, 0])
ax = min([i[0] for i in p])
bx = max([i[0] for i in p])
ay = min([i[1] for i in p])
by = max([i[1] for i in p])
xr = (ax+bx)/2
yr = (ay+by)/2
print("Начальные", xr, yr)
k = koef(xr, yr, p, e)
k_new = np.inf
while abs(k_new - k) > epsilon:
k_new = k
xr = gs_x(p, e, yr, ax, bx)
yr = gs_y(p, e, xr, ay, by)
k = koef(xr, yr, p, e)
return xr, yr, k
N = 7
p = shed.builtPoints(N, 10, 10)
print(p)
#p = [[1, 5], [4, 4], [3, 8], [9, 6], [7, 2], [9, 4], [8, 7]]
face = divide_on_convex_polygon(p)
edges = []
for f in face:
for i in range(-1, len(f) - 1):
edges.append([f[i], f[i + 1]])
#for i in edges:
# plt.plot([p[i[0]][0], p[i[1]][0]], [p[i[0]][1], p[i[1]][1]], color='Green')
#for i in range(len(p)):
# plt.annotate(i, xy=(p[i][0] + 0.15, p[i][1] + 0.15))
#plt.show()
G = nx.Graph()
G.add_edges_from(edges)
nx.draw_networkx(G, p, node_size=150, font_size=10, node_color='skyblue')
plt.show()
for f in face:
print("Грань", f)
if len(f) > 3:
# tmp_edges = []
# tmp_p = []
tmp_p = [p[i] for i in f]
# for i in range(-1, len(f) - 1):
# tmp_edges.append([f[i], f[i + 1]])
# tmp_p.append(p[f[i]])
# edges.append([f[i], f[i + 1]])
# edges.append([f[i], len(p)])
print("Заходит с точками",tmp_p)
x, y, k = gold_method(tmp_p)
print(x,y)
p.append([x, y])
for i in range(-1, len(f) - 1):
edges.append([f[i], len(p)-1])
print("Ребра\n", edges)
print("Вершины\n", p)
#for i in edges:
# plt.plot([p[i[0]][0], p[i[1]][0]], [p[i[0]][1], p[i[1]][1]], color='Green')
#for i in range(len(p)):
# plt.annotate(i, xy=(p[i][0] + 0.15, p[i][1] + 0.15))
#plt.show()
G = nx.Graph()
G.add_edges_from(edges)
nx.draw_networkx(G, p, node_size=150, font_size=10, node_color='skyblue')
plt.show()