Files
SHiNE-server/shine-UI/js/pages/network/communities.js
T

661 lines
31 KiB
JavaScript
Raw Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
import { t } from '../../i18n/index.js';
// Группы людей на карте связей: «Компании» (кто с кем знаком), «Интересы» (кто на что подписан)
// и «Города» (кто где живёт).
//
// Компании ищутся по знакомствам между людьми первого круга – из их собственных графов связей.
// Метод Лувена (максимум модулярности) собирает вместе тех, кто плотно знаком между собой:
// школа кунг-фу знакома внутри себя, коллеги – внутри себя, а между ними редкие мостики.
// Всё считается на устройстве за миллисекунды и детерминированно: те же данные – та же картина.
//
// Названия: своё (дал владелец карты) → по каналу, который читает большинство компании и
// заметно реже остальные → по самому связанному человеку («Илья С. и др.»).
//
// Раскладка «островами»: внутри компании люди стоят сотами (ровный шаг, подписи не
// налезают), в середине – самые связанные, знакомые – рядом. Острова упаковываются вокруг
// человека в центре: крупные ближе, связанные между собой – по соседству.
export const REST_GROUP = 'rest';
export const ISLAND_COLORS = 8; // цветов подложек; сами цвета – в движке карты (зависят от темы)
// Вес знакомства по виду связи: близкие сближают сильнее контактов.
const TIE_WEIGHT = { close_friend: 3, family: 3, friend: 2, contact: 1 };
const RELATION_RANK = { close_friend: 0, family: 1, friend: 2, contact: 3 };
export function tieWeight(type, mutual = true) {
return (TIE_WEIGHT[type] || 1) * (mutual ? 1 : 0.6);
}
function byName(a, b) {
return String(a.name || a.id).localeCompare(String(b.name || b.id), 'ru');
}
// Короткое имя для подписей: «Илья С.»; без фамилии – как есть.
export function shortPersonName(person) {
const first = String(person?.firstName || '').trim();
const last = String(person?.lastName || '').trim();
const text = first && last ? `${first} ${last[0]}.` : String(person?.name || person?.login || person?.id || '');
return text.length > 18 ? `${text.slice(0, 17)}…` : text;
}
function jaccard(a, b) {
if (!a.size || !b.size) return 0;
let common = 0;
const [small, big] = a.size <= b.size ? [a, b] : [b, a];
small.forEach((id) => { if (big.has(id)) common += 1; });
return common / (a.size + b.size - common);
}
// --- Сообщества -----------------------------------------------------------------------------
/**
* Метод Лувена: узлы переходят в соседнее сообщество, пока это повышает модулярность,
* затем сообщества сворачиваются в узлы, и всё повторяется уровнем выше.
* @param {string[]} ids
* @param {Map<string, Map<string, number>>} weights – веса знакомств (можно несимметрично)
* @returns {string[][]} сообщества (одиночки – тоже сообщества)
*/
export function detectCommunities(ids, weights, { resolution = 1 } = {}) {
const order = [...new Set(ids)].sort();
if (!order.length) return [];
const index = new Map(order.map((id, i) => [id, i]));
// Неориентированный граф: у пары – наибольший из весов в обе стороны.
const pairs = new Map();
weights.forEach((near, a) => {
const i = index.get(a);
if (i === undefined) return;
near.forEach((w, b) => {
const j = index.get(b);
if (j === undefined || j === i || !(w > 0)) return;
const key = i < j ? i * order.length + j : j * order.length + i;
pairs.set(key, Math.max(pairs.get(key) || 0, w));
});
});
let adj = order.map(() => new Map());
let loops = new Float64Array(order.length);
let total = 0;
pairs.forEach((w, key) => {
const i = Math.floor(key / order.length);
const j = key % order.length;
adj[i].set(j, w);
adj[j].set(i, w);
total += w;
});
if (total <= 0) return order.map((id) => [id]);
let membership = order.map((_, i) => i); // исходный человек → узел текущего уровня
for (let level = 0; level < 16; level += 1) {
const n = adj.length;
const degree = new Float64Array(n);
for (let i = 0; i < n; i += 1) {
let k = 2 * loops[i];
adj[i].forEach((w) => { k += w; });
degree[i] = k;
}
const m2 = 2 * total;
const comm = Int32Array.from({ length: n }, (_, i) => i);
const tot = Float64Array.from(degree);
let improved = false;
for (let pass = 0; pass < 40; pass += 1) {
let moved = 0;
for (let i = 0; i < n; i += 1) {
const own = comm[i];
const links = new Map();
adj[i].forEach((w, j) => { links.set(comm[j], (links.get(comm[j]) || 0) + w); });
tot[own] -= degree[i];
let best = own;
let bestGain = (links.get(own) || 0) - (resolution * tot[own] * degree[i]) / m2;
links.forEach((w, c) => {
if (c === own) return;
const gain = w - (resolution * tot[c] * degree[i]) / m2;
if (gain > bestGain + 1e-12) { best = c; bestGain = gain; }
else if (best !== own && Math.abs(gain - bestGain) <= 1e-12 && c < best) best = c;
});
tot[best] += degree[i];
if (best !== own) { comm[i] = best; moved += 1; }
}
if (!moved) break;
improved = true;
}
if (!improved) break;
const renum = new Map();
for (let i = 0; i < n; i += 1) if (!renum.has(comm[i])) renum.set(comm[i], renum.size);
if (renum.size === n) break;
const nextAdj = Array.from({ length: renum.size }, () => new Map());
const nextLoops = new Float64Array(renum.size);
for (let i = 0; i < n; i += 1) {
const ci = renum.get(comm[i]);
nextLoops[ci] += loops[i];
adj[i].forEach((w, j) => {
const cj = renum.get(comm[j]);
if (ci === cj) {
if (i < j) nextLoops[ci] += w;
} else {
nextAdj[ci].set(cj, (nextAdj[ci].get(cj) || 0) + w);
}
});
}
membership = membership.map((node) => renum.get(comm[node]));
adj = nextAdj;
loops = nextLoops;
}
const groups = new Map();
membership.forEach((c, i) => {
if (!groups.has(c)) groups.set(c, []);
groups.get(c).push(order[i]);
});
return [...groups.values()];
}
// Самый связанный внутри группы: по нему компания узнаётся («Илья С. и др.»).
// При равенстве – тот, кто ближе вам, затем по имени.
function hubOf(members, weights, byId) {
const inside = new Set(members);
const rows = members.map((id) => {
let score = 0;
weights.get(id)?.forEach((w, other) => { if (inside.has(other)) score += w; });
const person = byId.get(id) || { id };
return { id, score, rank: RELATION_RANK[person.relationType] ?? 9, person };
});
rows.sort((a, b) => b.score - a.score || a.rank - b.rank || byName(a.person, b.person));
return rows[0]?.id || '';
}
// «Илья С. и др.»: число людей подпись покажет отдельно («· 26»), как у названных компаний.
function autoLabel(members, hubId, byId) {
const hub = shortPersonName(byId.get(hubId) || { id: hubId });
return members.length > 1 ? t('screens.communities.text_013', { value1: hub }) : hub;
}
/**
* Названия по подпискам: канал, который читает заметная часть группы и заметно чаще,
* чем все остальные. Каждый канал – одной группе (с самым сильным перевесом).
* @returns {Map<string, string>} id группы → ключ канала
*/
function channelNames(groups, subs, everyone) {
const out = new Map();
if (!subs?.of?.size) return out;
const total = new Map();
let known = 0;
for (const id of everyone) {
const list = subs.of.get(id);
if (!list) continue;
known += 1;
list.forEach((key) => total.set(key, (total.get(key) || 0) + 1));
}
if (!known) return out;
const candidates = [];
for (const group of groups) {
const n = group.members.length;
if (n < 3) continue;
const counts = new Map();
group.members.forEach((id) => subs.of.get(id)?.forEach((key) => counts.set(key, (counts.get(key) || 0) + 1)));
counts.forEach((count, key) => {
const share = count / n;
const lift = share / ((total.get(key) || count) / known);
if (count >= 3 && share >= 0.34 && lift >= 1.3) candidates.push({ group: group.id, key, score: count * lift });
});
}
candidates.sort((a, b) => b.score - a.score || (a.key < b.key ? -1 : 1));
const usedChannels = new Set();
for (const row of candidates) {
if (out.has(row.group) || usedChannels.has(row.key)) continue;
out.set(row.group, row.key);
usedChannels.add(row.key);
}
return out;
}
// Цвета островов: свои (сохранённые) остаются; остальным – свободный цвет, а когда свободных
// нет – тот, что у наименее связанных с этой группой (на карте связанные стоят рядом,
// и одинаковые цвета соседей сливались бы).
function assignColors(groups, savedColors, weights = null) {
const used = new Map(); // цвет → группы
const take = (group, color) => {
group.color = color;
if (!used.has(color)) used.set(color, []);
used.get(color).push(group);
};
groups.forEach((group) => {
const color = savedColors.get(group.id);
if (group.kind !== 'rest' && Number.isInteger(color) && color >= 0 && color < ISLAND_COLORS && !used.has(color)) take(group, color);
});
const affinity = (g1, g2) => {
if (!weights) return 0;
const inside = new Set(g2.members);
let sum = 0;
g1.members.forEach((id) => weights.get(id)?.forEach((w, other) => { if (inside.has(other)) sum += w; }));
return sum;
};
groups.forEach((group) => {
if (group.kind === 'rest' || Number.isInteger(group.color)) return;
// Свой цвет у группы – от её id (у компании это её самый связанный человек): перенос
// одного человека или новые знакомые не перекрашивают всю карту.
const own = hashColor(group.id);
let pick = -1;
for (let k = 0; k < ISLAND_COLORS; k += 1) {
const c = (own + k) % ISLAND_COLORS;
if (!used.has(c)) { pick = c; break; }
}
if (pick < 0) {
let best = Infinity;
for (let c = 0; c < ISLAND_COLORS; c += 1) {
const clash = used.get(c).reduce((sum, other) => sum + 1 + affinity(group, other), 0);
if (clash < best) { best = clash; pick = c; }
}
}
take(group, pick);
});
}
function hashColor(text) {
let h = 2166136261;
for (let i = 0; i < text.length; i += 1) {
h ^= text.charCodeAt(i);
h = Math.imul(h, 16777619);
}
return (h >>> 0) % ISLAND_COLORS;
}
function sortGroups(groups) {
return groups.sort((a, b) => (a.kind === 'rest') - (b.kind === 'rest')
|| b.members.length - a.members.length
|| String(a.label).localeCompare(String(b.label), 'ru'));
}
/**
* Компании первого круга.
* @param {Object} o
* @param {Array<{id:string, name:string, firstName?:string, lastName?:string, relationType:string}>} o.people
* @param {Map<string, Map<string, number>>} o.weights – веса знакомств
* @param {{ groups: Array<{id:string, name:string, members:string[], color?:number}>, assign: Map<string,string> }} o.saved
* @param {{ of: Map<string,string[]>, info: Map<string,{name:string}> } | null} [o.subs] – подписки для названий
* @returns {{ groups: Array<object>, byPerson: Map<string,string>, snapshots: Array<{id:string, members:string[]}> }}
*/
export function buildCompanies({ people, weights, saved, subs = null }) {
const byId = new Map(people.map((person) => [person.id, person]));
const ids = people.map((person) => person.id);
const assign = new Map([...(saved?.assign || new Map())].filter(([id]) => byId.has(id)));
const savedGroups = (saved?.groups || []).filter((group) => group && group.id);
const savedById = new Map(savedGroups.map((group) => [group.id, group]));
const communities = detectCommunities(ids, weights)
.map((members) => members.filter((id) => !assign.has(id)))
.filter((members) => members.length);
// Сохранённые компании узнаются по составу: наибольшее совпадение, не меньше трети.
const scores = [];
communities.forEach((members, ci) => {
const set = new Set(members);
savedGroups.forEach((group) => {
const score = jaccard(set, new Set((group.members || []).filter((id) => byId.has(id) && !assign.has(id))));
if (score >= 0.3) scores.push({ ci, id: group.id, score });
});
});
scores.sort((a, b) => b.score - a.score || a.ci - b.ci || (a.id < b.id ? -1 : 1));
const matchedCommunity = new Map();
const matchedSaved = new Set();
for (const row of scores) {
if (matchedCommunity.has(row.ci) || matchedSaved.has(row.id)) continue;
matchedCommunity.set(row.ci, row.id);
matchedSaved.add(row.id);
}
const groups = new Map();
const rest = [];
communities.forEach((members, ci) => {
const savedId = matchedCommunity.get(ci);
if (savedId) {
groups.set(savedId, { id: savedId, kind: 'company', members: [...members], saved: true });
} else if (members.length >= 3) {
const hub = hubOf(members, weights, byId);
const id = `a:${hub}`;
groups.set(id, { id, kind: 'company', members: [...members], saved: false });
} else {
rest.push(...members);
}
});
// Перенесённые вручную – в свою компанию (даже если её состав сейчас не узнан).
assign.forEach((groupId, personId) => {
if (groupId === REST_GROUP) { rest.push(personId); return; }
let group = groups.get(groupId);
if (!group && savedById.has(groupId)) {
group = { id: groupId, kind: 'company', members: [], saved: true };
groups.set(groupId, group);
}
if (group) group.members.push(personId);
else rest.push(personId);
});
const list = [...groups.values()].filter((group) => group.members.length);
const named = channelNames(list.filter((group) => !savedById.get(group.id)?.name), subs, ids);
for (const group of list) {
group.members.sort((a, b) => byName(byId.get(a) || { id: a }, byId.get(b) || { id: b }));
group.hubId = hubOf(group.members, weights, byId);
const own = savedById.get(group.id);
group.name = String(own?.name || '').trim();
group.channel = named.get(group.id) || '';
group.autoLabel = group.channel ? (subs.info.get(group.channel)?.name || '') : '';
if (!group.autoLabel) group.autoLabel = autoLabel(group.members, group.hubId, byId);
group.label = group.name || group.autoLabel;
// Коротко – для подписи на мелкой карте: без «и др.».
group.shortLabel = group.name || (group.channel ? group.autoLabel : shortPersonName(byId.get(group.hubId) || { id: group.hubId }));
}
if (rest.length) {
rest.sort((a, b) => byName(byId.get(a) || { id: a }, byId.get(b) || { id: b }));
list.push({ id: REST_GROUP, kind: 'rest', members: rest, name: '', autoLabel: t('screens.communities.text_005'), label: t('screens.communities.text_001'), shortLabel: t('screens.communities.text_006'), hubId: '' });
}
sortGroups(list);
assignColors(list, new Map(savedGroups.map((group) => [group.id, group.color])), weights);
// Состав узнанных компаний обновляется, чтобы их узнавать и дальше, когда люди прибавятся.
const snapshots = [];
list.forEach((group) => {
const own = savedById.get(group.id);
if (!own) return;
const now = group.members.filter((id) => !assign.has(id));
if (jaccard(new Set(now), new Set(own.members || [])) < 0.85 || own.color !== group.color) {
snapshots.push({ id: group.id, members: now, color: group.color });
}
});
const byPerson = new Map();
list.forEach((group) => group.members.forEach((id) => byPerson.set(id, group.id)));
return { groups: list, byPerson, snapshots };
}
/**
* Интересы: люди собираются у каналов, на которые подписаны. Каждый – у одного канала, самого
* «своего»: из читаемых им каналов – того, что реже всего встречается среди этих людей (общие
* «Новости района» читают все, а «Ушу» – только свои). Канал, у которого так набирается
* меньше minSize человек, группой не считается – его читатели переходят к следующему.
* @param {Object} o
* @param {Array<{id:string, name:string}>} o.people
* @param {{ of: Map<string,string[]>, info: Map<string,{name:string}> }} o.subs
*/
export function buildInterestGroups({ people, subs }) {
const byId = new Map(people.map((person) => [person.id, person]));
const followers = new Map();
people.forEach((person) => subs?.of?.get(person.id)?.forEach((key) => {
if (!followers.has(key)) followers.set(key, []);
followers.get(key).push(person.id);
}));
const minSize = people.length > 30 ? 3 : 2;
const eligible = new Set([...followers.entries()].filter(([, ids]) => ids.length >= minSize).map(([key]) => key));
let assignment = new Map();
for (let round = 0; round < 12; round += 1) {
assignment = new Map();
for (const person of people) {
let best = '';
for (const key of subs?.of?.get(person.id) || []) {
if (!eligible.has(key)) continue;
const n = followers.get(key).length;
if (!best || n < followers.get(best).length || (n === followers.get(best).length && key < best)) best = key;
}
if (best) assignment.set(person.id, best);
}
const sizes = new Map();
assignment.forEach((key) => sizes.set(key, (sizes.get(key) || 0) + 1));
let dropped = false;
eligible.forEach((key) => {
if ((sizes.get(key) || 0) < minSize) { eligible.delete(key); dropped = true; }
});
if (!dropped) break;
}
const byChannel = new Map();
assignment.forEach((key, id) => {
if (!byChannel.has(key)) byChannel.set(key, []);
byChannel.get(key).push(id);
});
const list = [...byChannel.entries()].map(([key, members]) => {
const name = String(subs.info.get(key)?.name || key);
return { id: `c:${key}`, kind: 'interest', channel: key, members, name: '', autoLabel: name, label: name, shortLabel: name, hubId: '' };
});
const remaining = new Set(people.map((person) => person.id).filter((id) => !assignment.has(id)));
for (const group of list) {
group.members.sort((a, b) => byName(byId.get(a) || { id: a }, byId.get(b) || { id: b }));
// Что ещё читают в этой группе – для карточки группы.
const counts = new Map();
group.members.forEach((id) => subs.of.get(id)?.forEach((key) => {
if (key !== group.channel) counts.set(key, (counts.get(key) || 0) + 1);
}));
group.alsoRead = [...counts.entries()]
.filter(([, count]) => count >= 2)
.sort((a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : 1))
.slice(0, 3)
.map(([key, count]) => ({ key, count, name: String(subs.info.get(key)?.name || key) }));
}
if (remaining.size) {
const members = [...remaining].sort((a, b) => byName(byId.get(a) || { id: a }, byId.get(b) || { id: b }));
list.push({ id: REST_GROUP, kind: 'rest', members, name: '', autoLabel: t('screens.communities.text_007'), label: t('screens.communities.text_002'), shortLabel: t('screens.communities.text_008'), hubId: '' });
}
sortGroups(list);
assignColors(list, new Map());
const byPerson = new Map();
list.forEach((group) => group.members.forEach((id) => byPerson.set(id, group.id)));
return { groups: list, byPerson, snapshots: [] };
}
/**
* Города: кто где живёт (по полю «Город» в профиле). Разные написания одного города – одна
* группа (cities.js). Когда городов много, города с одним человеком собираются в «Другие города».
* @param {Object} o
* @param {Array<{id:string, name:string}>} o.people
* @param {{ of: Map<string,string> }} o.cities
* @param {(value:string) => string} o.cityKey
* @param {(key:string, spellings:string[]) => string} o.cityLabel
*/
export function buildCityGroups({ people, cities, cityKey, cityLabel }) {
const byId = new Map(people.map((person) => [person.id, person]));
const byCity = new Map();
const unknown = [];
for (const person of people) {
const raw = cities?.of?.get(person.id) || '';
const key = raw ? cityKey(raw) : '';
if (!key) { unknown.push(person.id); continue; }
if (!byCity.has(key)) byCity.set(key, { members: [], spellings: [] });
byCity.get(key).members.push(person.id);
byCity.get(key).spellings.push(raw);
}
let list = [...byCity.entries()].map(([key, row]) => {
const name = cityLabel(key, row.spellings);
return { id: `city:${key}`, kind: 'city', city: key, members: row.members, name: '', autoLabel: name, label: name, shortLabel: name, hubId: '' };
});
const singles = list.filter((group) => group.members.length === 1);
if (list.length > 14 && singles.length > 1) {
list = list.filter((group) => group.members.length > 1);
const members = singles.flatMap((group) => group.members);
list.push({ id: 'city:*', kind: 'city', city: '', members, name: '', autoLabel: t('screens.communities.text_009'), label: t('screens.communities.text_003'), shortLabel: t('screens.communities.text_010'), hubId: '' });
}
for (const group of list) group.members.sort((a, b) => byName(byId.get(a) || { id: a }, byId.get(b) || { id: b }));
if (unknown.length) {
unknown.sort((a, b) => byName(byId.get(a) || { id: a }, byId.get(b) || { id: b }));
list.push({ id: REST_GROUP, kind: 'rest', members: unknown, name: '', autoLabel: t('screens.communities.text_011'), label: t('screens.communities.text_004'), shortLabel: t('screens.communities.text_012'), hubId: '' });
}
sortGroups(list);
assignColors(list, new Map());
const byPerson = new Map();
list.forEach((group) => group.members.forEach((id) => byPerson.set(id, group.id)));
return { groups: list, byPerson, snapshots: [] };
}
// --- Раскладка островами --------------------------------------------------------------------
export const ISLAND_STEP = 74; // шаг сот: точка и подпись под ней не налезают на соседей
export const ISLAND_PAD = 30; // от края точек до края острова (для упаковки)
const ISLAND_GAP = 62; // между островами: над каждым – его подпись
const NODE_RADIUS = 22; // точка первого круга (как в движке карты)
// Места на шестиугольной сетке, ближайшие к середине: остров получается круглым при любом
// числе людей (а не шестиугольником с недостроенным краем). При равном расстоянии – по углу.
function hexSlots(count) {
const size = ISLAND_STEP / Math.sqrt(3);
const rings = Math.ceil(Math.sqrt(count / 3)) + 2;
const all = [];
for (let q = -rings; q <= rings; q += 1) {
for (let r = Math.max(-rings, -q - rings); r <= Math.min(rings, -q + rings); r += 1) {
const x = size * Math.sqrt(3) * (q + r / 2);
const y = size * 1.5 * r;
all.push({ x, y, d: Math.round(Math.hypot(x, y) * 100), a: Math.atan2(y, x) });
}
}
all.sort((p, s) => p.d - s.d || p.a - s.a);
return all.slice(0, count).map(({ x, y }) => ({ x, y }));
}
/**
* Люди острова по сотам: самые связанные – в середине, знакомые – рядом. Начальная
* расстановка по спирали, затем жадные обмены местами, пока они сокращают сумму длин
* знакомств (с весом) и держат связанных ближе к середине.
*/
function islandSlots(members, weights, rankOf) {
const n = members.length;
const slots = hexSlots(n);
const index = new Map(members.map((id, i) => [id, i]));
const links = members.map(() => []);
const strength = new Float64Array(n);
members.forEach((a, i) => {
weights.get(a)?.forEach((w, b) => {
const j = index.get(b);
if (j === undefined || j === i) return;
links[i].push([j, w]);
strength[i] += w;
});
});
// Начало: по связанности, при равенстве – ближе к вам, затем по имени (порядок members).
const order = members.map((_, i) => i).sort((a, b) => strength[b] - strength[a] || rankOf(members[a]) - rankOf(members[b]) || a - b);
const at = new Int32Array(n); // человек → номер места
order.forEach((person, k) => { at[person] = k; });
const radius = slots.map((p) => Math.hypot(p.x, p.y));
const centerPull = 0.35;
const dist = (s, t) => Math.hypot(slots[s].x - slots[t].x, slots[s].y - slots[t].y);
const costAt = (i, s, skip) => {
let c = centerPull * strength[i] * radius[s] + 4 * rankOf(members[i]) * radius[s] / ISLAND_STEP;
for (const [j, w] of links[i]) if (j !== skip) c += w * dist(s, at[j]);
return c;
};
if (n > 2 && n <= 260) {
for (let pass = 0; pass < 8; pass += 1) {
let swapped = 0;
for (let i = 0; i < n; i += 1) {
for (let j = i + 1; j < n; j += 1) {
const si = at[i];
const sj = at[j];
const before = costAt(i, si, j) + costAt(j, sj, i);
const after = costAt(i, sj, j) + costAt(j, si, i);
if (after < before - 1e-6) {
at[i] = sj;
at[j] = si;
swapped += 1;
}
}
}
if (!swapped) break;
}
}
const out = new Map();
members.forEach((id, i) => out.set(id, { x: slots[at[i]].x, y: slots[at[i]].y }));
return out;
}
/**
* Острова вокруг центра. Каждый следующий – туда, где он ближе всего к центру (с учётом
* растяжения под экран), но рядом с теми островами, с кем у него больше знакомств.
* Положение по каждому направлению считается точно: для каждого уже стоящего острова
* запретный отрезок расстояний – корни квадратного уравнения.
*/
function packIslands(islands, affinity, focusRadius, stretch) {
const placed = [];
const centers = new Map();
const ANGLES = 96;
for (const island of islands) {
let best = null;
for (let k = 0; k < ANGLES; k += 1) {
const theta = -Math.PI / 2 + (k * Math.PI * 2) / ANGLES;
const ux = Math.cos(theta) * stretch.x;
const uy = Math.sin(theta) * stretch.y;
const uu = ux * ux + uy * uy;
const intervals = [];
const keep = focusRadius + island.r + ISLAND_GAP;
intervals.push([-Infinity, keep / Math.sqrt(uu)]);
for (const other of placed) {
const reach = island.r + other.r + ISLAND_GAP;
const b = -2 * (ux * other.x + uy * other.y);
const c = other.x * other.x + other.y * other.y - reach * reach;
const disc = b * b - 4 * uu * c;
if (disc <= 0) continue;
const sq = Math.sqrt(disc);
intervals.push([(-b - sq) / (2 * uu), (-b + sq) / (2 * uu)]);
}
intervals.sort((p, q) => p[0] - q[0]);
let d = 0;
for (let guard = 0; guard < intervals.length + 2; guard += 1) {
let moved = false;
for (const [d1, d2] of intervals) {
if (d1 < d + 1e-6 && d < d2 - 1e-6) { d = d2; moved = true; }
}
if (!moved) break;
}
const x = ux * d;
const y = uy * d;
let pull = 0;
let pullW = 0;
affinity.get(island.id)?.forEach((w, otherId) => {
const c = centers.get(otherId);
if (!c) return;
pull += w * Math.hypot(x - c.x, y - c.y);
pullW += w;
});
const cost = d + (pullW ? (0.55 * pull) / pullW : 0) + k * 1e-6;
if (!best || cost < best.cost) best = { x, y, cost };
}
const spot = { id: island.id, x: best.x, y: best.y, r: island.r };
placed.push(spot);
centers.set(island.id, spot);
}
return centers;
}
/**
* Координаты людей первого круга островами.
* @param {Object} o
* @param {Array<{id:string, kind:string, members:string[]}>} o.groups – по порядку (крупные первыми)
* @param {Map<string, Map<string, number>>} o.weights
* @param {(id:string) => number} o.rankOf – близость к центру (0 – близкий … 3 – контакт)
* @param {number} o.focusRadius – сколько места оставить вокруг человека в центре
* @param {{x:number, y:number}} o.stretch
* @returns {{ positions: Map<string,{x:number,y:number}>, islands: Map<string,{x:number,y:number,r:number}> }}
*/
export function layoutIslands({ groups, weights, rankOf, focusRadius = 70, stretch = { x: 1, y: 1 } }) {
const local = new Map();
const islands = [];
for (const group of groups) {
if (!group.members.length) continue;
const slots = islandSlots(group.members, weights, rankOf);
let r = 0;
slots.forEach((p) => { r = Math.max(r, Math.hypot(p.x, p.y)); });
local.set(group.id, slots);
islands.push({ id: group.id, r: r + NODE_RADIUS + ISLAND_PAD });
}
// Сколько знакомств между островами – соседями становятся самые связанные.
const groupOf = new Map();
groups.forEach((group) => group.members.forEach((id) => groupOf.set(id, group.id)));
const affinity = new Map();
weights.forEach((near, a) => {
const ga = groupOf.get(a);
if (!ga) return;
near.forEach((w, b) => {
const gb = groupOf.get(b);
if (!gb || gb === ga) return;
if (!affinity.has(ga)) affinity.set(ga, new Map());
affinity.get(ga).set(gb, (affinity.get(ga).get(gb) || 0) + w);
});
});
const centers = packIslands(islands, affinity, focusRadius, stretch);
const positions = new Map();
local.forEach((slots, groupId) => {
const c = centers.get(groupId);
slots.forEach((p, id) => positions.set(id, { x: c.x + p.x, y: c.y + p.y }));
});
return { positions, islands: centers };
}