I'm looking for the numerically fastest algorithm to determine coordinates & radius of the largest inscribed circle of a convex quadrilateral.
I've found plenty of input on approaches for general polygons, but all of them rather numerically slow. I'm curious if there's any much simpler & faster approach for plain old convex quads.
The most promising approach I found was described in here, based on the circle touching three sides of the quad. However, I'm not quite sure how to actually calculate this. My initial approach was to:
- Check all combinations of 3 adjacent sides
- Calculate the intersection of the two bisecting lines
- Assume that intersection point is the center of the incircle
- Check if the circle is "valid" (doesn't extend beyond the fourth side), and get the largest circle found that way
But that doesn't work, e.g. for the quad (-1,0), (1,0), (2,1), (-2,1). The incircle's center must be at y=0.5, but none of the angle bisecting lines intersect there (unless I'm somehow miscalculating these)
Is there any reasonably easy & fast way to do this?
Edit: My math skills aren't good enough to prove this, but my intuition is: My approach above works IF no pair of the 3 adjacent sides I'm checking are parallel.
If on the other hand I'm processing 3 sides, and the two opposite ones of them are indeed parallel: I can assume the diameter of the inscribed circle will be the distance between those two parallel lines. To find the center of the circle, I could get the mid point of the third (non parallel) side, and add a vector in the opposite direction of the first line with length sqrt(2)*circle radius. I'd probably still have to check if the resulting circle fully lies within the quad.
For my case above, that seems to give the correct result, but I can't really prove if this is generally correct