Source code for sect.core.delaunay.quad_edge

from typing import (Iterable,
                    List,
                    Optional)

from ground.base import (Context,
                         Orientation)
from ground.hints import Point
from reprit.base import generate_repr


[docs]class QuadEdge: """ Based on: quad-edge data structure. Reference: https://en.wikipedia.org/wiki/Quad-edge http://www.sccg.sk/~samuelcik/dgs/quad_edge.pdf """
[docs] @classmethod def from_endpoints(cls, start: Point, end: Point, *, context: Context) -> 'QuadEdge': """Creates new edge from endpoints.""" result, opposite = (cls(start, context=context), cls(end, context=context)) rotated, triple_rotated = (cls(context=context), cls(context=context)) result._left_from_start = result opposite._left_from_start = opposite rotated._left_from_start = triple_rotated triple_rotated._left_from_start = rotated result._rotated = rotated rotated._rotated = opposite opposite._rotated = triple_rotated triple_rotated._rotated = result return result
@property def context(self) -> Context: return self._context @property def left_from_start(self) -> 'QuadEdge': """ aka "Onext" in L. Guibas and J. Stolfi notation. """ return self._left_from_start @property def end(self) -> Point: """ aka "Dest" in L. Guibas and J. Stolfi notation. """ return self.opposite.start @property def left_from_end(self) -> 'QuadEdge': """ aka "Lnext" in L. Guibas and J. Stolfi notation. """ return self.rotated.opposite.left_from_start.rotated @property def opposite(self) -> 'QuadEdge': """ aka "Sym" in L. Guibas and J. Stolfi notation. """ return self.rotated.rotated @property def right_from_end(self) -> 'QuadEdge': """ aka "Rprev" in L. Guibas and J. Stolfi notation. """ return self.opposite.left_from_start @property def right_from_start(self) -> 'QuadEdge': """ aka "Oprev" in L. Guibas and J. Stolfi notation. """ return self.rotated.left_from_start.rotated @property def rotated(self) -> 'QuadEdge': """ aka "Rot" in L. Guibas and J. Stolfi notation. """ return self._rotated @property def start(self) -> Point: """ aka "Org" in L. Guibas and J. Stolfi notation. """ return self._start __slots__ = '_context', '_left_from_start', '_rotated', '_start' def __init__(self, start: Optional[Point] = None, left_from_start: Optional['QuadEdge'] = None, rotated: Optional['QuadEdge'] = None, *, context: Context) -> None: (self._context, self._left_from_start, self._rotated, self._start) = context, left_from_start, rotated, start __repr__ = generate_repr(from_endpoints)
[docs] def connect(self, other: 'QuadEdge') -> 'QuadEdge': """Connects the edge with the other.""" result = self.from_endpoints(self.end, other.start, context=self.context) result.splice(self.left_from_end) result.opposite.splice(other) return result
[docs] def delete(self) -> None: """Deletes the edge.""" self.splice(self.right_from_start) self.opposite.splice(self.opposite.right_from_start)
[docs] def orientation_of(self, point: Point) -> Orientation: """Returns orientation of the point relative to the edge.""" return self.context.angle_orientation(self.start, self.end, point)
[docs] def splice(self, other: 'QuadEdge') -> None: """Splices the edge with the other.""" alpha = self.left_from_start.rotated beta = other.left_from_start.rotated self._left_from_start, other._left_from_start = ( other.left_from_start, self.left_from_start) alpha._left_from_start, beta._left_from_start = ( beta.left_from_start, alpha.left_from_start)
[docs] def swap(self) -> None: """ Swaps diagonal in a quadrilateral formed by triangles in both clockwise and counterclockwise order around the start. """ side = self.right_from_start opposite = self.opposite opposite_side = opposite.right_from_start self.splice(side) opposite.splice(opposite_side) self.splice(side.left_from_end) opposite.splice(opposite_side.left_from_end) self._start = side.end opposite._start = opposite_side.end
def edge_to_neighbours(edge: QuadEdge) -> List[QuadEdge]: return (list(_edge_to_incidents(edge)) + list(_edge_to_incidents(edge.opposite))) def edges_with_opposites(edges: Iterable[QuadEdge]) -> Iterable[QuadEdge]: for edge in edges: yield edge yield edge.opposite def _edge_to_incidents(edge: QuadEdge) -> Iterable[QuadEdge]: if (edge.orientation_of(edge.right_from_start.end) is Orientation.CLOCKWISE): yield edge.right_from_start if (edge.orientation_of(edge.left_from_start.end) is Orientation.COUNTERCLOCKWISE): yield edge.left_from_start