저번 글에서 원의 세 원의 교점을 이용해 위치를 구할 수 있다는 것까지 알아보았다.

이번에는 실제로 원의 교점을 이용하여 위치를 구해보자.

우선 대표적인 방법으로 두 원이 겹칠​ 때 그 두 교점을 지나는 직선의 방정식을 유도하고, 이 직선의 방정식의 교점을 찾는 방법이 있다.



그림으로 표현하면 위와 같다.

이것을 식으로 유도하려면?

우선 원의 방정식을 생각해 보자. 직교좌표계에서 원의 방정식은 이러한 형태로 나타난다.

$$(x-a)^2+(y-b)^2=r_1^2$$

우리는 세 원이 한 평면에 있음으로 직교좌표계를 설정할 때 한 원은 중심이 원점에, 다른 하나의 원은 한 축 위에, 나머지 한 원은 임의의 한 점에 놓을 수 있다.


(굳이 이렇게 놓는 이유는 계산이 편해지기 때문이다.)

위의 그림처럼 놓고 세 원에 대한 방정식을 세워 보면

$$x^2+y^2=r_1^2$$

$$(x-a)^2+y^2=r_2^2$$

$$ (x-b)^2+(y-c)^2=r_3^2$$

각각의 원에 대해 위의 방정식 3개를 유도할 수 있다.


여기까지 잘 따라왔다면 이제 직선의 방정식을 구해야 한다. 이를 위해서 원의 방정식을 연립하여 교선을 찾아야 한다.

( \(xy\) 직교좌표계 상의 어떠한 원의 방정식을 전개하든 \(x^2\)과 \(y^2\)이 등장한다. 그러므로 원의방정식 두개를 연립하면 \(x^2\)과 \(y^2\)이 소거되어 \(x\)와 \(y\)만으로 이루어진 직선의 방정식만 남게된다)

우선 위의 식들을 전개하면 각각 다음과 같다.


$$x^2+y^2=r_1^2$$

$$x^2-2ax+a^2+y^2=r_2^2$$

$$x^2-2bx+b^2+y^2-2cx+c^2=r_3^2$$


첫번째와 두번째, 두번째와 세번째, 첫번째와 세번째 식을 각각 연립하면 3개의 직선의 방정식을 유도할 수 있다. 이를 유도하면 다음과 같다.


$$2ax-a^2=r_1^2-r_2^2$$

$$(2b-2a)x+2cy-c^2=r_2^2-r_3^2$$

$$2bx-b^2+2cy-c^2=r_1^2-r_3^2$$


첫번째 식을 정리하면 다음과 같이 \(x\)성분만 남는다.


$$x=\frac{r_1^2-r_2^2+a^2}{2a}$$


두 원의 중심이 한 축 위에 있음으로 이 두원의 교점으로 유도된 직선의 방정식은 무조건 그 축에 수직이기 때문이다. 덕분에 수월해진다.

이 후 이론상으로는 세 직선이 한 점에서만 만나기 때문에 두 직선의 교점만 구해도 위치를 구할 수 있다.


그러므로 \(x\)성분에 대해 정리된 식을 2번째 식에 대입하면 우리가 원하는 교점이 도출된다.

대입하면


$$\frac{(2b-2a)(r_1^2-r_2^2+a^2)}{2a}+2cy-c^2=r_2^2-r_3^2$$


이를  \(y\) 성분에 대해 정리하면


$$y=\frac{r_2^2-r_3^2+c^2}{2c}-\frac{(2b-2a)(r_1^2-r_2^2+a^2)}{4ac}$$


그러므로 결과적으로


$$x=\frac{r_1^2-r_2^2+a^2}{2a}$$

$$y=\frac{r_2^2-r_3^2+c^2}{2c}-\frac{(2b-2a)(r_1^2-r_2^2+a^2)}{4ac}$$


위 두 식을 계산하면 우리가 원하는 위치 (\(x\),\(y\))를 얻을 수 있다.

그러면 이 수식을 코드로 바꾸어 보자

이처럼 간단히 파이썬 코드로 바꾸어 구현할 수 있다.

하지만 이렇게 위치를 구해도 끝이 아닌것이 실제 상황에서는 오차가 발생하여 세 원이 한 점에서 만나지 않는 경우가 대부분이다.

다음에는 이 오차를 수학적으로 계산하고, 이를 고려한 위치를 출력하는 것을 해 볼 것이다.


