API tools faq
paste
Ladies_Man

triang

Ladies_Man
Apr 28th, 2017
116
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 8.98 KB | None | 0 0
raw download clone embed print report
  1. """triangulation"""
  2.  
  3.  
  4. class Point:
  5.     def __init__(self, x, y, z):
  6.         self._x, self._y, self._z = x, y, z
  7.  
  8.     def get_x(self): return self._x
  9.     def get_y(self): return self._y
  10.     def get_z(self): return self._z
  11.  
  12.  
  13. # TODO -------------------------------------------------------
  14. class Edge:
  15.     def __init__(self, a, b):
  16.         self._a, self._b = a, b
  17.         self._t1 = self._t2 = None
  18.  
  19.     def get_a(self): return self._a
  20.     def get_b(self): return self._b
  21.     def get_t1(self): return self._t1
  22.     def set_t1(self, t1): self._t1 = t1
  23.     def get_t2(self): return self._t2
  24.     def set_t2(self, t2): self._t2 = t2
  25.  
  26.  
  27. # TODO -------------------------------------------------------
  28. class Triangle:
  29.     def __init__(self, a, b, c):
  30.         self._a, self._b, self._c = a, b, c
  31.         self._ab, self._bc, self._ac = Edge(a, b), Edge(b, c), Edge(a, c)
  32.  
  33.         if None != self._ab.get_t1(): self._ab.set_t1(self)   #our triangle lies to the left from vector ab
  34.         else: self._ab.set_t2(self)
  35.         if None != self._bc.get_t1(): self._bc.set_t1(self)
  36.         else: self._bc.set_t2(self)
  37.         if None != self._ac.get_t2(): self._ac.set_t2(self)   #and to the right from ac
  38.         else: self._ac.set_t1(self)
  39.  
  40.         self._edges = [self._ab, self._bc, self._ac]
  41.  
  42.         self._abc = count_angle(self._ab, self._bc)
  43.         self._bca = count_angle(self._bc, self._ac)
  44.         self._cab = count_angle(self._ab, self._ac)
  45.  
  46.         if self._abc < self._bca and self._abc < self._cab: self._min_ang = self._abc
  47.         elif self._cab < self._abc and self._cab < self._bca: self._min_ang = self._cab
  48.         else: self._min_ang = self._bca
  49.  
  50.         self._color = 0
  51.  
  52.     def get_min_ang(self): return self._min_ang
  53.     def get_edges(self): return self._edges
  54.  
  55.  
  56. # TODO -------------------------------------------------------
  57. class Band:
  58.     def __init__(self):
  59.         self._pts = []
  60.         self._edges = []
  61.         self._triangles = []
  62.  
  63.     def get_edges(self): return self._edges
  64.     def set_edges(self, edges): self._edges = edges
  65.     def get_pts(self): return self._pts
  66.     def get_triangles(self): return self._triangles
  67.     def set_triangles(self, triangles): self._triangles = triangles
  68.  
  69.  
  70. # TODO =======================================================
  71.  
  72. def divide_into_bands(pts, band_num):
  73.     band_list = []
  74.     sorted_by_x = sorted(pts, key=lambda x: x.get_x())
  75.  
  76.     x_min = sorted_by_x[0]
  77.     x_max = sorted_by_x[len(sorted_by_x)] + 0.001  # to engage last point
  78.     band_width = (x_max - x_min) / band_num
  79.  
  80.     for i in range(1, band_num):
  81.         x_from = x_min + (i - 1) * band_width
  82.         x_to = x_min + i * band_width
  83.  
  84.         b = Band()
  85.         b.get_pts().extend([x for x in pts if x_from <= x.get_x() < x_to])
  86.         band_list.append(b)
  87.  
  88.     for i in range(1, band_num):
  89.         b_prev = band_list[i - 1]
  90.         b_curr = band_list[i]
  91.  
  92.         if len(b_curr.get_pts()) < 3:
  93.             b_prev.get_pts().extend(b_curr.get_pts())
  94.             band_list.remove(b_curr)
  95.             band_num -= 1
  96.  
  97.     return band_list
  98.  
  99.  
  100. def triang_band(band):
  101.     n = len(band.get_pts())
  102.     sorted_by_y = sorted(band.get_pts(), key=lambda x: x.get_y(), reverse=True)
  103.     triang_list = []
  104.  
  105.     first = Triangle(sorted_by_y[0], sorted_by_y[1], sorted_by_y[2])
  106.     triang_list.append(first)
  107.  
  108.     for i in range(3, n):
  109.         t = triang_list[len(triang_list) - 1]  # prev triang
  110.         p = band.get_pts()[i]
  111.  
  112.         t_new = object
  113.         if intersect(Edge(t[0], t[2]), Edge(p, t[1])):
  114.             t_new = Triangle(t[1], t[2], p)
  115.         elif intersect(Edge(t[1], t[2]), Edge(p, t[0])):
  116.             t_new = Triangle(t[0], t[2], p)
  117.         else:
  118.             tmp1 = Triangle(t[0], t[2], p)
  119.             tmp2 = Triangle(t[1], t[2], p)
  120.             if tmp1.get_min_ang() > tmp2.get_min_ang():
  121.                 t_new = tmp1
  122.             else:
  123.                 t_new = tmp2
  124.  
  125.         triang_list.append(t_new)
  126.  
  127.     band.set_triangles(triang_list)
  128.     return band
  129.  
  130.  
  131. def convex_band(band):
  132.     """because fuck convexing"""
  133.     pass
  134.  
  135.  
  136. def fill_triang_data(band):
  137.     """fill triagnle data for every edge with DFS. then go edge by edge to make outline"""
  138.     edges = []
  139.     for t in band.get_triangles():
  140.         edges.extend(t.get_edges())
  141.  
  142.  
  143. def get_outlines(band):
  144.  
  145.     def find_edges_by_point(edges, p):
  146.         res = []
  147.         for e in edges:
  148.             if e.get_a() is p or e.get_b() is p:
  149.                 res.append(e)
  150.         return res
  151.  
  152.     def filter_edges_below_point(edges, p):
  153.         """find edges that lay below point p"""
  154.         res = []
  155.         for e in edges:
  156.             if e.get_a() is p and p.get_y() > e.get_b().get_y():
  157.                 res.append(e)
  158.             elif e.get_b() is p and p.get_y() > e.get_a().get_y():
  159.                 res.append(e)
  160.         return res
  161.  
  162.     def find_leftmost_edge(edges, p):
  163.         """find leftmost edge by leftmost point among those which below point p"""
  164.         leftmost_edge = object
  165.         xmin = 999
  166.         for e in edges:
  167.             if e.get_a() is not p:
  168.                 if e.get_a().get_x() < xmin:
  169.                     xmin = e.get_a().get_x()
  170.                     leftmost_edge = e
  171.  
  172.             elif e.get_b() is not p:
  173.                 if e.get_b().get_x() < xmin:
  174.                     xmin = e.get_b().get_x()
  175.                     leftmost_edge = e
  176.         return leftmost_edge
  177.  
  178.     def find_rightmost_edge(edges, p):
  179.         rightmost_edge = object
  180.         xmax = -999
  181.         for e in edges:
  182.             if e.get_a() is not p:
  183.                 if e.get_a().get_x() > xmax:
  184.                     xmax = e.get_a().get_x()
  185.                     rightmost_edge = e
  186.  
  187.             elif e.get_b() is not p:
  188.                 if e.get_b().get_x() > xmax:
  189.                     xmax = e.get_b().get_x()
  190.                     rightmost_edge = e
  191.         return rightmost_edge
  192.  
  193.     sorted_edges = sorted(band.get_edges(), key=lambda x: x.get_a().get_y())
  194.     sorted_pts = sorted(band.get_pts(), key=lambda x: x.get_y())
  195.  
  196.     top = sorted_pts[0]
  197.     bot = sorted_pts[len(sorted_pts) - 1]
  198.  
  199.     left_outline = []
  200.     while top is not bot:
  201.  
  202.         es = find_edges_by_point(sorted_edges, top)
  203.         es2 = filter_edges_below_point(es, top)
  204.         leftmost_e = find_leftmost_edge(es2, top)
  205.  
  206.         left_outline.append(leftmost_e)
  207.  
  208.         if leftmost_e.get_a() is top:
  209.             top = leftmost_e.get_b()
  210.         elif leftmost_e.get_b() is top:
  211.             top = leftmost_e.get_a()
  212.  
  213.     right_outline = []
  214.     while top is not bot:
  215.  
  216.         es = find_edges_by_point(sorted_edges, top)
  217.         es2 = filter_edges_below_point(es, top)
  218.         rightmost_e = find_rightmost_edge(es2, top)
  219.  
  220.         right_outline.append(rightmost_e)
  221.  
  222.         if rightmost_e.get_a() is top:
  223.             top = rightmost_e.get_b()
  224.         elif rightmost_e.get_b() is top:
  225.             top = rightmost_e.get_a()
  226.  
  227.     return left_outline, right_outline
  228.  
  229.  
  230.  
  231. def merge_bands(band_left, band_right):
  232.  
  233.     _t, contour1 = get_outlines(band_left)
  234.     contour2, _t = get_outlines(band_right)
  235.  
  236.     #considering only 2 nearest outlines:
  237.     #right outline of left band
  238.     sorted_left_edges = sorted(contour1, key=lambda x: x.get_a().get_y() + x.get_b().get_y(), reverse=True)
  239.     t1 = retrieve_points(contour1)
  240.     sorted_left_points = sorted(t1, key=lambda x: x.get_y(), reverse=True)
  241.  
  242.     #and left outline of right band
  243.     sorted_right_edges = sorted(contour2, key=lambda x: x.get_a().get_y() + x.get_b().get_y(), reverse=True)
  244.     t2 = retrieve_points(contour2)
  245.     sorted_right_points = sorted(t2, key=lambda x: x.get_y(), reverse=True)
  246.  
  247.  
  248.     starting_point = highest_point(sorted_left_edges[0], sorted_right_edges[0])
  249.  
  250.  
  251.     # make edge list representing right outline of left band
  252.     left_sorted_by_y = sorted(band1.get_pts(), key=lambda x: x.get_y(), reverse=True)
  253.     p_top1 = left_sorted_by_y[0]
  254.     left_outline = []
  255.     lower_by_y = sorted(band1.get_pts(), key=lambda x: x.get_y() < left_sorted_by_y[0])
  256.  
  257.  
  258.     # -//- left outline of right band
  259.     right_sorted_by_y = sorted(band2.get_pts(), key=lambda x: x.get_y(), reverse=True)
  260.     p_top2 = right_sorted_by_y[0]
  261.  
  262.     p0, p1 = object, object
  263.     if p_top1 > p_top2:
  264.         p0 = p_top1
  265.         p1 = p_top2
  266.  
  267.     else:
  268.         p0 = p_top2
  269.         p1 = p_top1
  270.  
  271.     pass
  272.  
  273.  
  274. def count_angle(e1, e2):
  275.     return 60
  276.  
  277.  
  278. def intersect(e1, e2):
  279.     return True
  280.  
  281.  
  282. def highest_point(e1, e2):
  283.     max_e1, max_e2 = object, object
  284.  
  285.     if e1.get_a().get_y() > e1.get_b().get_y(): max_e1 = e1.get_a()
  286.     else: max_e1 = e1.get_b()
  287.     if e2.get_a().get_y() > e2.get_b().get_y(): max_e2 = e2.get_a()
  288.     else: max_e2 = e2.get_b()
  289.  
  290.     if max_e1 > max_e2: return max_e1
  291.     else: return max_e2
  292.  
  293.  
  294. def retrieve_points(edges):
  295.     res = set()
  296.     for e in edges:
  297.         res.add(e.get_a())
  298.         res.add(e.get_b())
  299.     return res
  300.  
  301.  
  302. def triang():
  303.     points = []
  304.     band_num = 3
  305.  
  306.  
  307. def main():
  308.     pass
  309.  
  310.  
  311. if __name__ == '__main__':
  312.     main()
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!