BoolSortOpenInterList
Section: C Library Functions (3)
Updated: IRIT Version 6.0
Index
Return to Main Contents
NAME
BoolSortOpenInterList()
SYNOPSIS
bool_lib/bool1low.c:1201
void BoolSortOpenInterList(IPPolygonStruct *Pl, InterSegListStruct **POpen)
DESCRIPTION
Sorts the open loops of given polygon to an order that can be used in
subdividing into sub polygons later (see comment of BoolExtractPolygons).
This order is such that each loops will have no other loop between its
end points, if we walk along the polygon in the (linked list direction)
perimeter from one end to the other, before it. For example:
-----------------------------L3
| ---------------L1 -----L2 | --------L4 --L5
| | | | | | | | | |
P0 ------ P1 ------- P2 ----- P3 -------- P4 ------ P5 -------- P0
In this case, any order such that L1, L2 are before L3 will do. Obviously
this is not a total order, and they are few correct ways to sort it.
Algorithm:
For each open loop, for each of its two end, evaluate a RealType key for
the end point P between segment P(i) .. P(i+1) to be i + t, where:
t is the ratio (P - P(i)) / (P(i+1) - P(i)) . This maps the all perimeter
of the polygon onto 0..N-1, where N is number of vertices of that polygon.
Sort the keys, and while they are keys in data sturcture, search and
remove a consecutive pair of keys assosiated with same loop, and output it.
Note that each open loop point sequence is tested to be such that it
starts on the first point (first and second along vertex list) on polygon
perimeter, and the sequence end is on the second point, and the sequence
is reversed if not so. This order will make the replacement of the
perimeter from first to second points by the open loop much easier.
This may be real problem if there are two intersection points almost
identical - floating point errors may cause it to loop forever. We use
some reordering heuristics in this case, and return fatal error if fail!
PARAMETERS:
Pl: To sort the loops for.
POpen: The set of open loops. Updated in place.
FUNCTION RETURN VALUE
void
ORIGIN
(C) Copyright 1989/90-95 Gershon Elber, Technion, IIT
Index
- NAME
-
- SYNOPSIS
-
- DESCRIPTION
-
- PARAMETERS:
-
- FUNCTION RETURN VALUE
-
- ORIGIN
-
This document was created by
man2html,
using the manual pages.
Time: 07:27:20 GMT, July 20, 2024