Discrete Frechet distance

[Hana]

Dear all,

I am facing some problems relating to calculate distance between two shapes.
I studied Frechet distance and wrote an draft code (not yet tested).

Problem:
Calculates the discrete Frechet distance between curves P and Q.

P and Q are two sets of points that define polygonal curves with rows of vertices (data points) and columns of dimensionality. The points along the curves are taken to be in the order as they appear in P and Q.

Return:
1. discrete Frechet distance
2. two points with the Frechet distance

Here are two points I need your help:

1. How to arrange points in the order as they appear in P and Q.
2. How to find out the points in #2 (with discrete Frechet distance).

I attached a file describing Frechet and algorithm I am using for calculating the distance.

 

[Ratchit]

Dear all,

I am facing some problems relating to calculate distance between two shapes.
I studied Frechet distance and wrote an draft code (not yet tested).

Problem:
Calculates the discrete Frechet distance between curves P and Q.

P and Q are two sets of points that define polygonal curves with rows of vertices (data points) and columns of dimensionality. The points along the curves are taken to be in the order as they appear in P and Q.

Return:
1. discrete Frechet distance
2. two points with the Frechet distance

Here are two points I need your help:

1. How to arrange points in the order as they appear in P and Q.
2. How to find out the points in #2 (with discrete Frechet distance).

I attached a file describing Frechet and algorithm I am using for calculating the distance.

