Sorry! I've forgotten to attach the quicksort method for coordinates as
well, here it is:
public void quicksort (Coordinate[] a, int lo, int hi)
{
// lo is the lower index, hi is the upper index
// of the region of array a that is to be sorted
int i=lo, j=hi;
Coordinate h;
Coordinate x=a[(lo+hi)/2];
// partition
do
{
while (a[i].compareTo(x)==-1) i++;
while (a[j].compareTo(x)==1) j--;
if (i<=j)
{
h=a[i]; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);
// recursion
if (lo<j) quicksort(a, lo, j);
if (i<hi) quicksort(a, i, hi);
}
2008/4/24, Gloria Muñoz <[EMAIL PROTECTED]>:
>
> Ok, Basically I've used the class
> ConvexHull<http://www.jump-project.org/docs/jts/1.6/api/com/vividsolutions/jts/algorithm/ConvexHull.html>
> but I've created the methods below instead of preSort and grahamScan:
>
> - preSort2: Uses quicksort algorithm and sorts the points by
> increasing x- and then y- coordinates
> - chainHull_2D: Computes the upper and lower hulls and then join
> them together avoiding duplicated endpoints
>
>
> /*
> * preSort2 for chainHull_2D()
> * find the westmost point in the set. If two or more points have
> * the same minimum x coordinate choose the one with the minimum y.
> * Points sorted by increasing x- and then y- coordinates
> * */
> private Coordinate[] preSort2(Coordinate[] pts) {
>
> quicksort(pts, 0, pts.length-1);
> return pts;
> }
>
>
> /*
> * 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;
> }
>
> It works with a small polygon I've created but fails with bigger data.
>
> Thanks!
>
_______________________________________________
jts-devel mailing list
[email protected]
http://lists.refractions.net/mailman/listinfo/jts-devel
