Opened 10 years ago

Closed 9 years ago

#1898 closed patch (fixed)

ST_DelaunayTriangles option to output as TIN

Reported by: robe Owned by: nw
Priority: high Milestone: PostGIS 2.1.0
Component: postgis Version: master
Keywords: history Cc: nw@…


It would be really nice if we had an option to output Delaunay Triangles as TINS. We already know they are so no validation is necessary as would be required when converting a polygon collection to a TIN. TINS naturally translate to X3D constructs. polygon collections do not have the same meaning.

I imagine for other 3D surface systems, TINS have special meaning and it would be nice to get that meaning back out.

Attachments (2)

delaunay_tin.patch (3.8 KB ) - added by nw 9 years ago.
delaunaytinopt.patch (5.9 KB ) - added by nw 9 years ago.

Download all attachments as: .zip

Change History (28)

comment:1 by strk, 10 years ago

What isn't clear to me is how to make _valid_ TIN, not being there any validation routine. Would simply tagging the multicomponent as a TIN be enough, knowing that it contains only triangles and no holes ? Isn't there any requirement about ordering of those triangles ?

comment:2 by strk, 10 years ago

We need a TIN building API in liblwgeom for this to proceed

comment:3 by robe, 10 years ago

Milestone: PostGIS 2.1.0PostGIS Future

by nw, 9 years ago

Attachment: delaunay_tin.patch added

comment:4 by nw, 9 years ago

Owner: changed from pramsey to nw
Status: newassigned

I have looked at the code for this and what is returned is a geometrycollection, which is binary compatible with a TIN. Unfortunately, what is returned is a collection of polygons, not a collection of triangles, which is what a TIN wants, and Polygon is not binary compatible with a Triangle.

So in order to create a tin, we need to convert all the polygons to triangles.

I have modified the st_delaunayTriangles to return a TIN (always) unless edgesonly is used, in which case, it returns a multilinestring (as it did before, I use the old code). Since a TIN is a collection, I think it should be acceptable to return one. Code that is specifically wanting a generic collection rather than an actual TIN will break of course, so this isn't technically a backwards compatible change. We could add an additional argument to ask for a TIN if it's really needed.

Personally, I think the flags argument to ST_DelaunayTriangles should be a boolean, since that's what it is. Since this is a new function, presumably that would be acceptable, as there shouldn't be any existing code that would break.

Patch attached.

comment:5 by robe, 9 years ago

I'm hesitant to touch this just because I think there may be some overlap with what Olivier is dong with sfcgal. Also since TINS aren't well supported in our code base (not many functions work with them) people might prefer polygons.

comment:6 by nw, 9 years ago

What is being done with sfcgal? What is sfcgal?

Would a different function be better? It would be fairly easy to create ST_DelaunayTIN or some such.

comment:7 by robe, 9 years ago

It's built on CGAL so has a lot of the goodness for 3D handling that CGAL has but sounds like it might be a pain to compile. Olivier is supposed to change the configure to allow this optional configure. Then all the SFCGAL functions will be provided as a separate extension similar to what is done with postgis_topology.

I'm okay with ST_DelaunayTriangles returning TIN as long as its not the default behavior and there is an option to get polygons if you want (so that means that flag has to be tri-state not 2 state). The reason being things like ST_Union and friends don't like the extended types and extended type behavior might change in future. So then TIN would only be useful for viewing with tin supporting outputs or manipulating with external tools. (which is not bad but not great).

comment:8 by robe, 9 years ago

ah here is the article I was looking for:

by nw, 9 years ago

Attachment: delaunaytinopt.patch added

comment:9 by nw, 9 years ago

Added another patch. The flags argument is now 0 for polygons, 1 for edges, 2 for a TIN, defaulting to 0. I still think we should return a tin and provide a function to turn a tin into a collection of polygons.

On that note, the default return is a geometrycollection of polygons. Is there any reason that is preferable to a multipolygon?

comment:10 by robe, 9 years ago

Milestone: PostGIS FuturePostGIS 2.1.0
Type: enhancementpatch

Yes because it would return an invalid multipolygon. Multipolygons can't have in their set any polygons that intersect at more than a finite set of points.

