/*
 * cvhhisto.c		Jim Piper	11-09-86
 *
 * Construct convex semi-hull of histogram object.  Ignore leading
 * and trailing zero-valued histogram points.  Return as an
 * open integer polygon (no values domain).
 *
 * MODIFICATIONS
 * -------------
 * jimp	13-05-87	detect empty histogram, exit with error message
 */

#include <stdio.h>
#include <math.h>
#include <wstruct.h>


struct object *cvhhisto (histo)
struct object *histo;
{
	int i,hl,*h,x;
	struct object *cvhh, *makemain();
	struct polygondomain *cvhpdom, *makepolydmn();
	struct histogramdomain *hdom;
	register struct ivertex *wtx, *w1tx, *w2tx;

	/*
	 * ignore histogram trailing and leading zeroes
	 */
	hdom = (struct histogramdomain *)histo->idom;
	hl = hdom->npoints;
	h = hdom->hv + hl - 1;
	while (*h-- == 0)
		hl--;
	if (hl == 0) {
		fprintf(stderr,"CVHHISTO: empty histogram\n");
		exit(1);
	}
	h = hdom->hv;
	x = 0;
	while (*h == 0) {
		hl--;
		x++;
		h++;
	}
	/*
	 * make polygon
	 */
	cvhpdom = makepolydmn(1,NULL,0,hl,1);
	cvhh = makemain(10,cvhpdom,NULL,NULL,histo);
	wtx = cvhpdom->vtx;
	/*
	 * set up first chord
	 */
	for (i=1; i<=2; i++,wtx++) {
		wtx->vtX = x++;
		wtx->vtY = *h++;
	}
	cvhpdom->nvertices = 2;
	w1tx = wtx-1;
	w2tx = wtx-2;
	/*
	 * add extra chords, checking concavity condition
	 */
	hl -= 2;
	while (hl-- > 0) {
		wtx->vtX = x++;
		wtx->vtY = *h++;
		cvhpdom->nvertices++;
		/*
		 * Concavity condition (may propagate backwards).
		 */
		while ((cvhpdom->nvertices >= 3) &&
    			(wtx->vtY-w2tx->vtY)*(w1tx->vtX-w2tx->vtX) >=
    			(w1tx->vtY-w2tx->vtY)*(wtx->vtX-w2tx->vtX)) {
			w1tx->vtX = wtx->vtX;
			w1tx->vtY = wtx->vtY;
			wtx--;
			w1tx--;
			w2tx--;
			cvhpdom->nvertices--;
		}
		wtx++;
		w1tx++;
		w2tx++;
	}
	return(cvhh);
}