next up previous contents index
Next: extract_connex Up: Reference Previous: disc   Contents   Index

dsplit_convex

$ \bigcirc$Name


dsplit_convex Split a curve (Dlist) into convex components




$ \bigcirc$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)




$ \bigcirc$Function Summary


Dlists dsplit_convex (in , out , ncc , eps )

Dlist in ;

Dlists out ;

int *ncc ;

double *eps ;




$ \bigcirc$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
$\displaystyle \varepsilon$(A, B, C) = $\displaystyle \varepsilon_{0}^{}$$\displaystyle \left(\vphantom{ \frac{}{} }\right.$$\displaystyle {\frac{{}}{{}}}$   | xB - xA|*(| yC| + | yB|) + (| xB| + | xA|)| yC - yB|  
  + | yB - yA|(| xC| + | xB|) + (| yB| + | yA|)| xC - xB|        $\displaystyle \left.\vphantom{ \frac{}{} }\right.$$\displaystyle {\frac{{}}{{}}}$$\displaystyle \left.\vphantom{ \frac{}{} }\right)$,  

where $ \varepsilon_{0}^{}$ = 10-15 is the relative precision of double numbers. The points B for which

| d (A, B, C)| $\displaystyle \leq$ $\displaystyle \varepsilon$(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.




$ \bigcirc$See Also


dkinfo.


$ \bigcirc$Version 1.1


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


$ \bigcirc$Author


Lionel Moisan






next up previous contents index
Next: extract_connex Up: Reference Previous: disc   Contents   Index
mw 2004-05-05