Ok, I've found the error and it's turned out to be a very silly mistake! I
had forgotten some braces. I attach the final code:
/*
* chainHull_2D(): Andrew's monotone chain 2D convex hull algorithm
* Input: Coordinate[] = an array of coordinates presorted
* by increasing x- and y-coordinates
* Return: ps = a stack of the convex hull vertices
*/
private Stack chainHull_2D(Coordinate[] c )
{
Coordinate p;
Stack ps = new Stack();
int i; // array scan index
// Get the indices of points with min x-coord and min|max y-coord
int minmin = 0;
int minmax = 0;
double xmin = c[0].x;
for (i=1; i<c.length; i++){
if (c[i].x != xmin) break;
}
minmax = i-1;
if (minmax == c.length -1) {
// degenerate case: all x-coords == xmin
p = (Coordinate)ps.push(c[minmin]);
if (c[minmax].y != c[minmin].y) // a nontrivial segment
p = (Coordinate)ps.push(c[minmax]); // add polygon
endpoint
p = (Coordinate)ps.push(c[minmin]); // add polygon endpoint
return ps;
}
// Get the indices of points with max x-coord and min|max y-coord
int maxmin = c.length -1;
int maxmax = c.length -1;
double xmax = c[c.length -1].x;
for (i=c.length-2; i>=0; i--)
if (c[i].x != xmax) break;
maxmin = i+1;
// Compute the LOWER HULL on the stack ps
// push minmin point onto stack
p = (Coordinate)ps.push(c[minmin]);
i = minmax;
while (++i <= maxmin)
{
// the lower line joins c[minmin] with c[maxmin]
if (CGAlgorithms.computeOrientation( c[minmin], c[maxmin], c[i]) >= 0
&& i < maxmin)
continue; // ignore c[i] above or on the lower line
while (ps.size() > 1) // there are at least 2 points on the
lower stack
{
p = (Coordinate)ps.pop();
// test if c[i] is left of the line at the stack top
if (CGAlgorithms.computeOrientation((Coordinate)ps.peek(), p,
c[i]) > 0){
p = (Coordinate)ps.push(p);
break; // c[i] is a new hull vertex
}
}
// push c[i] onto stack
p = (Coordinate)ps.push(c[i]);
}
int size_lower = ps.size();
// Next, compute the UPPER HULL on the stack upper
if (maxmax != maxmin)
// if distinct xmax points push maxmax point onto stack
p = (Coordinate)ps.push(c[maxmax]);
i = maxmin;
while (--i >= minmax)
{
// the upper line joins c[maxmax] with c[minmax]
if (CGAlgorithms.computeOrientation(c[maxmax], c[minmax], c[i]) >= 0
&& i > minmax)
continue; // ignore c[i] below or on the upper line
while (ps.size() - size_lower > 1)
// at least 2 points of the upper hull on the stack
{
p = (Coordinate)ps.pop();
// test if c[i] is left of the line at the stack top
if (CGAlgorithms.computeOrientation((Coordinate)ps.peek(), p,
c[i]) > 0){
p = (Coordinate)ps.push(p);
break; // c[i] is a new hull vertex
}
}
// push c[i] onto stack
p = (Coordinate)ps.push(c[i]);
}
if (minmax != minmin)
// push joining endpoint onto stack
p = (Coordinate)ps.push(c[minmin]);
return ps;
}
Sorry for any inconvenience.!!
Gloria
_______________________________________________
jts-devel mailing list
[email protected]
http://lists.refractions.net/mailman/listinfo/jts-devel