Assuming a distinct set of P and Q points at each time stamp exists, arrange the points P and Q in time order. Next, compute the distance between P and Q at each time stamp. Select the longest distance to be the Frechet distance. From the time of the longest distance, the particular P and Q values can be determined. If the set of P and Q points can vary, then the solution method depends on the type of path taken by the P and Q curve (polygon, arbitrary curve, etc.

Ratch

 

[Hana]

Dear Ratch,
Thank for the idea.
Sorry I am not sure what you mean by time order here. There is no time parameter here, just two sets of points.
Points in these sets are not arranged in order they appear in P and Q respectively.
So my first task is to arrange them in the order that they appear in P and Q.

 

[Ratchit]

Dear Ratch,
Thank for the idea.
Sorry I am not sure what you mean by time order here. There is no time parameter here, just two sets of points.
Points in these sets are not arranged in order they appear in P and Q respectively.
So my first task is to arrange them in the order that they appear in P and Q.

What do those sets of points represent? I thought they represent positions on a P curve and a Q curve. I assume that there are the same number of P points as Q points. Unless the points were all made at the same time, they have an order sequence. If they have an order, then they have an a sequential time stamp that can be assigned to each point.
Perhaps if you made a simple example of say, six points showing the proposed method and solution, I could understand the problem better and suggest a method of solving a larger problem.

Ratch

 

[Hana]

Dear Ratch,
These points represent two shapes. Each set of points is saved into an array but they don't have an order. And two sets can have different number of points. Each point is reprented by coordinates x, y. If you plot them, it represents a shape for example a triangle or something else.
The points in each set is not in order. The first element of array is a point of the shape. The second can be any element of the shape not necessary the point next to the first one.
Sorry I am not at computer now. I will draw some shapes when I go home.
For example, I have two shape one rectangle and a square that need to calculate Frechet distance.
Now I have two arrays. Each array has coordinates of points in a shape in any order.
Goal: calculate Frechet distance.
Note: the number of points in each array is not necessary the same.
Before apply the proposed algorithm, I need to arrange points in each curve in order they appear. However, I don't understand how to do that. Here two shapes appear at the same time. No time element here. In which order should I save points coordinates into each array so that I could apply the algorithm?

 

[Ratchit]

Dear Ratch,
These points represent two shapes. Each set of points is saved into an array but they don't have an order. And two sets can have different number of points. Each point is reprented by coordinates x, y. If you plot them, it represents a shape for example a triangle or something else.
The points in each set is not in order. The first element of array is a point of the shape. The second can be any element of the shape not necessary the point next to the first one.
Sorry I am not at computer now. I will draw some shapes when I go home.
For example, I have two shape one rectangle and a square that need to calculate Frechet distance.
Now I have two arrays. Each array has coordinates of points in a shape in any order.
Goal: calculate Frechet distance.
Note: the number of points in each array is not necessary the same.
Before apply the proposed algorithm, I need to arrange points in each curve in order they appear. However, I don't understand how to do that. Here two shapes appear at the same time. No time element here. In which order should I save points coordinates into each array so that I could apply the algorithm?

OK, first plot the points so you can see the two different shapes. Then select the starting point where the distance between the shapes is the closest. Then calculate the distance from each point of say Q, holding the starting P point stationary. Record the longest distance after completing the circuit around Q. Then advance P by one point and do the same thing. If the longest distance is more, then replace the value from the previous circuit. After all the points from each shape have been calculated, the final value is the Frechet distance. Actually, you don't have to plot and find the smallest distance, but I suggested that in order to show the concept. As long as you know the distance from each point to point, then it is a simple to find the max distance.

Ratch

 

[Hana]

Hi Ratch,
I think there are some problems here.
OK, first plot the points so you can see the two different shapes.
OK, that can be done easily.
Then select the starting point where the distance between the shapes is closest.
OK, but here I have to choose the starting point automatically by an algorithm not by eye.
Then calculate the distance from each point of say Q, holding the starting P point stationary. Record the longest distance after completing the circuit around Q.
OK, no problem here but I don't understand why you choose the longest not shortest one.
Then advance P by one point and do the same thing.
OK, no problem.
If the longest distance is more, then replace the value from the previous circuit.
After all the points from each shape have been calculated, the final value is the Frechet distance.
I think there is a problem here relating to your understanding of Frechet distance.
Why do you choose the longest distance?
Where did you get that algorithm?

 

[Ratchit]

Hi Ratch,
I think there are some problems here.
OK, first plot the points so you can see the two different shapes.
OK, that can be done easily.
Then select the starting point where the distance between the shapes is closest.
OK, but here I have to choose the starting point automatically by an algorithm not by eye.

It doesn't matter where you start. As long as you evaluate the distance of each point from one curve with all the points of the other curve. Even if you duplicate the point distance calculations, it won't change the answer, only make more unnecessary work.

Then calculate the distance from each point of say Q, holding the starting P point stationary. Record the longest distance after completing the circuit around Q.

OK, no problem here but I don't understand why you choose the longest not shortest one.

I was basing my understanding of the Frechet distance by the example given in the PDF material you submitted in post #1. The author(s) describe the distance as the minimum length of a dog leash needed by an owner traveling on one curve and a dog on the other. As you can discern, the minimum length will be the maximum distance from the owner to the dog as both move around their respective curves.

Then advance P by one point and do the same thing.

OK, no problem.
If the longest distance is more, then replace the value from the previous circuit.
After all the points from each shape have been calculated, the final value is the Frechet distance.

I think there is a problem here relating to your understanding of Frechet distance.

Perhaps so. Maybe you can enlighten me on what the real definition of the Frechet distance is.

Why do you choose the longest distance?

Any shorter distance would restrict the travel of the dog and owner due to the lessor lease length.

Where did you get that algorithm?

I invented it myself. It might not be the most efficient way to do the problem. I believe the paper you referenced tries to solve the problem efficiently.

Ratch

 

[Hana]

Hi Ratch,

It doesn't matter where you start. As long as you evaluate the distance of each point from one curve with all the points of the other curve. Even if you duplicate the point distance calculations, it won't change the answer, only make more unnecessary work.

Yes, I see. However, there is a problem relating to your understanding of Frechet distance and your algorithm. I will show it below.

I was basing my understanding of the Frechet distance by the example given in the PDF material you submitted in post #1. The author(s) describe the distance as the minimum length of a dog leash needed by an owner traveling on one curve and a dog on the other. As you can discern, the minimum length will be the maximum distance from the owner to the dog as both move around their respective curves.

The red sentence is not right. Let's see the picture illustrating Frechet distance below.

As marked in the picture the Frechet distance is the minimum leash that allows the owner and the dog to go to the end of each shape with velocity of dog and owner can be any from zero to a very large.
Your algorithm doesn't make sense. Let's take an example of two shapes that are identical and same position. The Frechet distance should be zero but your algorithm results in a big number.

 

[Ratchit]

Hi Ratch,

Yes, I see. However, there is a problem relating to your understanding of Frechet distance and your algorithm. I will show it below.


The red sentence is not right. Let's see the picture illustrating Frechet distance below.
View attachment 93760
View attachment 93759



As marked in the picture the Frechet distance is the minimum leash that allows the owner and the dog to go to the end of each shape with velocity of dog and owner can be any from zero to a very large.
Your algorithm doesn't make sense. Let's take an example of two shapes that are identical and same position. The Frechet distance should be zero but your algorithm results in a big number.

You are adding a stipulation that the dog and owner have to be at a particular place on each of their respective curves. Your previous sentence said that the F distance for your example should be zero, but yet, you marked it on the diagram as being greater than zero. Also you mentioned velocity, but previously said that time was not a factor. If velocity is considered, then time is a factor, and there should be a set of points of the P curve that corresponds to each point on the Q curve and vice versa. So I am still unsure of the definition of the F distance.

Ratch

 

[Hana]

You are adding a stipulation that the dog and owner have to be at a particular place on each of their respective curves.

Yes, because here is discrete Frechet distance, the place is points along these shapes.

Your previous sentence said that the F distance for your example should be zero, but yet, you marked it on the diagram as being greater than zero.

Well, I am talking for two cases.
1. With two shape at the same position, size and same shape, the Frechet distance should be zero.
2. For the case in the picture, the Frechet is not zero.

Also you mentioned velocity, but previously said that time was not a factor. If velocity is considered, then time is a factor, and there should be a set of points of the P curve that corresponds to each point on the Q curve and vice versa.

I mentioned velocity only for the sake of solving the problem easier.
Here is the definition of Frechet distance fro Wikipedia:
https://en.wikipedia.org/wiki/Fréchet_distance

The Fréchet distance between two curves is the minimum length of a leash required to connect a dog and its owner, constrained on two separate paths, as they walk without backtracking along their respective curves from one endpoint to the other. The definition is symmetric with respect to the two curves. Imagine a dog walking along one curve and the dog's owner walking along the other curve, connected by a leash. Both walk continuously along their respective curve from the prescribed start point to the prescribed end point of the curve. Both may vary their speed, and even stop, at arbitrary positions and for arbitrarily long periods of time. However, neither can backtrack. The Fréchet distance between the two curves is the length of the shortest leash (not the shortest leash that is sufficient for all walks, but the shortest leash of all the leashes) that is sufficient for traversing both curves in this manner.

 

[Ratchit]

Yes, because here is discrete Frechet distance, the place is points along these shapes.

Well, I am talking for two cases.
1. With two shape at the same position, size and same shape, the Frechet distance should be zero.
2. For the case in the picture, the Frechet is not zero.

I mentioned velocity only for the sake of solving the problem easier.
Here is the definition of Frechet distance fro Wikipedia:
https://en.wikipedia.org/wiki/Fréchet_distance

The Fréchet distance between two curves is the minimum length of a leash required to connect a dog and its owner, constrained on two separate paths, as they walk without backtracking along their respective curves from one endpoint to the other. The definition is symmetric with respect to the two curves. Imagine a dog walking along one curve and the dog's owner walking along the other curve, connected by a leash. Both walk continuously along their respective curve from the prescribed start point to the prescribed end point of the curve. Both may vary their speed, and even stop, at arbitrary positions and for arbitrarily long periods of time. However, neither can backtrack. The Fréchet distance between the two curves is the length of the shortest leash (not the shortest leash that is sufficient for all walks, but the shortest leash of all the leashes) that is sufficient for traversing both curves in this manner.

Ah, I think I understand now. You want the length of the shortest leash when both man and dog cooperate during their travel to make it so. So here is how I would do it. Start with any point occupied by the man. Calculate and find the distance between the man's current position and every point on the dog's position. Select and store the shortest distance. Do the same thing with the man's next position. If the shortest distance is larger than the previous stored distance, store that distance. Keep repeating the process until the walk is completed. When finished, the stored value should be the F value you want. It does not matter whether you compare the dog with the man or the man with the dog. Even the order of the points can be mixed up as long as you determine the shortest distance between every point and opposite path and select the largest value of those distances to be the F distance. Let me know if that is what you want. If you are into programming, you can see that there are some shortcuts you can use. For instance, if the distances between the points and the opposite path are less that a previous calculation, that distance can be immediately ignored.

Ratch

 

[Hana]

Morning, Ratch.

What you understand and your algorithm are actually Hausdorff distance. I already did it but Hausdorff distance not very good at comparing the dissimilarity between two shapes. So I studied discrete Frechet distance to solve this problem.
Please see here for detail about the week point of Hausdorff distance:
1. http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2002/StephanePelletier/
2. http://math.stackexchange.com/questions/764286/hausdorff-and-fréchet-distances

Now my problems are as mentioned in the first post.
With two shapes, how can I take them into each array in the order they appear.

 

[Ratchit]

Morning, Ratch.

What you understand and your algorithm are actually Hausdorff distance. I already did it but Hausdorff distance not very good at comparing the dissimilarity between two shapes. So I studied discrete Frechet distance to solve this problem.
Please see here for detail about the week point of Hausdorff distance:
1. http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2002/StephanePelletier/
2. http://math.stackexchange.com/questions/764286/hausdorff-and-fréchet-distances

Now my problems are as mentioned in the first post.
With two shapes, how can I take them into each array in the order they appear.

View attachment 93765

From the attached diagram, and assuming that the man points are linked to the dog points, sort the "x" values of the man points from lowest to highest. Then put the man points into the man array in that order. Similarly, put the linked corresponding dog points into the dog array. Then you can process the points. It is easy to determine the consecutive dog points that are higher like 3,4,5,6,7 and which are lower like 1,2 and 8,9,10.

Ratch

 

[Hana]

Hi, I don't see how would you do that here. The algorithm should work for an arbitrary shape.

 

[Ratchit]

Hi, I don't see how would you do that here. The algorithm should work for an arbitrary shape.

I see. I don't have the time to study and assimilate all the references you provided, and figure out how to solve that problem. Perhaps someone else can. I will keep it in mind, and if I am inspired, I will communicate with you again.

Ratch

 

[Hana]

OK, I appreciate your patience and help. I will read more for solution.

 

[Ratchit]

OK, I appreciate your patience and help. I will read more for solution.

Thanks, I looked over the references you sent. It appears that there are several variations of the F distances. Also the study of F distances can be very specialized and involved. Since I, and probably all others in this forum, are not students of comparative geometry, we will not be able to help you much. I suggest you present your questions to a mathematics forum, because this is a forum for electrical topics. I found a link to a Mathworks program that is supposed to calculate the F distances between two curves. Perhaps that program can assist you if you do not already know about it. https://www.mathworks.com/matlabcentral/fileexchange/41956-frechet-distance-calculator

Ratch