부족한 글 읽어주셔서 감사합니다^^

오타나 오류가 있으면 지적 부탁드립니다ㅎㅎ

  1. 박성아 2016.08.02 12:37

    와..ㅠㅠㅠ 수학식 계산으로 들어가니 이해하기가 너무 어렵네요 ㅠㅠ

    • ghatdev 2016.08.02 13:23 신고

      언뜻 보면 복잡해보이지만 실상은 원의 방정식과 연립방정식이 전부입니다ㅎㅎ 한줄한줄 직접 유도해보시명 쉽게 금방 하실 수 있으세요

  2. Ha 2016.08.28 15:37

    감사합니다 좋은 정보 잘 읽고갑니다.

  3. 너무너무재밋네요 2016.08.29 10:33

    3편이 기대됩니다 ^^

  4. 취준생 2016.09.05 20:11

    글이 너무 좋네요 ~ 다름이 아니라 이번에 제가 졸업논문을 쓰는데 비콘 2개를 이용해서 두개의 신호의 강도에 따라 약한쪽에 어떤 액션을 취하고 또 양쪽을비교해서 약한쪽에 어떤 액션을 취하게 하고 싶은데 도저히 감이 잡히질 않습니다. 조금만 팁을 주시면 안될까요?

    • ghatdev 2016.09.05 21:23 신고

      잘 읽어주셔서 감사합니다ㅎㅎ
      비콘 2개를 이용할 때 어떤 조건인지를 조금더 자세히 설명해 주실 수 있으세요? 열린 공간인지, 장애물은 없는지 말이에요
      혹시 2개 비콘에서 등거리를 유지하며 직선으로 나아가는 액션을 취하시려는 건가요?

  5. kafka 2016.10.18 15:36

    실내 네비게이션을 구현해 보려다 여기 들어왔는데요.
    위의 공식으로 실제 비콘에서 송신된 데이터로 값을 알아내려니 필자님 말씀대로 제대로 한점에서 만나지 않는 것 같습니다. T.T
    3편은 언제쯤 올리실 생긱이신가요?

    혹시 3편에 올리실 내용을 미리 좀 알려주시면 안될런지요 ㅋㅋ

    • ghatdev 2016.12.12 14:07 신고

      늦어서 죄송합니다ㅠ 입시가 이제끝났네요. 빠른시일안에 3편 업로드하도록 하겠습니다!

  6. wskng 2017.02.15 07:56

    정말 좋은 내용이네요.
    혹시 다음 글은 언제 올리실 예정인지 궁금합니다.

  7. 장형민 2017.09.18 11:25

    좋은 글 감사드립니다.

    혹시 다음 편에서 진행 될 오차의 대한 수학적 계산이라는 것이 어떠한 원리로 되는지 간단하게 나마 알수 있을까요??

저번에 R&E 연구를 위해 라즈베리파이를 세팅하는 과정을 올렸었습니다.

그 주제가 iBeacon 을 통한 실내 정밀측위 알고리즘의 개발이라 관련한(연구한) 알고리즘에 대해 몇자 적어봅니다.


iBeacon으로 거리를 측정하는 방법은 우선 이렇습니다. Beacon 발생기(HM-10 사용)를 이용하여 Beacon 신호를 주기적으로 송출하면 BLE(Bluetooth Low Energy) 4.0 이상을 지원하는 다른 기기 및 모듈에서 Beacon 신호를 검색할 수 있습니다. 검색을 하게되면 TxPower(송출신호크기), RSSI(신호의 세기), 모듈의 UUID 등의 정보를 얻을 수 있습니다. (아래 그림 참고)


-57이라고 적혀있는 rssi 값고 -59라고 적혀있는 TxPower 보이시나요? 그리고 제일 위에 있는 이상한 숫자와 영문자 조합이 UUID입니다. 이 UUID로 비콘을 식별할 수 있습니다. 우선, 거리를 측정하기 위해서 필요한것은 rssi와 TxPower 두가지밖에 없습니다. 원리는 간단합니다. 거리가 멀어질수록 신호 세기가 약해져서 rssi값이 낮아지는 것을 이용한 것입니다. 계산하는 공식은 이렇습니다.

RSSI = -10nlogd + TxPower

여기서 d는 거리, n은 전파 손실도와 관련된 값인듯 한데, 장애물이 없는 공간에서는 n=2로 생각하고 계산하면 된다고 합니다.

여기서 얻고싶은 값이 d이기 때문에 수식에 조금 변형이 필요하겠죠?

