dsplit_convex Split a curve (Dlist) into convex components
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)
Dlists dsplit_convex (in , out , ncc , eps )
Dlist in ;
Dlists out ;
int *ncc ;
double *eps ;
This module splits a curve, given by a 2-Dlist, into convex components.
Given 3 successive points A, B, C, the determinant
|(A, B, C) =||| xB - xA|*(| yC| + | yB|) + (| xB| + | xA|)| yC - yB||
|+||| yB - yA|(| xC| + | xB|) + (| yB| + | yA|)| xC - xB| ,|
doublenumbers. The points B for which
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.
Last Modification date : Thu Nov 29 20:23:56 2001