Movatterモバイル変換

[0]ホーム
URL:

はてなブックマークアプリ

サクサク読めて、
アプリ限定の機能も多数！

アプリで開く

はてなブックマーク

  • はてなブックマーク
  • テクノロジー
  • 毎秒現在地を使った最近傍探索をしたい - Mobile Factory Tech Blog
  • Twitterでシェア
  • Facebookでシェア

気に入った記事をブックマーク

  • 気に入った記事を保存できます
    保存した記事の一覧は、はてなブックマークで確認・編集ができます
  • 記事を読んだ感想やメモを書き残せます
  • 非公開でブックマークすることもできます
適切な情報に変更

エントリーの編集

loading...

エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。

タイトルガイドライン

このページのオーナーなので以下のアクションを実行できます

タイトル、本文などの情報を
再取得することができます
コメントを非表示にできますコメント表示の設定

ブックマークしました

ここにツイート内容が記載されますhttps://b.hatena.ne.jp/URLはspanで囲んでください

Twitterで共有

ONにすると、次回以降このダイアログを飛ばしてTwitterに遷移します

149usersがブックマークコメント16

    ガイドラインをご確認の上、良識あるコメントにご協力ください

    0/0
    入力したタグを追加

    現在プライベートモードです設定を変更する

    おすすめタグタグについて

      よく使うタグ

        毎秒現在地を使った最近傍探索をしたい - Mobile Factory Tech Blog

        ガイドラインをご確認の上、良識あるコメントにご協力ください

        0/0
        入力したタグを追加

        現在プライベートモードです設定を変更する

        おすすめタグタグについて

          よく使うタグ

            はてなブックマーク

            はてなブックマークで
            関心をシェアしよう

            みんなの興味と感想が集まることで
            新しい発見や、深堀りがもっと楽しく

            ユーザー登録

            アカウントをお持ちの方はログインページへ

            記事へのコメント16件

            • 注目コメント
            • 新着コメント
            オーナーコメントを固定しています
            dorapon2000
            オーナー 書きました！

            その他
            mcq
            基準点(0,0)/現在地(-1,0)/駅A(2.5,0)/駅B(-4,0)っていう例を考えると、Aの距離3.5、Bの距離3.0で最寄り駅はBなのに、赤円の半径3.0内に存在するAを間違って出力しそう＼11/22に修正されたけど、←の例でAは赤円内だけど青円外になる

              その他
              shunkeen
              事前計算のO(N)のとこ、ソート処理入れたらO(N log N)じゃない？まあ、移動したところで 、ほとんど整列済みだからリストを再利用して、挿入ソートすれば瞬殺かもだが。あとはpartial sortで誤魔化しても問題ない気もする。

                その他
                razokulover
                高速に移動する点P問題

                  その他
                  fashi
                  「ChatGPT に聞くと KD-Tree という初めて聞くデータ構造で時間計算量を落とす方法を紹介されました」「コードレビューもメンテナンスも大変です」理論が確立されてて実装例も多くある方式の方がメンテしやすい気がするな

                  その他
                  napsucks
                  SPFとかで道のり最短の駅を探すのかと思ったが、円とか半径とかでてくるので直線距離の最短を出す話だった。

                    その他
                    tohima
                    事前計算をブロック式にして現在地を(0,0)として(-1,-1)から(1,1)の範囲の駅を事前計算して、毎秒を(0,0)にいるか判定したほうが効率良さそうな気がするけど、実際と感覚って結構違うから違うんだろなw

                      その他
                      オーナーコメントを固定しています
                      dorapon2000
                      オーナーdorapon2000 書きました！

                      2024/11/21リンク

                      その他
                      sanze
                      このアルゴリズムでは緯度経度をそのまま使っているので距離の大小比較ができず、正しく最近傍点を求められていません。 地球は丸いので円を描くなどの平面幾何をそのまま使うことができません。

                        その他
                        bellonieta
                        事前にボロノイ図作って、クライアントに持たせちゃダメなんかな

                          その他
                          takilog
                          KDTreeをはじめてきく…？真っ先に出てくると思うんだけどマジ？

                            その他
                            fashi
                            fashi「ChatGPT に聞くと KD-Tree という初めて聞くデータ構造で時間計算量を落とす方法を紹介されました」「コードレビューもメンテナンスも大変です」理論が確立されてて実装例も多くある方式の方がメンテしやすい気がするな

                            2024/11/22リンク

                            その他
                            tomaho
                            たとえば10kmメッシュの配列に駅座標入れて現在地メッシュの近傍を探索する、みたいなシンプル手法は何がだめなんだろう。事前計算も省けるのに。

                              その他
                              misshiki
                              “毎秒最寄り駅を計算するロジックをどのように実現しているのか”

                              その他
                              oooooo4150
                              そういえば最近patoさんのPR広告読んでない気がする。読みたい

                                その他
                                toaruR
                                青円内に駅がある想定か

                                  その他
                                  napsucks
                                  napsucksSPFとかで道のり最短の駅を探すのかと思ったが、円とか半径とかでてくるので直線距離の最短を出す話だった。

                                    2024/11/22リンク

                                    その他
                                    shunkeen
                                    shunkeen事前計算のO(N)のとこ、ソート処理入れたらO(N log N)じゃない？まあ、移動したところで 、ほとんど整列済みだからリストを再利用して、挿入ソートすれば瞬殺かもだが。あとはpartial sortで誤魔化しても問題ない気もする。

                                      2024/11/22リンク

                                      その他
                                      mcq
                                      mcq基準点(0,0)/現在地(-1,0)/駅A(2.5,0)/駅B(-4,0)っていう例を考えると、Aの距離3.5、Bの距離3.0で最寄り駅はBなのに、赤円の半径3.0内に存在するAを間違って出力しそう＼11/22に修正されたけど、←の例でAは赤円内だけど青円外になる

                                        2024/11/22リンク

                                        その他
                                        razokulover
                                        razokulover高速に移動する点P問題

                                          2024/11/22リンク

                                          その他
                                          tohima
                                          tohima事前計算をブロック式にして現在地を(0,0)として(-1,-1)から(1,1)の範囲の駅を事前計算して、毎秒を(0,0)にいるか判定したほうが効率良さそうな気がするけど、実際と感覚って結構違うから違うんだろなw

                                            2024/11/22リンク

                                            その他
                                            mohno
                                            「ステーションメモリーズ！（駅メモ！）10 周年」←駅メモはインストールしたことあるけど、舞台めぐりと併用が大変でやめちゃったんだよな……。こっちの方が長生きだったか。

                                            その他
                                            sumijk
                                            どちらもO(N)だが動的に探索範囲を更新して平均(最悪)計算量を抑えるという話だと思うが移動速度が電車程度だとするとベースラインをN_max〜全国の駅数とするのはフェアなのか？上位1割くらいしか更新されないよね

                                              その他

                                              注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています

                                              リンクを埋め込む

                                              以下のコードをコピーしてサイトに埋め込むことができます

                                              プレビュー
                                              アプリのスクリーンショット
                                              いまの話題をアプリでチェック！
                                              • バナー広告なし
                                              • ミュート機能あり
                                              • ダークモード搭載
                                              アプリをダウンロード

                                              関連記事

                                                usersに達しました！

                                                さんが1番目にブックマークした記事「毎秒現在地を使っ...」が注目されています。

                                                気持ちをシェアしよう

                                                ツイートする

                                                毎秒現在地を使った最近傍探索をしたい - Mobile Factory Tech Blog

                                                こんにちは。駅メモエンジニアの id:dorapon2000 です。 約半年前の 6 月 1 日にステーションメモリーズ...こんにちは。駅メモエンジニアの id:dorapon2000 です。 約半年前の 6 月 1 日にステーションメモリーズ！（駅メモ！）10 周年を記念してタイムラインと地図の切替機能をリリースしました。大変好評を頂いておりとても嬉しいです。 今回は、その機能の中で毎秒最寄り駅を計算するロジックをどのように実現しているのかについてお話します。様々なスペックの端末で遊ばれているため、可能な限りリソースを節約するような工夫をしました。堅い言い方をすれば、過去の計算情報を使った最近傍探索アルゴリズムを実装しました。 記事中のサンプルコードはTypeScript で記述しています。 2024/11/22 追記：はてなブックマークでのご指摘ありがとうございます。 ご指摘をいただいた「事前計算の時間計算量」と「基準点と現在地の距離が近すぎるとき」の説明部分を修正しております。 誤：事前計算を O(N

                                                ブックマークしたユーザー

                                                • techtech05212024/12/30techtech0521
                                                • kkeisuke2024/12/07kkeisuke
                                                • sanze2024/11/29sanze
                                                • kat212024/11/27kat21
                                                • t_f_m2024/11/27t_f_m
                                                • W53SA2024/11/27W53SA
                                                • techno_salmon2024/11/25techno_salmon
                                                • nna7742024/11/25nna774
                                                • utgwkk2024/11/24utgwkk
                                                • yamamototarou465422024/11/23yamamototarou46542
                                                • tasukuchan2024/11/23tasukuchan
                                                • s_ryuuki2024/11/23s_ryuuki
                                                • yoshikoyamazil2024/11/23yoshikoyamazil
                                                • bellonieta2024/11/23bellonieta
                                                • ayaniimi2132024/11/22ayaniimi213
                                                • kyama652024/11/22kyama65
                                                • kazre2024/11/22kazre
                                                • se7en12024/11/22se7en1
                                                すべてのユーザーの
                                                詳細を表示します

                                                ブックマークしたすべてのユーザー

                                                同じサイトの新着

                                                同じサイトの新着をもっと読む

                                                いま人気の記事

                                                いま人気の記事をもっと読む

                                                いま人気の記事 - テクノロジー

                                                いま人気の記事 - テクノロジーをもっと読む

                                                新着記事 - テクノロジー

                                                新着記事 - テクノロジーをもっと読む

                                                同時期にブックマークされた記事

                                                いま人気の記事 - 企業メディア

                                                企業メディアをもっと読む

                                                はてなブックマーク

                                                公式Twitter

                                                はてなのサービス

                                                • App Storeからダウンロード
                                                • Google Playで手に入れよう
                                                Copyright © 2005-2025Hatena. All Rights Reserved.
                                                設定を変更しましたx
                                                [8]ページ先頭
                                                ©2009-2025 Movatter.jp