Skip to content

Commit

Permalink
[processing] port delaunay triangulation algorithm to C++
Browse files Browse the repository at this point in the history
  • Loading branch information
@alexbruy @wonder-sk
alexbruy authored and wonder-sk committed Oct 9, 2023
1 parent d824314 commit 451d1ba
Show file tree
Hide file tree
Showing 11 changed files with 376 additions and 265 deletions.
3 changes: 0 additions & 3 deletions python/plugins/processing/algs/help/qgis.yaml
View file
Expand Up @@ -45,9 +45,6 @@ qgis:definecurrentprojection: >

The .prj and .qpj files associated with the Shapefile will be overwritten - or created if missing - to match the provided CRS.

qgis:delaunaytriangulation: >
This algorithm creates a polygon layer with the delaunay triangulation corresponding to a points layer.

qgis:distancematrix: >
This algorithm creates a table containing a distance matrix, with distances between all the points in a points layer.

Expand Down
157 changes: 0 additions & 157 deletions python/plugins/processing/algs/qgis/Delaunay.py
View file

This file was deleted.

2 changes: 0 additions & 2 deletions python/plugins/processing/algs/qgis/QgisAlgorithmProvider.py
View file
Expand Up @@ -34,7 +34,6 @@
from .Climb import Climb
from .ConcaveHull import ConcaveHull
from .DefineProjection import DefineProjection
from .Delaunay import Delaunay
from .EliminateSelection import EliminateSelection
from .ExecuteSQL import ExecuteSQL
from .ExportGeometryInfo import ExportGeometryInfo
Expand Down Expand Up @@ -97,7 +96,6 @@ def getAlgs(self):
Climb(),
ConcaveHull(),
DefineProjection(),
Delaunay(),
EliminateSelection(),
ExecuteSQL(),
ExportGeometryInfo(),
Expand Down
31 changes: 0 additions & 31 deletions python/plugins/processing/tests/testdata/expected/multipoint_delaunay.gfs
View file

This file was deleted.

147 changes: 76 additions & 71 deletions python/plugins/processing/tests/testdata/expected/multipoint_delaunay.gml
View file
@@ -1,86 +1,91 @@
<?xml version="1.0" encoding="utf-8" ?>
<ogr:FeatureCollection
gml:id="aFeatureCollection"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://ogr.maptools.org/ multipoint_delaunay.xsd"
xmlns:ogr="http://ogr.maptools.org/"
xmlns:gml="http://www.opengis.net/gml">
<gml:boundedBy>
<gml:Box>
<gml:coord><gml:X>0</gml:X><gml:Y>-5</gml:Y></gml:coord>
<gml:coord><gml:X>8</gml:X><gml:Y>3</gml:Y></gml:coord>
</gml:Box>
</gml:boundedBy>

<gml:featureMember>
<ogr:multipoint_delaunay fid="multipoint_delaunay.0">
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>7,-1 8,-1 0,-5 7,-1</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>7.000000000000000</ogr:POINTA>
<ogr:POINTB>6.000000000000000</ogr:POINTB>
<ogr:POINTC>5.000000000000000</ogr:POINTC>
xmlns:gml="http://www.opengis.net/gml/3.2">
<gml:boundedBy><gml:Envelope srsName="urn:ogc:def:crs:EPSG::4326"><gml:lowerCorner>-5 0</gml:lowerCorner><gml:upperCorner>3 8</gml:upperCorner></gml:Envelope></gml:boundedBy>

