背景:
系统中有N个不规则的几何图形,每个图形都是由5个坐标(X1,Y1),(X2,Y2),(X3,Y3),(X4,Y4),(X5,Y5)构成的,每个图形的形状都是唯一的
需求:
随意输入一组图形的5个坐标数据,如何检测这个图形是否在系统中已经存在,或者说匹配度达到系统预设的值(如99.99%匹配)?
需求挖掘
能不能对系统给定的原点进行特征提取,生成一串唯一的给geohash值,通过比较hash值之间的距离就可以得出相似度?
不管位置或大小,只要形状类似就是匹配成功
<?php
/**
* Created by PhpStorm.
* User: liuchao
* Date: 16/5/9
* Time: 22:16
*/
$point = array(
'x' => array(10, 20, 30, 40, 50),
'y' => array(5, 6, 7, 8, 9)
);
$points = array(
array(
'x' => array(10, 20, 30, 40, 50),
'y' => array(5, 6, 7, 8, 9)
),
array(
'x' => array(10, 30, 30, 40, 50),
'y' => array(5, 6, 7, 8, 9)
),
array(
'x' => array(10, 50, 30, 40, 50),
'y' => array(5, 6, 7, 8, 9)
),
array(
'x' => array(10, 60, 30, 40, 50),
'y' => array(5, 6, 7, 8, 9)
),
array(
'x' => array(10, 70, 30, 40, 50),
'y' => array(5, 6, 7, 8, 9)
)
);
function Cosine($point)
{
$cosine_arr = array();
$size = count($point['x']);
for ($i = 0; $i < $size; $i++) {
$cosine_arr[$i] = $point['y'][$i] * $point['x'][$i]/sqrt($point['x'][$i]*$point['x'][$i]+$point['y'][$i]*$point['y'][$i]);
}
return $cosine_arr;
}
$cosine = Cosine($point);
foreach($points as $p){
$cosine_p = Cosine($p);
$top = $bottom_x = $bottom_y = 0.00;
$size = count($cosine);
for ($i = 0; $i < $size; $i++) {
$top += $cosine[$i] * $cosine_p[$i];
$bottom_x += $cosine[$i] * $cosine[$i];
$bottom_y += $cosine_p[$i] * $cosine_p[$i];
}
echo $top / (sqrt($bottom_x) * sqrt($bottom_y));
echo "\r\n";
}
转换成树,就可以快速查找是否重复
多维空间中两个向量夹角的余弦公式
利用这个就可以求出相似度
首先相似度的定义很多,你需要先确定一下
然后,你是要检测形状吗?那么不同位置上,形状一样的算一个形状吗?
所有这些都会影响到最终算法的选择