2016-12-15

分簇+触摸屏精确定位Algo

问题分析

现代生活，触摸屏手机已是非常普及，可以说人手一只。我们只要用手指轻轻在屏幕上触碰，手机就能感应到我们的操作，并且执行相应的功能。那么，手机是怎样定位到触摸点的呢？这个就是我们今天要讨论算法所重点要模拟解决的问题。

解决的思路是：把我们手机屏幕看成一个二维坐标系，横竖分别分为X轴和Y轴，这样我们就可以通过坐标值来定位某个点。知道如何表示触摸点还不足够，我们怎样确定定位点呢？这就涉及到硬件了，每个屏幕TP上面都会有电容感应器，当你用手触摸某个地方时，那里对应的电容值便会升高。多点触摸，就会有多个地方电容值升高。

但问题又来了，我们触摸的地方往往是一个区域，因为我们手指有一定的宽度。所以，我们需要按电容值的高低对屏幕坐标先进行分簇，即局部最大值聚类。对np_values搜索局部极大值。如果只找到一个局部最大值，则有一个单点触摸。如果找到多个局部极大值，则有多个接触。

分簇完成，接下来就好办了，可以通过计算电容加权平均值得出每个分簇的精确定位。

分簇实现

下面是一个屏幕电容值的模拟数据表：

可以看到，表中所给电容值横轴方向、纵轴方向都有所变化，当触摸屏某个位置有触摸动作发生时，该处电容值会升高，由此可判断出，上图中有两处按压。

可得到两个序列：

x轴序列是{0，6，137，84，9，4}，Y轴序列是{1，4，45，25，2，2，13，52，58，15，4}。

分簇要找的就是所给序列的突峰区间，如果用索引（坐标索引从0开始计）来表示的话，上述x轴序列有一个分簇区间[0，5]，y轴序列有两个分簇区间[0，4]和[5，10]。图示如下：

最后，我们需要输出分簇结果：x轴分簇[0，5]，y轴分簇[0，4]、[5，10]。

分簇算法实现的难点在哪儿呢？我觉得应该是如何判断一个分簇的开始与结束。为了实现判断，我在遍历索引的时候，加上了标志变量（如果当前电容值比它的前者大的话，标志变量置1，否则置2）。然后在输出分簇的时候，我们就可以通过判断标志变量，准确输出区间。主要实现代码如下：

printf("x方向上的增减标志位如下:\n");
   for (i = 0; i < x-1; i++)
   {
       if(xx[i] <= xx[i+1])
       {
           xTag[i] = 1;
       }
       if(xx[i] >= xx[i+1])
       {
           xTag[i] = 2;
           bianjieX++;
       }
       printf("%d", xTag[i]);
   }
       printf("y方向上的增减标志位如下:\n");
   for (j = 0; j < y-1; j++)
   {
       if(yy[j] <= yy[j+1])
       {
           yTag[j] = 1;
       }
       //根据区间来看，前后相等的情况应该赋值为2，所以上面小于情况的=号可下可不下
       if(yy[j] >= yy[j+1])
       {
           yTag[j] = 2;
           bianjieY++;
       }
       printf("%d", yTag[j]);
   }
   //定义二维数组用于存储区间的索引
   for (i = 0; i < x-1; i++) {
    if(xTag[i] == 2 && xTag[i+1] == 1) {
        xsection[count++][1] = i;
        xsection[count][0] = i+1;
    }
}
if(xsection[count][1] == 0) {
    xsection[count][1] = x-1;
}
while(i < x-1) {
    printf("\nX方向上的分簇[%d, %d]", xsection[i][0], xsection[i][1]);
}

精确定位实现

有了分簇结果，我们就可以借用分簇结果来计算每个分簇对应的精确坐标值了。计算的过程：首先需要找到分簇区间中每个索引对应的电容值，把电容值累加到变量CapacitanceALL，然后将每个索引值*对应电容值累加到变量AddAll，最后就可通过AddAll / CapacitanceALL来计算出每个分簇的精确值location。

主要实现代码如下：

while(i < x-1) {
	    printf("\nX方向上的分簇[%d, %d]", xsection[i][0], xsection[i][1]);
	    AddAll = 0.0,CapacitanceALL = 0.0;
	    location = 0.0;
	    //输出此段分簇区间的精确定位
	    for(m = xsection[i][0];m <= xsection[i][1];m++)
	    {
	        AddAll = AddAll + xx[m] * m;
	        CapacitanceALL = CapacitanceALL + xx[m];
	    }
	    location = AddAll / CapacitanceALL;
        printf("  此段分簇区间的加权精确x值是：%.3f",location);
	    i++;
	    if(xsection[i][0] == 0) {
	        break;
	    }
	}