<ogr:featureMember>
<ogr:multipoint_delaunay gml:id="multipoint_delaunay.0">
<gml:boundedBy><gml:Envelope srsName="urn:ogc:def:crs:EPSG::4326"><gml:lowerCorner>-5 0</gml:lowerCorner><gml:upperCorner>1 4</gml:upperCorner></gml:Envelope></gml:boundedBy>
<ogr:geometryProperty><gml:Polygon srsName="urn:ogc:def:crs:EPSG::4326" gml:id="multipoint_delaunay.geom.0"><gml:exterior><gml:LinearRing><gml:posList>-1 0 -5 0 1 4 -1 0</gml:posList></gml:LinearRing></gml:exterior></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>7</ogr:POINTA>
<ogr:POINTB>5</ogr:POINTB>
<ogr:POINTC>3</ogr:POINTC>
</ogr:multipoint_delaunay>
</gml:featureMember>
<gml:featureMember>
<ogr:multipoint_delaunay fid="multipoint_delaunay.1">
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>0,-5 4,1 7,-1 0,-5</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>5.000000000000000</ogr:POINTA>
<ogr:POINTB>4.000000000000000</ogr:POINTB>
<ogr:POINTC>7.000000000000000</ogr:POINTC>
</ogr:featureMember>
<ogr:featureMember>
<ogr:multipoint_delaunay gml:id="multipoint_delaunay.1">
<gml:boundedBy><gml:Envelope srsName="urn:ogc:def:crs:EPSG::4326"><gml:lowerCorner>-1 0</gml:lowerCorner><gml:upperCorner>1 4</gml:upperCorner></gml:Envelope></gml:boundedBy>
<ogr:geometryProperty><gml:Polygon srsName="urn:ogc:def:crs:EPSG::4326" gml:id="multipoint_delaunay.geom.1"><gml:exterior><gml:LinearRing><gml:posList>-1 0 1 4 1 1 -1 0</gml:posList></gml:LinearRing></gml:exterior></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>0</ogr:POINTA>
<ogr:POINTB>7</ogr:POINTB>
<ogr:POINTC>3</ogr:POINTC>
</ogr:multipoint_delaunay>
</gml:featureMember>
<gml:featureMember>
<ogr:multipoint_delaunay fid="multipoint_delaunay.2">
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>0,-1 4,1 0,-5 0,-1</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>8.000000000000000</ogr:POINTA>
<ogr:POINTB>4.000000000000000</ogr:POINTB>
<ogr:POINTC>5.000000000000000</ogr:POINTC>
</ogr:featureMember>
<ogr:featureMember>
<ogr:multipoint_delaunay gml:id="multipoint_delaunay.2">
<gml:boundedBy><gml:Envelope srsName="urn:ogc:def:crs:EPSG::4326"><gml:lowerCorner>1 1</gml:lowerCorner><gml:upperCorner>2 4</gml:upperCorner></gml:Envelope></gml:boundedBy>
<ogr:geometryProperty><gml:Polygon srsName="urn:ogc:def:crs:EPSG::4326" gml:id="multipoint_delaunay.geom.2"><gml:exterior><gml:LinearRing><gml:posList>1 1 1 4 2 2 1 1</gml:posList></gml:LinearRing></gml:exterior></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>0</ogr:POINTA>
<ogr:POINTB>3</ogr:POINTB>
<ogr:POINTC>7</ogr:POINTC>
</ogr:multipoint_delaunay>
</gml:featureMember>
<gml:featureMember>
<ogr:multipoint_delaunay fid="multipoint_delaunay.3">
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>1,1 4,1 0,-1 1,1</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>0.000000000000000</ogr:POINTA>
<ogr:POINTB>4.000000000000000</ogr:POINTB>
<ogr:POINTC>8.000000000000000</ogr:POINTC>
</ogr:featureMember>
<ogr:featureMember>
<ogr:multipoint_delaunay gml:id="multipoint_delaunay.3">
<gml:boundedBy><gml:Envelope srsName="urn:ogc:def:crs:EPSG::4326"><gml:lowerCorner>1 2</gml:lowerCorner><gml:upperCorner>3 4</gml:upperCorner></gml:Envelope></gml:boundedBy>
<ogr:geometryProperty><gml:Polygon srsName="urn:ogc:def:crs:EPSG::4326" gml:id="multipoint_delaunay.geom.3"><gml:exterior><gml:LinearRing><gml:posList>2 2 1 4 3 3 2 2</gml:posList></gml:LinearRing></gml:exterior></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>0</ogr:POINTA>
<ogr:POINTB>3</ogr:POINTB>
<ogr:POINTC>7</ogr:POINTC>
</ogr:multipoint_delaunay>
</gml:featureMember>
<gml:featureMember>
<ogr:multipoint_delaunay fid="multipoint_delaunay.4">
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>2,2 4,1 1,1 2,2</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>1.000000000000000</ogr:POINTA>
<ogr:POINTB>4.000000000000000</ogr:POINTB>
<ogr:POINTC>0.000000000000000</ogr:POINTC>
</ogr:featureMember>
<ogr:featureMember>
<ogr:multipoint_delaunay gml:id="multipoint_delaunay.4">
<gml:boundedBy><gml:Envelope srsName="urn:ogc:def:crs:EPSG::4326"><gml:lowerCorner>1 3</gml:lowerCorner><gml:upperCorner>3 5</gml:upperCorner></gml:Envelope></gml:boundedBy>
<ogr:geometryProperty><gml:Polygon srsName="urn:ogc:def:crs:EPSG::4326" gml:id="multipoint_delaunay.geom.4"><gml:exterior><gml:LinearRing><gml:posList>3 3 1 4 2 5 3 3</gml:posList></gml:LinearRing></gml:exterior></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>0</ogr:POINTA>
<ogr:POINTB>3</ogr:POINTB>
<ogr:POINTC>7</ogr:POINTC>
</ogr:multipoint_delaunay>
</gml:featureMember>
<gml:featureMember>
<ogr:multipoint_delaunay fid="multipoint_delaunay.5">
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>5,2 7,-1 4,1 5,2</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>3.000000000000000</ogr:POINTA>
<ogr:POINTB>7.000000000000000</ogr:POINTB>
<ogr:POINTC>4.000000000000000</ogr:POINTC>
</ogr:featureMember>
<ogr:featureMember>
<ogr:multipoint_delaunay gml:id="multipoint_delaunay.5">
<gml:boundedBy><gml:Envelope srsName="urn:ogc:def:crs:EPSG::4326"><gml:lowerCorner>-1 4</gml:lowerCorner><gml:upperCorner>2 7</gml:upperCorner></gml:Envelope></gml:boundedBy>
<ogr:geometryProperty><gml:Polygon srsName="urn:ogc:def:crs:EPSG::4326" gml:id="multipoint_delaunay.geom.5"><gml:exterior><gml:LinearRing><gml:posList>2 5 1 4 -1 7 2 5</gml:posList></gml:LinearRing></gml:exterior></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>7</ogr:POINTA>
<ogr:POINTB>3</ogr:POINTB>
<ogr:POINTC>5</ogr:POINTC>
</ogr:multipoint_delaunay>
</gml:featureMember>
<gml:featureMember>
<ogr:multipoint_delaunay fid="multipoint_delaunay.6">
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>3,3 4,1 2,2 3,3</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>2.000000000000000</ogr:POINTA>
<ogr:POINTB>4.000000000000000</ogr:POINTB>
<ogr:POINTC>1.000000000000000</ogr:POINTC>
</ogr:featureMember>
<ogr:featureMember>
<ogr:multipoint_delaunay gml:id="multipoint_delaunay.6">
<gml:boundedBy><gml:Envelope srsName="urn:ogc:def:crs:EPSG::4326"><gml:lowerCorner>-1 5</gml:lowerCorner><gml:upperCorner>2 8</gml:upperCorner></gml:Envelope></gml:boundedBy>
<ogr:geometryProperty><gml:Polygon srsName="urn:ogc:def:crs:EPSG::4326" gml:id="multipoint_delaunay.geom.6"><gml:exterior><gml:LinearRing><gml:posList>2 5 -1 7 -1 8 2 5</gml:posList></gml:LinearRing></gml:exterior></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>7</ogr:POINTA>
<ogr:POINTB>5</ogr:POINTB>
<ogr:POINTC>3</ogr:POINTC>
</ogr:multipoint_delaunay>
</gml:featureMember>
<gml:featureMember>
<ogr:multipoint_delaunay fid="multipoint_delaunay.7">
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>3,3 5,2 4,1 3,3</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>2.000000000000000</ogr:POINTA>
<ogr:POINTB>3.000000000000000</ogr:POINTB>
<ogr:POINTC>4.000000000000000</ogr:POINTC>
</ogr:featureMember>
<ogr:featureMember>
<ogr:multipoint_delaunay gml:id="multipoint_delaunay.7">
<gml:boundedBy><gml:Envelope srsName="urn:ogc:def:crs:EPSG::4326"><gml:lowerCorner>-5 0</gml:lowerCorner><gml:upperCorner>-1 8</gml:upperCorner></gml:Envelope></gml:boundedBy>
<ogr:geometryProperty><gml:Polygon srsName="urn:ogc:def:crs:EPSG::4326" gml:id="multipoint_delaunay.geom.7"><gml:exterior><gml:LinearRing><gml:posList>-1 8 -1 7 -5 0 -1 8</gml:posList></gml:LinearRing></gml:exterior></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>7</ogr:POINTA>
<ogr:POINTB>5</ogr:POINTB>
<ogr:POINTC>3</ogr:POINTC>
</ogr:multipoint_delaunay>
</gml:featureMember>
<gml:featureMember>
<ogr:multipoint_delaunay fid="multipoint_delaunay.8">
<ogr:geometryProperty><gml:Polygon srsName="EPSG:4326"><gml:outerBoundaryIs><gml:LinearRing><gml:coordinates>5,2 8,-1 7,-1 5,2</gml:coordinates></gml:LinearRing></gml:outerBoundaryIs></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>3.000000000000000</ogr:POINTA>
<ogr:POINTB>6.000000000000000</ogr:POINTB>
<ogr:POINTC>7.000000000000000</ogr:POINTC>
</ogr:featureMember>
<ogr:featureMember>
<ogr:multipoint_delaunay gml:id="multipoint_delaunay.8">
<gml:boundedBy><gml:Envelope srsName="urn:ogc:def:crs:EPSG::4326"><gml:lowerCorner>-5 0</gml:lowerCorner><gml:upperCorner>1 7</gml:upperCorner></gml:Envelope></gml:boundedBy>
<ogr:geometryProperty><gml:Polygon srsName="urn:ogc:def:crs:EPSG::4326" gml:id="multipoint_delaunay.geom.8"><gml:exterior><gml:LinearRing><gml:posList>-5 0 -1 7 1 4 -5 0</gml:posList></gml:LinearRing></gml:exterior></gml:Polygon></ogr:geometryProperty>
<ogr:POINTA>7</ogr:POINTA>
<ogr:POINTB>5</ogr:POINTB>
<ogr:POINTC>3</ogr:POINTC>
</ogr:multipoint_delaunay>
</gml:featureMember>
</ogr:featureMember>
</ogr:FeatureCollection>

0 comments on commit 451d1ba

Please sign in to comment.