이항하여 정리하면

d = 10 ^ ((TxPower - RSSI) / (10 * n)) 

을 얻을 수 있습니다.

하지만 여기서 발생하는 문제. 

측정된 값은 스칼라 값으로 방향에 관한 정보가 없고, 송신모듈로부터 얼마나 떨어진것인가 밖에 측정할 수 없게 됩니다.

(참고로 스칼라 값이란 흔히 사용하는 숫자값입니다. 양만을 나타내고 방향에 관한 정보는 없습니다.

반대로 벡터값은 양과 방향에 대한 정보를 모두 가지고 있습니다. 주로 화살표로 표시하구요.)

다시 본론으로 돌아오면, 스칼라값을 이용해서 상대적인 위치를 확인해야 합니다. 즉, 방향을 확인해야 합니다.

처음에는 약간 낯설수도 있는데요, 그럼 이렇게 한번 생각해 봅시다. 송신모듈의 좌표를 (0,0)에 놓고, 측정된 거리를 반지름으로 하여 원을 그려봅시다.

그러면 감이 오시나요? 

네 맞습니다. 바로 원들을 이용하여 방향을 결정합니다. 원들의 교점을 이용하여 유일한 한 점을 결정하는 방법입니다.

하지만 이러려면 원이 여러개 있어야 합니다. 한번 생각해보죠.

원이 두개가 있으면 이론적으로는 교점이 1개(접점) 혹은 2개가 생기게 됩니다. 1개만 생긴다면 좋은데 2개일때가 문제이군요.

그러면 원을 3개를 사용하면? 교점이 2개인 상태에서 원 하나를 더 교차시키면 그중에서도 하나를 찾을 수 있죠.

그러므로 원을 최소 3개를 사용해야 합니다.

아래의 그림을 참고하세요 (밑에는 4개인 상황을 가정했습니다. 하지만 결과적으로는 같은 값을 얻을 수 있습니다.)

위의 그림에서 C1,2,3,4 은 각각 비콘신호 송신모듈의 위치이며 편의상 정사각형의 형태로 배치하였습니다. d1,2,3,4 는 각각의 송신모듈에서부터 측정된 거리입니다. 

같은색으로 그려진 원들이 각 거리를 반지름으로 하여 그린 원의 일부입니다.

그러면 이론적으로 한 점에서 3개의 원이 교차하는 교점이 생깁니다. 바로 저 점의 좌표를 찾으면 저희가 원하는 위치를 알아낼 수 있습니다.

하지만 이건 어디까지나 '이론적'인 부분이구요, 실제에서는 엄청난(?)오차 때문에 한점에서 교차할 일이 거의 없습니다. 

다음 포스팅에서는 한점에서 만나지 않을때 위치를 찾는 방법과 실제로 원의 방정식을 연립하여 위치의 좌표를 가져오는 식을 유도해 보도록 하겠습니다.




  1. 박성아 2016.07.13 10:07

    한점에서 만나지 않을때 위치를 찾는 방법과 실제로 원의 방정식을 연립하여 위치의 좌표를 가져오는 식을 유도해하신다고 하셨는데
    다음 글을 찾을 수 없네요 ㅠ 없는 건가요?

    • ghatdev 2016.07.13 16:48 신고

      시간이 안나서 작성하지 못했습니다.. 사실 읽는분도 많지 않으셔서요ㅠ 조만간 작성하여 올리도록 하겠습니다

  2. 박성아 2016.07.21 09:08

    ghatdev님 감사합니당 ㅎㅎㅎ
    네 꼭 올려주세요 지금 그 글을 기다리고 있거든요!

  3. 윤승환 2017.03.27 10:22

    라즈베리 파이에서 비콘의 신호의 세기를 측정하려고 하는데 가능할까요??

  4. 윤수연 2017.05.09 15:20

    안녕하세요! 라즈베리파이로 비콘 데이터를 받아들여 거리를 측정을 하려는 대학생입니다. 글쓴이님께서 올려주신 어플리케이션 사진은 어떤 app 를 이용한 것인가요? 현재 아직 부품테스트중인데 다른 어플로는 rssi 값만 알수있고 txpower 는 알수가 없어서요!

    • ghatdev 2017.05.09 15:22 신고

      https://play.google.com/store/apps/details?id=com.radiusnetworks.locate
      이 어플이였던 것 같습니다 ㅎㅎ

+ Recent posts