I'm going to hold off a tad bit longer on committing this until I verify Olivier's patch in #2254 doesn't conflict with this, but I do plan to commit this in some shape or form in 2.1.

comment:11 by robe, 9 years ago

okay your patch doesn't conflict with Olivier's since he just does a geos/cgal swap in his and doesn't touch this function.

However I can't apply it. Fails during cu_test regress.

c:\ming64\projects\postgis\postgis-2.1.0SVN\liblwgeom/lwgeom_geos.c:1329: undefi
ned reference to `GEOSDelaunayTriangulation'
c:\ming64\projects\postgis\postgis-2.1.0SVN\liblwgeom/lwgeom_geos.c:1332: undefi
ned reference to `GEOSGeom_destroy'
c:\ming64\projects\postgis\postgis-2.1.0SVN\liblwgeom/lwgeom_geos.c:1342: undefi
ned reference to `GEOSSetSRID'
c:\ming64\projects\postgis\postgis-2.1.0SVN\liblwgeom/lwgeom_geos.c:1350: undefi
ned reference to `GEOSGeom_destroy'
c:\ming64\projects\postgis\postgis-2.1.0SVN\liblwgeom/lwgeom_geos.c:1350: undefi
ned reference to `GEOSGeom_destroy'
../../liblwgeom/.libs/liblwgeom.a(lwgeom_geos.o): In function `lwgeom_geos_versi
c:\ming64\projects\postgis\postgis-2.1.0SVN\liblwgeom/lwgeom_geos.c:415: undefin
ed reference to `GEOSversion'
collect2: ld returned 1 exit status
make[2]: *** [cu_tester] Error 1
make[2]: Leaving directory `/c/ming64/projects/postgis/postgis-2.1.0SVN/loader/c
make[1]: *** [check] Error 2
make[1]: Leaving directory `/c/ming64/projects/postgis/postgis-2.1.0SVN/loader'
make: *** [check] Error 1

The issue might very well be I screwed up my environment or order with lwtin.c the include you added

#include "lwgeom_geos.h" 

Might be something stupid like the ordering of the includes since I think I've run into this issue before.

comment:12 by nw, 9 years ago

I can recreate the patch.

After a git pull on svn-trunk, the top log message is…

commit 4d9a4acc9cb59309fc053198d7f6a699be85940a Author: Regina Obe <lr@…> Date: Sun May 5 22:35:47 2013 +0000

#1818 slight doc change move the FromGeoHash family to constructor section and link back to ST_GeoHash output and amend credits to Jason Smith

git-svn-id: b70326c6-7e19-0410-871a-916f4a2858ee

Would a diff against that work, that would be pretty easy given a git rebase.

comment:13 by robe, 9 years ago

I doubt that would matter. The patch applied cleanly

If I repull down it seems fine and as soon as I apply the patch it fails. Weirdly it fails after all the tests are done (right after the topology tests) almost like its failing on shutdown of cu_tester because it can't find my geos. I'll t ryoswapthe includes to see if it makes a difference.

At first I though mayybe liblwgeom shouldn't ahve geos in there since I thought it was supposed to be self-contained, but then why an lwgeos is in that folder destroys that theory.

comment:14 by robe, 9 years ago

Your patch may be fine. It did pass the st_delaunay tests. The failure is happening in the cunit tests for shp2pgsql-gui which seems to fail randomly when liblwgeom changes. I found that liblwgeom.h got installed in my system include folder and the .a and .la in my system lib somehow and I deleted them. Sadly it didn't help.

comment:15 by robe, 9 years ago

I went ahead and committed anyway at r11361 since its the shp2pgsql-gui cu tester that is failing. I'll monitor and see if winnie buildbot runs into same issue to rule out just something with my paths. As noted in #2303 I'm seeing issues with how things are included in the gui and I don't have GEOS in my path during compile (though it works fine with other regress parts)

comment:16 by robe, 9 years ago

bah windows bot has the same issue when it gets to the shp2pgsql-gui check. The debian bot is not setup to build shp2pgsql-gui so can't tell if its isolated to windows. Output of bot is easier to read than mine.

make[2]: Entering directory `/c/jenkins/postgis/branches/2.1/loader/cunit'
x86_64-w64-mingw32-gcc -g -O2  -Wall -Wmissing-prototypes  -I/c/ming64/projects/rel-libiconv-1.13.1w64/include -I/c/jenkins/postgresql/rel/pg9.0w64/include -I/c/ming64/projects/gettext/rel-gettext-0.18.1/include -I/c/ming64/projects/rel-libiconv-1.13.1w64/include -I.. -mms-bitfields -Ic:/ming64/projects/gtk/include/gtk-2.0 -Ic:/ming64/projects/gtk/lib/gtk-2.0/include -Ic:/ming64/projects/gtk/include/atk-1.0 -Ic:/ming64/projects/gtk/include/cairo -Ic:/ming64/projects/gtk/include/gdk-pixbuf-2.0 -Ic:/ming64/projects/gtk/include/pango-1.0 -Ic:/ming64/projects/gtk/include/glib-2.0 -Ic:/ming64/projects/gtk/lib/glib-2.0/include -Ic:/ming64/projects/gtk/include/pixman-1 -Ic:/ming64/projects/gtk/include -Ic:/ming64/projects/gtk/include/freetype2 -Ic:/ming64/projects/gtk/include/libpng14    -Ic:/jenkins/POSTGR~1/rel/PG9~1.0W6/include -c -o cu_pgsql2shp.o cu_pgsql2shp.c

