How to find closest points between two convex hull in MATLAB?

Question

In part of an Artificial Neural Network matlab code, I want to find nearest points of two convex polygons.

I saw

dsearchn(X,T,XI)

command's description here, but that finds closest points between two sets of points, and polygons (like convexs) have infinites points.

So can you suggest any way/idea?

Notice: I'm using MATLAB 2014a. I have the coordinate of each convex's vertex point.

There's a function to this this on File Exchange that will do this. As noted in the comments, the complexity of this function is O(mn) while the minimum complexity is known to be O(logm + logn) (see Edelsbrunner). — beaker
@beaker yes, I've found this function before you tell and with a little code changing, that gave my answer. Thank you for your time. — pooria haddad

gsamaras gsamaras · Accepted Answer · 2016-07-03T16:34:34

If you are not happy with what is provided by dsearchn, then, If I were you, I would do one of two following:

Find Nearest Neighbours on the vertices (for example which vertex of polygon A is the NN of a given vertex of polygon B).
Pick a random point inside polygon A (you may want to compute the convex hull of A, but you may skip that and take into account only the vertices you know already). That random point is the query. Find an NN of that point from the vertices of polygon B.

You may want to ask in Software recommendations for more.

Edit:

Another approach is this:

Create a representative dataset of polygon A. Set the size of the dataset yourself and fill it with samples of points that lie inside the polygon. Choose them uniformly randomly inside the polygon.

Then take a point of polygon B (either a vertex or a random point inside polygon B) and that's the query point, for which you will seek Nearest Neighbour(s) inside the representative dataset of polygon A.

Of course that's just an approximation, but I can't think of something else now.

Notice that you can of course do the same for polygon B.

How to find closest points between two convex hull in MATLAB?

2 Answers