Module imagingbook.common
Package imagingbook.common.geometry.delaunay.guibas

Class TriangulationGuibas

java.lang.Object
imagingbook.common.geometry.delaunay.guibas.TriangulationGuibas
All Implemented Interfaces:
DelaunayTriangulation
public class TriangulationGuibas extends Object implements DelaunayTriangulation

This is an implementation of the triangulation algorithm described in [1].

[1] L. J. Guibas, D. E. Knuth, and M. Sharir" "Randomized incremental construction of Delaunay and Voronoi diagrams", Algorithmica, 7, pp. 381--413 (1992).

  • Constructor Details

    • TriangulationGuibas

      public TriangulationGuibas(Collection<? extends Pnt2d> points, boolean shuffle)
      Constructor.
      Parameters:
      points - the point set to be triangulated
      shuffle - set true to randomly shuffle the input points

    • TriangulationGuibas

      public TriangulationGuibas(Collection<? extends Pnt2d> points)
      Constructor. Supplied points are inserted without shuffling, i.e., in their original order.
      Parameters:
      points - the point set to be triangulated

  • Method Details

    • size

      public int size()
      Description copied from interface: DelaunayTriangulation
      Returns the number of triangles in this triangulation.
      Specified by:
      size in interface DelaunayTriangulation
      Returns:
      the number of triangles

    • getTriangles

      public List<Triangle> getTriangles()
      Description copied from interface: DelaunayTriangulation
      Returns a list of Triangle instances contained in this triangulation. The list does not contain the initial outer triangle.
      Specified by:
      getTriangles in interface DelaunayTriangulation
      Returns:
      a list of triangles

    • getPoints

      public List<Pnt2d> getPoints()
      Description copied from interface: DelaunayTriangulation
      Returns a list of 2D vertices contained in this triangulation. The list does not contain the vertices of the initial (outer) triangle.
      Specified by:
      getPoints in interface DelaunayTriangulation
      Returns:
      a list of points

    • findContainingTriangle

      public Triangle2D findContainingTriangle(Pnt2d point)
      Returns the triangle that contains the specified point or null if no such triangle exists.
      Parameters:
      point - the query point
      Returns:
      the containing triangle or null if none was found

    • findNeighbour

      public Triangle2D findNeighbour(Triangle2D tri1, Edge2D edge)
      Returns the neighboring triangle of the specified triangle sharing the same edge as specified. If no neighbor sharing the same edge exists null is returned. NOTE: Searching over ALL triangles seems to be unnecessarily expensive!
      Parameters:
      tri1 - the triangle
      edge - the edge
      Returns:
      the triangle's neighboring triangle sharing the same edge or null if no such triangle exists

    • findOneTriangleSharing

      public Triangle2D findOneTriangleSharing(Edge2D edge)
      Returns one of the possible triangles sharing the specified edge. Based on the ordering of the triangles in this triangle soup the returned triangle may differ. To find the other triangle that shares this edge use the findNeighbour(Triangle2D triangle, Edge2D edge) method.
      Parameters:
      edge - the edge
      Returns:
      the triangle that shares the specified edge or null if none exists

    • findNearestEdge

      public Edge2D findNearestEdge(Pnt2d point)
      Returns the triangle edge nearest to the specified point.
      Parameters:
      point - the query point
      Returns:
      the triangle edge nearest to the specified point

    • removeTrianglesUsing

      public void removeTrianglesUsing(Pnt2d point)
      Removes all triangles that contain the specified corner point.
      Parameters:
      point - the corner point