5个坐标点构成的几何图形，如何进行特征提取与匹配？

Question

背景：

系统中有N个不规则的几何图形，每个图形都是由5个坐标(X1,Y1),(X2,Y2),(X3,Y3),(X4,Y4),(X5,Y5)构成的，每个图形的形状都是唯一的

需求：

随意输入一组图形的5个坐标数据，如何检测这个图形是否在系统中已经存在，或者说匹配度达到系统预设的值(如99.99%匹配)？

需求挖掘

能不能对系统给定的原点进行特征提取，生成一串唯一的给geohash值，通过比较hash值之间的距离就可以得出相似度?

不管位置或大小，只要形状类似就是匹配成功

Answer 1

<?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";
}

Answer 2

• 首先相似度的定义很多，你需要先确定一下

• 然后，你是要检测形状吗？那么不同位置上，形状一样的算一个形状吗？

所有这些都会影响到最终算法的选择

Answer 3

转换成树，就可以快速查找是否重复

多维空间中两个向量夹角的余弦公式
利用这个就可以求出相似度