Skip to main content
Solved

Does FME provide a solution for computing the similarity between 2 geometries?


olivier
Contributor
Forum|alt.badge.img+7

Hi,

I would like to know if FME provides a transformer or a logic allowing to derive the similarity between 2 shape geometries. There are concepts such as the Hausdorff distance which could probably be used to some extent for that purpose. This similarity could be for instance expressed as a ratio but I don't know exactly of what yet. Basically I would like to be able to determine if 2 overlapping shapes are similar enough and can be considered as representing the same object in reality.

Thanks in advance for your hints!

Olivier

Best answer by redgeographics

It does now: HausdorffDistanceCalculator

Took a quick stab at it and I think I've got it, but I would welcome any suggestions for improvement.

View original
Did this help you find an answer to your question?

7 replies

philippeb
Enthusiast
Forum|alt.badge.img+17
  • Enthusiast
  • August 14, 2018

Maybe the UpdateDetector or the ChangeDetector?


redgeographics
Celebrity
Forum|alt.badge.img+47
  • Celebrity
  • Best Answer
  • August 15, 2018

It does now: HausdorffDistanceCalculator

Took a quick stab at it and I think I've got it, but I would welcome any suggestions for improvement.


olivier
Contributor
Forum|alt.badge.img+7
  • Author
  • Contributor
  • August 15, 2018
philippeb wrote:

Maybe the UpdateDetector or the ChangeDetector?

Thank you Philippe. However transformers you are suggesting report all geometry differences in the same way: they are just not matching. I need to measure the similarity between 2 shapes which I know upfront are not identical.

 

 


olivier
Contributor
Forum|alt.badge.img+7
  • Author
  • Contributor
  • August 15, 2018

Thank you very much @redgeographics ! I will look at your solution as soon as I can.


olivier
Contributor
Forum|alt.badge.img+7
  • Author
  • Contributor
  • August 16, 2018

Thank you @redgeographics ! I have tested it, runs great and produces expected results. Please note however that it considers only shapepoints for measuring distances.

So if we consider a rectangular polygon and a triangular polygon, the Hausdorff distance as calculated by the transformer will not be the one joining the right tip of the triangle with the mid-point of the greater length of the rectangle (if the triangle plays the role of the base). Maybe a densification option such as the one proposed in ST_FrechetDistance should be integrated. I also don't know conceptually what the expected Hausdorff distance should be between a donut polygon and the polygon occupying the donut hole (whether only the outer ring should be considered).

Now, I am wondering if implementing a similar transformer for the Frechet distance is also within reach with minimal efforts. It turns out the logic I was initially vaguely envisioning boilds down to the discrete Frechet distance. I then noticed that it was already suggested a while ago to Safe Software: https://knowledge.safe.com/idea/55848/calculate-frechet-distance-similarities-between-tw.html

Do you think creating such a transformer is possible? Thank you!


redgeographics
Celebrity
Forum|alt.badge.img+47
olivier wrote:

Thank you @redgeographics ! I have tested it, runs great and produces expected results. Please note however that it considers only shapepoints for measuring distances.

So if we consider a rectangular polygon and a triangular polygon, the Hausdorff distance as calculated by the transformer will not be the one joining the right tip of the triangle with the mid-point of the greater length of the rectangle (if the triangle plays the role of the base). Maybe a densification option such as the one proposed in ST_FrechetDistance should be integrated. I also don't know conceptually what the expected Hausdorff distance should be between a donut polygon and the polygon occupying the donut hole (whether only the outer ring should be considered).

Now, I am wondering if implementing a similar transformer for the Frechet distance is also within reach with minimal efforts. It turns out the logic I was initially vaguely envisioning boilds down to the discrete Frechet distance. I then noticed that it was already suggested a while ago to Safe Software: https://knowledge.safe.com/idea/55848/calculate-frechet-distance-similarities-between-tw.html

Do you think creating such a transformer is possible? Thank you!

In the situation where polygon A is a donut and polygon B completely fills the hole their Hausdorff distance is, most likely, 0 even though they're not similar at all. An additional test could be to compute the Hausdorff distance between the bounding boxes as well as a comparison of the surface areas.

 

 

As for the Discrete Frechet Distance, I've had a quick look and I'm a bit reluctant to say right now whether it would or would not be possible. I'd love to give it a try but I'm going to be too busy the next few days. There's some python examples out there, maybe one of the experts here could implement them.

 


olivier
Contributor
Forum|alt.badge.img+7
  • Author
  • Contributor
  • August 17, 2018
redgeographics wrote:
In the situation where polygon A is a donut and polygon B completely fills the hole their Hausdorff distance is, most likely, 0 even though they're not similar at all. An additional test could be to compute the Hausdorff distance between the bounding boxes as well as a comparison of the surface areas.

 

 

As for the Discrete Frechet Distance, I've had a quick look and I'm a bit reluctant to say right now whether it would or would not be possible. I'd love to give it a try but I'm going to be too busy the next few days. There's some python examples out there, maybe one of the experts here could implement them.

 

Hi @redgeographics

 

I fully understand and as a matter of fact it is not urgent. That being said, adding such logic to the FME Hub would provide additional options to users looking for comparing geometries. In some situations the Discrete Frechet Distance could be more appropriate or elegant than computing buffers and comparing area overlap ratios for instance. But again, it is not urgent and maybe I should also start spending some time on learning how to create new transformers. :-)

Reply


Cookie policy

We use cookies to enhance and personalize your experience. If you accept you agree to our full cookie policy. Learn more about our cookies.

 
Cookie settings