I'm trying to complete a code implementing the Kirkpatrick algorithm in Java using JTS and it's literally the first time doing working with such tools. There's a part that I need to remove a known point P (in the independent set) from a region which is consisted of multiple polygons all intersecting in P and return the remaining hole to be triangulated. The question is how to do remove a point P from a MultiPolygon?

 * Find a bounding polygon if point p is removed from affected regions
 * @param p
 * @param affectedRegions
 * @return
public Polygon findBoundingPolygon(Coordinate p, List<Geometry> affectedRegions) {
    // TODO: write a function that finds a bounding polygon
    GeometryFactory fact = new GeometryFactory();
    Geometry regions = fact.buildGeometry(affectedRegions);
    // TODO: bound <- a concave hull of regions
    LinearRing shell = fact.createLinearRing(coordsToLinearRingCoords(bound));
    return new Polygon(shell, null, fact);

Removing a vertex from a polygon is relatively easy:

  static final double tol = 1e-4;
  static final GeometryFactory gf = new GeometryFactory();
  public Polygon removePoint(Polygon p, Point pt) {
    if (p.getNumPoints() < 4) {
      throw new RuntimeException("Can't reduce polygon below 4 points");
    ArrayList<Coordinate> points = new ArrayList<>();
    for (Coordinate c : p.getCoordinates()) {
      if (!(Math.abs(c.x - pt.getX()) < tol && Math.abs(c.y - pt.getY()) < tol)) {
    return gf.createPolygon(points.toArray(new Coordinate[points.size()]));

If you are dealing with a MultiPolygon then simply iterate through the Polygons one at a time:

ArrayList<Polygon> polys = new ArrayList<>();
for (int i=0; i<mp.getNumGeometries();i++) {
  polys.add(me.removePoint(mp.getGeometryN(i), p));

Calculating the ConvexHull is also simple:

ConvexHull huller = new ConvexHull(poly.getCoordinates(), gf);
Polygon hull = (Polygon) huller.getConvexHull();

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.