Package micycle.pgs.commons

Class MinimumBoundingTriangle

java.lang.Object
micycle.pgs.commons.MinimumBoundingTriangle
public class MinimumBoundingTriangle extends Object
Computes the Minimum Bounding Triangle (MBT) for the points in a Geometry. The MBT is the smallest triangle which covers all the input points (this is also known as the Smallest Enclosing Triangle).

The algorithm for finding minimum area enclosing triangles is based on an elegant geometric characterisation initially introduced in Klee & Laskowski. The algorithm iterates over each edge of the convex polygon setting side C of the enclosing triangle to be flush with this edge. A side S is said to be flush with edge E if S⊇E. The authors of O’Rourke et al. prove that for each fixed flush side C a local minimum enclosing triangle exists. Moreover, the authors have shown that:

  • The midpoints of the enclosing triangle’s sides must touch the polygon.
  • There exists a local minimum enclosing triangle with at least two sides flush with edges of the polygon. The third side of the triangle can be either flush with an edge or tangent to the polygon.
Thus, for each flush side C the algorithm will find the second flush side and set the third side either flush/tangent to the polygon.

O'Rourke provides a θ(n) algorithm for finding the minimal enclosing triangle of a 2D convex polygon with n vertices. However, the overall complexity for the concave computation is O(nlog(n)) because a convex hull must first be computed for the input geometry.

Author:
Python implementation by Charlie Marsh, Java port by Michael Carleton

  • Constructor Details

    • MinimumBoundingTriangle

      public MinimumBoundingTriangle(org.locationtech.jts.geom.Geometry shape)
      Creates a new instance of a Maximum Inscribed Triangle computation.
      Parameters:
      shape - an areal geometry

  • Method Details

    • getTriangle

      public org.locationtech.jts.geom.Geometry getTriangle()
      Gets a geometry which represents the Minimium Bounding Triangle.
      Returns:
      a triangle Geometry representing the Minimum Bounding Triangle