Next: extract_connex Up: Reference Previous: disc   Contents   Index

#### dsplit_convex

Name

dsplit_convex Split a curve (Dlist) into convex components

Command Synopsis

dsplit_convex [-e eps] [-c ncc] in out

-e eps : numerical precision (default 1e-15) CHANGE WITH CAUTION

-c ncc (screen output) : number of convex components obtained (output)

in : input (Dlist)

out : output (Dlists)

Function Summary

Dlists dsplit_convex (in , out , ncc , eps )

Dlist in ;

Dlists out ;

int *ncc ;

double *eps ;

Description

This module splits a curve, given by a 2-Dlist, into convex components.

Given 3 successive points A, B, C, the determinant

d (A, B, C) = (xB - xA)(yC - yB) - (yB - yA)(xC - xB)

is computed, as well as the approximate error
 (A, B, C) = | xB - xA|*(| yC| + | yB|) + (| xB| + | xA|)| yC - yB| + | yB - yA|(| xC| + | xB|) + (| yB| + | yA|)| xC - xB|        ,

where = 10-15 is the relative precision of double numbers. The points B for which

| d (A, B, C)| (A, B, C)

are recursively ignored as zero-curvature'' points.

For each sequence of 4 successive remaining points A, B, C, D, we say that (B, C) is an inflexion segment when d (A, B, C) and d (B, C, D) have opposite signs. When this occurs, we define the middle of (B, C) as an inflexion point and break the curve accordingly.

The result is a Dlists describing the successive convex components encountered. Notice that this module is compatible with the convention that a curve whose first and end points have exactly the same coordinates must be considered as a closed curve.

Version 1.1

Last Modification date : Thu Nov 29 20:23:56 2001

Author

Lionel Moisan

Next: extract_connex Up: Reference Previous: disc   Contents   Index
mw 2004-05-05