Rectangle intersection/union routines. More...

#include "global.h"
#include <assert.h>
#include "data.h"
#include "intersect.h"
#include "mymem.h"

Include dependency graph for intersect.c:

Data Structures
struct	SegmentTreeNode
struct	SegmentTree
struct	LocationList
Functions
static int	compareleft (const void ptr1, const void ptr2)
static int	compareright (const void ptr1, const void ptr2)
static int	comparepos (const void ptr1, const void ptr2)
static int	nextpwrof2 (int i)
static LocationList	createSortedYList (BoxListType *boxlist)
	Create a sorted list of unique y coords from a BoxList.
static SegmentTree	createSegmentTree (Coord *yCoords, int N)
	Create an empty segment tree from the given sorted list of unique y coords.
void	insertSegment (SegmentTree *st, int n, Coord Y1, Coord Y2)
void	deleteSegment (SegmentTree *st, int n, Coord Y1, Coord Y2)
double	ComputeIntersectionArea (BoxListType *boxlist)
	Compute the area of the intersection of the given rectangles.
double	ComputeUnionArea (BoxListType *boxlist)
	Compute the area of the union of the given rectangles.

Detailed Description

Rectangle intersection/union routines.

Author:: this file, intersect.c, was written and is Copyright (c) 2001 C. Scott Ananian.

Copyright.

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

Contact addresses for paper mail and Email: harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA haceaton@aplcomm.jhuapl.edu

Definition in file intersect.c.

Function Documentation

static int compareleft	(	const void *	ptr1,
		const void *	ptr2
	)		`[static]`

Definition at line 291 of file intersect.c.

References BoxType::X1.

Referenced by ComputeUnionArea().

static int comparepos	(	const void *	ptr1,
		const void *	ptr2
	)		`[static]`

Definition at line 307 of file intersect.c.

Referenced by createSortedYList().

static int compareright	(	const void *	ptr1,
		const void *	ptr2
	)		`[static]`

Definition at line 299 of file intersect.c.

References BoxType::X2.

Referenced by ComputeUnionArea().

double ComputeIntersectionArea ( BoxListType * boxlist )

Compute the area of the intersection of the given rectangles.

That is the area covered by more than one rectangle (counted twice if the area is covered by three rectangles, three times if covered by four rectangles, etc.).