삼각형 안에 3개의 원이 들어가는지 확인 (Check if three circles fit inside a triangle)

문제 설명

삼각형 안에 3개의 원이 들어가는지 확인 (Check if three circles fit inside a triangle)

나는 주어진 지름을 가진 세 개의 원이 서로 겹치지 않고(만지는 것은 괜찮음) 주어진 변의 길이를 가진 삼각형 안에 들어갈 수 있는지 알려주는 프로그램을 작성하는 것에 대해 잠시 생각했습니다.

어떻게 할까요? 그렇게 할 생각?

참조 솔루션

방법 1:

I would try to find some way to enumerate the possible configurations for the three circles, and then test each configuration until one is found where the three circles fit, or until all configurations have been tested and rejected.

(In what follows I am assuming that each circle is known to fit in the triangle by itself. Obviously if any circle fails to fit by itself then it fails to fit in any configuration of three circles.)

Configuration (1) involves putting a circle in each corner of the triangle. (This is the configuration that everyone spotted.)

There are six ways to arrange the circles, and for each arrangement it sufficient to check whether the circles will fit pairwise:

The distance AS₁ is r₁/tan(½α), the distance S₂B is r₂/tan(½β), and the distance S₁S₂ is √((r₁ + r₂)² − (r₁ − r₂)²) = 2√r₁r₂

The circles fit if AS₁ + S₁S₂ + S₂B ≤ AB.

In configuration (2) we place two circles into two of the corners of the triangle, and the third circle between these two and one of the two edges that's not touching both circles:

Figuring out whether these will fit is a bit more complex:

To find the length AS₁ we have to walk round the triangle from corner C via the point T. I'll leave the details of this as an exercise.

There are eighteen ways to arrange the circles into this configuration.

Is there a configuration (3)? I looked but couldn't find one that couldn't be turned into one of the two I gave. For example, if all three circles touch the same side then there's always room to swap the middle circle over to the opposite side, getting configuration (2). However, enumeration of geometric configurations is always tricky and I could easily have missed one.

방법 2:

Just a guess: your problem could be related to that of Appolonius's circles.

I ran into it while trying to fit recursively 3 circles within a 4th one without any intersection for some fractal animation, so it may be worth a try.

You'll find it explained in length at Wolfram (this problem was solved only in 1968): http://mathworld.wolfram.com/ApolloniusProblem.html

방법 3:

this seems to be a tough and interesting problem. Through the solution of the Marble Problem (related to Malfatti's Circles) by Los and Zalgaller in 1994, it might be possible for you to tediously extract a necessary condition for existence of a configuration of three non‑overlapping circles with given radii inside a triangle with prescribed side lengths. If you can place them inside the triangle, the sum of their areas will be at most the maximal possible area for three triangles inside a circle. The Marble Problem is the problem of determining the maximal area of three non‑overlapping circles inside a given triangle. Right now, I can't see that this is also sufficient.

Perhaps it would be worth, as a start, to introduce an ε to the problem and then look for an algortihm that in a finite number of steps, could determine if a configuration which is at most "bad by ε" (defined in some sensible way) exists.

Some of the World's top mathematicians participate regularly at stackoverflow's sibling, mathoverflow.org, so you could try posting this problem over there.

Thanks for posting this.

방법 4:

I think it's sufficient to try all 6 possible permutations (A1 B2 C3, A2 B1 C3, A1 B3 C2, A3 B1 C2, A2 B3 C1, A3 B2 C1). If a circle isn't tangent to two edges of the triangle, then it's placement is suboptimal in some sense and you could make more space for the other two by sliding it into a corner. If it's possible to stick three circles in a triangle without them overlapping then it's probably possible to slide them into the corners (for the case in which they're all jammed against the edges, lift them all up together and rotate by 60 degrees). Of course, this isn't a rigorous proof, but I'm pretty sure it works. Furthermore, I imagine the solution will always be to place the largest circles at the widest angles, because those are the ones that could potentially take up the most central triangle space.

(by faximan、Gareth Rees、MoonSilex、user531602、dspyz)

참조 문서

1. Check if three circles fit inside a triangle (CC BY‑SA 3.0/4.0)