지도 좌표 거리순 정렬

antz의 이미지

지도 좌표를 거리순으로 정렬하려고 합니다.

"피타고라스의 정리"에서
a^2 + b^2 = c^2 를 사용해서,

X좌표와 Y좌표 각각의 제곱에 합을 구해서 정렬하려합니다.

헌데, 지도 좌표 숫자 크기가 커서 제곱하면 long형을 벗어 나는 군요.

Quote:
19975> (lX,lY)=(572427,373915), pIdxDoubleTemp->lDist=-685264350
19976> (lX,lY)=(971032,470015), pIdxDoubleTemp->lDist=-147712707
19977> (lX,lY)=(892017,853492), pIdxDoubleTemp->lDist=-605377707
19978> (lX,lY)=(533507,1097770), pIdxDoubleTemp->lDist=-657585103
19979> (lX,lY)=(429080,1107977), pIdxDoubleTemp->lDist=-1352302395
19980> (lX,lY)=(981100,466580), pIdxDoubleTemp->lDist=-890853400
19981> (lX,lY)=(495045,1127072), pIdxDoubleTemp->lDist=-795052419
19982> (lX,lY)=(659462,1218602), pIdxDoubleTemp->lDist=-6978544
19983> (lX,lY)=(709030,1072307), pIdxDoubleTemp->lDist=-1032192351
19984> (lX,lY)=(851630,1295547), pIdxDoubleTemp->lDist=-1508942991
19985> (lX,lY)=(510052,1179735), pIdxDoubleTemp->lDist=-1668491571
19986> (lX,lY)=(398120,180727), pIdxDoubleTemp->lDist=-2123322131
19987> (lX,lY)=(506515,903360), pIdxDoubleTemp->lDist=-1153286475
19988> (lX,lY)=(371310,361720), pIdxDoubleTemp->lDist=-1885125548
19989> (lX,lY)=(496520,907117), pIdxDoubleTemp->lDist=-81567155
19990> (lX,lY)=(496520,907117), pIdxDoubleTemp->lDist=-81567155
19991> (lX,lY)=(493815,1131430), pIdxDoubleTemp->lDist=-758795655
19992> (lX,lY)=(391125,130990), pIdxDoubleTemp->lDist=-1671988215
19993> (lX,lY)=(586892,787530), pIdxDoubleTemp->lDist=-1749409276

지도 좌표의 최소 X, Y 값을 각각 X, Y에 뺀다음 제곱하면 숫자가 작아질것은 같은데, 그래도 클것같습니다.

좋은 방법있으면, 답변 부탁드립니다.

다시한번 설명하자면, 거리 정렬하기 위한 숫자를 구하는겁니다.

체스맨의 이미지

간단하게는 64비트 정수를 사용하면 됩니다.
32비트 컴파일러인 경우 gcc 에서 long long, vc 에서 __int64 입니다.
그리고...

Orion Project : http://orionids.org

체스맨의 이미지

long 만으로 해결하고자 한다면, 실제로 테스트는 안해봤지만,
다음 방법이 있지 않나 생각되네요. 일단, 연산 시간은 좀 더 들겠구요.

거리로 정렬하고자 한다면 결국 실제 거리값은 중요하지 않고,
두 거리의 차가 0보다 큰가 같은가, 작은가만 판별하면 됩니다.

그렇다면 좌표 (a,b) , (c,d) 에 대해
다음 값의 부호를 판별하면 되죠.
a^2 + b^2 - (c^2+d^2) > 0 ( 이라면 (a,b)>(c,d) )

정리하면
(a-c)/(b+d) > - (b-d)/(a+c)
(다른 식으로도 정리될 수 있지만, 0보다 작은 값으로 나누는 경우
부등호 방향이 바뀌어야 하므로, 좌표값이 모두 0보다 크다는 전제하에서는
위의 유일한 식을 사용해도 될 것 같네요. 좌표가 정수라면 몇몇
case 를 고려해야 할 겁니다.)

일단 나눗셈이 행해지기 때문에, 값을 몫과 나머지(%이용)로 나눌 수 있으므로,
크기 판별이 가능하지 않나 생각됩니다.

