weavingspace.topology_elements

  1#!/usr/bin/env python
  2# coding: utf-8
  3
  4import shapely.geometry as geom
  5import weavingspace.tiling_utils as tiling_utils
  6
  7class Tile(object):
  8  """Class to capture and manipulate essential features of polygons in a tiling.
  9  """
 10  ID: int
 11  """integer ID number which indexes the Tile in the containing Topology tiles 
 12  list."""
 13  base_ID: int
 14  """ID of corresponding Tile in the base tileable unit"""
 15  corners: list["Vertex"]
 16  """list of Vertex objects. This includes all corners of the original polygon 
 17  and any tiling vertices induced by (for example) a the corner of an adjacent 
 18  tile lying halfway along an edge of the original polygon on which this tile 
 19  is based. Vertex objects are stored in strictly clockwise sequence."""
 20  edges: list["Edge"]
 21  """list of Edge objects that together compose the tile boundary."""
 22  edges_CW: list[bool]
 23  """list of Edge direction. Edges are stored only once in a Topology so some 
 24  edges are in clockwise order and others  are in counter-clockwise order. 
 25  These boolean flags are True if the corresponding Edge is clockwise, False if 
 26  counter-clockwise."""
 27  label: str
 28  """tile_id label from the tileable source"""
 29  vertex_labels: list[str]
 30  """list of (upper case) letter labels of the tile corners (i.e. all corners, 
 31  not only tiling vertices)."""
 32  edge_labels: list[str]
 33  """list of (lower case) letter labels of the tile edges (tiling edges, not 
 34  tile sides)."""
 35  shape: geom.Polygon = None
 36  """the tile geometry (which may include some redundant points along sides 
 37  where neighbouring tiles induce a tiling vertex). So for example a rectangle 
 38  might have additional points along its sides:
 39      
 40        +---+-------+
 41        |   |   2   |
 42        | 1 A---B---E---+
 43        |   |   |   4   |
 44        +---C 3 D-------+
 45            |   |
 46            +---+
 47      
 48  In the above Tile 1 has additional point A, 2 has B and 3 has C and D induced 
 49  by the corners of neighbouring tiles."""
 50  centre: geom.Point = None
 51  """a point centre for the Tile (determined by weavingspace.tiling_utils.
 52  incentre)."""
 53  shape_group: int = None
 54  """the tile shape group of this tile in its containing Topology."""
 55  transitivity_class: int = None
 56  """the tile transitivity class of this tile its containing Topology"""
 57  
 58  def __init__(self, ID:int):
 59    """Class constructor.
 60
 61    Args:
 62      ID (int): Tile ID which indexes it in the containing Topology tiles list.
 63    """
 64    # self.set_shape(tiling_utils.get_clean_polygon(shape))
 65    self.ID = ID
 66    self.corners = []
 67    self.edges = []
 68    self.edges_CW = []
 69    self.vertex_labels = []
 70    self.edge_labels = []
 71
 72  def __str__(self) -> str:
 73    """Returns string representation of the Tile.
 74
 75    Returns:
 76      str: string including Tile ID, list of corner vertex IDs and list of
 77        edge IDs.
 78    """
 79    return f"Tile {self.ID} Corners: {self.get_corner_IDs()} Edges: {self.get_edge_IDs()}"
 80  
 81  def __repr__(self) -> str:
 82    return str(self)
 83
 84  def get_corner_IDs(self) -> list[int]:
 85    """Convenience method to return list of corner IDs (not Vertex objects).
 86
 87    Returns:
 88      list[int]: list of integer IDs of tile corners.
 89    """
 90    return [c.ID for c in self.corners]
 91
 92  def get_edge_IDs(self) -> list[tuple[int]]:
 93    """Convenience method to return list of edge IDs (not Edge objects).
 94
 95    Returns:
 96      list[tuple[int]]: list of 2-element tuples of the start and end Vertex IDs
 97        of each edge.
 98    """
 99    return [e.ID for e in self.edges]