x86_64-w64-mingw32-gcc -g -O2  -Wall -Wmissing-prototypes  -I/c/ming64/projects/rel-libiconv-1.13.1w64/include -I/c/jenkins/postgresql/rel/pg9.0w64/include -I/c/ming64/projects/gettext/rel-gettext-0.18.1/include -I/c/ming64/projects/rel-libiconv-1.13.1w64/include -I.. -mms-bitfields -Ic:/ming64/projects/gtk/include/gtk-2.0 -Ic:/ming64/projects/gtk/lib/gtk-2.0/include -Ic:/ming64/projects/gtk/include/atk-1.0 -Ic:/ming64/projects/gtk/include/cairo -Ic:/ming64/projects/gtk/include/gdk-pixbuf-2.0 -Ic:/ming64/projects/gtk/include/pango-1.0 -Ic:/ming64/projects/gtk/include/glib-2.0 -Ic:/ming64/projects/gtk/lib/glib-2.0/include -Ic:/ming64/projects/gtk/include/pixman-1 -Ic:/ming64/projects/gtk/include -Ic:/ming64/projects/gtk/include/freetype2 -Ic:/ming64/projects/gtk/include/libpng14    -Ic:/jenkins/POSTGR~1/rel/PG9~1.0W6/include -c -o cu_shp2pgsql.o cu_shp2pgsql.c
x86_64-w64-mingw32-gcc -g -O2  -Wall -Wmissing-prototypes  -I/c/ming64/projects/rel-libiconv-1.13.1w64/include -I/c/jenkins/postgresql/rel/pg9.0w64/include -I/c/ming64/projects/gettext/rel-gettext-0.18.1/include -I/c/ming64/projects/rel-libiconv-1.13.1w64/include -I.. -mms-bitfields -Ic:/ming64/projects/gtk/include/gtk-2.0 -Ic:/ming64/projects/gtk/lib/gtk-2.0/include -Ic:/ming64/projects/gtk/include/atk-1.0 -Ic:/ming64/projects/gtk/include/cairo -Ic:/ming64/projects/gtk/include/gdk-pixbuf-2.0 -Ic:/ming64/projects/gtk/include/pango-1.0 -Ic:/ming64/projects/gtk/include/glib-2.0 -Ic:/ming64/projects/gtk/lib/glib-2.0/include -Ic:/ming64/projects/gtk/include/pixman-1 -Ic:/ming64/projects/gtk/include -Ic:/ming64/projects/gtk/include/freetype2 -Ic:/ming64/projects/gtk/include/libpng14    -Ic:/jenkins/POSTGR~1/rel/PG9~1.0W6/include -c -o cu_tester.o cu_tester.c
x86_64-w64-mingw32-gcc  ../dbfopen.o ../shpopen.o ../getopt.o ../shpcommon.o ../safileio.o ../pgsql2shp-core.o ../shp2pgsql-core.o cu_pgsql2shp.o cu_shp2pgsql.o cu_tester.o -o cu_tester ../../liblwgeom/.libs/liblwgeom.a -lm  -Lc:/jenkins/POSTGR~1/rel/PG9~1.0W6/lib -lpq -L/c/ming64/projects/rel-libiconv-1.13.1w64/lib -liconv -L/c/jenkins/postgresql/rel/pg9.0w64/lib -L/c/jenkins/gdal/rel-1.9.2w64/lib -L/c/ming64/projects/gettext/rel-gettext-0.18.1/lib -L/c/ming64/projects/rel-libiconv-1.13.1w64/lib -lcunit

