How to find the largest rectangle inside a parallelogram?

I do not have a complete solution, but perhaps a piece of the puzzle. Assuming the parallel sides were running perfectly horizontal I was able to achieve promising results using the following method:
BoundingBoxAccumulator on the parallelogram, Clip the bounding box with the parallelogram (resulting in 2 separate triangles), Deaggregate the triangles and then create a separate bounding box for each of the triangles, finally clip the parallelogram with the triangle bounding boxes.

I think possible next steps to get this to work for you would be set up a method to rotate the parallelogram, perform the above steps, and then rotate the results back to the original parallelogram’s rotation.

Hi @jennychu There’s no easy way to do this now with FME; you might want to up-vote this idea Find Largest Internal Rectangle from a Polygon

@jennychu Do you have a sample of data that I can test with?

Also, I have some steps for you to try to get the rotation. With a test parallelogram I created similar to yours, I was able to use a CenterPointReplacer to get the centroid, and then a NeighborFinder to get the angle to the closest point on the parallelogram. With my understanding of how the angles and rotation work, I decided to subtract 180 from the result (if it was over 180) to get the angle < 180, and then subtracted that angle from 90 to calculate the rotation degree. I used a Rotator before the steps I listed above, and then again afterwards to rotate the resulting rectangle to match the input parallelogram. I am not sure how well this will work with parallelograms of various height x width ratios though, it certainly needs more testing.

hey @liamfez thank you for the reply and inspiration!

In the attachment, you'll find a small demo to test.

They are actually a series of parking spaces, and I want to get the actual “parked car area”. Unfortunately, they are not perfect parallelograms. That led to too many vertices. I tried to simplify them with a “generalizer,” but it did not work so well.

I think these approximate parallelograms could first be framed using the BoundingBoxAccumulator, then use the parallel sides from the box to replace the original sides. After that, try to remove two separate triangles. I only need to get as approximate results as possible instead of very precise ones.

In other words, I want to remove the two triangles outside these approximate parallelograms to make them resemble rectangles more closely.

hey @DanAtSafe thank you for the reply! Yes, I checked this link before, and I still want to find a way to get as approximate results as possible instead of very precise ones. 

regards,

Jenny

@jennychu I took a look at your sample data, and I noticed that the parking spaces on either end have some spikes that you would want to remove before generalizing. What I have done is sampled the middle parking space. My thinking is that since you just want an approximate result, and these spaces should all be similar, to just sample the middle one and only work on one. Once I got the middle one, I did use a Generalizer (Douglas with a tolerance of 0.5 seemed enough). And then I did have to add another step to the initial process. I added a spike remover between the set of clippers, that helped to clean up the triangles and gave me results that should be close enough for you.

@liamfez , your methods sound workable and helpful, I will check and run it and then let you know what’s looks like with my dataset.

Thank you again for your time!

liamfez wrote:

Here is my workspace (2021) with what I think should be a good enough solution for you to get an approximate area.

 

 

@liamfez I just tested your workspace, and yes, I even just changed some tiny details and then it works very well with all my data.

Thank you very much again! I have stuck here for a while, and finally, I could move forward. :)