물론 이 방법도 덧셈 오버플로우 가능성은 있으나, 그런 상황은 잘 일어나지
않을 겁니다.

아, 그리고 분모가 0인 경우는 특수 경우로, 좌표가 동일 축상에 존재하는
경우이므로 판별이 쉬워질 겁니다.

Orion Project : http://orionids.org

cdpark의 이미지

나눗셈까지 동원할거라면 그냥 double에서 계산하는게... :(

체스맨의 이미지

이 방법도 문제는 있네요...
대부분 저 식이면 분모가 큰 경우가 되고, 나눈 값은 1 이하의 값이 나올텐데,
나머지 연산만가지고는 예를 들어, 2/7과 1/4 중 어떤 값이 큰지는
알 수 없겠군요.... 이 해결이 필요하겠습니다. -_-

double 로 캐스팅하는 방법을 쓰자면 어차피 제곱할 때 그렇게 해도 되는
문제구요.

Orion Project : http://orionids.org

체스맨의 이미지

cdpark wrote:
나눗셈까지 동원할거라면 그냥 double에서 계산하는게... :(

예, 64비트 정수가 아니라면 그게 좋을 것 같습니다. :)
긴정수만으로 해결할 수 없을지 생각해봤었는데 아주 복잡해지고
잘 해결도 안되는군요. 하지만 double 로는 long 의 제곱에 대한
정확도를 완전히 보장할 수는 없는 문제가 있습니다.

Orion Project : http://orionids.org

antz의 이미지

답변 감사드립니다. :D

우선 long long 형을 해보고 있습니다. 데이터가 많아서 컨버트 하는데 시간이 오래걸리네요. double도 잘 생각해 보겠습니다.

건수가 많기 때문에 시간이 오래걸리면 안될것 같습니다.

속도에는 long long 제곱과 double 제곱 중 차이가 있나요?

체스맨의 이미지

곱셈만 따지면 double 곱셈이 훨씬 빠릅니다. 64비트 정수 곱셈은
32비트 컴파일러에서 대개 내부적으로 함수 호출이 이루어지기 때문입니다.

하지만, double 을 이용하면, 큰값의 곱셈에서 정확도를 보장할 수 없는
문제가 일단 있구요.
정수->실수 변환이 수반되므로, 심각하게 큰 차이를 보이진 않을 겁니다.
그런데 정수->실수변환은 FPU 지원 사항이므로, 속도면에서는
double을 쓰는 게 유리하다고 봐야겠죠.

Orion Project : http://orionids.org

catzbi의 이미지

예전에 long type -> string 으로 저장하고 프레임( plus : 9 digit ) ( minus : 9 digit ) , ( multiply : 4digit ) , ( divide : 4digit ) 으로 해서
사치기연산을 해본적이 있습니당.
( duron 1Ghz : 3??mB , max digits : 20 만 ?)

Quote:
frame traits : [+-][1-9]..... [ real part ] . [0-9]......... [ float part ]

frame operation : . 소수점을 기준으로 해서 더해줍니다.

long -> string 변환은 ltoa () , atol () 을 이용했슴다.


carry, borrow 도 생각하셔야 되구요.
소수점 계산은 float 로 하셔도 될것같습니다.

Quote:
곱셈은 123 ( 1st Operand ) x 12 ( 2nd Operand ) [ initial pow 1: step deciaml )
= sequential ( 123 x 2 ,&pow) // >> lsfhit by 1 of 12
+ sequential ( 123 x 1 ,&pow) // >> lshift by 1 of 2 -> sentinel 0 ;
end

추신>

지도 좌표의 순수거리 재는 방식은 아닙니다만,

cubic tiles 개수로 지도의 큐빅의 개수에 의해서 거리의 우위 비교하는 방안도.

중심에서 동심원내에 원내부를 큐빅으로 구역할당을 합니다.

반지름을 점점 늘려갑니다. 큐빅에 걸친 좌표값은 입력후 제거합니다.

fibonacci의 이미지

1차 정렬에서 자료를 부동소수점 형태로 바꾸어 대강 정렬하고

2차 정렬에서 크기가 비슷해 부동소수점의 데이터 형으로 비교가 어려운것들을 정렬하는 알고리즘도 있습니다.

No Pain, No Gain.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.