Package micycle.pgs

Class PGS_Voronoi

java.lang.Object
micycle.pgs.PGS_Voronoi
public final class PGS_Voronoi extends Object
Voronoi Diagrams of shapes and point sets. Supports polygonal constraining and relaxation to generate centroidal Voronoi.
Author:
Michael Carleton

  • Method Summary

    Modifier and Type
    Method
    Description
    static processing.core.PShape
    compoundVoronoi(processing.core.PShape shape)
    Generates a Voronoi diagram for a set of disjoint shapes.
    static processing.core.PShape
    compoundVoronoi(processing.core.PShape shape, double[] bounds)
    Generates a Voronoi diagram for a set of disjoint shapes.
    static processing.core.PShape
    farthestPointVoronoi(Collection<processing.core.PVector> sites)
    Generates the farthest-point Voronoi diagram (FPVD) for a set of sites.
    static processing.core.PShape
    farthestPointVoronoi(Collection<processing.core.PVector> sites, double[] bounds)
    Generates a farthest-point Voronoi diagram (FPVD) for a given set of sites and a bounding box.
    static processing.core.PShape
    innerVoronoi(Collection<processing.core.PVector> points)
    Generates a Voronoi diagram for a set of points.
    static processing.core.PShape
    innerVoronoi(Collection<processing.core.PVector> points, double[] bounds)
    Generates a Voronoi diagram for a set of points.
    static processing.core.PShape
    innerVoronoi(Collection<processing.core.PVector> points, double[] bounds, int relaxations)
    Generates a boundary-constrained Voronoi diagram for a set of points, with relaxation.
    static processing.core.PShape
    innerVoronoi(Collection<processing.core.PVector> points, int relaxations)
    Generates a Voronoi diagram for a set of points, with relaxation.
    static processing.core.PShape
    innerVoronoi(processing.core.PShape shape, boolean constrain)
    Generates a Voronoi diagram for a single shape, where shape vertices are voronoi point sites.
    static processing.core.PShape
    innerVoronoi(processing.core.PShape shape, boolean constrain, double[] bounds, Collection<processing.core.PVector> steinerPoints, int relaxations)
    Generates an inner Voronoi diagram for the specified shape, optionally constrained to the shape's bounds, with additional options for including Steiner points and specifying the number of Lloyd's relaxations to apply.
    static processing.core.PShape
    innerVoronoi(processing.core.PShape shape, int relaxations)
    Generates an inner Voronoi diagram of a given shape with a specified number of relaxations.
    static processing.core.PShape
    innerVoronoi(processing.core.PShape shape, Collection<processing.core.PVector> additionalSites)
    Generates an inner Voronoi diagram of a given shape with additional sites.
    static processing.core.PShape
    innerVoronoi(processing.core.PShape shape, Collection<processing.core.PVector> additionalSites, int relaxations)
    Generates an inner Voronoi diagram of a given shape with additional sites and relaxation.
    static org.tinfour.voronoi.BoundedVoronoiDiagram
    innerVoronoiRaw(Collection<processing.core.PVector> points, double[] bounds, int relaxations)
    Converts a collection of points into a Raw Voronoi diagram object within specified bounds, optionally applying Lloyd's relaxation to improve the diagram's properties.
    static org.tinfour.voronoi.BoundedVoronoiDiagram
    innerVoronoiRaw(processing.core.PShape shape, double[] bounds, Collection<processing.core.PVector> steinerPoints, int relaxations)
    Generates a Voronoi diagram of a given shape, where shape vertices are voronoi point sites.
    static processing.core.PShape
    multiplicativelyWeightedVoronoi(Collection<processing.core.PVector> sites, double[] bounds)
    Generates a Multiplicatively Weighted Voronoi Diagrams diagram for a set of weighted sites.
    static processing.core.PShape
    multiplicativelyWeightedVoronoi(Collection<processing.core.PVector> sites, double[] bounds, boolean forceConforming)
    Generates a Multiplicatively Weighted Voronoi Diagrams diagram for a set of weighted sites.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • innerVoronoi

      public static processing.core.PShape innerVoronoi(processing.core.PShape shape, boolean constrain)
      Generates a Voronoi diagram for a single shape, where shape vertices are voronoi point sites. In this method each voronoi cell designates the area closest to some vertex.

      Note: If the input shape is polygonal, the output is sensitive to how densely populated lines are in the input. Consider processing a shape with densify(density=~10) method first before using this method on a polygon.

      Parameters:
      shape - A shape whose vertices to use as Voronoi sites
      constrain - A flag indicating whether or not to constrain the resulting diagram to the original shape (if it is polygonal).
      Returns:
      a GROUP PShape, where each child shape is a Voronoi cell
      See Also:

    • innerVoronoi

      public static processing.core.PShape innerVoronoi(processing.core.PShape shape, int relaxations)
      Generates an inner Voronoi diagram of a given shape with a specified number of relaxations.
      Parameters:
      shape - The shape to generate the inner Voronoi diagram for.
      relaxations - The number of times to relax the diagram.
      Returns:
      The generated inner Voronoi diagram as a GROUP PShape, where each child shape is a Voronoi cell

    • innerVoronoi

      public static processing.core.PShape innerVoronoi(processing.core.PShape shape, Collection<processing.core.PVector> additionalSites)
      Generates an inner Voronoi diagram of a given shape with additional sites.
      Parameters:
      shape - The shape to generate the inner Voronoi diagram for.
      additionalSites - A collection of PVector points representing additional sites to be used in the diagram.
      Returns:
      The generated inner Voronoi diagram as a GROUP PShape, where each child shape is a Voronoi cell.
      See Also:

    • innerVoronoi

      public static processing.core.PShape innerVoronoi(processing.core.PShape shape, Collection<processing.core.PVector> additionalSites, int relaxations)
      Generates an inner Voronoi diagram of a given shape with additional sites and relaxation.
      Parameters:
      shape - The shape to generate the inner Voronoi diagram for.
      additionalSites - A collection of PVector points representing additional sites to be used in the diagram.
      relaxations - The number of times to relax the diagram.
      Returns:
      The generated inner Voronoi diagram as a GROUP PShape, where each child shape is a Voronoi cell.
      See Also:

    • innerVoronoi

      public static processing.core.PShape innerVoronoi(processing.core.PShape shape, boolean constrain, @Nullable double[] bounds, @Nullable Collection<processing.core.PVector> steinerPoints, int relaxations)
      Generates an inner Voronoi diagram for the specified shape, optionally constrained to the shape's bounds, with additional options for including Steiner points and specifying the number of Lloyd's relaxations to apply. This method allows for the creation of a more customized Voronoi diagram by providing additional control over the generation process.
      Parameters:
      shape - The shape to generate the inner Voronoi diagram for.
      constrain - Indicates whether the resulting Voronoi diagram should be constrained to the bounds of the shape. If true, Voronoi cells will be clipped to the shape's boundary.
      bounds - An optional array of doubles specifying the bounding box within which the Voronoi diagram is generated. If null, no bounding box is applied beyond the shape's bounds when constraining. The array should be of the form [minX, minY, maxX, maxY].
      steinerPoints - An optional collection of PVector points representing additional sites (Steiner points) to be used in the diagram. These points are in addition to the vertices of the input shape.
      relaxations - The number of Lloyd's relaxations to apply to the Voronoi diagram. This process helps to create more evenly sized cells by adjusting the position of sites based on their cell centroids.
      Returns:
      A GROUP PShape where each child shape represents a Voronoi cell.
      Since:
      2.0
      See Also:

    • innerVoronoiRaw

      public static org.tinfour.voronoi.BoundedVoronoiDiagram innerVoronoiRaw(processing.core.PShape shape, @Nullable double[] bounds, @Nullable Collection<processing.core.PVector> steinerPoints, int relaxations)
      Generates a Voronoi diagram of a given shape, where shape vertices are voronoi point sites. In this method each voronoi cell designates the area closest to some vertex.

      Note: If the input shape is polygonal, the output is sensitive to how densely populated lines are in the input. It may be desirable to first process a polygonal shape with densify(density=~10) before using this method.

      The diagram may be "relaxed" into a Centroidal Voronoi Diagram. The relaxation process is a technique used to improve the quality of the Voronoi diagram. It involves moving the vertices of the diagram slightly to reduce the maximum distance between a vertex and the centroid of its associated cell. The process is repeated for a specified number of relaxations iterations. This process aims to reduce the number of irregular shaped polygons in the Voronoi diagram and produce a smoother and more evenly distributed diagram.

      Parameters:
      shape - The shape to generate the inner Voronoi diagram for (using its vertices for Voronoi sites).
      bounds - an optional array of the form [minX, minY, maxX, maxY] representing the bounds of the diagram. The boundary must fully contain the shape (but needn't contain all steiner points).
      steinerPoints - an optional collection of PVector points representing Steiner points to be used as additional sites in the diagram.
      relaxations - the number of times to relax the diagram. 0 or greater.
      Returns:
      a GROUP PShape, where each child shape is a Voronoi cell. The .name value of each cell is set to the integer index of its vertex site.
      See Also:

    • innerVoronoi

      public static processing.core.PShape innerVoronoi(Collection<processing.core.PVector> points)
      Generates a Voronoi diagram for a set of points. In this method each voronoi cell designates the area closest to some point.
      Parameters:
      points - the set of points to use as Voronoi sites
      Returns:
      a GROUP PShape, where each child shape is a Voronoi cell
      See Also:

    • innerVoronoi

      public static processing.core.PShape innerVoronoi(Collection<processing.core.PVector> points, int relaxations)
      Generates a Voronoi diagram for a set of points, with relaxation. In this method each voronoi cell designates the area closest to some point.
      Parameters:
      points - the set of points to use as Voronoi sites
      relaxations - the number of times to relax the diagram. 0 or greater.
      Returns:
      a GROUP PShape, where each child shape is a Voronoi cell
      See Also:

    • innerVoronoi

      public static processing.core.PShape innerVoronoi(Collection<processing.core.PVector> points, double[] bounds)
      Generates a Voronoi diagram for a set of points. In this method each voronoi cell designates the area closest to some point.
      Parameters:
      points - the set of points to use as Voronoi sites
      bounds - an array of the form [minX, minY, maxX, maxY] defining the boundary of the voronoi diagram. the boundary must fully contain the points.
      Returns:
      a GROUP PShape, where each child shape is a Voronoi cell

    • innerVoronoi

      public static processing.core.PShape innerVoronoi(Collection<processing.core.PVector> points, double[] bounds, int relaxations)
      Generates a boundary-constrained Voronoi diagram for a set of points, with relaxation. In this method each voronoi cell designates the area closest to some point.
      Parameters:
      points - the set of points to use as Voronoi sites
      bounds - an array of the form [minX, minY, maxX, maxY] representing the bounds of the diagram. The boundary must fully contain the shape.
      relaxations - the number of times to relax the diagram. 0 or greater.
      Returns:
      a GROUP PShape, where each child shape is a Voronoi cell
      See Also:

    • innerVoronoiRaw

      public static org.tinfour.voronoi.BoundedVoronoiDiagram innerVoronoiRaw(Collection<processing.core.PVector> points, @Nullable double[] bounds, int relaxations)
      Converts a collection of points into a Raw Voronoi diagram object within specified bounds, optionally applying Lloyd's relaxation to improve the diagram's properties.
      Parameters:
      points - a Collection of PVector objects representing the points to be used as the sites of the Voronoi diagram.
      bounds - an array of four doubles specifying the rectangular boundary of the Voronoi diagram in the form [minX, minY, maxX, maxY]. The bounds must be large enough to completely enclose all the points.
      relaxations - an integer specifying the number of Lloyd's relaxation iterations to perform on the Voronoi diagram. This process can help make the cells more uniform in size and shape. A value of 0 indicates no relaxation.
      Returns:
      a PShape object representing the Voronoi diagram, where each child shape corresponds to a Voronoi cell associated with each input point. The PShape is of type GROUP, allowing for collective manipulation of the cells.
      Since:
      2.0
      See Also:

    • compoundVoronoi

      public static processing.core.PShape compoundVoronoi(processing.core.PShape shape)
      Generates a Voronoi diagram for a set of disjoint shapes. In this method each voronoi cell designates the area closest to some individual shape.

      Note: Each geometry primitive in a POINTS or LINES shape is treated as a distinct voronoi site (rather than a singular site representing the full mass of points or lines).

      Parameters:
      shape - a GROUP PShape consisting of any number of non-intersecting polygonal, lineal, or points child shapes
      Returns:
      GROUP shape consisting of voronoi cells; each cell corresponds to an area around a line segment for which the closest line segment to any point in that area is the line segment
      Since:
      1.3.0

    • compoundVoronoi

      public static processing.core.PShape compoundVoronoi(processing.core.PShape shape, double[] bounds)
      Generates a Voronoi diagram for a set of disjoint shapes. In this method each voronoi cell designates the area closest to some individual shape.

      Note: Each geometry primitive in a POINTS or LINES shape is treated as a distinct voronoi site (rather than a singular site representing the full mass of points or lines).

      Parameters:
      shape - a GROUP PShape consisting of any number of non-intersecting polygonal, lineal, or points child shapes
      bounds - an array of the form [minX, minY, maxX, maxY] defining the boundary of the voronoi diagram. the boundary must fully contain the shape.
      Returns:
      GROUP shape consisting of voronoi cells; each cell corresponds to an area around a line segment for which the closest line segment to any point in that area is the line segment
      Since:
      1.3.0

    • multiplicativelyWeightedVoronoi

      public static processing.core.PShape multiplicativelyWeightedVoronoi(Collection<processing.core.PVector> sites, double[] bounds)
      Generates a Multiplicatively Weighted Voronoi Diagrams diagram for a set of weighted sites.

      MWVDs are a generalisation of Voronoi diagrams where each site has a weight associated with it. These weights influence the boundaries between cells in the diagram. Instead of being equidistant from generator points, the boundaries are defined by the ratio of distances to the weighted generator points. This results in characteristically curved cell boundaries, unlike the straight line boundaries seen in standard Voronoi diagrams.

      Parameters:
      sites - A list of PVectors, each representing one site: (.x, .y) represent the coordinate and .z represents weight.
      bounds - an array of the form [minX, minY, maxX, maxY] representing the bounds of the diagram. The boundary must cover all points.
      Returns:
      a GROUP PShape, where each child shape is a Voronoi cell
      Since:
      2.0

    • multiplicativelyWeightedVoronoi

      public static processing.core.PShape multiplicativelyWeightedVoronoi(Collection<processing.core.PVector> sites, double[] bounds, boolean forceConforming)
      Generates a Multiplicatively Weighted Voronoi Diagrams diagram for a set of weighted sites.

      MWVDs are a generalisation of Voronoi diagrams where each site has a weight associated with it. These weights influence the boundaries between cells in the diagram. Instead of being equidistant from generator points, the boundaries are defined by the ratio of distances to the weighted generator points. This results in characteristically curved cell boundaries, unlike the straight line boundaries seen in standard Voronoi diagrams.

      Parameters:
      sites - A list of PVectors, each representing one site: (.x, .y) represent the coordinate and .z represents weight.
      bounds - an array of the form [minX, minY, maxX, maxY] representing the bounds of the diagram. The boundary must cover all points.
      forceConforming - Whether to apply additional processing to ensure the MWVD creates a conforming mesh. A conforming mesh has no tiny gaps between adjacent cells.
      Returns:
      a GROUP PShape, where each child shape is a Voronoi cell
      Since:
      2.0

    • farthestPointVoronoi

      public static processing.core.PShape farthestPointVoronoi(Collection<processing.core.PVector> sites)
      Generates the farthest-point Voronoi diagram (FPVD) for a set of sites.

      The farthest-point Voronoi diagram partitions the plane into regions such that each region consists of all points for which a particular site is the farthest among all provided sites (not the nearest). Only sites that are convex hull vertices have regions in the FPVD.

      The resulting diagram is not clipped to a bounding box and may extend well beyond the convex hull of the input sites, but it is still represented by a finite set of edges.

      Parameters:
      sites - a collection of PVector representing the sites; only convex hull vertices have regions
      Returns:
      a PShape representing the farthest-point Voronoi diagram as a set of edges
      Since:
      2.1
      See Also:

    • farthestPointVoronoi

      public static processing.core.PShape farthestPointVoronoi(Collection<processing.core.PVector> sites, double[] bounds)
      Generates a farthest-point Voronoi diagram (FPVD) for a given set of sites and a bounding box.

      The farthest-point Voronoi diagram is a variant of the Voronoi diagram in which the region for each site p consists of all points in the plane for which p is the farthest site among all sites. In contrast to a regular (nearest-point) Voronoi diagram, where each region surrounds and contains its generating site, in the FPVD, regions do not hug their site; instead, the generator of a region is {typically distant and not even contained within} its region.

      Properties:

      • Only sites that are vertices of the convex hull have non-empty regions in the FPVD, since only those can be farthest from some location in the plane.
      • A useful interpretation: all points in a given FPVD region share the same farthest generator site. However, the generator site is not visually apparent from the region itself, as it is not located within or even near the region.
      Parameters:
      sites - A collection of PVectors representing sites; only the convex hull vertices will have corresponding regions in the output diagram.
      bounds - A double array of form [minX, minY, maxX, maxY] representing the axis-aligned bounding box for clipping the diagram.
      Returns:
      A PShape representing the farthest-point Voronoi diagram. Each cell corresponds to the region for one convex hull vertex site.
      Since:
      2.1