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