100
101  def set_shape_from_corners(self):
102    """Sets the shape attribute based on the current list of corners, and sets 
103    the associated tile centre.
104    """
105    self.shape = geom.Polygon([c.point for c in self.corners])
106    self.centre = tiling_utils.incentre(
107      tiling_utils.get_clean_polygon(self.shape))
108
109  def set_corners_from_edges(self, update_shape:bool = True):
110    """Sets the corners attribute from the edges attribute. Typically called 
111    after modification of topology edges. Optionally the shape attribute is NOT
112    updated, which may save time when multiple changes to the edges of a tile
113    are in process (i.e., only update the shape after all changes are complete).
114
115    Args:
116      update_shape (bool, optional): if True the shape attribute will be 
117        updated, otherwise not. Defaults to True.
118    """
119    self.corners = []
120    for e, cw in zip(self.edges, self.edges_CW):
121      if cw: # clockwise to extend by all but the first corner
122        self.corners.extend(e.corners[:-1])
123      else: # counter-clockwise so extend in reverse
124        self.corners.extend(e.corners[1:][::-1])
125    if update_shape:
126      self.set_shape_from_corners()
127
128  def set_edge_directions(self):
129    """Sets up the edges_CW attribute by inspection of the edges list.
130    It is (frankly!) hard to keep track of the correct sequence of CW/CCW order
131    of edges as new ones are created or old ones merged. This method inspects
132    the 'tail-head' relations between consecutive edges to set these flags 
133    correctly.
134
135    The test is simply to check if the 'tail' Vertex ID in each edge appears
136    in the ID tuple of the following edge, i.e. if successive edge 
137    IDs are (0, 1) (2, 1) or (0, 1) (1, 2), then edge (0, 1) is in clockwise
138    direction, but if we have (0, 1) (2, 3) then it is not.
139    """
140    edge_IDs = self.get_edge_IDs()
141    self.edges_CW = [e1[-1] in e2 for e1, e2 in 
142                     zip(edge_IDs, edge_IDs[1:] + edge_IDs[:1])]
143
144  def insert_vertex_at(self, v:"Vertex", i:int, 
145                       update_shape:bool = False) -> tuple:
146    """Method to insert the supplied Vertex into tile at index position i, 
147    optionally updating the shape attribute. Both corners and edges attributes
148    are updated, and the old edge IDs for removal and the new edge itself are
149    returned to the calling context (the containing Topology) for update of its
150    edges collection.
151
152    This is NOT a generic vertex insertion method: it is only for use during 
153    Topology initialisation, and does not guarantee correct maintenance of 
154    all tile, edge and vertex relations in the general case---at any rate it
155    has not been tested for this!
156
157    Args:
158        v (Vertex): the Vertex to insert.
159        i (int): index position in current corners after which to insert 
160          supplied Vertex.
161        update_shape (bool, optional): if True shape attribute is updated. 
162          Defaults to False.
163
164    Returns:
165      tuple: the (tuple) ID of the old edge which should be deleted, and 
166        the new Edges arising from insertion of this Vertex.
167    """
168    self.corners = self.corners[:i] + [v] + self.corners[i:]
169    old_edge = self.edges[i - 1]
170    # store current ID of the affected edge for return to calling context
171    old_edge_ID = old_edge.ID
172    new_edges = old_edge.insert_vertex(v, self.corners[i - 1])
173    self.edges = self.edges[:(i-1)] + new_edges + self.edges[i:]
174    self.set_edge_directions()
175    if update_shape:
176      self.set_shape_from_corners()
177    return old_edge_ID, new_edges
178
179  def merge_edges_at_vertex(self, v:"Vertex") -> tuple:
180    """Method to merge the edges that meet at the supplied Vertex. It is 
181    assumed that only two tiles are impacted this one, and its neighbour across
182    the Edge on which v lies. Both are updated. For this reason the work is
183    delegated to get_updated_edges_from_merge which is run on both affected
184    tiles, but only determines the edges to remove and the new edge to be added
185    once. See that method for details.
186    
187    Args:
188      v (Vertex): Vertex at which to merge Edges. This should currently be an
189        end
190    
191    Returns:
192      tuple: 2 item list of the edge IDs to be removed and a new Edge object to
193        be added by the calling context (i.e. the containing Topology).
194    """
195    to_remove, new_edge = self.get_updated_edges_from_merge(v)
196    if len(v.tiles) > 1:
197      v.tiles[1].get_updated_edges_from_merge(v, new_edge)
198    return to_remove, new_edge
199
200  def get_updated_edges_from_merge(self, v:"Vertex", new_edge:"Edge" = None):
201    """Updates the edges and edges_CW attributes based on insertion of 
202    the supplied Vertex. If new_edge is supplied then the neighbour tile at
203    v has already created the needed new Edge and this Edge is the one that
204    will be 'slotted in' at the appropriate spot in the edges list.
205
206    The edges_CW is also updated to maintain correct directions of the edges.
207    The corners attribute is unaffected by these changes.
208
209    Args:
210      v (Vertex): existing Vertex at which to carry out the merge.
211      new_edge (Edge, optional): if another Tile has already carried out this 
212        merge this should be the resulting new Edge for insertion into this 
213        Tile. Defaults to None (when the new Edge will be constructed).
214  
215    Returns:
216      Union[None, tuple]: either None (if a new edge was supplied) or a tuple 
217        of the two edge IDs to be removed and the new edge added for return to
218        the calling context (i.e. the containing Topology).
219    """
220    # get the two edge list index positions in which Vertex v is found
221    i, j = self.get_edge_IDs_including_vertex(v)
222    if new_edge is None: # then we must make a new one
223      # also record existing edge IDs to be removed
224      to_remove = [self.edges[i].ID, self.edges[j].ID]
225      new_edge = self.get_merged_edge(i, j)
226      return_edge_updates = True
227    else:
228      return_edge_updates = False
229    if abs(i - j) != 1:
230      # edge indices 'wrap' around from end of edge list to start so drop 
231      # first and last current edges and stick new one on at the end
232      self.edges = self.edges[1:-1] + [new_edge] 
233    else:
234      # insert new edge into list in place of the two old ones
235      self.edges = self.edges[:i] + [new_edge] + self.edges[j+1:]
236    # update the edge directions
237    self.set_edge_directions()
238    if return_edge_updates:
239      return to_remove, new_edge
240    else:
241      return None
242
243  def get_edge_IDs_including_vertex(self, v:"Vertex") -> tuple[int]:
244    """Gets the (two) index positions of the edges that include supplied Vertex.
245
246    Args:
247        v (Vertex): Vertex of interest.
248
249    Returns:
250      tuple[int]: two index positions of Edges in edges list that contain v.
251    """
252    return (i for i, e in enumerate(self.edges) if v.ID in e.ID)
253
254  def get_merged_edge(self, i:int, j:int) -> "Edge":
255    """Returns the new edge resulting from merging the two existing edges at
256    index positions i and j in the edges list. For example, if the current list 
257    of edge IDs was
258
259        (0 1 2) (4 2) (4 5) (5 0)
260
261    and the merge Vertex was #2, the resulting new edge is constructed from 
262    vertices (0 1 2 4). 
263
264    Returns:
265      Edge: the requested new Edge.
266    """
267    # if i and j are not consecutive, then j is predecessor edge
268    if abs(i - j) != 1:
269      i, j = j, i
270    # get edges and their directions
271    ei, ej = self.edges[i], self.edges[j]
272    CWi, CWj = self.edges_CW[i], self.edges_CW[j]
273    # DON'T MESS WITH THIS!!!
274    # for predecessors (the head) we want everything including the Vertex 
275    # where the merge is occurring; for successors (the tail) we want all but 
276    # the first Vertex (which is the one where the merge is occurring). In both 
277    # cases contingent on whether existing Edges are CW or CCW we may need to 
278    # flip the Vertex sequence to ensure that the merge Vertex is in the middle 
279    # of the new edge that will be created
280    head = ei.corners if CWi else ei.corners[::-1]
281    tail = ej.corners[1:] if CWj else ej.corners[::-1][1:]
282    v_sequence = (head if CWi else head[::-1]) + (tail if CWj else tail[::-1])
283    return Edge(v_sequence)
284
285  def offset_corners(self, offset:int):
286    """Shifts shape, corners, edges, and edges_CW by an offset amount. This is
287    used to align tiles that are similar, which is required for correct 
288    transfer of 'base' tile labelling on to 'radius 1' tiles during Topology 
289    construction.
290
291    Args:
292      offset int: the number of positions to shift the lists.
293    """
294    if not offset is None or offset == 0:
295      self.shape = tiling_utils.offset_polygon_corners(self.shape, offset)
296      self.corners = self.corners[offset:] + self.corners[:offset]
297      self.edges = self.edges[offset:] + self.edges[:offset]
298      self.edges_CW = self.edges_CW[offset:] + self.edges_CW[:offset]
299
300  def get_edge_label(self, e:"Edge") -> str:
301    """Returns edge label of specified edge.
302
303    Args:
304        e (Edge): Edge whose label is required.
305
306    Returns:
307        str: requested edge label.
308    """
309    return self.edge_labels[self.get_edge_IDs().index(e.ID)]
310
311  def get_corner_label(self, v:"Vertex") -> str:
312    """Returns corner label of specified corner.
313
314    Args:
315        v (Vertex): corner whose label is required.
316
317    Returns:
318        str: requested corner label.
319    """
320    return self.edge_labels[self.get_corner_IDs().index(v.ID)]
321
322  def get_vertex_label_positions(self) -> list[geom.Point]:
323    """Returns a viable location at which to position corner labels inside
324    tile shape. The method is convoluted because a negative buffer may remove
325    colinear corners resulting in fewer positions than we have corners in the
326    tile shape!
327
328    Returns:
329        list[geom.Point]: list of locations.
330    """
331    d = (self.shape.area ** 0.5) / 8
332    c = self.centre
333    corners = [c.point for c in self.corners]
334    return [geom.LineString([p, c]).line_interpolate_point(d) for p in corners]
335    
336  def get_edge_label_positions(self) -> list[geom.Point]:
337    """Returns a reasonable location at which to position edge labels inside
338    tile shape.
339
340    Returns:
341        list[geom.Point]: list of locations
342    """
343    d = (self.shape.area ** 0.5) / 8
344    c = self.centre
345    # note direction is important as edge might not be a simple line segment
346    sides = [e.get_geometry(CW) for e, CW in zip(self.edges, self.edges_CW)]
347    return [geom.LineString([s.centroid, c]).line_interpolate_point(d) 
348            for s in sides]
349
350  def angle_at(self, v:"Vertex") -> float:
351    """Returns interior angle at the specified corner (in degrees).
352
353    Args:
354        v (Vertex): corner where angle is requested.
355
356    Returns:
357        float: angle at corner v in degrees.
358    """
359    i = self.corners.index(v)
360    n = len(self.corners)
361    return tiling_utils.get_inner_angle(self.corners[i-1].point,
362                                        self.corners[i].point,
363                                        self.corners[(i + 1) % n].point)
364
365
366class Vertex:
367  """Class to store attributes of a vertex in a tiling."""
368  point: geom.Point
369  """point (geom.Point): point location of the vertex."""
370  ID: int
371  """integer (mostly but not necessarily in sequence) of vertex keyed into the 
372  points dictionary of the containing Topology."""
373  tiles: list["Tile"]
374  """list of Tiles incident on this vertex."""
375  neighbours: list[int]
376  """list of the immediately adjacent other corner IDs. Only required to 
377  determine if a point is a tiling vertex (when it will have) three or more 
378  neighbours, so only IDs are stored."""
379  base_ID: int = 1_000_000
380  """ID of corresponding Vertex in the tileable base_unit"""
381  transitivity_class: int = None
382  """transitivity class of the vertex under symmetries of the tiling"""
383  label: str = ""
384  """the (upper case letter) label of the vertex under the symmetries of the 
385  tiling."""
386  is_tiling_vertex: bool = True
387  """is_tiling_vertex (bool): True if this is a tiling vertex, rather than a 
388  tile corner. E.g., A below is a corner, not a tiling vertex. B is a tiling 
389  vertex:
390      
391      +-------+
392      | 1     |
393      |   A---B---+
394      |   | 2     |
395      +---C   +---+
396          |   |
397          +---+"""
398  
399  def __init__(self, point:geom.Point, ID:int):
400    """Class constructor.
401
402    Args:
403      point (geom.Point): point location of the vertex.
404      ID (int): a unique integer ID (which will be its key in the containing
405        Topology points dictionary).
406    """
407    self.point = point
408    self.ID = ID
409    self.base_ID = self.ID
410    self.tiles = []
411    self.neighbours = []
412
413  def __str__(self) -> str:
414    """Returns string representation of Vertex.
415    
416    Returns:
417        str: string including ID, point and list of incident Tiles.
418    """
419    return f"Vertex {self.ID} at {self.point} Tiles: {self.get_tile_IDs()}"
420
421  def __repr__(self) -> str:
422    return str(self)
423
424  def get_tile_IDs(self) -> list[int]:
425    """Convenience method to return list of Tile IDs (not the Tiles themselves).
426
427    Returns:
428        list[int]: list of Tile IDs
429    """
430    return [t.ID for t in self.tiles]
431
432  def add_tile(self, tile:Tile):
433    """Adds supplied Tile to the tiles list if it is not already present.
434
435    Args:
436        tile (Tile): Tile to add.
437    """
438    if not tile in self.tiles:
439      self.tiles.append(tile)
440
441  def add_neighbour(self, vertex_id:int):
442    """Adds supplied ID to the neighbours list if it is not already present
443
444    Args:
445      vertex_id (int): ID to add to the neighbours list.
446    """
447    if not vertex_id in self.neighbours:
448      self.neighbours.append(vertex_id)
449
450  def clockwise_order_incident_tiles(self):
451    """Reorders the tiles list clockwise (this is for dual tiling construction)
452    """
453    cw_order = tiling_utils.order_of_pts_cw_around_centre(
454      [t.centre for t in self.tiles], self.point)
455    self.tiles = [self.tiles[i] for i in cw_order]
456
457  def is_interior(self) -> bool:
458    """Tests if vertex is completely enclosed by its incident Tiles. Based on
459    summing the interior angles of the incident tiles at this vertex.
460
461    Returns:
462        bool: True if vertex is completely enclosed by incident Tiles.
463    """
464    return abs(360 - sum([t.angle_at(self) for t in self.tiles])) \
465                     < tiling_utils.RESOLUTION
466
467
468class Edge:
469  """Class to represent edges in a tiling (not tile sides) per the definitions
470  in Grünbaum and Shephard.
471  """
472  ID: tuple[int]
473  """IDs of the vertices at ends of the edge. Used as key in the containing 
474  Topology's edges dictionary."""
475  vertices: list["Vertex"]
476  """two item list of the end vertices."""
477  corners: list["Vertex"]
478  """list of all the vertices in the edge (including its end vertices). In a 
479  'normal' edge to edge tiling corners and vertices will be identical."""
480  right_tile: "Tile" = None
481  """the tile to the right of the edge traversed from its first to its last 
482  vertex. Given clockwise winding default, all edges will have a right_tile."""
483  left_tile: "Tile" = None
484  """the tile to the left of the edge traversed from its first to its last 
485  vertex. Exterior edges of the tiles in a Topology will not have a left_tile.
486  """
487  base_ID: tuple[int] = (1_000_000, 1_000_000)
488  """ID of corresponding edge in the base tileable"""
489  transitivity_class: int = None
490  """transitivity class of the edge under symmetries of the tiling"""
491  label: str = ""
492  """the (lower case letter) label of the edge under the symmetries of the 
493  tiling."""
494  
495  def __init__(self, corners:list[Vertex]):
496    """Class constructor. Initialises the corners and vertices lists and sets ID
497    to (vertices[0].ID, vertices[1].ID). The vertices list is all the corners
498    with is_tiling_vertex property True -- Note that during initialisation the
499    default of this property is True until after the relations between tiles and
500    vertices have been determined.
501
502    Args:
503      corners (list[Vertex]): list of all corners along the edge.
504    """
505    self.corners = corners
506    self.vertices = [v for v in self.corners if v.is_tiling_vertex]
507    self.ID = tuple(v.ID for v in self.vertices)
508
509  def __str__(self) -> str:
510    """Returns a string representation of  the Edge.
511
512    Returns:
513        str: include ID and a list of corner vertex IDs.
514    """
515    return f"Edge {self.ID} Corners: {[c.ID for c in self.corners]}"
516
517  def __repr__(self) -> str:
518    return str(self)
519
520  def get_corner_IDs(self) -> list[int]:
521    """Convenience method to get the IDs of edge corners.
522
523    Returns:
524        list[int]: IDs of all corners.
525    """
526    return [c.ID for c in self.corners]
527
528  def get_vertex_IDs(self) -> list[int]:
529    """Convenience method to get IDs of edge vertices.
530
531    Returns:
532        list[int]: list of IDs of the vertices.
533    """
534    return [v.ID for v in self.vertices]
535
536  def insert_vertex(self, v:"Vertex", predecessor:"Vertex") -> list["Edge"]:
537    """Inserts a vertex along this edge after the specified predecessor 
538    Vertex and returns this edge modified and a new edge. 
539    
540    If the initial edge was (say) (0 1 2 5) and the predecessor was set to 1 
541    the returned edges would be (0 1 v) and (v 2 5).
542    """
543    i = self.corners.index(predecessor)
544    new_edge = Edge([v] + self.corners[(i+1):])
545    if not self.right_tile is None:
546      new_edge.right_tile = self.right_tile
547    if not self.left_tile is None:
548      new_edge.left_tile = self.left_tile
549    self.corners = self.corners[:(i+1)] + [v]
550    self.vertices = [self.vertices[0], v]
551    self.ID = tuple(v.ID for v in self.vertices)
552    return [self, new_edge]
553
554  def get_geometry(self, forward = True) -> geom.LineString:
555    """Returns a geom.LineString representing the geometry (including all
556    corners) of this Edge, optionally starting at either end.
557
558    Args:
559      forward (bool, optional): if True the returned LineString starts at
560        corners[0], else at corners[-1]. Defaults to True.
561
562    Returns:
563      geom.LineString: the required LineString.
564    """
565    if forward:
566      return geom.LineString([v.point for v in self.corners])
567    else:
568      return geom.LineString([v.point for v in self.corners[::-1]])
569
570  def get_topology(self, forward = True) -> geom.LineString:
571    """Returns a LineString connecting the first and last corners (i.e. the
572    vertices) of this tilin edge, optionally starting from either end.
573
574    Args:
575      forward (bool, optional): if True LineString starts at vertices[0], 
576        else at vertices[1]. Defaults to True.
577
578    Returns:
579        geom.LineString: the required LineString.
580    """
581    if forward:
582      return geom.LineString([v.point for v in self.vertices])
583    else:
584      return geom.LineString([v.point for v in self.vertices[::-1]])