Re: [jts-devel] Extend a LineString in a Polygon
Below is one way of doing it. I can almost guarantee there will be a much better way :) Michael import com.vividsolutions.jts.geom.Coordinate; 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.io.WKTReader; public class Foo { public static void main(String[] args) throws Exception { GeometryFactory gf = new GeometryFactory(); WKTReader reader = new WKTReader(gf); Geometry poly = reader.read(POLYGON((0 0, 0 10, 10 10, 10 0, 0 0))); // a line inside the square LineString line = (LineString) reader.read(LINESTRING(4 4, 6 5)); if (!line.intersects(poly)) { System.out.println(line does not intersect polygon); return; } Coordinate[] coords = line.getCoordinates(); final int END = coords.length - 1; // extend start point beyond poly Coordinate newStart = new Coordinate(coords[0]); Point testP = gf.createPoint(newStart); while (poly.contains(testP)) { newStart.x += newStart.x - coords[1].x; newStart.y += newStart.y - coords[1].y; testP = gf.createPoint(newStart); } // extend end point beyond poly Coordinate newEnd = new Coordinate(coords[END]); testP = gf.createPoint(newEnd); while (poly.contains(testP)) { newEnd.x += newEnd.x - coords[END-1].x; newEnd.y += newEnd.y - coords[END-1].y; testP = gf.createPoint(newEnd); } LineString extended = gf.createLineString(new Coordinate[]{newStart, newEnd}); System.out.println(extended line: + extended); System.out.println(crosses polygon: + extended.crosses(poly)); } } ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] [Fwd: Re: Book]
Hi Martin @Michael: thx for the link to the Pragmatic site. They sound very encouraging. Now all I have to do is to write 20 pages of the book to show them... 8^) I'd be more than happy to comment on anything you write. I don't have any experience with writing a book, other than watching colleagues labour over their own book projects (and yes, it is a BIG task), but I've written many papers, articles, presentations etc and done a lot of scientific reviewing and editing. Another nice thing about the Pragmatic model is that once you get most chapters up to draft stage you can put the manuscript up as a 'beta book'. People can then make an advance purchase which entitles them to get each manuscript update, and the final book. They can then submit comments, errata and suggestions via the publishers site for you to work with. I've recently did this myself with Terence Parr's new book about ANTLR... http://www.pragprog.com/titles/tpdsl/language-implementation-patterns Readers comments on the manuscript go to this page... http://www.pragprog.com/titles/tpdsl/errata (it was a much longer list while the book was in progress) You have the advantage of many proof-readers plus you can assess and adjust your assumptions about the level of knowledge and areas of interest of your audience. Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] JTS Book (was Re: Merging many polygons)
2009/10/9 Martin Davis mbda...@refractions.net: Great! No book yet unfortunately... I did approach O'Reilly at one time, but nothing came of it. It would be nice to have for sure... Martin, A JTS book would be fantastic ! http://pragprog.com/write-for-us Nice small, ethical company. Great titles in their catalogue. Hard copy and e-book formats for each title. Note: I'm not connected with them, just a happy customer. Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Newbie - Merge Polygons
PS. I should have also mentioned that the code example assumes the pairs are in lon-lat order. If they're in lat-lon order just switch the indices in the loop. Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Angle.normalizePositive
Hi Justin, It's a bug, fixed in JTS 1.11 See: http://n2.nabble.com/patch-for-Angle-java-td2443776.html#a2443776 Michael 2009/9/12 Justin York gustaf...@gmail.com: The documentation for Angle.normalizePositive says that it should take any angle in radians and return an equivalent angle between 0 and 2*PI, however if I pass anything greater than 2*PI it returns the same angle, still greater than 2*PI. Have I misinterpreted the documentation? ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] CVS JTS 1.10
Sorry to be vague but I don't understand the purpose of this one... Michael 2009/8/27 Alex Djioev alexandre.dji...@lisasoft.com: Hi Jody and Tuure, yes, I was aiming this pom.xml for package releases, not for trunk. I modified build.xml and pom.xml so that when you run ant makezip command it will do the following: * ant script will copy pom.xml from /src directory into ${pre-zip} * Update @jts.version@ tag in pom.xml file with a value from build.properties * Include pom.xml into zip file. Cheers Alex ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] CVS JTS 1.10
Sigh... my talent for finding the long way of doing things again... Just tried the simple method with the unedited pom and it worked fine for jar and javadocs. Nice. Many thanks Alex ! Michael 2009/8/26 Jody Garnett jody.garn...@gmail.com: I have not tried it yet; I was going to just drop it in the root directory of a JTS download and say: mvn install You should find that that other things work as well such as mvn javadoc:javadoc etc... Jody ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] CVS JTS 1.10
2009/8/20 Martin Davis wrote: I'm happy using ant, but if you want to provide a maven pom and someone else says they want it too I will stuff it into CVS. I want it :) Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Randomly generate points withing a Geometry
Hi Justin, If each of your geometries occupy most of its bounding envelope I'd do the simple method that Michaël suggests. If a geometry only occupies a very small portion of its envelope a better way is to stratify the random point generation by dividing up the envelope into smaller, equal-sized rectangles, noting which of these overlap the geometry. Then generate each point using the simple algorithm within a randomly chosen rectangle. Hope this helps Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Minimum Area bounding box
HI Jatin I assume you're referring to an enclosing rectangle rotated to minimize its area - yes ? Here is an old but still very nice explanation of an algorithm to do that with a demo applet: http://cgm.cs.mcgill.ca/~orm/maer.html Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Minimum Area bounding box
Hi Sandro, Many thanks for the code ! I've just had a quick look at your code and tried it out with some randomly generated convex polygons If found a couple of little problems... In the Vector2 class, I think you want to make those public final fields static members: private static final double ZERO_TOLERANCE = 1e-06f; public static final Vector2 ZERO = new Vector2(0.0d, 0.0d); public static final Vector2 UNIT_X = new Vector2(1.0d, 0.0d); public static final Vector2 UNIT_Y = new Vector2(0.0d, 1.0d); And in the method Box2.computeVertices I think this line: akVertex[1] = center.add(akEAxis[0]).add(akEAxis[1]); should be: akVertex[1] = center.add(akEAxis[0]).sub(akEAxis[1]); ...otherwise you get a triangle instead of a rectangle :-) Once I made those changes the code seemed to work well. I think that this would be a nice facility to add to JTS. Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Minimum Area bounding box
Sandro, Here's a little demo app for your code. It displays a random convex polygon and the associated MER. Click on the display panel to generate new polygons. Michael package jtsdemos.minimumenclosure; import com.vividsolutions.jts.algorithm.ConvexHull; import com.vividsolutions.jts.geom.Coordinate; import com.vividsolutions.jts.geom.GeometryFactory; import com.vividsolutions.jts.geom.Polygon; import java.awt.Color; import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.event.MouseAdapter; import java.awt.event.MouseEvent; import java.awt.image.BufferedImage; import java.util.Random; import javax.swing.JFrame; import javax.swing.JPanel; import javax.swing.SwingUtilities; /** * A simple app to demonstrate Sandro Zacchino's minimum enclosing * rectangle (MER) code. It generates a random convex polygon, calculates the * MER, and displays both on screen. Mouse click on the display panel to * generate new polygons. * * @author Michael Bedward */ public class Demo { private static final double CLOUD_MIN = 150; private static final double CLOUD_W = 200; private static final int IMGW = (int)(CLOUD_W + 2 * CLOUD_MIN); private Polygon hullPoly; private Polygon merPoly; public static void main(String[] args) { (new Demo()).doDemo(); } private void doDemo() { generatePolys(); final JPanel panel = new JPanel() { @Override protected void paintComponent(Graphics g) { super.paintComponent(g); BufferedImage bufImg = new BufferedImage(IMGW, IMGW, BufferedImage.TYPE_INT_ARGB); Graphics2D gr = (Graphics2D) bufImg.getGraphics(); gr.setColor(Color.BLUE); Coordinate[] hullCoords = hullPoly.getCoordinates(); Coordinate c0 = hullCoords[0]; for (int i = 1; i hullCoords.length; i++) { gr.fillOval((int)c0.x-4, (int)c0.y-4, 9, 9); Coordinate c1 = hullCoords[i]; gr.drawLine((int)c0.x, (int)c0.y, (int)c1.x, (int)c1.y); c0 = c1; } gr.setColor(Color.MAGENTA); Coordinate[] merCoords = merPoly.getCoordinates(); c0 = merCoords[0]; for (int i = 1; i merCoords.length; i++) { Coordinate c1 = merCoords[i]; gr.drawLine((int)c0.x, (int)c0.y, (int)c1.x, (int)c1.y); c0 = c1; } ((Graphics2D)g).drawImage(bufImg, null, 0, 0); } }; panel.addMouseListener(new MouseAdapter() { @Override public void mouseClicked(MouseEvent e) { generatePolys(); panel.repaint(); } }); panel.setToolTipText(click for new polygon); final JFrame frame = new JFrame(MER demo); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); frame.add(panel); frame.setSize(IMGW, IMGW); SwingUtilities.invokeLater(new Runnable() { public void run() { frame.setVisible(true); } }); } private void generatePolys() { hullPoly = randomConvexPoly(); merPoly = MinimumEnclosure.computeMER(hullPoly); } private Polygon randomConvexPoly() { Random rand = new Random(); final Coordinate[] cloud = new Coordinate[10]; for (int i = 0; i cloud.length; i++) { cloud[i] = new Coordinate( CLOUD_MIN + CLOUD_W * rand.nextDouble(), CLOUD_MIN + CLOUD_W * rand.nextDouble()); } ConvexHull hull = new ConvexHull(cloud, new GeometryFactory()); return (Polygon) hull.getConvexHull(); } } ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Delaunay triangulation code in JTS 1.11
Hi Martin, This is great news - thanks ! I'd also be interested in having a sticky beak at the pre-release code. I've recently been using the OpenJump code, slightly hacked. 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
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
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] Re: concave hull ref
Here is the reference about an alpha-shapes approach that Dragan has been basing his implementation on. http://www.isprs.org/congresses/beijing2008/proceedings/3b_pdf/37.pdf Stefan, I'm interested in the student presentation that you mentioned involving animal tracking data. I'm working with similar data, both real and simulated. 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
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
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
Re: [jts-devel] basic questions
Hi Roberto, For your first question, the short answer is that JTS works with cartesian (planar) geometry so it won't deal correctly with distances between points on the globe expressed as lat/long coords. There are various ways to do what you want. See this recent discussion... http://n2.nabble.com/Lat-lon-coordinate-systems.-td2275815.html For your second question. If you have created a Coordinate object to hold current position, you can always change the x and y values without needing to construct a new object.. Coordinate c = new Coordinate(); c.x = ... c.y = ... // later c.x = ... c.y = ... But perhaps I don't understand your question correctly. If not, please say so... Hope this helps Michael 2009/3/31 roberto.cal...@gmail.com: I'm a beginner and have two questions I couldn't find the answer in documentation: - Is it possible to define a projection system for my calculations? Example, I want to calculate the distance in km between two points that has coordinates in latitude/longitude degrees in a given projection system for Earth. - I made a class that represents a moving object, so I used Coordinate implement its location (that changes all the time). I wanted to use Point, but Coordinate is the best class for dynamic info. So I'm instantiating a new Geometry everytime I need to perform calculation using this objects, is that right? Thank you. ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Re: what shall I do If I get a topology exception in union op?
2009/3/19 Martin Davis mbda...@refractions.net: No, I don't use this technique. It looks pretty complicated! That's reassuring. Ironic given the title :-) Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Re: what shall I do If I get a topology exception in union op?
2009/3/18 Martin Davis mbda...@refractions.net: So it doesn't need debugging - it needs some brilliant new thinking! Sounds like what I think about most of my code... Out of interest Martin, do you use anything like the approach described here... Edelsbrunner Mucke (1990) Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.5997 I've been trying to understand it. Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] patch for Angle.java
Hi Martin and everyone, Angle.normalizePositive doesn't give the advertised results if the input is greater than 2PI. I've attached a patch based on cvs code. cheers Michael anglefix.patch Description: Binary data ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] Re: patch for Angle.java
oops - sorry, here is the patch again without the spurious line at the top... 2009/3/8 Michael Bedward michael.bedw...@gmail.com: Hi Martin and everyone, Angle.normalizePositive doesn't give the advertised results if the input is greater than 2PI. I've attached a patch based on cvs code. cheers Michael anglefix.patch Description: Binary data ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Best way to turn arbitrary Geometries into multi-point approximation
Hi Mark, Yes, I think that's a reasonable approach. Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Best way to turn arbitrary Geometries into multi-point approximation
Hi Mark Interesting question - the polygon case is a bit like the recent discussion of concave hulls, only in reverse :) For line strings maybe the LengthIndexedLine class is your friend. For polygons, an easy hack would be to get the bounding box, generate points on a regular grid within that and then test for point in polygon, though you might need some elaboration of that if you're dealing with long, narrow polygons. Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Projection question.
thanks for posting that link Jeff - definitely one for my handy snippets collection Michael 2009/2/17 Jeff Adams jad...@avencia.com: I wound up just doing the math in lat/lon, which works (different math than in a cartesian coord system of course, but I found a couple examples here: http://forum.worldwindcentral.com/showthread.php?t=20688). ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Re: [jump-users] Question on JTS Geometry#buffer( )
Regarding Geotools, there is also the current work by Martin Desruisseaux on 'Geotidy', a refactored version of some of the Geotools 2.x code. Well worth a look... http://geotidy.geomatys.fr/javadocs/ Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Existing code to subdivide an envelope?
Don't know if this is useful, but here is a nice little paper about square-ish partitioning. http://www.win.tue.nl/~vanwijk/stm.pdf Although the applications are complex the algorithm is very simple. Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Existing code to subdivide an envelope?
2009/1/28 Martin Davis mbda...@refractions.net: It sounds like you want to create a grid of specified extent and size (= # of horizontal and vertical cells). It's pretty straightforward to code this up as a nested loop which creates Envelopes. That reminded me of something in my code cellar... SS: if you hack out the Geotools bits from this, add a line or two to process your envelope, and it might do what you want... Feel free to do whatever with it. Michael public FeatureCollection makeRegularLattice( Rectangle2D bounds, double cellWidth, CoordinateReferenceSystem crs) { int rows = (int)Math.round((bounds.getHeight()) / cellWidth); int cols = (int)Math.round((bounds.getWidth()) / cellWidth); double[] xvertices = new double[cols+1]; for (int i = 0; i = cols; i++) { xvertices[i] = bounds.getMinX() + i*cellWidth; } double[] yvertices = new double[rows+1]; for (int i = 0; i rows; i++) { yvertices[i] = bounds.getMinY() + i*cellWidth; } SimpleFeatureTypeBuilder typeBuilder = new SimpleFeatureTypeBuilder(); typeBuilder.setName(lattice); typeBuilder.setCRS(crs); typeBuilder.add(shape, Polygon.class, (CoordinateReferenceSystem) null); typeBuilder.add(id, Integer.class); typeBuilder.add(somevalue, Double.class); SimpleFeatureType type = typeBuilder.buildFeatureType(); SimpleFeatureBuilder builder = new SimpleFeatureBuilder(type); GeometryFactory gf = new GeometryFactory(); Coordinate[] cellVertices = new Coordinate[5]; int[] xind = {0, 1, 1, 0}; int[] yind = {0, 0, 1, 1}; FeatureCollection features = FeatureCollections.newCollection(); int id = 1; double valuePlaceHolder = 0; for (int i = 0; i rows; i++) { for (int j = 0; j cols; j++) { for (int v = 0; v 4; v++) { cellVertices[v] = new Coordinate(xvertices[j + xind[v]], yvertices[i + yind[v]]); } cellVertices[4] = new Coordinate(cellVertices[0]); Polygon poly = gf.createPolygon(gf.createLinearRing(cellVertices), null); builder.add(poly); builder.add(id++); builder.add(valuePlaceHolder); features.add(builder.buildFeature(null)); } } return features; } ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] Re: decompose rectilinear polygon
3. Find a concave vertex that is proceeded by 3 or more convex vertices; sorry, that should read preceded by 3 or more... ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] Re: decompose rectilinear polygon
Apologies for all the self-replies on the this thread... I now have code that seems to work - slightly more involved than I previously described after I realized that many configurations will not have 3 consecutive convex vertices and that I needed to guard against colinear point in the polygon's boundary. In case it's of use to anyone, here is the code. I'd also still be keen to hear how this task should really be done ! Michael package org.emilythecamel.jtsutils; import com.vividsolutions.jts.algorithm.CGAlgorithms; import com.vividsolutions.jts.geom.Coordinate; import com.vividsolutions.jts.geom.Geometry; import com.vividsolutions.jts.geom.GeometryFactory; import com.vividsolutions.jts.geom.Polygon; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Stack; /** * A class to decompose a recti-linear (aka orthogonal) polygon into a set of * non-overlapping rectangular polygons. * * @author Michael Bedward */ public class OrthoPolygonDecomposer { private GeometryFactory gf; /** * Constructor */ public OrthoPolygonDecomposer() { gf = new GeometryFactory(); } /** * Decompose an orthogonal (rectilinear) polygon into a series of non-overlapping * rectangles. * @param orthoPoly the input polygon; it must not contain any holes and * is ASSUMED to be orthogonal * @return a list of non-overlapping rectangular Polygons */ public ListPolygon decompose(Geometry orthoPoly) { if (((Polygon) orthoPoly).getNumInteriorRing() 0) { throw new IllegalArgumentException(can't deal with holes yet); } ListPolygon rectangles = new ArrayListPolygon(); ListCoordinate vertices = new ArrayListCoordinate(); ListInteger orientation; Geometry edPoly = new EditablePolygon((Geometry) orthoPoly.clone()); Polygon rect; while (true) { ((EditablePolygon)edPoly).removeColinearOuterVertices(); vertices.addAll(Arrays.asList(edPoly.getCoordinates())); if (vertices.size() = 5) { break; } vertices.remove(vertices.size() - 1); orientation = getVertexOrientation(vertices); rect = search3(vertices, orientation); rectangles.add(rect); Geometry diff = edPoly.difference(rect); if (diff.getGeometryType().equals(Polygon)) { edPoly = new EditablePolygon(diff); } else { throw new RuntimeException(expected more polygons); } vertices.clear(); } rect = makeRectPoly(vertices.get(0), vertices.get(2)); rectangles.add(rect); return rectangles; } /** * Searches for a rectangle by looking for a concave vertex preceded by 3 or more * convex vertices. If this configuration is found a new rectangle is constructed * having, as its diagonal, the line segment between the 1st and 3rd preceding * convex vertices; * otherwise the search is passed to * {...@linkplain #search2(java.util.List, java.util.List) } * @param vertices list of unique polygon vertices * @param orientation corresponding list of vertex orientations * @return a new rectangular polygon or null if one could not be constructed */ private Polygon search3(ListCoordinate vertices, ListInteger orientation) { int n = vertices.size(); StackInteger convex = new StackInteger(); for (int i = 0; i n; i++) { switch (orientation.get(i)) { case CGAlgorithms.LEFT: if (convex.size() = 3) { int h = convex.pop(); convex.pop(); int f = convex.pop(); return makeRectPoly(vertices.get(f), vertices.get(h)); } else { convex.clear(); } break; case CGAlgorithms.RIGHT: convex.push(i); break; } } return search2(vertices, orientation); } /** * Searches for a rectangle by looking for a concave vertex preceded by 2 or more * convex vertices. If this configuration is found, a rectangle is constructed * that has, as its diagonal, the line segment between the concave vertex and the * convex vertex two positions before it. * @param vertices list of unique polygon vertices * @param orientation corresponding list of vertex orientations * @return a new rectangular polygon or null if one could not be constructed */ private Polygon search2(ListCoordinate vertices, ListInteger orientation) { int n = vertices.size(); StackInteger convex = new StackInteger(); for (int i = 0; i n; i
Re: [jts-devel] hilbert rtree
Many thanks for the paper Rory. On first skim it looks very interesting and I'll enjoy studying it further. cheers Michael 2008/12/16 Rory Plaire codekai...@gmail.com: Hi Michael, I don't have a great deal of experience with various R-Trees, and the main reason for this is the paper on STR R-Trees which shows that they outperform Hilbert trees by a small but significant margin on a variety of spatial datasets. (http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19970016975_1997026099.pdf) After reading this, I just didn't have interest in them anymore. In my experience, I've never really seen a Hilbert R-Tree, and I just assumed that STR trees were the state of the art, and reading the paper cemented this concept. I would be interested in revisiting this, if my assumptions are wrong... -rory ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] hilbert rtree
PS. one recent paper worth looking at is: Chris H. Hamilton, Andrew Rau-Chaplin (2008) Compact Hilbert indices: Space-filling curves for domains with unequal side lengths. Information Processing Letters 105: 155–163. I have a PDF that I can send off-list if anyone is interested. Michael 2008/12/16 Michael Bedward michael.bedw...@gmail.com: Many thanks for the paper Rory. On first skim it looks very interesting and I'll enjoy studying it further. cheers Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel