00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #include "subdivSegment.h"
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 static int
00026 binary_search(double val, const double *array, int bot, int top) {
00027 if (top < bot) {
00028 return bot;
00029 }
00030 int mid = (bot + top)/2;
00031
00032 if (array[mid] < val) {
00033 return binary_search(val, array, mid+1, top);
00034 } else {
00035 return binary_search(val, array, bot, mid-1);
00036 }
00037 }
00038
00039
00040
00041
00042
00043
00044
00045 void SubdivSegment::
00046 cut() {
00047 int c;
00048 double ct = get_score();
00049
00050 _cuts.erase(_cuts.begin(), _cuts.end());
00051 int last = _f;
00052 for (c = 1; c < _num_cuts+1; c++) {
00053 double val = (double)c * ct / (double)(_num_cuts+1) + _cint[_f];
00054 int i = binary_search(val, _cint, _f, _t);
00055 if (i != last && i < _t) {
00056 _cuts.push_back(i);
00057 }
00058 last = i;
00059 }
00060
00061 while ((int)_cuts.size() < _num_cuts) {
00062
00063 int last = _f;
00064 int mc = -1;
00065 int mv = 0;
00066 for (c = 0; c < (int)_cuts.size(); c++) {
00067 if (mc == -1 || _cuts[c] - last > mv) {
00068 mc = c;
00069 mv = _cuts[c] - last;
00070 }
00071 last = _cuts[c];
00072 }
00073
00074 if (mc==-1) {
00075
00076 return;
00077 }
00078 if (mc==0) {
00079 _cuts.insert(_cuts.begin() + mc, (_cuts[mc] + _f) / 2);
00080 } else {
00081 _cuts.insert(_cuts.begin() + mc, (_cuts[mc] + _cuts[mc-1]) / 2);
00082 }
00083 }
00084 }
00085