Package micycle.pgs

Class PGS_Polygonisation

java.lang.Object
micycle.pgs.PGS_Polygonisation
public class PGS_Polygonisation extends Object
Generates simple polygonisations of point sets.

A polygonisation is a simple polygon whose vertex set is exactly the given point set, i.e. a non-self-intersecting Hamiltonian cycle through all points. Different algorithms may produce different polygonisations of the same point set.

Polygonisations are distinct from geometric hulls: hulls may select a subset of extreme points to form an enclosing boundary, whereas polygonisations must use all points as vertices.

Since:
2.2
Author:
Michael Carleton

  • Constructor Summary

    Constructors
    Constructor
    Description
    PGS_Polygonisation()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    static processing.core.PShape
    angular(Collection<processing.core.PVector> points)
    Generates a polygonisation by angular (radial) sorting: points are sorted by angle around the centroid, tie-broken by distance from the centroid, and then a 2-opt uncrossing pass is applied.
    static processing.core.PShape
    circular(Collection<processing.core.PVector> points)
    Builds a polygonisation by grouping points into concentric "rings" around the centroid, ordering points within each ring by polar angle, and stitching the rings together into a single sequence.
    static processing.core.PShape
    hilbert(Collection<processing.core.PVector> points)
    Produces a polygonisation by ordering points according to a Hilbert curve (space-filling curve) ordering, then applying a local uncrossing (2-opt) pass to remove any segment intersections.
    static processing.core.PShape
    horizontal(Collection<processing.core.PVector> points)
    Builds a polygonisation by scanning points horizontally (primary sort by Y, secondary by X) and then removing edge crossings via a 2-opt (segment reversal) uncrossing routine.
    static processing.core.PShape
    maxArea(Collection<processing.core.PVector> points)
    Produces a simple polygonisation that attempts to maximise the polygon area while using every point in the supplied set as a vertex.
    static processing.core.PShape
    minArea(Collection<processing.core.PVector> points)
    Produces a simple polygonisation that attempts to minimise the polygon area while using every point in the supplied set as a vertex.
    static processing.core.PShape
    minPerimeter(Collection<processing.core.PVector> points)
    Computes a polygonisation that approximates a shortest closed tour visiting every point exactly once (a Hamiltonian cycle with small perimeter).
    static processing.core.PShape
    onion(Collection<processing.core.PVector> points)
    Constructs a polygonisation using the "onion" (convex-layers) strategy: repeatedly peel convex hull layers (outermost first), stitch hull layers into a single cyclic order (alternating directions for continuity), insert any leftover points with a cheapest-insertion heuristic, and finally apply a 2-opt uncrossing pass.
    static processing.core.PShape
    vertical(Collection<processing.core.PVector> points)
    Builds a polygonisation by scanning points vertically (primary sort by X, secondary by Y) and then removing edge crossings via a 2-opt (segment reversal) uncrossing routine.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • PGS_Polygonisation

      public PGS_Polygonisation()

  • Method Details

    • minArea

      public static processing.core.PShape minArea(Collection<processing.core.PVector> points)
      Produces a simple polygonisation that attempts to minimise the polygon area while using every point in the supplied set as a vertex.
      Parameters:
      points - the input point set (must not be null) containing >2 points.
      Returns:
      a new PShape representing a simple polygon that polygonises the input points and (attempts to) minimise area.
      Since:
      2.2

    • maxArea

      public static processing.core.PShape maxArea(Collection<processing.core.PVector> points)
      Produces a simple polygonisation that attempts to maximise the polygon area while using every point in the supplied set as a vertex.
      Parameters:
      points - the input point set (must not be null) containing >2 points.
      Returns:
      a new PShape representing a simple polygon that polygonises the input points and (attempts to) maximise area.
      Since:
      2.2
      See Also:

    • minPerimeter

      public static processing.core.PShape minPerimeter(Collection<processing.core.PVector> points)
      Computes a polygonisation that approximates a shortest closed tour visiting every point exactly once (a Hamiltonian cycle with small perimeter).

      This method is effectively a TSP-style polygonisation: it returns a simple polygon whose total edge length is minimised (or approximated by the underlying shortest-tour routine).

      Parameters:
      points - the input point set (must not be null). If the set contains fewer than three distinct points an appropriate degenerate PShape containing the input points will be returned.
      Returns:
      a new PShape representing a simple polygon that attempts to minimise perimeter.
      Since:
      2.2

    • horizontal

      public static processing.core.PShape horizontal(Collection<processing.core.PVector> points)
      Builds a polygonisation by scanning points horizontally (primary sort by Y, secondary by X) and then removing edge crossings via a 2-opt (segment reversal) uncrossing routine.

      The produced polygon has "horizontal scanline" characteristics.

      Parameters:
      points - the input point set (may be null). If null an empty PShape is returned. If the set contains fewer than three distinct points a degenerate PShape containing the input points is returned.
      Returns:
      a new PShape representing a simple polygon constructed by horizontal scan and uncrossing.
      Since:
      2.2

    • vertical

      public static processing.core.PShape vertical(Collection<processing.core.PVector> points)
      Builds a polygonisation by scanning points vertically (primary sort by X, secondary by Y) and then removing edge crossings via a 2-opt (segment reversal) uncrossing routine.

      The produced polygon has "vertical scanline" characteristics.

      Parameters:
      points - the input point set (may be null). If null an empty PShape is returned. If the set contains fewer than three distinct points a degenerate PShape containing the input points is returned.
      Returns:
      a new PShape representing a simple polygon constructed by vertical scan and uncrossing.
      Since:
      2.2

    • hilbert

      public static processing.core.PShape hilbert(Collection<processing.core.PVector> points)
      Produces a polygonisation by ordering points according to a Hilbert curve (space-filling curve) ordering, then applying a local uncrossing (2-opt) pass to remove any segment intersections.

      Hilbert ordering tends to preserve locality and thus often produces visually compact, low-crossing initial orderings which the uncrossing step refines into a simple polygon.

      Parameters:
      points - the input point set (must not be null). If the set contains fewer than three distinct points an appropriate degenerate PShape containing the input points will be returned.
      Returns:
      a new PShape representing a simple polygon obtained from Hilbert ordering + uncrossing.
      Since:
      2.2

    • circular

      public static processing.core.PShape circular(Collection<processing.core.PVector> points)
      Builds a polygonisation by grouping points into concentric "rings" around the centroid, ordering points within each ring by polar angle, and stitching the rings together into a single sequence.

      This is a heuristic polygonisation: it favors "circular" or banded structures (concentric/clustered layouts) and often produces visually compact, low-crossing initial orders that the uncrossing step refines into a simple polygon.

      Parameters:
      points - the input point set (may be null). If null an empty PShape is returned. If the set contains fewer than three distinct points a degenerate PShape containing the input points is returned.
      Returns:
      a new PShape representing a simple polygon constructed by concentric ring (circular) ordering and subsequent uncrossing.
      Since:
      2.2

    • angular

      public static processing.core.PShape angular(Collection<processing.core.PVector> points)
      Generates a polygonisation by angular (radial) sorting: points are sorted by angle around the centroid, tie-broken by distance from the centroid, and then a 2-opt uncrossing pass is applied.

      The angular sort usually gives a star-shaped output.

      Parameters:
      points - the input point set (may be null). If null an empty PShape is returned. If the set contains fewer than three distinct points a degenerate PShape containing the input points is returned.
      Returns:
      a new PShape representing a simple polygon constructed by radial sorting and uncrossing.
      Since:
      2.2

    • onion

      public static processing.core.PShape onion(Collection<processing.core.PVector> points)
      Constructs a polygonisation using the "onion" (convex-layers) strategy: repeatedly peel convex hull layers (outermost first), stitch hull layers into a single cyclic order (alternating directions for continuity), insert any leftover points with a cheapest-insertion heuristic, and finally apply a 2-opt uncrossing pass.

      This approach tends to respect global convex structure and produces spiral-like polygonisations that use all points as vertices.

      Parameters:
      points - the input point set (may be null). If null an empty PShape is returned. If the set contains fewer than three distinct points a degenerate PShape containing the input points is returned.
      Returns:
      a new PShape representing a simple polygon constructed by convex-layer peeling, stitching and uncrossing.
      Since:
      2.2