Calculate minimum distance between two arbitrary shape

Question

I have two arbitrary shape. Now I want to calculate the minimum distance between two shapes. Here I am attaching the image

First of all draw part is completed. This Shapes are combination of Arc and line. Now I am facing problem when I am going to calculate the minimum distance between this shapes. Draw this shapes using GWT (java) html5 canvas.

For calculating minimum distance between two shape I have used below code in java but I am not getting any optimized way to do that -

private double calculateMinimumDistance(Coordinate[] coordinates_1, Coordinate[] coordinates_2) { 
    double minDistance = 100000;
    double currentDistance = 0;

    for(int i = 0; i < coordinates_1.length; ++i) {
      for(int j = 0; j < coordinates_2.length; ++j) {
        currentDistance = coordinates_1[i].distanceTo(coordinates_2[j]);
        if(currentDistance < minDistance) {
          minDistance = currentDistance;
        }  
      } 
    }

    return minDistance;
}

coordinates_1 contains the collection of points of shape-1.
coordinates_2 contains the collection of points of shape-2.

Is there any optimized way to calculate the distance between two shape? This shapes are could be any where and any type of shapes.

Instead of calculating the minimum distance between two set of point we can do it in optimized way by calculating distance between line to line or line to arc or arc to arc. In this way we can calculate the minimum distance in optimized way.

You have to make some assumptions first, like on what basis are your program is going to count the distance, eg. their location and for most important how are you going to represent those shapes in a program. — itwasntme, Sep 18 '15 at 07:50
First idea on how to start with that: Define your shapes. How is a shaped represented in Java code? If you can't tell the Java code about your shape, how would you expect it to do anything? — Andreas, Sep 18 '15 at 07:52
possible duplicate of [Finding Minimum Distance between Contours](http://stackoverflow.com/questions/24619645/finding-minimum-distance-between-contours) — Orace, Sep 18 '15 at 08:47
@Marco13 No. This are general shape means this are draw using moveTo, lineTo and arcTo. — Shiladittya Chakraborty, Sep 18 '15 at 09:57
@Marco13 No. This shape are generated in HTML5 canvas (GWT). — Shiladittya Chakraborty, Sep 18 '15 at 12:01

Nyavro · Answer 1 · 2015-09-19T11:59:28.183

The idea is to represent shape as a List of vertexes. Then to find minimum distance between arbitrary shapes I would implement basic algorithm to find distance between two convex shapes. Then split arbitrary shape into non-intersecting set of convex shapes, calculate all distances between distinct pairs and get the minimal distance.

To calculate distance between two convex shapes just iterate through all combinations of vertex pairs, calculate distance and take min value. Of course, this approach will require n^2 operations, so you probably need to optimize it. You can use some simplified forms of shapes: say, represent each shape as 8-10 basic points shape, then on each shape find edge closest to another shape, and then search inside edge's points.

score 1 · Answer 2 · answered Sep 18 '15 at 09:31

1

Consider the two shapes as two distinct sets of points on a plane. Then measure the distance from each point from the first set to every point in second set.

Use a nested for loop for this and measure the distance using the distance formula of coordinate geometry.

Store only the shortest distance and if you want the two points coinciding to the distance.

answered Sep 18 '15 at 09:31

CoderBrain

103
1
11

I followed this steps but its performing slow because polygons are containing lots of points. So is there any optimized way to do that? – Shiladittya Chakraborty Sep 22 '15 at 14:37
You could create 2D array and also store which half of the image the point lies in. Eg the left half or the right half. You can then compare only the left of the right points of the first image with left part of the right image. – CoderBrain Sep 23 '15 at 09:16
I have already created a 2D two array which store all the points for two polygon. But problem is that how to take the half points of the polygon because polygon can be any where. So how to get the exactly nearest half of set of the points? – Shiladittya Chakraborty Sep 24 '15 at 13:24
Store the values in two different arrays. Next for each array find the left most and right most. Then find its average of the two. You can now tell which is the right and left half roughly – CoderBrain Sep 26 '15 at 12:47

David Shaked · Answer 3 · 2015-09-25T13:41:00.560

1

For each point in contour A and contour B, use the distance formula to calculate hypotenuse: hypot=sqrt(xA-xB)^2+(yA-yB)^2)... I'm solving the same problem for an set of N contours, so I'll share my code when I'm done.

edited Sep 25 '15 at 13:41

answered Sep 24 '15 at 20:32

David Shaked

3,171
3
20
31

I have already used this formula for calculating distance between two coordinates. Basically I used two loop to find the minimum distance between two polygon but working slow because two polygon has lots of point. – Shiladittya Chakraborty Sep 25 '15 at 06:05
Ran into the same problem: Workable temporary solution might be to use the geometric center of the objects. Assuming length of objects << distance between objects, the estimation should hold up well. – David Shaked Sep 25 '15 at 06:46
Check out the response to a recent post of mine. http://stackoverflow.com/questions/32773476/opencv-minimum-distance-between-arbitrarily-large-sets-of-contours-python. The code works for an arbitrarily large number of objects e.g., contours A: {A1, A2, A3, ... An} distance to contours B: {B1, B2, B3, ... Bm}. The first bit of code I wrote (for which I haven't yet found a solution) compares distance from edges, but should, in my estimation, be far slower than the geometric centers approach. – David Shaked Sep 25 '15 at 13:19
I am using java and you wrote all the in Python. – Shiladittya Chakraborty Sep 25 '15 at 13:33
The approach can be implemented in many different languages. Let me know if you have any specific questions. – David Shaked Sep 25 '15 at 13:38
What is the use of maskBuilder this function? – Shiladittya Chakraborty Sep 25 '15 at 13:44
Do you mind moving this discussion to my linked post? I can answer those questions for you. – David Shaked Sep 25 '15 at 13:47
http://stackoverflow.com/questions/32773476/opencv-minimum-distance-between-arbitrarily-large-sets-of-contours-python – David Shaked Sep 25 '15 at 13:53
Also, note that I upvoted answers I found helpful on this post. You should do so if you feel inclined to encourage participation on this site. – David Shaked Sep 25 '15 at 14:14
Can you access through Java/GWT all the (x,y) coordinates defining your contours? Also, I hate to ask, but can you post your code? I think I may be Java literate enough to help better with it. – David Shaked Sep 25 '15 at 14:47
I don't have any straight forward code its a big code and lot of things there so I can not post my code here. Sorry for that. If I found any optimized way then I will share the calculation method here. – Shiladittya Chakraborty Sep 26 '15 at 06:17

score 0 · Answer 4 · answered Jul 11 '18 at 16:26

0

Use Imgproc.distanceTransform to find the distances of all points in the image to the first shape. Intersect the result with the second shape. Find the minimum non-zero value in the resulted map and that is your minimum distance.

answered Jul 11 '18 at 16:26

Felix Pîrvan

3
5

Calculate minimum distance between two arbitrary shape

4 Answers4

Linked