Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Merge pull request #1333 from p0cisk/ConcaveHull
[Processing][Feature] Add Concave Hull algorithm
  • Loading branch information
alexbruy committed May 7, 2014
2 parents c64c89e + bb93600 commit 8b40a63
Show file tree
Hide file tree
Showing 2 changed files with 134 additions and 1 deletion.
132 changes: 132 additions & 0 deletions python/plugins/processing/algs/qgis/ConcaveHull.py
@@ -0,0 +1,132 @@
# -*- coding: utf-8 -*-

"""
***************************************************************************
ConcaveHull.py
---------------------
Date : May 2014
Copyright : (C) 2012 by Piotr Pociask
Email : piotr dot pociask at gis-support dot pl
***************************************************************************
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
***************************************************************************
"""

__author__ = 'Piotr Pociask'
__date__ = 'May 2014'
__copyright__ = '(C) 2014, Piotr Pociask'

# This will get replaced with a git SHA1 when you do a git archive

__revision__ = '$Format:%H$'

from PyQt4.QtCore import *
from PyQt4.QtGui import *
from qgis.core import *
from processing.core.GeoAlgorithm import GeoAlgorithm
from processing.parameters.ParameterVector import ParameterVector
from processing.parameters.ParameterNumber import ParameterNumber
from processing.parameters.ParameterBoolean import ParameterBoolean
from processing.outputs.OutputVector import OutputVector
from processing.tools import dataobjects
import processing
from math import sqrt

class ConcaveHull(GeoAlgorithm):

INPUT = 'INPUT'
ALPHA = 'ALPHA'
HOLES = 'HOLES'
NO_MULTIGEOMETRY = 'NO_MULTIGEOMETRY'
OUTPUT = 'OUTPUT'

def defineCharacteristics(self):
self.name = 'Concave hull'
self.group = 'Vector geometry tools'
self.addParameter(ParameterVector(ConcaveHull.INPUT, 'Input point layer',
[ParameterVector.VECTOR_TYPE_POINT]))
self.addParameter(ParameterNumber(self.ALPHA,
'Threshold (0-1, where 1 is equivalent with Convex Hull)', 0, 1, 0.3))
self.addParameter(ParameterBoolean(self.HOLES, 'Allow holes', True))
self.addParameter(ParameterBoolean(self.NO_MULTIGEOMETRY,
'Split multipart geometry into singleparts geometries', False))
self.addOutput(OutputVector(ConcaveHull.OUTPUT, 'Convex hull'))

def processAlgorithm(self, progress):
#get parameters
layer = dataobjects.getObjectFromUri(self.getParameterValue(ConcaveHull.INPUT))
alpha = self.getParameterValue(self.ALPHA)
holes = self.getParameterValue(self.HOLES)
no_multigeom = self.getParameterValue(self.NO_MULTIGEOMETRY)
#Delaunay triangulation from input point layer
progress.setText('Creating Delaunay triangles ...')
delone_triangles = processing.runalg("qgis:delaunaytriangulation", layer, None)['OUTPUT']
delaunay_layer = processing.getObject(delone_triangles)
#get max edge length from Delaunay triangles
progress.setText('Computing edges max length ...')
features = delaunay_layer.getFeatures()
counter = 50./delaunay_layer.featureCount()
lengths = []
edges = {}
for feat in features:
line = feat.geometry().asPolygon()[0]
for i in range(len(line)-1):
lengths.append(sqrt(line[i].sqrDist(line[i+1])))
edges[feat.id()] = max(lengths[-3:])
progress.setPercentage(feat.id()*counter)
max_length = max(lengths)
#get features with longest edge longer than alpha*max_length
progress.setText('Removing features ...')
counter = 50./len(edges)
i = 0
ids = []
for id, max_len in edges.iteritems():
if max_len > alpha*max_length:
ids.append(id)
progress.setPercentage(50+i*counter)
i += 1
#remove features
delaunay_layer.setSelectedFeatures(ids)
delaunay_layer.startEditing()
delaunay_layer.deleteSelectedFeatures()
delaunay_layer.commitChanges()
#dissolve all Delaunay triangles
progress.setText('Dissolving Delaunay triangles ...')
dissolved = processing.runalg("qgis:dissolve", delaunay_layer,
True, '', None)['OUTPUT']
dissolved_layer = processing.getObject(dissolved)
#save result
progress.setText('Saving data ...')
feat = QgsFeature()
dissolved_layer.getFeatures(QgsFeatureRequest().setFilterFid(0)).nextFeature(feat)
writer = self.getOutputFromName(
self.OUTPUT).getVectorWriter(layer.pendingFields().toList(),
QGis.WKBPolygon, layer.crs())
geom = feat.geometry()
if no_multigeom and geom.isMultipart():
#only singlepart geometries are allowed
geom_list = geom.asMultiPolygon()
for single_geom_list in geom_list:
single_feature = QgsFeature()
single_geom = QgsGeometry.fromPolygon(single_geom_list)
if not holes:
#delete holes
deleted = True
while deleted:
deleted = single_geom.deleteRing(1)
single_feature.setGeometry(single_geom)
writer.addFeature(single_feature)
else:
#multipart geometries are allowed
if not holes:
#delete holes
deleted = True
while deleted:
deleted = geom.deleteRing(1)
writer.addFeature(feat)
del writer
3 changes: 2 additions & 1 deletion python/plugins/processing/algs/qgis/QGISAlgorithmProvider.py
Expand Up @@ -72,6 +72,7 @@

from mmqgisx.MMQGISXAlgorithms import *

from ConcaveHull import ConcaveHull
from Polygonize import Polygonize
from RasterLayerStatistics import RasterLayerStatistics
from StatisticsByCategories import StatisticsByCategories
Expand Down Expand Up @@ -137,7 +138,7 @@ def __init__(self):
SaveSelectedFeatures(), JoinAttributes(),
AutoincrementalField(), Explode(), FieldsPyculator(),
EquivalentNumField(), PointsLayerFromTable(),
StatisticsByCategories(), Polygonize(),
StatisticsByCategories(), ConcaveHull(), Polygonize(),
RasterLayerStatistics(), PointsDisplacement(),
ZonalStatistics(), PointsFromPolygons(),
PointsFromLines(),
Expand Down

0 comments on commit 8b40a63

Please sign in to comment.