AN ALGORITHM FOR DETERMINING CONCAVE VERTEX OF OBJECT BASED ON VECTOR PRODUCT

Concave vertex of an object is an important parameter for analyzing an object’s shape. A new algorithm for searching concave vertex is proposed in this paper. The new algorithm requires tracking the border firstly,and then uses sampling border to obtain coordinates sequence of discrete boundary points. Each sampling point of the discrete border is determined to be either concave or convex according to the value of vector product. Two inflexions can be searched by the change of concavo-convex trend. The region between two inflexions is defined as concave area. The values of distance are calculated between all boundary points on the concave area and a straight line connected by two inflexions. The boundary point corresponding to the greatest distances is max concave vertex,or the object’s concave vertex. Experimental results have proved that the new algorithm can extract the max concave vertexes of an object accurately and reliably.

Concave vertex of an object is an important parameter for analyzing an object＇s shape. A new algorithm for searching concave vertex is proposed in this paper. The new algorithm requires tracking the border firstly, and then uses sampling border to obtain coordinates sequence of discrete boundary points. Each sampling point of the discrete border is determined to be either concave or convex according to the value of vector product. Two inflexions can be searched by the change of concavo-eonvex trend. The region between two inflexions is defined as concave area. The values of distance are calculated between all boundary points on the concave area and a straight line connected by two inflexions. The boundary point corresponding to the greatest distances is max concave vertex, or the objeet＇s concave vertex. Experimental results have proved that the new algorithm can extract the max concave vertexes of an object accurately and reliably.