ForHosting KIT · 旅行・地理

点群の凸包

Q: 点の最小数はいくつですか？

最低一つです。 一意点が一つなら一頂点の凸包、二点なら線分、三点以上が非共線なら多角形凸包です。

点(0, 0)、(4, 0)、(4, 3)、(0, 3)、(2, 1)の凸包は最初の4点が作る長方形で、(2, 1)は内側に残ります。点の周りに輪ゴムを張ったときにできる輪郭です。ブラウザで無料で使えます。

無料
ブラウザで動作
登録不要
データは端末の外に出ません

ご利用方法ウェブAPIメールTelegramアプリ近日

凸包とは、有限点集合をすべて含む最小の凸多角形です。板に打った釘に輪ゴムをかけたときの輪郭と同じイメージです。測量、GIS分析、ゲーム開発、計算幾何の学習では、GPS軌跡・建物輪郭・スプライト頂点・教室の (x, y) 点群など、順序のないサンプルからこの輪郭が必要になります。本ツールはAndrewの単調鎖スキャンを実行します。点を水平座標・垂直座標の順に並べ、下側鎖と上側鎖を線形走査で構築し、極端頂点を反時計回りで返します。内部点や辺の途中の共線サンプルは自動で落ちます。平面の x/y または地理の lat/lon を送れます。geo モードでも経度・緯度平面上の平面凸包を計算します。これは都市規模・敷地規模の包絡に用いる通常の局所近似です。

凸包とは何か、単調鎖がどう動くか

平面上の有限点集合に対し、凸包はそれらすべてを含む一意の最小凸集合です。境界は入力の部分集合を頂点とする凸多角形です。外に「飛び出す」極端点はすべて凸包上に現れ、他点の凸結合で書ける点は内部または辺上にあります。

Andrewの単調鎖（単調鎖スキャンとも呼ばれます）は、ソートが支配する O(n log n) 時間でその境界を求めます。x 昇順（x が同値なら y）で並べたあと、アルゴリズムは左から右へ下側鎖を構築し、スタック末尾の三点が常に厳密な左折になるよう保ちます。続けて右から左へ上側鎖を同じ左折判定で構築します。

共有する最左・最右端点を重複させずに両鎖を連結すると、最左（ついで最下）の極端点から始まる反時計回りの完全な凸包が得られます。厳密でない折り判定（外積が 0 以下）により辺上の共線中間点を除き、各辺を最大にします。退化集合も明確に扱います。

一意点が一つなら一頂点の凸包、相異なる二点なら二頂点の線分、三点以上が共線なら両端だけを返します。これは極端点凸包の授業定義に沿い、辺中間サンプルによる面積ゼロの「へこみ」を後段の多角形ツールに持ち込みません。

座標の入れ方と結果の読み方

座標レコードは少なくとも一つ必要です。各レコードは平面作業用の {x, y}、地理サンプル用の {lat, lon}、または二数の配列で構いません。auto では lat/lon キーが地理ラベル、x/y が平面ラベルを選びます。

geo モードは緯度 [−90, 90] と経度 [−180, 180] を検証し、なお lon–lat 平面で凸包を計算します（x = longitude、y = latitude）。任意の precision（0–15、既定 10）は返却座標の小数桁を決めます。凸包の環は開いており、先頭頂点は末尾で繰り返されません。

面積や周長の計算機と組み合わせるのは順序付き環ができた後にしてください。点群の包絡指標が必要なとき、凸包出力はすでに順序付きでそれらのツールに渡せます。

凸包が役立つ場面

地図・物流チームは配送停止点、資産の ping、測量マーカーの凸包を計算し、手デジタイズなしで単純な外側境界を描きます。ゲームとCADのパイプラインはメッシュやスプライト頂点の凸包に衝突プロキシやUI選択枠を縮め、重なり判定を安く保ちます。

データサイエンスのノートブックは、バウンディングボックスが緩すぎ、凹アルファ形状が重すぎるとき、散布図や異常レビューの頑健な外側輪郭として凸包を使います。教室や競技プラットフォームは「極端点を順に列挙せよ」の決定的オラクルを必要とします。純粋 parse 能力は固定精度の安定座標を返し、採点器が浮動小数ノイズで落ちません。

検証失敗は残高を消費しません。点群を一万点未満に保ち、テストで凸包頂点を固定すれば、GIS ETL・エッジワーカー・宿題向けに再現可能な包絡が得られ、自前の完全な幾何ライブラリは不要です。

活用例

GPSサンプルのGIS包絡

現地測量や車両軌跡の順序なし lat/lon を送り、地図オーバーレイや簡易サービスエリア図用の反時計回り凸輪郭を得ます。

ゲーム・CADの衝突プロキシ

メッシュやスプライト頂点の雲を厳密な凸包に縮め、完全な計算幾何ライブラリなしでブロードフェーズ衝突と選択境界を高速化します。

教室での計算幾何チェック

学生に点集合を提出させ、共線・重複の境界例も含め、単調鎖理論に照らして順序付き極端頂点を検証させます。

よくある質問

地理モードは球面測地凸包を使いますか？

