Opened 11 years ago

Closed 10 years ago

Last modified 7 years ago

#627 closed enhancement (fixed)

Voronoi

Reported by: smathermather Owned by: strk
Priority: blocker Milestone: 3.5.0
Component: Default Version: main
Severity: Unassigned Keywords: history
Cc: hi.vishal123@…

Description

Port voronoi from JTS. Would be really nice to add ST_Voronoi to PostGIS

Possibly remove dependency of cgal for pgRouting

Allow for any number of skeletonization solutions

Thus allowing for non-polygon outputs from Raster, like an ST_PixelAsLinestring

start the process toward world peace

Change History (27)

comment:1 by woodbri, 11 years ago

If/When this is done, I'm willing to rework the pgRouting code to use it and get rid of CGAL. Ideally, we would like to care along a Z value with each point so we can generate a 3D triangulated surface and be able to then intersect that with planes in Z to generate contours.

Thanks!

comment:2 by mdavis, 11 years ago

Given #487 this shouldn't be too hard to do.

comment:3 by strk, 11 years ago

This ticket is to:

  1. Port the Voronoi classes from JTS to GEOS
  2. Write C++ testcases (port or write from scratch)
  3. Expose the function trough the C-API of GEOS
  4. Write C testcases

comment:4 by robe, 11 years ago

Just as an FYI - we discussed in sprint and Bborie mentioned this might be a good Google Summer of Code project since it just requires someone with C++/Java skills to port and not too much hand holding as to explanations. So probably not much mentoring involved.

comment:5 by robe, 11 years ago

Milestone: GEOS Future3.5.0

comment:6 by robe, 11 years ago

this is currently being worked on by vishal tiwari (GSOC 2013)

https://github.com/vishaltiwari/GSoC-GEOS

Proposal details and project plan: https://google-melange.appspot.com/gsoc/proposal/review/google/gsoc2013/vishal_tiwari/13001

progress reports: http://trac.osgeo.org/geos/wiki/GSoC

comment:7 by strk, 11 years ago

Cc: hi.vishal123@… added
Owner: changed from geos-devel@… to strk
Status: newassigned

Commits so far: r3849 r3862 r3899 r3912 r3944 r3951

comment:8 by strk, 11 years ago

Version: 3.3.8svn-trunk

comment:9 by strk, 11 years ago

With r3953 Voronoi is also accessible via C-API. Next stop: PHP api

comment:10 by strk, 11 years ago

r3954 renames the C-API signature to GEOSVoronoiDiagram (from GEOSVoronoiDiagramBuilder).

comment:11 by strk, 11 years ago

Should we have an "only edges" parameter too ? It would match with the GEOSDelaunayTriangles interface

comment:12 by strk, 11 years ago

Vishal: would you be interested in adding the "only edges" parameter ? It should be as simpl as calling getSubdivision()->getEdges(someGeomFactory) on the VoronoiDiagramBuilder object. The rest would be writing the testcase :)

Once that's in place I'll do the PHP part

in reply to:  12 comment:13 by vishaltiwari, 11 years ago

Replying to strk:

Vishal: would you be interested in adding the "only edges" parameter ? It should be as simpl as calling getSubdivision()->getEdges(someGeomFactory) on the VoronoiDiagramBuilder object. The rest would be writing the testcase :)

Once that's in place I'll do the PHP part

Sure! I will add the "only edges" parameter and the corresponding test cases. :)

comment:14 by vishaltiwari, 11 years ago

Added "onlyEdges" parameter. The commit can be found here:

https://github.com/vishaltiwari/libgeos/commit/fade372f6cc21d3bc337e6cf917a358c3ec5eb87

comment:15 by strk, 11 years ago

Oops, you missed the change in function name (I removed the "Builder" part). Could you rebase to trunk please ? Also, git diff showed a difference in indentation between existing code and new code, could you also fix that ? Thank you !

comment:16 by vishaltiwari, 11 years ago

It was a big blunder. So I made a new branch:

https://github.com/vishaltiwari/libgeos/compare/Voronoi_corrections

It should rebase now. Also fixed the indentation issue. Thanks

comment:17 by strk, 11 years ago

Great! r3959 ready for PHP (up for more fun? or I'll do it next week ;)

comment:18 by vishaltiwari, 11 years ago

I am not that much familiar with PHP, so i suggest you do it. :)

comment:19 by strk, 10 years ago

Vishal, are you still around ? I just realized that the output for "edge only" Voronoi looks weird

comment:20 by strk, 10 years ago

Priority: majorblocker

By passing an 'onlyEdges' flag the function returns edges of the delaunay triangulation rather than of the voronoi diagram. I saw there's no support for returning voronoi diagram as linestrings in JTS but seems straightfoward to add.

Martin, any reason why getting the diagram as edges is missing ?

Also, I think it would it make sense for the voronoi diagram functions to take a mandatory clipping extent.

comment:21 by strk, 10 years ago

With r3983 I've exposed methods in the VoronoiDiagramBuilder to extract the edges of the voronoi diagram cells, as a MULTILINESTRING. That's what we get now when specifying "edgesOnly" parameter.

Commit r3984 exposes it all to the PHP APIs.

Still missing: accepting a clipping envelope. This is better accounted for now, or it'll take an additional C-API signature later... Would be nice if Vishal was still around to do this part :)

comment:22 by strk, 10 years ago

Keywords: history added
Resolution: fixed
Status: assignedclosed

Envelope clipping accepted with r3985 -- consider this completed.

comment:23 by vishaltiwari, 10 years ago

Just saw the mail and the changes u made in the C-api and VoronoiDiagramBuilder. Looks like you have taken care of it. :) Let me know if something comes up.

comment:24 by strk, 10 years ago

Hey, glad to see you're still following.

Yep, nothing more to do here, but if you're up for some more fun it would be lovely to see more triangulation classes ported (for constrained triangulation)

comment:25 by Sandro Santilli <strk@…>, 7 years ago

In 86e20a2/git:

Rename CAPI method GEOSVoronoiDiagramBuilder to GEOSVoronoiDiagram

See #627

git-svn-id: http://svn.osgeo.org/geos/trunk@3954 5242fede-7e19-0410-aef8-94bd7d2200fb

comment:26 by Sandro Santilli <strk@…>, 7 years ago

In 86e20a2/git:

Rename CAPI method GEOSVoronoiDiagramBuilder to GEOSVoronoiDiagram

See #627

git-svn-id: http://svn.osgeo.org/geos/trunk@3954 5242fede-7e19-0410-aef8-94bd7d2200fb

comment:27 by Sandro Santilli <strk@…>, 7 years ago

In 86e20a2/git:

Rename CAPI method GEOSVoronoiDiagramBuilder to GEOSVoronoiDiagram

See #627

git-svn-id: http://svn.osgeo.org/geos/trunk@3954 5242fede-7e19-0410-aef8-94bd7d2200fb

Note: See TracTickets for help on using tickets.