intersect.h File Reference

Prototypes for rectangle intersection/union routines. More...

#include "global.h"

Include dependency graph for intersect.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
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

Prototypes for rectangle intersection/union routines.

Author:

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

---

Copyright.

PCB, interactive printed circuit board design Copyright (C) 1994,1995,1996 Thomas Nau Copyright (C) 1998,1999,2000,2001 harry eaton

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.h.

---

Function Documentation

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.).

Note:

Runs in O(N ln N) time.

Definition at line 203 of file intersect.c.

References BoxListType::Box, BoxListType::BoxN, ComputeUnionArea(), BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by ComputeCost().

Here is the call graph for this function:

double ComputeUnionArea

(

BoxListType *

boxlist

)

Compute the area of the union of the given rectangles.

Note:

Runs in O(N ln N) time.

Definition at line 221 of file intersect.c.

References SegmentTreeNode::area, BoxListType::Box, BoxListType::BoxN, compareleft(), compareright(), createSegmentTree(), createSortedYList(), deleteSegment(), insertSegment(), lastX, SegmentTree::nodes, LocationList::p, LocationList::size, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by ComputeIntersectionArea().

Here is the call graph for this function: