Casco convexo de pontos
Para os pontos (0, 0), (4, 0), (4, 3), (0, 3) e (2, 1), o casco convexo é o retângulo dos quatro primeiros, e (2, 1) fica dentro. É o contorno que um elástico esticado ao redor dos seus pontos formaria. Grátis no seu navegador.
- Grátis
- Funciona no seu navegador
- Sem cadastro
- Seus dados não saem do seu aparelho
Executar grátis
O casco convexo é o menor polígono convexo que contém todos os pontos de um conjunto finito — o contorno de um elástico esticado em torno de pregos em uma tábua. Topógrafos, analistas GIS, desenvolvedores de jogos e estudantes de geometria computacional precisam desse contorno a partir de amostras desordenadas: trilhas GPS, pegadas de edifícios, vértices de sprites ou nuvens de sala de aula de pares (x, y). Esta ferramenta de casco convexo de pontos executa o varredura de cadeia monótona de Andrew: ordena os pontos pela coordenada horizontal e depois pela vertical, constrói as cadeias inferior e superior em passagens lineares e devolve os vértices extremos em sentido anti-horário. Pontos interiores e amostras colineares no meio da aresta saem automaticamente. Você pode enviar pares planos x/y ou pontos geográficos lat/lon; o modo geo ainda calcula um casco planar no plano longitude–latitude, a aproximação local usual para envelopes em escala de cidade ou de sítio.
O que é um casco convexo e como a cadeia monótona funciona
Dado um conjunto finito de pontos no plano, o casco convexo é o único menor conjunto convexo que os contém todos. Seu contorno é um polígono convexo cujos vértices são um subconjunto da entrada: todo ponto extremo que «salta» aparece no casco, e todo ponto que pode ser escrito como combinação convexa de outros fica estritamente dentro ou sobre uma aresta. A cadeia monótona de Andrew (também chamada varredura de cadeia monótona) calcula esse contorno em tempo O(n log n) dominado pela ordenação.
Após ordenar por x crescente (e por y em empates de x), o algoritmo caminha da esquerda para a direita para o casco inferior, mantendo sempre uma virada estrita à esquerda nos três últimos vértices da pilha; depois caminha da direita para a esquerda para o casco superior com o mesmo teste de virada. Concatenar as duas cadeias sem duplicar os extremos compartilhados mais à esquerda e mais à direita produz o casco completo em sentido anti-horário, começando no extremo mais à esquerda (e depois mais baixo).
Um teste de virada não estrito (produto vetorial menor ou igual a zero) remove pontos colineares intermediários para que cada aresta seja maximal. Conjuntos degenerados são tratados com clareza: um único ponto devolve um casco de um vértice; dois pontos distintos, um segmento de dois vértices; três ou mais colineares, apenas os dois extremos. Esse comportamento alinha-se às definições de sala de aula do casco de pontos extremos e evita «entalhes» de área nula em ferramentas de polígono a jusante causados por amostras no meio da aresta.
Onde um contorno convexo ajuda
Equipes de mapeamento e logística calculam o envelope convexo de paradas de entrega, pings de ativos ou marcos de levantamento para desenhar um contorno exterior simples sem digitalizar manualmente. Pipelines de jogos e CAD reduzem proxies de colisão ou caixas de seleção de UI ao casco de vértices de malha ou sprite para que testes de sobreposição permaneçam baratos.
Cadernos de ciência de dados usam o casco como contorno exterior robusto para gráficos de dispersão e revisão de anomalias quando um bounding box é largo demais e uma forma alfa côncava é pesada demais. Plataformas de sala de aula e de competições precisam de um oráculo determinístico para exercícios de «liste os pontos extremos em ordem»; uma capacidade parse pura devolve coordenadas estáveis em precisão fixa para que corretores não falhem por ruído flutuante. Validação com falha não consome saldo.
Mantenha as nuvens abaixo do teto de dez mil pontos, fixe os vértices do casco em testes e obtenha envelopes reproduzíveis para ETL GIS, workers de borda e lições de casa sem montar uma biblioteca completa de geometria própria.
Casos de uso
Envelope GIS de amostras GPS
Envie pings lat/lon desordenados de um levantamento de campo ou da trilha de um veículo e obtenha o contorno convexo anti-horário para sobreposições de mapa e esboços simples de área de serviço.
Proxies de colisão em jogos e CAD
Reduza uma nuvem de vértices de malha ou sprite a um casco convexo estrito para colisão de fase ampla e limites de seleção sem enviar uma biblioteca completa de geometria computacional.
Checagens de geometria computacional em sala
Permita que os alunos enviem conjuntos de pontos e verifiquem os vértices extremos ordenados em relação à teoria da cadeia monótona, incluindo casos colineares e duplicados.
Perguntas frequentes
Como calculo o casco convexo de um conjunto de pontos?
Envie points como array de registros {x,y} ou {lat,lon} (pelo menos um).
O modo geográfico usa um casco geodésico esférico?
Não. O modo geo valida faixas lat/lon e executa uma cadeia monótona planar no plano longitude–latitude. Essa aproximação local é padrão para envelopes em escala de cidade e de sítio; cascos geodésicos globais estão fora do escopo.
Pontos colineares são mantidos no casco?
Pontos colineares intermediários em uma aresta são removidos. Só permanecem os extremos de cada aresta do casco, de modo que o polígono é estritamente convexo (sem viradas de 180°).
Qual é o número mínimo de pontos?
Pelo menos um. Um único ponto devolve um casco de um vértice; dois pontos, um segmento; três ou mais não colineares, um casco poligonal.
Em que ordem os vértices do casco são devolvidos?
Em sentido anti-horário, começando pelo ponto mais à esquerda ou, se vários dividirem essa borda, pelo mais baixo deles. O anel fica aberto: o primeiro vértice não se repete no final.
Ferramentas relacionadas
Para desenvolvedores — acesso via API
Tudo nesta página está disponível via API. Esta seção é para equipes que querem integrar a ferramenta aos próprios sistemas; quem não precisa disso pode simplesmente usar a ferramenta acima.
Endpoint
Autenticação por token Bearer. Um único POST coloca a tarefa na fila; o resultado chega por webhook ou link assinado.
Chame do seu código
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)Exemplo de requisição
{
"points": [
{
"x": 0,
"y": 0
},
{
"x": 4,
"y": 0
},
{
"x": 4,
"y": 3
},
{
"x": 0,
"y": 3
},
{
"x": 2,
"y": 1
}
]
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "geo.polygon_convex_hull",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}A API é assíncrona: cada chamada devolve um task_id na hora. Se preferir polling, consulte o status a até 1 requisição por segundo.
Preço
Preço publicado, sem tokens nem créditos escondidos. Tarefa que falha não é cobrada.
Erros
| HTTP | Código | O que significa |
|---|---|---|
401 | unauthorized | Token ausente ou inválido. Confira o header Authorization. |
402 | insufficient_balance | Saldo insuficiente para esta tarefa. Faça uma recarga e tente de novo. |
404 | unknown_type | Esse tipo de tarefa não existe. Confira o campo type no catálogo. |
429 | rate_limited | Muitas requisições em pouco tempo. Espere um instante e tente de novo. |
Notas técnicas
O que é um casco convexo e como a cadeia monótona funciona
Coordenadas exatamente duplicadas são colapsadas antes das varreduras para que um canto repetido nunca inflacione hull_count.
Contrato de entrada, modos de coordenadas e campos de resposta
Cada registro pode ser {x, y} para trabalho planar, {lat, lon} para amostras geográficas, ou um array de dois números. No modo auto, chaves lat/lon selecionam rotulagem geográfica; x/y selecionam rotulagem planar. O modo geo valida latitude em [−90, 90] e longitude em [−180, 180] e ainda executa o casco no plano lon–lat (x = longitude, y = latitude). A precision opcional (0–15, padrão 10) define as casas decimais das coordenadas devolvidas. O anel do casco é aberto: o primeiro vértice não se repete no final. Envie um corpo JSON com points obrigatório: um array de pelo menos um registro de coordenadas. Os aliases vertices, coordinates e coords são aceitos para o array. O coord_mode opcional é auto (padrão), planar ou geo. Em sucesso o corpo inclui hull (vértices extremos ordenados), hull_count, point_count (comprimento da entrada), unique_count (após remover duplicatas exatas), interior_count (únicos fora do casco), method igual a monotone_chain, coord_mode resolvido para planar ou geo, e orientation igual a ccw. Points ausentes, array vazio, números não finitos, latitudes ou longitudes fora da faixa no modo geo, ou mais de dez mil pontos falham com invalid_input e não são cobrados. Combine este endpoint com calculadoras de área ou perímetro só depois de ter um anel ordenado; a saída do casco já está ordenada e pronta para essas ferramentas quando você precisa das métricas do envelope de uma nuvem de pontos em vez de um polígono digitalizado à mão.
Onde uma API de casco convexo justifica o custo
Como a implementação é parse pura de nível A, cada chamada bem-sucedida custa o preço base publicado US$ 0,002 sem tokens de modelo e sem rede de saída.
Perguntas técnicas
Quanto custa a calculadora de casco convexo de pontos?
A ferramenta do navegador é gratuita. Solicitações API usam saldo KIT pré-pago a US$ 0,002 por chamada bem-sucedida; entrada inválida não é cobrada.