import numpy as np
import shed
import matplotlib.pyplot as plt
from scipy.spatial import Delaunay
import networkx as nx
from sympy import Line, Point, Segment
def divide_on_convex_polygon(p, show = False):
tri = Delaunay(p)
e, face = shed.getEdgesDelaunay(tri)
print(shed.calculateStretchFactor(p, e))
G = nx.Graph()
G.add_edges_from(e)
if show:
nx.draw_networkx(G, p, node_size=150, font_size=10, node_color='skyblue')
plt.show()
for i in e:
av_faces = []
for f in face:
if set(i).issubset(f):
av_faces.append(f)
if len(av_faces) == 2:
a = shed.mergeTwoPolygons(av_faces[0], av_faces[1], p)
if a is not None:
face.remove(av_faces[0])
face.remove(av_faces[1])
face.append(a)
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 convert(s):
try:
return float(s)
except ValueError:
num, denom = s.split('/')
return float(num) / float(denom)
def intersect(p):
p1, p2, p3, p4 = (Point(p[0][0], p[0][1]), Point(p[1][0], p[1][1]),
Point(p[2][0], p[2][1]), Point(p[3][0], p[3][1]))
line1 = Line(p1, p3)
line2 = Line(p2, p4)
inter = line1.intersection(line2)
return convert(inter[0].x), convert(inter[0].y)
def gold_method(p, epsilon=0.01):
if len(p) == 4:
xr, yr = intersect(p)
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
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 = 10
p = shed.builtPoints(N, 10000, 10000)
#print(p)
#p = [[9, 2], [8, 6], [6, 2], [2, 5], [2, 7], [3, 1], [3, 7], [5, 2], [8, 7], [2, 3]]
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]])
#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:
if len(f) > 3:
tmp_p = [p[i] for i in f]
x, y, k = gold_method(tmp_p)
p.append([x, y])
for i in range(-1, len(f) - 1):
edges.append([f[i], len(p)-1])
#G = nx.Graph()
#G.add_edges_from(edges)
#fillcolor = []
#for i in range(len(p)):
# if i<N:
# fillcolor.append('skyblue')
# else:
# fillcolor.append('pink')
#nx.draw_networkx(G, p, node_size=150, font_size=10, node_color=fillcolor)
#plt.show()
print(shed.calculateStretchFactor(p, edges))