1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
/*
* C o m p u t e C o m p l e x E n v e l o p e
*
* The basic algorithm has been complexified in order to speed up the computation
* and to address the problem of few points in an elongated part, to split them
* fairly amongst the sides.
*
* The amount of time is :
* proportionnal to the number of points
* anti-proportional to the convexity from 100% to 50% and
* and 2.25*anti-proportional to the convexity from 50% to 0%
* (0% convexity runs 4.5 times slower than 50%, which run 2 times slower than 100%)
*
* *
*
*
*
* *
* *
*
* 100% 50% 0%
*
*
* The basic algorithm is :
*
* * Computes the convex enveloppe (gift-wrapping algorithm)
* * Then explores in between each of the convex summits to find
* the farthest "inside" point with maximum view angle to the
* 2 adjacents summits. A threshold is set so that the contour
* will not go through all points, but only through points giving
* a certain "smoothness" in the contour.
* * Then explores between new formed summits the same way until no
* new summits can ne found.
*
* The main inconvenient of that algorithm is that, as points were ranked
* relative to their angle form the lower-right point in order to perform
* the gift-wrapping convex algorithm, we have to explore all the remaining
* points each time we want to find if a point lies in between 2 summits, as
* this ranking does not provide a clue as to whether a point lies within the
* geometrical limits of the segment. Furthermore, because of the concavity
* in some parts the angles of close points could be outside the range.
*
* Thus, in order to speed up the process, we derived a more complex algorithm
* which, despite being more complex, provides a sort of ranking improving a lot
* the exploration of remaining points. It uses the basic algorithm, but as the
* final stage of the computation. The basic algorithm is an addition-algorithm,
* the complexified is a deletion-algorithm.
*
* Here is the process of this complexified but faster algorithm :
*
* * First sort the points by their angle to the closest-to-center point
* (this should ensure that we have an enveloppe of the set of point,
* although going through all points)
* * Then place the lower-right point at the first rank of the array,
* keeping the same order. We thus have a contour going through all
* points but starting from the lower-right point.
* * Then finds the convex contour of points by storing the indexes of
* the convex summits, without re-arranging the points.
* * Then finds points whose viewpoint of the 2 adjacent summits is within
* the limits (this step is much faster than the one of the basic algorithm
* as we have to explore only the array of points between the indexes of the
* convex summits. Thus we store only the indexes of points in order not to
* re-arrange the points). At that stage we have a sensible complex contour,
* but not completely satisfactory, as the shape of the whole polygon could
* be elongated, and thus taking the angle from the center of mass could be
* a bit wrong (it's the true contour at an almost 90% confidence level, but
* for very concave parts).
* * Then we re-arrange the points, storing all already found summits at the
* beginning of the array, and moving unkept points at the end.
* * Then we sort the remaining points by their distance to the lower-right
* point.
* * And now we can apply the central computation of the basic algorithm.
* With the previous sorting we have a way of skipping and stopping the
* exploration of the remaining points, thus speeding up a lot this phase.
* Another factor of speed up is also the fact that the previous stage was
* already almost complete, leaving anly a few iterations at that stage.
* * Finally we have to check for extremely thin strips, as the alogithm
* above tries to be fair between each summit, thus it can produce a point
* which belongs less to a (i,i+1) than to (i+1, i+2).
*
*
*/
int MCore_ComputeComplexEnvelope ( MCore_GeoPt *Pts, int N_Pts, int EnvelopeType, MCore_GeoPt **NewPts ) |
