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.
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.
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?
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.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.
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.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.
Perhaps so. Maybe you can enlighten me on what the real definition of the Frechet distance is.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?
Yes, I see. However, there is a problem relating to your understanding of Frechet distance and your algorithm. I will show it below.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.
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.
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.
Yes, because here is discrete Frechet distance, the place is points along these shapes.You are adding a stipulation that the dog and owner have to be at a particular place on each of their respective curves.
Well, I am talking for two cases.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.
I mentioned velocity only for the sake of solving the problem easier.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.
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.
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
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.Hi, I don't see how would you do that here. The algorithm should work for an arbitrary shape.
OK, I appreciate your patience and help. I will read more for solution.
We use cookies and similar technologies for the following purposes:
Do you accept cookies and these technologies?
We use cookies and similar technologies for the following purposes:
Do you accept cookies and these technologies?