いいえ。 geo モードは lat/lon 範囲を検証し、経度・緯度平面上で平面単調鎖を実行します。都市・敷地規模の包絡ではこの局所近似が標準です。全球の測地凸包は対象外です。

共線点は凸包に残りますか？

辺上の中間共線点は除去されます。各凸包辺の極端端点だけが残り、多角形は厳密に凸（180°の折りなし）になります。

点の最小数はいくつですか？

最低一つです。一意点が一つなら一頂点の凸包、二点なら線分、三点以上が非共線なら多角形凸包です。

凸包の頂点はどの順番で返りますか？

反時計回りで、最も左にある点から始まります。左端に複数の点がある場合は、その中で最も下の点からです。輪は閉じずに返すため、最初の頂点は最後に繰り返されません。

一度に何点まで入力できますか？

1回の計算で10000点までです。まったく同じ座標の点は輪郭を作る前にまとめられるため、2回入力した角が凸包に2回現れたり、頂点の数が増えたりすることはありません。

開発者向け — APIアクセス

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

エンドポイント

POSThttps://api.kit.forhosting.com/geo/polygon-convex-hull

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

お使いのスタックから呼び出す

curl -X POST https://api.kit.forhosting.com/geo/polygon-convex-hull \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"points":[{"x":0,"y":0},{"x":4,"y":0},{"x":4,"y":3},{"x":0,"y":3},{"x":2,"y":1}]}'

const res = await fetch("https://api.kit.forhosting.com/geo/polygon-convex-hull", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "points": [
      {
        "x": 0,
        "y": 0
      },
      {
        "x": 4,
        "y": 0
      },
      {
        "x": 4,
        "y": 3
      },
      {
        "x": 0,
        "y": 3
      },
      {
        "x": 2,
        "y": 1
      }
    ]
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/geo/polygon-convex-hull",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "points": [
        {
            "x": 0,
            "y": 0
        },
        {
            "x": 4,
            "y": 0
        },
        {
            "x": 4,
            "y": 3
        },
        {
            "x": 0,
            "y": 3
        },
        {
            "x": 2,
            "y": 1
        }
    ]
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/geo/polygon-convex-hull", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"points":[{"x":0,"y":0},{"x":4,"y":0},{"x":4,"y":3},{"x":0,"y":3},{"x":2,"y":1}]}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"points":[{"x":0,"y":0},{"x":4,"y":0},{"x":4,"y":3},{"x":0,"y":3},{"x":2,"y":1}]}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/geo/polygon-convex-hull", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "points": [
    {
      "x": 0,
      "y": 0
    },
    {
      "x": 4,
      "y": 0
    },
    {
      "x": 4,
      "y": 3
    },
    {
      "x": 0,
      "y": 3
    },
    {
      "x": 2,
      "y": 1
    }
  ]
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "geo.polygon_convex_hull",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

料金

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

エラー

HTTP	コード	意味
`401`	`unauthorized`	APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
`402`	`insufficient_balance`	残高が不足しています。チャージ後に再度お試しください。
`404`	`unknown_type`	指定されたタスクタイプは存在しません。タイプ名を確認してください。
`429`	`rate_limited`	リクエストが多すぎます。しばらく待ってから再度お試しください。

技術的な注記

凸包とは何か、単調鎖がどう動くか

走査前に完全一致の重複座標を潰すため、同じ角の繰り返しが hull_count を膨らませることはありません。

入力契約、座標モード、応答フィールド

必須の points を含む JSON 本体を POST してください。配列には vertices、coordinates、coords の別名も受け付けます。任意の coord_mode は auto（既定）、planar、geo です。成功時の本体には hull（順序付き極端頂点）、hull_count、point_count（入力長）、unique_count（完全重複除去後）、interior_count（凸包上にない一意点）、method が monotone_chain、coord_mode が planar または geo に解決された値、orientation が ccw が含まれます。points 欠落、空配列、非有限数、geo での範囲外の緯度経度、一万点超は invalid_input で失敗し課金されません。

凸包APIが価値を生む場面

実装は純粋 parse ティア A のため、成功した各呼び出しは公開の基本価格 $0.002 で、モデルトークンも外向き通信もありません。

技術的な質問

点集合の凸包はどう計算しますか？

points を {x,y} または {lat,lon} の配列（最低一つ）で POST してください。API は並べ替えて Andrew の単調鎖を実行し、method が monotone_chain の反時計回り凸包頂点を返します。

点群の凸包計算機の料金は？

ブラウザツールは無料です。API は成功した呼び出しごとに前払い KIT 残高から $0.002 を使用します。無効入力は課金されません。

KITの完全なドキュメントを見る →

点群の凸包

無料で実行

凸包とは何か、単調鎖がどう動くか

座標の入れ方と結果の読み方

凸包が役立つ場面

活用例

GPSサンプルのGIS包絡

ゲーム・CADの衝突プロキシ

教室での計算幾何チェック

よくある質問

関連ツール

開発者向け — APIアクセス

エンドポイント

お使いのスタックから呼び出す

リクエスト例

レスポンス例

料金

エラー

技術的な注記

凸包とは何か、単調鎖がどう動くか

入力契約、座標モード、応答フィールド

凸包APIが価値を生む場面

技術的な質問

ありがとう