Re: [jts-devel] polygonizer and line strings
Hi Dragan and everyone,
I've written some code (see below) that demonstrates the concave hull
algorithm described in the Shen Wei paper and I think I now have a
better idea of what can go wrong with it.
The paper is a bit naughty really :) None of the point clouds
depicted in the figures are very testing for the algorithm. In my
demo I generate a sparser cloud within an irregular polygon to give
the algorithm a bit more challenge. If you run the program a few
times you will see that while it does a generally good job of defining
a hull, only a small number of replicate runs is required to find at
least one solution with a degenerate polygon. I suspect this is what
is happening with your data Dragan.
Still, the simplicity of the algorithm is really appealing and there
are various tweaks that could be tried. One obvious one is to make
the alpha parameter locally adaptive. At present, the algorithm will
fail if there is any point further than 2*alpha from its nearest
neighbour, but if the alpha parameter was treated as a minimum, and
allowed to increase when necessary, this problem would be avoided and
the algorithm could be used to generate a more detailed hull for those
regions of the point cloud that supported it.
Michael
package mxb.concavehull;
import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.Envelope;
import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.LineString;
import com.vividsolutions.jts.geom.Point;
import com.vividsolutions.jts.geom.Polygon;
import com.vividsolutions.jts.index.ItemVisitor;
import com.vividsolutions.jts.index.strtree.STRtree;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Insets;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import javax.swing.JFrame;
import javax.swing.JPanel;
public class ConcaveHullBuilder {
private GeometryFactory gf = new GeometryFactory();
private Random rand = new Random();
private double alpha = 50d;
public static void main(String[] args) {
ConcaveHullBuilder hull = new ConcaveHullBuilder();
hull.demo();
}
private void demo() {
/**
* Make an irregular polygon and generate random points within it
* to test the concave hull algorithm
*/
final int numPoints = 200;
Coordinate[] vertices = {
new Coordinate(0, 0),
new Coordinate(100, 100),
new Coordinate(0, 250),
new Coordinate(200, 300),
new Coordinate(200, 450),
new Coordinate(350, 450),
new Coordinate(350, 200),
new Coordinate(250, 200),
new Coordinate(350, 100),
new Coordinate(0, 0)
};
Polygon poly = gf.createPolygon(gf.createLinearRing(vertices), null);
Envelope env = poly.getEnvelopeInternal();
int n = 0;
Point[] points = new Point[numPoints];
while (n < numPoints) {
Coordinate c = new Coordinate();
c.x = rand.nextDouble() * env.getWidth() + env.getMinX();
c.y = rand.nextDouble() * env.getHeight() + env.getMinY();
Point p = gf.createPoint(c);
if (poly.contains(p)) {
points[n++] = p;
}
}
List edges = getConcaveHull(points, alpha);
display((int)(env.getWidth()*1.1), (int)(env.getHeight()*1.1),
poly, Color.GRAY,
points, Color.RED,
edges, Color.RED);
}
/**
* Identify a concave hull using the simple alpha-shape algorithm
* described in:
*
* Shen Wei (2003) Building boundary extraction based on LIDAR
point clouds data.
* The International Archives of the Photogrammetry, Remote
Sensing and Spatial
* Information Sciences. Vol. XXXVII. Part B3b. Beijing 2008
*
* @param points the point cloud
* @param alpha the single parameter for the algorithm
* @return a List of LineString boundary segments for the concave hull
*/
private List getConcaveHull(Point[] points, double alpha) {
double alpha2 = 2 * alpha;
/*
* Index the points for faster processing
*/
STRtree index = new STRtree();
for (Point p : points) {
index.insert(p.getEnvelopeInternal(), p);
}
index.build();
List edges = new ArrayList();
List candidates = new ArrayList();
candidates.addAll(Arrays.asList(points));
while (!candidates.isEmpty()) {
Point p1 = candidates.remove(0);
Envelope qEnv = new Envelope(p1.getX() - alpha2, p1.getX() + alpha2,
p1.getY() - alpha2, p1.getY() + alpha2);
PointVisitor visitor = new PointVisitor(p1, alpha2);
index.query(qEnv, visitor);
Re: [jts-devel] polygonizer and line strings
Well done Dragan - you've got Martin interested :-) I suspect he will find a solution slightly faster than I will ! Michael 2009/4/4 Martin Davis : > Two possibilities: > > 1. bug in Polygonizer > 2. your input is not fully noded. > > I would suspect #2. Can you post sample data? (to the list or to me > directly). > I'd like to see the concave hull paper you mention as well - I'm quite > interested in an implementation of this. Although as pointed out there is > no single interpretation of how concave hull should be defined - so there > could be several ways to compute something reasonable) > ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] polygonizer and line strings
Two possibilities: 1. bug in Polygonizer 2. your input is not fully noded. I would suspect #2. Can you post sample data? (to the list or to me directly). I'd like to see the concave hull paper you mention as well - I'm quite interested in an implementation of this. Although as pointed out there is no single interpretation of how concave hull should be defined - so there could be several ways to compute something reasonable) As for a user guide to JTS, I realize this would be very nice to have. I'd very much like to provide something for this. Unfortunately it's quite time-consuming to create, and it's been hard for me to find the time to put to it. For the time being I try and keep enhancing the Javadoc whenever it looks like it could be improved. Martin Dragan Blagojevic wrote: Hi, I have question regarding proper use of Polygonizer class (I'm using NTS, but it shouldn't matter I hope) I'm working on utility to create convex hull of a point set. Result of first step of that utility is whole bunch of line strings representing convex hull or point set. Then I'm using Polygonizer to transform list of line strings to polygon. Problem is that sometime result of polygonizer is not one 'Big' outlining polygon (having potentially some holes in it), but instead lot of small polygons. I suspect that problem is when some line segments lie on the boundary and as well form smaller hole in polygon that somehow create probelm. It's a bit difficult to describe, but I'll try to simplify it as much as possible. Imagine chess board (8x8 square) having line segments of lenght 1 all arround. If it happens that there are line segments arroung some of little squares arround the edges (e.g. field C1) then instead or returning big polygon (8x8) polygonizer return only small one (1x1 C1 square). My guess is that line segment on the edge get assigned to that small polygon, and then rest of the line segments do not form closed ring. That is of course totaly different of what I need, as I want to get back largest possible polygon, potentially discarding all those smaller but it seem that they take precedence and mess up desired output. Is there any way to control how polygonizer work so that i get my big polygon back. Thanks Dragan Blagojevic -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] polygonizer and line strings
I'm actually very interested in finding a concave hull implementation myself. I contacted the authors of this paper recently... http://repositorium.sdum.uminho.pt/handle/1822/6429?locale=en ...and asked for a copy. Unfortunately, they told me that they are patenting their algorithm (not just their code) and any use of it will require commercial licensing. Given that, I decided that ignorance was legally safer and it was best not to take up their offer to send me the paper ! But back to your problem... yes, if you could send me an example shapefile that would be great. I'm not one of the real gurus here so I can't promise to find the solution. But perhaps with help from others we will work it out. Yes, there is quite a lot of papers mentioning concave hull but it apear that it's kind of secret :-) It took me a while to find description of Alpha Shape algorithm, I believe that is basically the same thing as one in the link you mentioned above, main difference being that this one was published open. I'll send you a paper with algorithm description I found tomorrow when I get to the office, together with shape files. If you wait a while, I'll send you code of my implementation as well - at the moment code is in total mess as I was experimenting with various options and optimizations, so it won't do you any good in it's current state. It's in C#, but it will be trivial to change it to Java. Regards Dragan -- View this message in context: http://n2.nabble.com/polygonizer-and-line-strings-tp2572524p2574242.html Sent from the jts-devel mailing list archive at Nabble.com. ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] polygonizer and line strings
2009/4/2 Dragan Blagojevic wrote: > > Just realized that in my first post I said by mistake that I want to get > convex hull of a point set. > > I'm actually after concave hull OK - it all makes a lot more sense now :-) I'm actually very interested in finding a concave hull implementation myself. I contacted the authors of this paper recently... http://repositorium.sdum.uminho.pt/handle/1822/6429?locale=en ...and asked for a copy. Unfortunately, they told me that they are patenting their algorithm (not just their code) and any use of it will require commercial licensing. Given that, I decided that ignorance was legally safer and it was best not to take up their offer to send me the paper ! But back to your problem... yes, if you could send me an example shapefile that would be great. I'm not one of the real gurus here so I can't promise to find the solution. But perhaps with help from others we will work it out. cheers Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] polygonizer and line strings
Just realized that in my first post I said by mistake that I want to get convex hull of a point set. I'm actually after concave hull Regards Dragan -- View this message in context: http://n2.nabble.com/polygonizer-and-line-strings-tp2572524p2573981.html Sent from the jts-devel mailing list archive at Nabble.com. ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] polygonizer and line strings
Hi Michael, What I'm trying to get is Concave hull of set of points. Result of that particular concave hull algorithm (Alpha Shapes) is bunch of line segments. That part is fine, and I get bunch of line segments which outline my points just fine, however they are line segments, not polygon which is what I need. When you visually inspect those line segments, you can see big outlining polygon, lot of holes in it, lot of dangling lines, cut lines and what not. Generally polygonizer munch that lines and create polygon with holes just fine. However there is quite often situation that along the border of that (not yet formed) big polygon group of line segments form a small polygon which would in ideal case be interpreted as a hole in big polygon. Problem generally arises if one or more of line segments is shared by big and small polygon. I don't know how polygonizer works, but it would appear that those small holes get somehow created first, and line segment that belong both to hole and big polygon get 'stolen' by that small polygon, which leave big outlining polygon without one of line segments. That in turn make it not closed and basically it get thrown away. Now, what I would like to get is exact opposite, I wouldn't mind to have some small inside discarded as long as I get big outline. I hope that I explained problem better this time. If you wish I can send you .shp files with line segments and resulting polygons where is much easier to see what the problem is. Another question, is there any good user guide for JTS / NTS? I didn't find anything except class reference and some very basic user guide. Regards Dragan -- View this message in context: http://n2.nabble.com/polygonizer-and-line-strings-tp2572524p2573676.html Sent from the jts-devel mailing list archive at Nabble.com. ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] polygonizer and line strings
Hi Dragan, Nice question :-) > Problem is that sometime result of polygonizer is not one 'Big' outlining > polygon (having potentially some holes in it), but instead lot of small > polygons. > When you get back a collection fo small polys instead of one large one, will unioning the polys give you the desired result ? Also I don't quite understand about the potential for holes, are you trying to generate a variation on the general convex hull ? Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
