程序包 org.hipparchus.geometry.euclidean.twod.hull

类 MonotoneChain

java.lang.Object
org.hipparchus.geometry.euclidean.twod.hull.MonotoneChain
所有已实现的接口:
ConvexHullGenerator2D, ConvexHullGenerator<Euclidean2D,Vector2D>
public class MonotoneChain extends Object
实现了Andrew的单调链方法，用于在二维欧几里德空间中生成有限点集的凸包。

运行时复杂度为O(n log n)，其中n为输入点的数量。如果点集已经按x坐标排序，则运行时复杂度为O(n)。

该实现对凸包上的共线点不敏感。参数includeCollinearPoints允许控制关于共线点的行为。如果为true，则将添加凸包边界上的所有点到凸包顶点中，否则只有极端点会出现。默认情况下，共线点不会被添加为凸包顶点。

参数tolerance（默认值：1e-10）用作判定相同和共线点的epsilon标准。

另请参阅:

  • 构造器详细资料

    • MonotoneChain

      public MonotoneChain()
      创建一个新的MonotoneChain实例。

    • MonotoneChain

      public MonotoneChain(boolean includeCollinearPoints)
      创建一个新的MonotoneChain实例。
      参数:
      includeCollinearPoints - 是否将共线点添加为凸包顶点

    • MonotoneChain

      public MonotoneChain(boolean includeCollinearPoints, double tolerance)
      创建一个新的MonotoneChain实例。
      参数:
      includeCollinearPoints - 是否将共线点添加为凸包顶点
      tolerance - 被视为相同的点的容差

  • 方法详细资料

    • findHullVertices

      public Collection<Vector2D> findHullVertices(Collection<Vector2D> points)
      从输入点集中找到凸包顶点。
      参数:
      points - 输入点集
      返回:
      逆时针排列的凸包顶点

    • getTolerance

      public double getTolerance()
      获取被视为相同的点的容差。
      返回:
      被视为相同的点的容差

    • isIncludeCollinearPoints

      public boolean isIncludeCollinearPoints()
      返回凸包上的共线点是否被添加为凸包顶点。
      返回:
      如果共线点被添加为凸包顶点，则返回true，否则只有极端点存在则返回false。

    • generate

      public ConvexHull2D generate(Collection<Vector2D> points) throws MathIllegalStateException
      从输入点集构建凸包。
      指定者:
      generate 在接口中 ConvexHullGenerator<Euclidean2D,Vector2D>
      指定者:
      generate 在接口中 ConvexHullGenerator2D
      参数:
      points - 输入点集
      返回:
      凸包
      抛出:
      MathIllegalStateException - 如果生成器无法为给定的输入点集生成凸包