Thread: [Jts-topo-suite-user] Triangulating polygons?
Brought to you by:
dr_jts
Menu
▾
▴
jts-topo-suite-user
|
From: Ian T. <ij...@ps...> - 2010-04-20 19:35:59
|
I have a need for the triangulation of a polygon. These are real world polygons so I'm guessing they are not going to be simple or convex. Does JTS provide this functionality or does any one have some code I can use? I'm actually calculating the moment of inertia for the polygons so if you can point to a better way I'd love to see that too. All the references I've found say to go with triangles and summation (and leave triangulation as an exercise for the reader). Thanks Ian -- Ian Turton |
|
From: Martin D. <mb...@re...> - 2010-04-22 16:50:11
|
JTS 1.11 provides Delaunay triangulation and Constrained Delaunay triangulation. In theory you could use CDT to triangulate a polygon, but I would probably look at more direct and simpler algorithms first. There is a very simple algorithm called Ear-Clipping (aka Ear Cutting or Ear Slicing). This page provides Java code for this: http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applet1.html Also have a look at this page - it provides an applet and a paper explaining the technique. http://www.sfu.ca/~cjs/triangulation/ Seems like this would be a nice thing to add to JTS. Anyone able to contribute a patch? Martin Ian Turton wrote: > I have a need for the triangulation of a polygon. These are real world > polygons so I'm guessing they are not going to be simple or convex. > Does JTS provide this functionality or does any one have some code I > can use? > > I'm actually calculating the moment of inertia for the polygons so if > you can point to a better way I'd love to see that too. All the > references I've found say to go with triangles and summation (and > leave triangulation as an exercise for the reader). > > Thanks > Ian > > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 |
|
From: Michael B. <mic...@gm...> - 2010-04-23 06:51:24
|
This isn't a patch but a demo of brute force ear-clipping. Need some
tips about how to deal with holes.
I also had a look at the paper you pointed to Martin. Haven't got my
head around it yet but it did make more sense when I finally realized
the pages are in the wrong order :)
import com.vividsolutions.jts.algorithm.Angle;
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.Polygon;
import com.vividsolutions.jts.io.WKTReader;
import java.util.ArrayList;
import java.util.List;
/**
* Demonstrates brute force approach to the ear clipping algorithm
* to triangulate a polygon. This demo doesn't yet cope with
* polygons that have holes.
*
* @author Michael Bedward
*/
public class EarClipping {
private static final double EPS = 1.0E-4;
GeometryFactory gf = new GeometryFactory();
public static void main(String[] args) throws Exception {
new EarClipping().demo();
}
/**
* Demonstrate the ear-clipping algorithm
* @throws Exception
*/
private void demo() throws Exception {
WKTReader reader = new WKTReader(gf);
Polygon poly = (Polygon )reader.read("POLYGON((0 0, 5 0, 2 3,
5 5, 10 0, 10 -5, 5 -2, 0 -5, 0 0))");
System.out.println("Input polygon:");
System.out.println(poly);
Geometry ears = triangulate(poly);
final int n = ears.getNumGeometries();
System.out.println();
System.out.println("Found " + n + " ears:");
for (int i = 0; i < n; i++) {
System.out.println(ears.getGeometryN(i));
}
}
/**
* Brute force approach to ear clipping
*
* @param inputPoly input polygon
* @return GeometryCollection of triangular polygons
*/
private Geometry triangulate(Polygon inputPoly) {
if (inputPoly.getNumGeometries() > 1) {
throw new IllegalArgumentException("Can't deal with holes yet");
}
List<Polygon> ears = new ArrayList<Polygon>();
Polygon workingPoly = (Polygon) inputPoly.clone();
Coordinate[] coords = workingPoly.getBoundary().getCoordinates();
int N = coords.length - 1;
boolean finished = false;
int k0 = 0;
do {
int k1 = (k0 + 1) % N;
int k2 = (k0 + 2) % N;
LineString ls = gf.createLineString(new Coordinate[]
{coords[k0], coords[k2]});
if (workingPoly.covers(ls)) {
Polygon ear = gf.createPolygon(
gf.createLinearRing(new
Coordinate[]{coords[k0], coords[k1], coords[k2], coords[k0]}),
null);
ears.add(ear);
workingPoly = (Polygon) workingPoly.difference(ear);
coords = workingPoly.getBoundary().getCoordinates();
coords = removeColinearVertices(coords);
N = coords.length - 1;
k0 = 0;
if (N == 3) { // triangle
ears.add(gf.createPolygon(gf.createLinearRing(coords), null));
finished = true;
}
} else {
k0++ ;
}
} while (!finished);
return gf.createGeometryCollection(ears.toArray(new Geometry[0]));
}
/**
* Remove co-linear vertices. TopologyPreservingSimplifier could be
* used for this but that seems like over-kill.
*
* @param coords polygon vertices
* @return coordinates with any co-linear vertices removed
*/
private Coordinate[] removeColinearVertices(Coordinate[] coords) {
final int N = coords.length - 1;
List<Coordinate> coordList = new ArrayList<Coordinate>();
for (int j = 1; j <= N; j++) {
int i = (j - 1) % N;
int k = (j + 1) % N;
if (Math.abs(Math.PI - Angle.angleBetween(coords[i],
coords[j], coords[k])) > EPS) {
coordList.add(coords[j]);
}
}
coordList.add(new Coordinate(coordList.get(0)));
return coordList.toArray(new Coordinate[0]);
}
}
|
|
From: Ian T. <ij...@ps...> - 2010-04-23 14:34:50
|
On Fri, Apr 23, 2010 at 2:51 AM, Michael Bedward <mic...@gm...> wrote: > This isn't a patch but a demo of brute force ear-clipping. Need some > tips about how to deal with holes. This works so much better than my attempt, thanks. I'll see if I have time to sort out holes today (depends on how demanding the students are). > > I also had a look at the paper you pointed to Martin. Haven't got my > head around it yet but it did make more sense when I finally realized > the pages are in the wrong order :) > It does seem to leave some steps out. :-) Ian -- Ian Turton |
|
From: Martin D. <mtn...@te...> - 2010-04-23 18:42:39
|
Thanks, Michael. I'll try this out ASAP.
For handling holes I can think of two approaches (neither of which is
trivial, but maybe not too difficult either)
1. When selecting an ear to clip, ensure that the clipping line does not
intersect any holes in the polygon. (Although - as I write this I can
think of a simple counterexample - if a hole is *almost* as large as the
shell itself, this won't be able to find a non-intersecting clipping line
2. (This one I think is foolproof, but harder). Turn the
shel-with-holes into a self-intersecting-shell, by adding lines which
connect each hole to the outer shell. Then triangulate the resulting
shell as per normal (the self-intersection should not affect the
triangulation algorithm. The tricky part is finding "good" lines to
connect each hole. Possibly an exhaustive approach of trying to connect
each hole vertex to each shell vertex and choosing the shortest line
segment will work. Process each hole sequentially - there can be
situations where a hole connects to a (former) hole.
Michael Bedward wrote:
> This isn't a patch but a demo of brute force ear-clipping. Need some
> tips about how to deal with holes.
>
> I also had a look at the paper you pointed to Martin. Haven't got my
> head around it yet but it did make more sense when I finally realized
> the pages are in the wrong order :)
>
>
> import com.vividsolutions.jts.algorithm.Angle;
> 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.Polygon;
> import com.vividsolutions.jts.io.WKTReader;
> import java.util.ArrayList;
> import java.util.List;
>
> /**
> * Demonstrates brute force approach to the ear clipping algorithm
> * to triangulate a polygon. This demo doesn't yet cope with
> * polygons that have holes.
> *
> * @author Michael Bedward
> */
> public class EarClipping {
> private static final double EPS = 1.0E-4;
>
> GeometryFactory gf = new GeometryFactory();
>
> public static void main(String[] args) throws Exception {
> new EarClipping().demo();
> }
>
> /**
> * Demonstrate the ear-clipping algorithm
> * @throws Exception
> */
> private void demo() throws Exception {
> WKTReader reader = new WKTReader(gf);
> Polygon poly = (Polygon )reader.read("POLYGON((0 0, 5 0, 2 3,
> 5 5, 10 0, 10 -5, 5 -2, 0 -5, 0 0))");
> System.out.println("Input polygon:");
> System.out.println(poly);
>
> Geometry ears = triangulate(poly);
> final int n = ears.getNumGeometries();
>
> System.out.println();
> System.out.println("Found " + n + " ears:");
> for (int i = 0; i < n; i++) {
> System.out.println(ears.getGeometryN(i));
> }
> }
>
> /**
> * Brute force approach to ear clipping
> *
> * @param inputPoly input polygon
> * @return GeometryCollection of triangular polygons
> */
> private Geometry triangulate(Polygon inputPoly) {
> if (inputPoly.getNumGeometries() > 1) {
> throw new IllegalArgumentException("Can't deal with holes yet");
> }
>
> List<Polygon> ears = new ArrayList<Polygon>();
> Polygon workingPoly = (Polygon) inputPoly.clone();
>
> Coordinate[] coords = workingPoly.getBoundary().getCoordinates();
> int N = coords.length - 1;
>
> boolean finished = false;
> int k0 = 0;
> do {
> int k1 = (k0 + 1) % N;
> int k2 = (k0 + 2) % N;
> LineString ls = gf.createLineString(new Coordinate[]
> {coords[k0], coords[k2]});
>
> if (workingPoly.covers(ls)) {
> Polygon ear = gf.createPolygon(
> gf.createLinearRing(new
> Coordinate[]{coords[k0], coords[k1], coords[k2], coords[k0]}),
> null);
> ears.add(ear);
> workingPoly = (Polygon) workingPoly.difference(ear);
> coords = workingPoly.getBoundary().getCoordinates();
> coords = removeColinearVertices(coords);
> N = coords.length - 1;
> k0 = 0;
> if (N == 3) { // triangle
>
> ears.add(gf.createPolygon(gf.createLinearRing(coords), null));
> finished = true;
> }
> } else {
> k0++ ;
> }
> } while (!finished);
>
> return gf.createGeometryCollection(ears.toArray(new Geometry[0]));
> }
>
> /**
> * Remove co-linear vertices. TopologyPreservingSimplifier could be
> * used for this but that seems like over-kill.
> *
> * @param coords polygon vertices
> * @return coordinates with any co-linear vertices removed
> */
> private Coordinate[] removeColinearVertices(Coordinate[] coords) {
> final int N = coords.length - 1;
> List<Coordinate> coordList = new ArrayList<Coordinate>();
>
> for (int j = 1; j <= N; j++) {
> int i = (j - 1) % N;
> int k = (j + 1) % N;
> if (Math.abs(Math.PI - Angle.angleBetween(coords[i],
> coords[j], coords[k])) > EPS) {
> coordList.add(coords[j]);
> }
> }
>
> coordList.add(new Coordinate(coordList.get(0)));
> return coordList.toArray(new Coordinate[0]);
> }
>
> }
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts...@li...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>
|
|
From: Ian T. <ij...@ps...> - 2010-04-23 18:48:22
|
On Fri, Apr 23, 2010 at 2:44 PM, Martin Davis <mtn...@te...> wrote: > Thanks, Michael. I'll try this out ASAP. > > For handling holes I can think of two approaches (neither of which is > trivial, but maybe not too difficult either) > > 1. When selecting an ear to clip, ensure that the clipping line does not > intersect any holes in the polygon. (Although - as I write this I can > think of a simple counterexample - if a hole is *almost* as large as the > shell itself, this won't be able to find a non-intersecting clipping line > > 2. (This one I think is foolproof, but harder). Turn the > shel-with-holes into a self-intersecting-shell, by adding lines which > connect each hole to the outer shell. Then triangulate the resulting > shell as per normal (the self-intersection should not affect the > triangulation algorithm. The tricky part is finding "good" lines to > connect each hole. Possibly an exhaustive approach of trying to connect > each hole vertex to each shell vertex and choosing the shortest line > segment will work. Process each hole sequentially - there can be > situations where a hole connects to a (former) hole. > One option I found is to convert the polygon to trapezoids and then triangulate the trapezoids http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.5877, There is C code at http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html that claims to handle holes. Ian -- Ian Turton |
|
From: Michael B. <mic...@gm...> - 2010-04-24 02:52:04
|
Thanks for the tip Martin. I'll try implementing the second idea. Ian, have you already tried the C code ? I'll defer looking at it until after having a go myself. Michael |
|
From: Martin D. <mtn...@te...> - 2010-04-24 04:43:05
|
Ok, great. Let us know how it goes. There's an obvious brute-force n^2 algorithm for finding the shortest connector between all holes and the current shell. This can be improved by indexing the vertices of the current shell and running a tree-traversal nearest-neighbour algorithm using the index. I can provide more details and maybe even a framework for doing this, once the basic algorithm has been written. Michael Bedward wrote: > Thanks for the tip Martin. I'll try implementing the second idea. > > Ian, have you already tried the C code ? I'll defer looking at it > until after having a go myself. > > Michael > > ------------------------------------------------------------------------------ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > |
|
From: Michael B. <mic...@gm...> - 2010-04-24 09:45:43
|
On 24 April 2010 14:44, Martin Davis <mtn...@te...> wrote:
> Ok, great. Let us know how it goes.
>
Made some progress and then got stuck. I'll describe what I've done so
far and then the next idea.
Get shell coords list
For each hole list:
Get hole coords
Find closest hole - shell vertices
Insert hole coords into shell coords list as:
{shell coords} {join} {hole coords} {join} {remaining shell coords}
I'm working with a list of coordinates because the self-intersecting
shell is no longer a valid polygon so I can't use the difference
method to subtract ears. That's OK because removing an ear just
involves removing one coordinate from the shell.
It works well up to a point but then ends up in configurations where
no valid ear can be found because of the order of coordinates being
tested.
Perhaps the method of joining holes to shell can be improved ?
In the meantime I'm falling back to a dumber algorithm:
1. triangulate ignoring holes
2. for each ear found in step 1, if it overlaps holes, subtract them
and re-triangulate
Michael
|
|
From: Michael B. <mic...@gm...> - 2010-04-24 09:49:21
|
PS. some more links about triangulation in this StackOverflow discussion... http://stackoverflow.com/questions/406301/polygon-triangulation-with-holes |
|
From: Martin D. <mtn...@te...> - 2010-04-24 16:37:58
|
By the way, I can definitely visualize situations where the "choose
shortest segment to connect hole" algorithm won't work. Eg the following:
POLYGON ((50 440, 50 50, 510 50, 510 440, 280 240, 50 440),
(105 230, 443 228, 106 208, 105 230),
(280 210, 260 190, 310 190, 280 210))
That's ok, though. There always has to be *some* sequence of line
segments which validly connects all holes to the shell or to another
hole. So if the heuristic of shortest segment fails, I think you just
have to delay connecting that hole to the last.
Michael Bedward wrote:
> On 24 April 2010 14:44, Martin Davis <mtn...@te...> wrote:
>
>> Ok, great. Let us know how it goes.
>>
>>
>
> Made some progress and then got stuck. I'll describe what I've done so
> far and then the next idea.
>
> Get shell coords list
> For each hole list:
> Get hole coords
> Find closest hole - shell vertices
> Insert hole coords into shell coords list as:
> {shell coords} {join} {hole coords} {join} {remaining shell coords}
>
> I'm working with a list of coordinates because the self-intersecting
> shell is no longer a valid polygon so I can't use the difference
> method to subtract ears. That's OK because removing an ear just
> involves removing one coordinate from the shell.
>
> It works well up to a point but then ends up in configurations where
> no valid ear can be found because of the order of coordinates being
> tested.
>
> Perhaps the method of joining holes to shell can be improved ?
>
> In the meantime I'm falling back to a dumber algorithm:
>
> 1. triangulate ignoring holes
> 2. for each ear found in step 1, if it overlaps holes, subtract them
> and re-triangulate
>
> Michael
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts...@li...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>
|
|
From: Ian T. <ij...@ps...> - 2010-04-24 20:53:17
|
On Fri, Apr 23, 2010 at 10:51 PM, Michael Bedward
<mic...@gm...> wrote:
> Thanks for the tip Martin. I'll try implementing the second idea.
>
> Ian, have you already tried the C code ? I'll defer looking at it
> until after having a go myself.
I've made a start but generating monotone polygons is harder than it
looks - I'm having problems with angles - the algorithm calls for
determining if the interior angle is less than PI so I was using
Angle.interiorAngle(c1,c2,c3) but it never seems to return a value >
PI, so I never end up with any merge points.
Am I missing something obvious?
I tried out the following
public void testAngle() {
GeometricShapeFactory gsf = new GeometricShapeFactory();
final Coordinate center = new Coordinate(1,1);
gsf.setBase(center);
gsf.setSize(1);
gsf.setNumPoints(360);
Polygon circle = gsf.createCircle();
Coordinate[] c = circle.getCoordinates();
Coordinate start = circle.getExteriorRing().getStartPoint().getCoordinate();
int i=0;
for(Coordinate cc:c) {
System.out.println(i);
i++;
System.out.println("interior "+Angle.interiorAngle(start, center, cc));
System.out.println("orientatedBetween
"+Angle.angleBetweenOriented(start, center, cc));
System.out.println("acute "+Angle.isAcute(start, center, cc)+"
"+Angle.isObtuse(start, center, cc));
}
}
and all the way around the circle I get acute angles and the two
angles are always the same.
Ian
--
Ian Turton
|
|
From: Martin D. <mtn...@te...> - 2010-04-24 16:31:56
|
Yes, you'll have to work with the coordinates directly, since the ring
will usually be invalid. That's ok - it's faster than using difference
anyway.
I can't visualize a situation where no ear can be found. Can you post
an example?
Michael Bedward wrote:
> On 24 April 2010 14:44, Martin Davis <mtn...@te...> wrote:
>
>> Ok, great. Let us know how it goes.
>>
>>
>
> Made some progress and then got stuck. I'll describe what I've done so
> far and then the next idea.
>
> Get shell coords list
> For each hole list:
> Get hole coords
> Find closest hole - shell vertices
> Insert hole coords into shell coords list as:
> {shell coords} {join} {hole coords} {join} {remaining shell coords}
>
> I'm working with a list of coordinates because the self-intersecting
> shell is no longer a valid polygon so I can't use the difference
> method to subtract ears. That's OK because removing an ear just
> involves removing one coordinate from the shell.
>
> It works well up to a point but then ends up in configurations where
> no valid ear can be found because of the order of coordinates being
> tested.
>
> Perhaps the method of joining holes to shell can be improved ?
>
> In the meantime I'm falling back to a dumber algorithm:
>
> 1. triangulate ignoring holes
> 2. for each ear found in step 1, if it overlaps holes, subtract them
> and re-triangulate
>
> Michael
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts...@li...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>
|
|
From: Michael B. <mic...@gm...> - 2010-04-25 04:52:23
|
On 25 April 2010 02:33, Martin Davis wrote:
> I can't visualize a situation where no ear can be found. Can you post
> an example?
>
A house-shaped polygon with a diamond hole...
POLYGON((0 0, 10 0, 10 5, 5 10, 0 5, 0 0), (5 3, 7 5, 5 7, 3 5, 5 3))
My algorithm first forms this self-intersecting shell...
{0 0, 10 0, 10 5, 7 5, 5 7, 3 5, 5 3, 7 5, 10 5, 5 10, 0 5, 0 0}
It then finds three ears...
ear 1 = {0 0, 10 0, 10 5, 0 0}
shell = {0 0, 10 5, 7 5, 5 7, 3 5, 5 3, 7 5, 10 5, 5 10, 0 5, 0 0}
ear2 = {10 5, 7 5, 5 7, 10 5}
shell = {0 0, 10 5, 5 7, 3 5, 5 3, 7 5, 10 5, 5 10, 0 5, 0 0}
ear3 = {5 3, 7 5, 10 5, 5 3}
shell = {0 0, 10 5, 5 7, 3 5, 5 3, 10 5, 5 10, 0 5, 0 0}
But now, scanning this coord array for ears {i, i+1, i+2} fails to
find another ear because all lines from i : i+2 cross the (original)
hole. The next ear I'd like it to find would be {5 7, 10 5, 5 10, 5 7}
but that would require a change to the order of the shell coords.
It's a nice puzzle :-) Any thoughts ?
Michael
|
|
From: Martin D. <mtn...@te...> - 2010-04-25 05:07:37
|
You might want to try normalizing the orientation of the shell and hole
rings, so that they are compatible (that is, so that they all have the
interior on the same side). In the polygon WKT below both the shell and
the hole are CCW. In a normalized polygon the shell is CW and the holes
are CCW. (There is a method Geometry.normalize() that does this - but
be aware that it modifies the geometry it is called on, rather than
creating a new one).
I think this might solve the problem of the loop in the last shell ring
created, which is what is preventing the next triangle from being found.
Michael Bedward wrote:
> On 25 April 2010 02:33, Martin Davis wrote:
>
>> I can't visualize a situation where no ear can be found. Can you post
>> an example?
>>
>>
>
> A house-shaped polygon with a diamond hole...
> POLYGON((0 0, 10 0, 10 5, 5 10, 0 5, 0 0), (5 3, 7 5, 5 7, 3 5, 5 3))
>
> My algorithm first forms this self-intersecting shell...
> {0 0, 10 0, 10 5, 7 5, 5 7, 3 5, 5 3, 7 5, 10 5, 5 10, 0 5, 0 0}
>
> It then finds three ears...
> ear 1 = {0 0, 10 0, 10 5, 0 0}
> shell = {0 0, 10 5, 7 5, 5 7, 3 5, 5 3, 7 5, 10 5, 5 10, 0 5, 0 0}
>
> ear2 = {10 5, 7 5, 5 7, 10 5}
> shell = {0 0, 10 5, 5 7, 3 5, 5 3, 7 5, 10 5, 5 10, 0 5, 0 0}
>
> ear3 = {5 3, 7 5, 10 5, 5 3}
> shell = {0 0, 10 5, 5 7, 3 5, 5 3, 10 5, 5 10, 0 5, 0 0}
>
> But now, scanning this coord array for ears {i, i+1, i+2} fails to
> find another ear because all lines from i : i+2 cross the (original)
> hole. The next ear I'd like it to find would be {5 7, 10 5, 5 10, 5 7}
> but that would require a change to the order of the shell coords.
>
> It's a nice puzzle :-) Any thoughts ?
>
> Michael
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts...@li...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>
|
|
From: Michael B. <mic...@gm...> - 2010-04-25 05:08:24
|
Aha ! Describing the problem seems to jogged a neuron. If I modify
the algorithm to test coords {i, i+k, i+k+1} where k can increase then
it will get out of that trap
Michael
|
|
From: Martin D. <mtn...@te...> - 2010-04-24 21:40:53
|
Yes you are missing something obvious.... 8^) Use
GeometricShapeFactory.setCentre, rather than setBase
I just tried this in your code and it produces the angles you'd expect -
interiorAngle starting from 0, increasing up to 2PI, and decreasing back
down to 0.
Ian, at some point can you post your Java code port of the Manocha C
code for the Seidel algorithm?
And I can't get the link to the extended C code for handling holes to
work - did you manage to find that code?
Martin
Ian Turton wrote:
> On Fri, Apr 23, 2010 at 10:51 PM, Michael Bedward
> <mic...@gm...> wrote:
>
>> Thanks for the tip Martin. I'll try implementing the second idea.
>>
>> Ian, have you already tried the C code ? I'll defer looking at it
>> until after having a go myself.
>>
>
> I've made a start but generating monotone polygons is harder than it
> looks - I'm having problems with angles - the algorithm calls for
> determining if the interior angle is less than PI so I was using
> Angle.interiorAngle(c1,c2,c3) but it never seems to return a value >
> PI, so I never end up with any merge points.
>
> Am I missing something obvious?
>
> I tried out the following
>
> public void testAngle() {
> GeometricShapeFactory gsf = new GeometricShapeFactory();
> final Coordinate center = new Coordinate(1,1);
> gsf.setBase(center);
> gsf.setSize(1);
> gsf.setNumPoints(360);
> Polygon circle = gsf.createCircle();
> Coordinate[] c = circle.getCoordinates();
> Coordinate start = circle.getExteriorRing().getStartPoint().getCoordinate();
> int i=0;
> for(Coordinate cc:c) {
> System.out.println(i);
> i++;
> System.out.println("interior "+Angle.interiorAngle(start, center, cc));
> System.out.println("orientatedBetween
> "+Angle.angleBetweenOriented(start, center, cc));
> System.out.println("acute "+Angle.isAcute(start, center, cc)+"
> "+Angle.isObtuse(start, center, cc));
> }
> }
>
> and all the way around the circle I get acute angles and the two
> angles are always the same.
>
> Ian
>
|
|
From: Ian T. <ij...@ps...> - 2010-04-25 20:09:11
Attachments:
MonotonePolygon.java
|
On Sat, Apr 24, 2010 at 5:42 PM, Martin Davis <mtn...@te...> wrote: > Yes you are missing something obvious.... 8^) Use > GeometricShapeFactory.setCentre, rather than setBase I'm an idiot! > > I just tried this in your code and it produces the angles you'd expect - > interiorAngle starting from 0, increasing up to 2PI, and decreasing back > down to 0. > I still seem to get a count up to PI and then down to 0 (or -PI -> PI for orientatedAngle). > Ian, at some point can you post your Java code port of the Manocha C > code for the Seidel algorithm? I gave up on that one - I've attached my current code which is based on Computational Geometry De Berg, M., van Kreveld, M.,Overmars, M., Schwarzkopf, O. Springer, 1997 > > And I can't get the link to the extended C code for handling holes to > work - did you manage to find that code? That was the problem I had too. Ian -- Ian Turton |
|
From: Michael B. <mic...@gm...> - 2010-04-25 05:11:07
|
Thanks Martin. That would indeed work in this case. Michael On 25 April 2010 15:09, Martin Davis <mtn...@te...> wrote: > You might want to try normalizing the orientation of the shell and hole > rings, so that they are compatible (that is, so that they all have the > interior on the same side). In the polygon WKT below both the shell and > the hole are CCW. In a normalized polygon the shell is CW and the holes > are CCW. (There is a method Geometry.normalize() that does this - but > be aware that it modifies the geometry it is called on, rather than > creating a new one). > > I think this might solve the problem of the loop in the last shell ring > created, which is what is preventing the next triangle from being found. > |
|
From: Michael B. <mic...@gm...> - 2010-04-25 05:54:06
|
Normalizing the polygon did the trick. For the house-with-diamond polygon...
POLYGON((0 0, 10 0, 10 5, 5 10, 0 5, 0 0), (5 3, 7 5, 5 7, 3 5, 5 3))
the algorithm returns these ears...
POLYGON ((0 0, 0 5, 3 5, 0 0))
POLYGON ((0 0, 3 5, 5 3, 0 0))
POLYGON ((5 7, 3 5, 0 5, 5 7))
POLYGON ((5 7, 0 5, 5 10, 5 7))
POLYGON ((7 5, 5 7, 5 10, 7 5))
POLYGON ((7 5, 5 10, 10 5, 7 5))
POLYGON ((5 3, 7 5, 10 5, 5 3))
POLYGON ((0 0, 5 3, 10 5, 0 0))
POLYGON ((0 0, 10 5, 10 0, 0 0))
Not the prettiest solution, the second last ear in particular is a
sliver, but it works. The code for this is below.
> By the way, I can definitely visualize situations where the "choose
> shortest segment to connect hole" algorithm won't work. Eg the following:
>
> POLYGON ((50 440, 50 50, 510 50, 510 440, 280 240, 50 440),
> (105 230, 443 228, 106 208, 105 230),
> (280 210, 260 190, 310 190, 280 210))
That's a nefarious polygon :-) I'll puzzle over that next.
Michael
/**
* Demonstrates brute force approach to the ear clipping algorithm
* to triangulate a polygon. This demo can deal with polygons having
* non-challenging holes
*
* @author Michael Bedward
*/
public class EarClipping2 {
private static final double EPS = 1.0E-4;
GeometryFactory gf = new GeometryFactory();
public static void main(String[] args) throws Exception {
new EarClipping2().demo();
}
/**
* Demonstrate the ear-clipping algorithm
* @throws Exception
*/
private void demo() throws Exception {
WKTReader reader = new WKTReader(gf);
Polygon poly = (Polygon) reader.read(
"POLYGON((0 0, 10 0, 10 5, 5 10, 0 5, 0 0), " +
"(5 3, 7 5, 5 7, 3 5, 5 3))");
Geometry ears = triangulate(poly);
for (int i = 0; i < ears.getNumGeometries(); i++) {
System.out.println(ears.getGeometryN(i));
}
}
/**
* Brute force approach to ear clipping
*
* @param inputPoly input polygon
* @return GeometryCollection of triangular polygons
*/
private Geometry triangulate(Polygon inputPoly) {
List<Polygon> ears = new ArrayList<Polygon>();
List<Coordinate> coords = connectHoles(inputPoly);
removeColinearVertices(coords);
int N = coords.size() - 1;
boolean finished = false;
boolean found = false;
boolean reversed = false;
int k0 = 0;
do {
int k1 = (k0 + 1) % N;
int k2 = (k1 + 2) % N;
LineString ls = gf.createLineString(new Coordinate[]
{coords.get(k0), coords.get(k2)});
found = false;
if (inputPoly.covers(ls)) {
Polygon ear = gf.createPolygon(gf.createLinearRing(
new Coordinate[]{coords.get(k0),
coords.get(k1), coords.get(k2), coords.get(k0)}),
null);
// additional check for hole over ear
if (inputPoly.covers(ear)) {
found = true;
ears.add(ear);
coords.remove(k1);
removeColinearVertices(coords);
N = coords.size() - 1;
k0 = 0;
if (N == 3) { // triangle
ears.add(gf.createPolygon(gf.createLinearRing(coords.toArray(new
Coordinate[4])), null));
finished = true;
}
}
}
if (!found) {
k0++;
if (k0 == N) {
throw new IllegalStateException("Algorithm failed");
}
}
} while (!finished);
return gf.createGeometryCollection(ears.toArray(new Geometry[0]));
}
/**
* Remove co-linear vertices. TopologyPreservingSimplifier could be
* used for this but that seems like over-kill.
*
* @param coords polygon vertices
* @return coordinates with any co-linear vertices removed
*/
private void removeColinearVertices(List<Coordinate> coords) {
int N = coords.size() - 1;
List<Coordinate> coordList = new ArrayList<Coordinate>();
for (int j = 1; j <= N; ) {
int i = (j - 1) % N;
int k = (j + 1) % N;
if (Math.abs(Math.PI - Angle.angleBetween(coords.get(i),
coords.get(j), coords.get(k))) < EPS) {
coords.remove(j);
N-- ;
} else {
j++ ;
}
}
}
/**
* Connect any holes in the input polygon to the exterior ring to
* form a self-intersecting shell
*
* @param inputPoly input polygon
* @return a new polygon with holes (if any) connected to the exterior
* ring
*/
private List<Coordinate> connectHoles(Polygon inputPoly) {
// defensively copy the input polygon
Polygon poly = (Polygon) inputPoly.clone();
poly.normalize();
Coordinate[] coords = poly.getExteriorRing().getCoordinates();
List<Coordinate> shellCoords = new ArrayList<Coordinate>();
shellCoords.addAll(Arrays.asList(coords));
for (int i = 0; i < inputPoly.getNumInteriorRing(); i++) {
List<Coordinate> holeCoords =
Arrays.asList(poly.getInteriorRingN(i).getCoordinates());
joinClosest(shellCoords, holeCoords);
}
return shellCoords;
}
private void joinClosest(List<Coordinate> shellCoords,
List<Coordinate> holeCoords) {
double minD2 = Double.MAX_VALUE;
int minIh = -1, minIs = -1;
final int Ns = shellCoords.size() - 1;
final int Nh = holeCoords.size() - 1;
for (int is = 0; is < Ns; is++) {
Coordinate cs = shellCoords.get(is);
for (int ih = 0; ih < Nh; ih++) {
Coordinate ch = holeCoords.get(ih);
double d2 = (ch.x - cs.x)*(ch.x - cs.x) + (ch.y -
cs.y)*(ch.y - cs.y);
if (d2 < minD2) {
minD2 = d2;
minIh = ih;
minIs = is;
}
}
}
/*
* Insert the join, then the hole coords, then the join again into
* shell coords list
*/
List<Coordinate> toAdd = new ArrayList<Coordinate>();
toAdd.add(new Coordinate(shellCoords.get(minIs)));
int i = minIh;
do {
toAdd.add(new Coordinate(holeCoords.get(i)));
i = (i + 1) % Nh;
} while (i != minIh);
toAdd.add(new Coordinate(holeCoords.get(minIh)));
shellCoords.addAll(minIs, toAdd);
}
}
|
|
From: Martin D. <mtn...@te...> - 2010-04-25 18:47:52
|
Good stuff, Michael!
A couple of ideas:
1. One way to improve triangulations is to "flip" edges within their
surrounding quadrilaterals, if flipping the edge would improve the
triangulation. (The exact test for improvement escapes me at the
moment, but I'll dig it out. Perhaps maximizing the minimum angle
size...) For instance, this would improve the sliver you noted.
2. For "connecting holes", I think perhaps a sweepline algorithm would
work. Sweep along (say) the Y axis from bottom to top. As the first
point of each hole is encountered, I think that some vertex of the
current shell should be visible from that point. Of course this might
not produce the best initial set of interior triangle segments - but
that's where #1 comes in.
Something to note is that creating a "good" triangulation is much harder
than creating "some" triangulation. In fact it's probably NP-complete
or something bad like that. So heuristic approachs like the one above
are always going to be necessary.
Martin
Michael Bedward wrote:
> Normalizing the polygon did the trick. For the house-with-diamond polygon...
> POLYGON((0 0, 10 0, 10 5, 5 10, 0 5, 0 0), (5 3, 7 5, 5 7, 3 5, 5 3))
>
> the algorithm returns these ears...
> POLYGON ((0 0, 0 5, 3 5, 0 0))
> POLYGON ((0 0, 3 5, 5 3, 0 0))
> POLYGON ((5 7, 3 5, 0 5, 5 7))
> POLYGON ((5 7, 0 5, 5 10, 5 7))
> POLYGON ((7 5, 5 7, 5 10, 7 5))
> POLYGON ((7 5, 5 10, 10 5, 7 5))
> POLYGON ((5 3, 7 5, 10 5, 5 3))
> POLYGON ((0 0, 5 3, 10 5, 0 0))
> POLYGON ((0 0, 10 5, 10 0, 0 0))
>
> Not the prettiest solution, the second last ear in particular is a
> sliver, but it works. The code for this is below.
>
>
>> By the way, I can definitely visualize situations where the "choose
>> shortest segment to connect hole" algorithm won't work. Eg the following:
>>
>> POLYGON ((50 440, 50 50, 510 50, 510 440, 280 240, 50 440),
>> (105 230, 443 228, 106 208, 105 230),
>> (280 210, 260 190, 310 190, 280 210))
>>
>
> That's a nefarious polygon :-) I'll puzzle over that next.
>
> Michael
>
> /**
> * Demonstrates brute force approach to the ear clipping algorithm
> * to triangulate a polygon. This demo can deal with polygons having
> * non-challenging holes
> *
> * @author Michael Bedward
> */
> public class EarClipping2 {
> private static final double EPS = 1.0E-4;
>
> GeometryFactory gf = new GeometryFactory();
>
> public static void main(String[] args) throws Exception {
> new EarClipping2().demo();
> }
>
> /**
> * Demonstrate the ear-clipping algorithm
> * @throws Exception
> */
> private void demo() throws Exception {
> WKTReader reader = new WKTReader(gf);
> Polygon poly = (Polygon) reader.read(
> "POLYGON((0 0, 10 0, 10 5, 5 10, 0 5, 0 0), " +
> "(5 3, 7 5, 5 7, 3 5, 5 3))");
>
> Geometry ears = triangulate(poly);
>
> for (int i = 0; i < ears.getNumGeometries(); i++) {
> System.out.println(ears.getGeometryN(i));
> }
> }
>
> /**
> * Brute force approach to ear clipping
> *
> * @param inputPoly input polygon
> * @return GeometryCollection of triangular polygons
> */
> private Geometry triangulate(Polygon inputPoly) {
> List<Polygon> ears = new ArrayList<Polygon>();
> List<Coordinate> coords = connectHoles(inputPoly);
>
> removeColinearVertices(coords);
> int N = coords.size() - 1;
>
> boolean finished = false;
> boolean found = false;
> boolean reversed = false;
> int k0 = 0;
> do {
> int k1 = (k0 + 1) % N;
> int k2 = (k1 + 2) % N;
> LineString ls = gf.createLineString(new Coordinate[]
> {coords.get(k0), coords.get(k2)});
>
> found = false;
> if (inputPoly.covers(ls)) {
> Polygon ear = gf.createPolygon(gf.createLinearRing(
> new Coordinate[]{coords.get(k0),
> coords.get(k1), coords.get(k2), coords.get(k0)}),
> null);
> // additional check for hole over ear
> if (inputPoly.covers(ear)) {
> found = true;
> ears.add(ear);
> coords.remove(k1);
> removeColinearVertices(coords);
> N = coords.size() - 1;
> k0 = 0;
> if (N == 3) { // triangle
>
> ears.add(gf.createPolygon(gf.createLinearRing(coords.toArray(new
> Coordinate[4])), null));
> finished = true;
> }
> }
> }
>
> if (!found) {
> k0++;
>
> if (k0 == N) {
> throw new IllegalStateException("Algorithm failed");
> }
> }
>
> } while (!finished);
>
> return gf.createGeometryCollection(ears.toArray(new Geometry[0]));
> }
>
> /**
> * Remove co-linear vertices. TopologyPreservingSimplifier could be
> * used for this but that seems like over-kill.
> *
> * @param coords polygon vertices
> * @return coordinates with any co-linear vertices removed
> */
> private void removeColinearVertices(List<Coordinate> coords) {
> int N = coords.size() - 1;
> List<Coordinate> coordList = new ArrayList<Coordinate>();
>
> for (int j = 1; j <= N; ) {
> int i = (j - 1) % N;
> int k = (j + 1) % N;
> if (Math.abs(Math.PI - Angle.angleBetween(coords.get(i),
> coords.get(j), coords.get(k))) < EPS) {
> coords.remove(j);
> N-- ;
> } else {
> j++ ;
> }
> }
> }
>
> /**
> * Connect any holes in the input polygon to the exterior ring to
> * form a self-intersecting shell
> *
> * @param inputPoly input polygon
> * @return a new polygon with holes (if any) connected to the exterior
> * ring
> */
> private List<Coordinate> connectHoles(Polygon inputPoly) {
> // defensively copy the input polygon
> Polygon poly = (Polygon) inputPoly.clone();
> poly.normalize();
>
> Coordinate[] coords = poly.getExteriorRing().getCoordinates();
> List<Coordinate> shellCoords = new ArrayList<Coordinate>();
> shellCoords.addAll(Arrays.asList(coords));
>
> for (int i = 0; i < inputPoly.getNumInteriorRing(); i++) {
> List<Coordinate> holeCoords =
> Arrays.asList(poly.getInteriorRingN(i).getCoordinates());
> joinClosest(shellCoords, holeCoords);
> }
>
> return shellCoords;
> }
>
> private void joinClosest(List<Coordinate> shellCoords,
> List<Coordinate> holeCoords) {
> double minD2 = Double.MAX_VALUE;
> int minIh = -1, minIs = -1;
>
> final int Ns = shellCoords.size() - 1;
> final int Nh = holeCoords.size() - 1;
>
> for (int is = 0; is < Ns; is++) {
> Coordinate cs = shellCoords.get(is);
> for (int ih = 0; ih < Nh; ih++) {
> Coordinate ch = holeCoords.get(ih);
> double d2 = (ch.x - cs.x)*(ch.x - cs.x) + (ch.y -
> cs.y)*(ch.y - cs.y);
> if (d2 < minD2) {
> minD2 = d2;
> minIh = ih;
> minIs = is;
> }
> }
> }
>
> /*
> * Insert the join, then the hole coords, then the join again into
> * shell coords list
> */
> List<Coordinate> toAdd = new ArrayList<Coordinate>();
> toAdd.add(new Coordinate(shellCoords.get(minIs)));
>
> int i = minIh;
> do {
> toAdd.add(new Coordinate(holeCoords.get(i)));
> i = (i + 1) % Nh;
> } while (i != minIh);
>
> toAdd.add(new Coordinate(holeCoords.get(minIh)));
> shellCoords.addAll(minIs, toAdd);
> }
>
> }
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts...@li...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>
|
|
From: Martin D. <mtn...@te...> - 2010-04-26 03:23:08
|
Michael,
The code you provided doesn't work for me. Any chance you sent out an
older version?
Michael Bedward wrote:
> Normalizing the polygon did the trick. For the house-with-diamond polygon...
> POLYGON((0 0, 10 0, 10 5, 5 10, 0 5, 0 0), (5 3, 7 5, 5 7, 3 5, 5 3))
>
> the algorithm returns these ears...
> POLYGON ((0 0, 0 5, 3 5, 0 0))
> POLYGON ((0 0, 3 5, 5 3, 0 0))
> POLYGON ((5 7, 3 5, 0 5, 5 7))
> POLYGON ((5 7, 0 5, 5 10, 5 7))
> POLYGON ((7 5, 5 7, 5 10, 7 5))
> POLYGON ((7 5, 5 10, 10 5, 7 5))
> POLYGON ((5 3, 7 5, 10 5, 5 3))
> POLYGON ((0 0, 5 3, 10 5, 0 0))
> POLYGON ((0 0, 10 5, 10 0, 0 0))
>
> Not the prettiest solution, the second last ear in particular is a
> sliver, but it works. The code for this is below.
>
>
>> By the way, I can definitely visualize situations where the "choose
>> shortest segment to connect hole" algorithm won't work. Eg the following:
>>
>> POLYGON ((50 440, 50 50, 510 50, 510 440, 280 240, 50 440),
>> (105 230, 443 228, 106 208, 105 230),
>> (280 210, 260 190, 310 190, 280 210))
>>
>
> That's a nefarious polygon :-) I'll puzzle over that next.
>
> Michael
>
> /**
> * Demonstrates brute force approach to the ear clipping algorithm
> * to triangulate a polygon. This demo can deal with polygons having
> * non-challenging holes
> *
> * @author Michael Bedward
> */
> public class EarClipping2 {
> private static final double EPS = 1.0E-4;
>
> GeometryFactory gf = new GeometryFactory();
>
> public static void main(String[] args) throws Exception {
> new EarClipping2().demo();
> }
>
> /**
> * Demonstrate the ear-clipping algorithm
> * @throws Exception
> */
> private void demo() throws Exception {
> WKTReader reader = new WKTReader(gf);
> Polygon poly = (Polygon) reader.read(
> "POLYGON((0 0, 10 0, 10 5, 5 10, 0 5, 0 0), " +
> "(5 3, 7 5, 5 7, 3 5, 5 3))");
>
> Geometry ears = triangulate(poly);
>
> for (int i = 0; i < ears.getNumGeometries(); i++) {
> System.out.println(ears.getGeometryN(i));
> }
> }
>
> /**
> * Brute force approach to ear clipping
> *
> * @param inputPoly input polygon
> * @return GeometryCollection of triangular polygons
> */
> private Geometry triangulate(Polygon inputPoly) {
> List<Polygon> ears = new ArrayList<Polygon>();
> List<Coordinate> coords = connectHoles(inputPoly);
>
> removeColinearVertices(coords);
> int N = coords.size() - 1;
>
> boolean finished = false;
> boolean found = false;
> boolean reversed = false;
> int k0 = 0;
> do {
> int k1 = (k0 + 1) % N;
> int k2 = (k1 + 2) % N;
> LineString ls = gf.createLineString(new Coordinate[]
> {coords.get(k0), coords.get(k2)});
>
> found = false;
> if (inputPoly.covers(ls)) {
> Polygon ear = gf.createPolygon(gf.createLinearRing(
> new Coordinate[]{coords.get(k0),
> coords.get(k1), coords.get(k2), coords.get(k0)}),
> null);
> // additional check for hole over ear
> if (inputPoly.covers(ear)) {
> found = true;
> ears.add(ear);
> coords.remove(k1);
> removeColinearVertices(coords);
> N = coords.size() - 1;
> k0 = 0;
> if (N == 3) { // triangle
>
> ears.add(gf.createPolygon(gf.createLinearRing(coords.toArray(new
> Coordinate[4])), null));
> finished = true;
> }
> }
> }
>
> if (!found) {
> k0++;
>
> if (k0 == N) {
> throw new IllegalStateException("Algorithm failed");
> }
> }
>
> } while (!finished);
>
> return gf.createGeometryCollection(ears.toArray(new Geometry[0]));
> }
>
> /**
> * Remove co-linear vertices. TopologyPreservingSimplifier could be
> * used for this but that seems like over-kill.
> *
> * @param coords polygon vertices
> * @return coordinates with any co-linear vertices removed
> */
> private void removeColinearVertices(List<Coordinate> coords) {
> int N = coords.size() - 1;
> List<Coordinate> coordList = new ArrayList<Coordinate>();
>
> for (int j = 1; j <= N; ) {
> int i = (j - 1) % N;
> int k = (j + 1) % N;
> if (Math.abs(Math.PI - Angle.angleBetween(coords.get(i),
> coords.get(j), coords.get(k))) < EPS) {
> coords.remove(j);
> N-- ;
> } else {
> j++ ;
> }
> }
> }
>
> /**
> * Connect any holes in the input polygon to the exterior ring to
> * form a self-intersecting shell
> *
> * @param inputPoly input polygon
> * @return a new polygon with holes (if any) connected to the exterior
> * ring
> */
> private List<Coordinate> connectHoles(Polygon inputPoly) {
> // defensively copy the input polygon
> Polygon poly = (Polygon) inputPoly.clone();
> poly.normalize();
>
> Coordinate[] coords = poly.getExteriorRing().getCoordinates();
> List<Coordinate> shellCoords = new ArrayList<Coordinate>();
> shellCoords.addAll(Arrays.asList(coords));
>
> for (int i = 0; i < inputPoly.getNumInteriorRing(); i++) {
> List<Coordinate> holeCoords =
> Arrays.asList(poly.getInteriorRingN(i).getCoordinates());
> joinClosest(shellCoords, holeCoords);
> }
>
> return shellCoords;
> }
>
> private void joinClosest(List<Coordinate> shellCoords,
> List<Coordinate> holeCoords) {
> double minD2 = Double.MAX_VALUE;
> int minIh = -1, minIs = -1;
>
> final int Ns = shellCoords.size() - 1;
> final int Nh = holeCoords.size() - 1;
>
> for (int is = 0; is < Ns; is++) {
> Coordinate cs = shellCoords.get(is);
> for (int ih = 0; ih < Nh; ih++) {
> Coordinate ch = holeCoords.get(ih);
> double d2 = (ch.x - cs.x)*(ch.x - cs.x) + (ch.y -
> cs.y)*(ch.y - cs.y);
> if (d2 < minD2) {
> minD2 = d2;
> minIh = ih;
> minIs = is;
> }
> }
> }
>
> /*
> * Insert the join, then the hole coords, then the join again into
> * shell coords list
> */
> List<Coordinate> toAdd = new ArrayList<Coordinate>();
> toAdd.add(new Coordinate(shellCoords.get(minIs)));
>
> int i = minIh;
> do {
> toAdd.add(new Coordinate(holeCoords.get(i)));
> i = (i + 1) % Nh;
> } while (i != minIh);
>
> toAdd.add(new Coordinate(holeCoords.get(minIh)));
> shellCoords.addAll(minIs, toAdd);
> }
>
> }
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts...@li...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>
|
|
From: Michael B. <mic...@gm...> - 2010-04-26 04:47:53
Attachments:
EarClipping2.java
|
On 26 April 2010 13:24, Martin Davis wrote: > Michael, > > The code you provided doesn't work for me. Any chance you sent out an > older version? Oops - sorry about that Martin. I've attached the correct version. Thanks for the new tips about connecting holes and improving the triangulation. I'll play with the holes idea first. Michael |
|
From: Martin D. <mtn...@te...> - 2010-04-26 04:56:17
|
Great, that works now. re the triangulation improvement algorithm: The algorithm requires being able to find neighbouring triangles across triangle sides. This can be done by embedding the triangles in a topological structure such as a Quadtree, but that gets a bit complex. A simpler option is to index the triangles by their edge coordinates, as normalized line segments (eg with coordinates in lexicographic order). A simple Java Map can be used to do this. Then it's easy to find neighbouring triangles. Also, Maps are easy to update, which is required if edges are flipped. And, as long as a check is made to ensure that candidate quadrilaterals are convex, I don't think flipping can ever violate the polygonal boundary constraints. Michael Bedward wrote: > On 26 April 2010 13:24, Martin Davis wrote: > >> Michael, >> >> The code you provided doesn't work for me. Any chance you sent out an >> older version? >> > > Oops - sorry about that Martin. I've attached the correct version. > > Thanks for the new tips about connecting holes and improving the > triangulation. I'll play with the holes idea first. > > Michael > > ------------------------------------------------------------------------ > > ------------------------------------------------------------------------------ > > ------------------------------------------------------------------------ > > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > |
|
From: Michael B. <mic...@gm...> - 2010-04-26 12:12:57
Attachments:
EarClipping3.java
|
Hi Martin, Ian, I've now extended the code to add holes to the shell by scanning from bottom to top. The new code (EarClipping3.java) successfully processes the MEP (Martin's Evil Polygon)... POLYGON ((50 440, 50 50, 510 50, 510 440, 280 240, 50 440), (105 230, 443 228, 106 208, 105 230), (280 210, 260 190, 310 190, 280 210)) Finding these ears... POLYGON ((50 50, 260 190, 310 190, 50 50)) POLYGON ((280 210, 260 190, 106 208, 280 210)) POLYGON ((280 210, 106 208, 443 228, 280 210)) POLYGON ((310 190, 280 210, 443 228, 310 190)) POLYGON ((50 50, 310 190, 443 228, 50 50)) POLYGON ((106 208, 260 190, 50 50, 106 208)) POLYGON ((105 230, 106 208, 50 50, 105 230)) POLYGON ((105 230, 50 50, 50 440, 105 230)) POLYGON ((105 230, 50 440, 280 240, 105 230)) POLYGON ((443 228, 105 230, 280 240, 443 228)) POLYGON ((443 228, 280 240, 510 440, 443 228)) POLYGON ((443 228, 510 440, 510 50, 443 228)) POLYGON ((50 50, 443 228, 510 50, 50 50)) Feeling pretty pleased about that :-) I've commented the code enough (I hope) to make clear what it's doing. I haven't yet tried to do anything about 'improving' the triangulation. Michael |
Thanks for helping keep SourceForge clean.
X