#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 , 11 years ago
comment:3 by , 11 years ago
This ticket is to:
- Port the Voronoi classes from JTS to GEOS
- Write C++ testcases (port or write from scratch)
- Expose the function trough the C-API of GEOS
- Write C testcases
comment:4 by , 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 , 11 years ago
| Milestone: | GEOS Future → 3.5.0 |
|---|
comment:6 by , 11 years ago
this is currently being worked on by vishal tiwari (GSOC 2013)
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 , 11 years ago
| Cc: | added |
|---|---|
| Owner: | changed from to |
| Status: | new → assigned |
comment:8 by , 11 years ago
| Version: | 3.3.8 → svn-trunk |
|---|
comment:10 by , 11 years ago
r3954 renames the C-API signature to GEOSVoronoiDiagram (from GEOSVoronoiDiagramBuilder).
comment:11 by , 11 years ago
Should we have an "only edges" parameter too ? It would match with the GEOSDelaunayTriangles interface
follow-up: 13 comment:12 by , 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
comment:13 by , 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 , 11 years ago
Added "onlyEdges" parameter. The commit can be found here:
https://github.com/vishaltiwari/libgeos/commit/fade372f6cc21d3bc337e6cf917a358c3ec5eb87
comment:15 by , 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 , 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 , 11 years ago
Great! r3959 ready for PHP (up for more fun? or I'll do it next week ;)
comment:19 by , 10 years ago
Vishal, are you still around ? I just realized that the output for "edge only" Voronoi looks weird
comment:20 by , 10 years ago
| Priority: | major → blocker |
|---|
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 , 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 , 10 years ago
| Keywords: | history added |
|---|---|
| Resolution: | → fixed |
| Status: | assigned → closed |
Envelope clipping accepted with r3985 -- consider this completed.
comment:23 by , 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 , 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)
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!