../../liblwgeom/.libs/liblwgeom.a(lwtin.o): In function `lwtin_from_geos':
c:\jenkins\postgis\branches\2.1\liblwgeom/lwtin.c:30: undefined reference to `GEOSGeomTypeId'
c:\jenkins\postgis\branches\2.1\liblwgeom/lwtin.c:32: undefined reference to `GEOSGetSRID'
c:\jenkins\postgis\branches\2.1\liblwgeom/lwtin.c:51: undefined reference to `GEOSGetNumGeometries'
c:\jenkins\postgis\branches\2.1\liblwgeom/lwtin.c:64: undefined reference to `GEOSGetGeometryN'
c:\jenkins\postgis\branches\2.1\liblwgeom/lwtin.c:65: undefined reference to `GEOSGetExteriorRing'	

comment:17 by nw, 9 years ago

I'm sure I'm missing something, windows builds not being something I'm familiar with, but…

x86_64-w64-mingw32-gcc ../dbfopen.o ../shpopen.o ../getopt.o

../shpcommon.o ../safileio.o ../pgsql2shp-core.o ../shp2pgsql-core.o cu_pgsql2shp.o cu_shp2pgsql.o cu_tester.o -o cu_tester ../../liblwgeom/.libs/liblwgeom.a -lm -Lc:/jenkins/POSTGR~1/rel/PG9~1.0W6/lib -lpq -L/c/ming64/projects/rel- libiconv-1.13.1w64/lib -liconv -L/c/jenkins/postgresql/rel/pg9.0w64/lib -L/c/jenkins/gdal/rel-1.9.2w64/lib -L/c/ming64/projects/gettext/rel- gettext-0.18.1/lib -L/c/ming64/projects/rel-libiconv-1.13.1w64/lib -lcunit

Where does this command line say to link against GEOS?

comment:18 by strk, 9 years ago

Robe I think -I../liblwgeom needs to be the first -I parameter for things to work correctly. I'm looking at it.

comment:19 by robe, 9 years ago

should I revert my r11363. That fixed the issue.

comment:20 by strk, 9 years ago

I've committed the liblwgeom include path fix in r11364 , but I see your problem is indeed with a missing GEOS link line. See the Makefile, GEOS_LDFLAGS should contain the link line

comment:21 by strk, 9 years ago

forget me, I can't build gtk to test (it needs a version I don't have, looks like, surprising enough)

comment:22 by robe, 9 years ago

Keywords: history added
Resolution: fixed
Status: assignedclosed

I'm going to consider this fixed since I can compile and make check (even gtk again) and I ammended the docs

comment:23 by robe, 9 years ago

Cc: nw@… added
Resolution: fixed
Status: closedreopened


I'm reopening this ticket because I think we need to rework it so that the #include "lwgeom_geos.h" is not in the lwtin.c. strk can correct me if I am wrong, but I don't think any of the type constructor files should have a dependency on GEOS and such dependencies need to be in lwgeom_geos.. files.

This is currently causing issue #2322 of which I am thinking is better to fix the root cause especially since liblwgeom is something we plan to share with other projects (and are sorta already)

comment:24 by robe, 9 years ago

hold on I'm testing now moving the lwgeos tin pieces to lwgeom_geos.c — got pased compile now in regress tests. If it works I'll commit and roll back my other changes.

comment:25 by robe, 9 years ago

okay committed what I think will fix things at r11438. Waiting for debbie to go thru her cycles before proclaiming victory.

comment:26 by robe, 9 years ago

Resolution: fixed
Status: reopenedclosed

image generator is working again :)

Note: See TracTickets for help on using tickets.