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;
}
}
ListLineString 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:
* blockquote
* 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
* /blockquote
* @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 ListLineString 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();
ListLineString edges = new ArrayListLineString();
ListPoint candidates = new ArrayListPoint();
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
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
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 mbda...@refractions.net: 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
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
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
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
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
