DataMuseum.dk

top - metrics - download

    Length: 3815 (0xee7)
    Types: TextFile
    Names: »polygon_area.c«

└─⟦b20c6495f⟧ Bits:30007238 EUUGD18: Wien-båndet, efterår 1987
    └─⟦this⟧ »EUUGD18/Sun/Qix/polygon_area.c« 
    └─⟦this⟧ »EUUGD18/X/Qix/polygon_area.c« 

TextFile

/*
 * File:	polygon_area.c
 * By:		Don Hatch
 *
 * For:		Yaq (Yet Another Qix)
 *
 * This procedure efficiently calculates the area of a closed polygon
 * consisting only of alternating horizontal and vertical segments.
 *
 * Running time is O(n), where n is the number of segments (or, equivalently,
 * the number of vertices).
 *
 * Input:	p -- an array containing the vertices
 *		n -- number of vertices (must be even, of course)
 *
 * Output:	function returns the area (always non-negative).
 *		The p array is not disturbed.
 *
 * Implementation:
 *	Total is initialized to zero.
 *
 *	Three consecutive points are chosen, namely p[n-1], p[n-2]
 *	and p[n-3].  These three points are replaced by a single point,
 *	effectively "ironing out" the kink p[n-2], and making a simpler
 *	polygon.  The area of the ironed-out kink (which is a rectangle)
 *	is added or subtracted from total, as appropriate.
 *
 *	We now have a polygon with two fewer vertices; decrement n by two
 *	and repeat the above until there's only two points left.
 *	The absolute value of total is returned (since we may have calculated
 *	the area "inside-out").
 *
 *	At the top of the loop, temp always represents p[n-1] in the current
 *	(simplified) polygon; we use temp so as not to disturb the input array.
 *
 *	Note that the type of coordinates need not be integer; this algorithm
 *	would work with floating-point coordinates as well.
 */

#include <pixrect/pixrect_hs.h>

#define rect_area(a, b)	(((b).x - (a).x) * ((b).y - (a).y))

simple_polygon_area0(p, n)	/* works if polygon is alternating
				   horizontal/vertical segments */
register struct pr_pos *p;
register int n;
{
    register int total = 0;
    register int first_line_is_horizontal = p[0].y == p[1].y;
    register struct pr_pos temp;		/* doesn't hurt */
    temp = p[n-1];

    for (; n > 2; n -= 2) {
	if (first_line_is_horizontal)
	    temp.y = p[n-3].y;
	else
	    temp.x = p[n-3].x;
	total += rect_area(p[n-2], temp);
    }
    return abs(total);
}
simple_polygon_area1(p, n)	/* works if polygon is alternating
				   horizontal/vertical segments */
register struct pr_pos *p;
register int n;
{
    register int total = 0;
    while (n--)
	total = p[n].x * p[n].y - total;	/* alternately add/subtract */
    return abs(total);
}
#define twice_triangle_area(a,b,c) ((b.y-a.y)*(c.x-a.x)-(c.y-a.y)*(b.x-a.x))
polygon_area(p, n) /* works on arbitrary polygons */
register struct pr_pos *p;
register int n;
{
    register int total = 0;

    for (; n > 2; n --)
	total += twice_triangle_area(p[0], p[n-1], p[n-2]);

    return abs(total)/2; /* note roundoff error if actual area is fractional*/
}
#define twice_segment_area(b,c)	((b.y * c.x) - (c.y * b.x))
polygon_area2(p, n) /* works on arbitrary polygons, if coords are close to 0 */
register struct pr_pos *p;
register int n;
{
    register int total = segment_area(p[n-1], p[0]);

    for (; --n > 0; ++p)
	total += segment_area(p[0], p[1]);

    return abs(total)/2; /* note roundoff error if actual area is fractional*/
}

#ifdef DRIVER
#define MAXPTS 10000
main(argc, argv)
char **argv;
{
    struct pr_pos p[MAXPTS];
    int n, is_tty = isatty(0);
    is_tty && printf("Enter x,y coords of the vertices, one per line.\n");
    while (is_tty && printf("--> "), scanf("%d %d", &p[n].x, &p[n].y) == 2)
	if (++n == MAXPTS) {
	    printf("That's quite enough!\n");
	    break;
	}
    dump(p, n);
    printf("simple area is        %d\n", old_simple_polygon_area(p, n));
    printf("simple simple area is %d\n", simple_polygon_area(p, n));
    printf("area is               %d\n", polygon_area(p, n));
    dump(p, n);	/* make sure it's the same */
}
dump(p, n)
struct pr_pos *p;
{
    int i;
    printf("%d pts: ", n);
    for (i = 0; i < n; ++i)
	printf("%d %d  ", p[i].x, p[i].y);
    printf("\n");
}
#endif