#javascript #math #charts
#javascript #математика #Диаграммы
Вопрос:
Я пытаюсь получить точки наименьших полигонов, которые линии создают вокруг начальной точки диаграммы, то есть самого внутреннего многоугольника. Линии различаются в зависимости от некоторых параметров, которые можно изменить.
Пример такой диаграммы:
Как видно из диаграммы, линии пересекаются много раз и, таким образом, создают несколько полигонов. Однако я заинтересован в получении только наименьшего многоугольника, который находится в начальной точке (центре) диаграммы.
Я думал о том, чтобы провести несколько параллелей с осью x от оси y влево и вправо сверху и снизу (наименьший перехват по осям y и -y) и посмотреть, какая строка получает «удар» первой, чтобы получить линии, которые будут охватывать этот многоугольник, а затем получитьих пересечения для вершин, которые можно использовать для рисования многоугольника. Однако, поскольку для точной проверки таких линий потребуется множество точек, мне интересно, есть ли, возможно, более элегантное решение проблемы?
Комментарии:
1. Пожалуйста, не могли бы вы упростить свой вопрос, кому-то трудно понять проблему, которую вы пытаетесь решить. Не позволяйте людям гадать, в чем может быть проблема.
2. Ах, мои извинения. Постараюсь сделать это более понятным.
3. Привет! Вы знакомы с линейным программированием? Эта проблема очень похожа на концепции, встречающиеся в линейном программировании.
Ответ №1:
Мне удалось решить это с помощью Stef и его алгоритма. Вот код, который я использовал:
const getIntersections = async (
lines: IPoint[][]
): Promise<IIntersectLine[]> => {
let lineIntersects: IIntersectLine[] = [];
lines.forEach((line) => {
let lineIntersect: IIntersectLine = {
line: line,
intersects: [],
};
let x1 = line[1].x;
let y1 = line[1].y;
let x2 = line[2].x;
let y2 = line[2].y;
for (let i = 0; i < lines.length; i ) {
let x3 = lines[i][1].x;
let y3 = lines[i][1].y;
let x4 = lines[i][2].x;
let y4 = lines[i][2].y;
if ((x1 === x2 amp;amp; y1 === y2) || (x3 === x4 amp;amp; y3 === y4)) continue;
let denominator = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
if (denominator === 0) continue;
let ua =
((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denominator;
let ub =
((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denominator;
if (ua < 0 || ua > 1 || ub < 0 || ub > 1) continue;
let x = x1 ua * (x2 - x1);
let y = y1 ua * (y2 - y1);
lineIntersect.intersects.push({
x: x.toFixed(4),
y: y.toFixed(4),
});
}
lineIntersect.intersects.sort((a, b) => {
return a.x - b.x;
});
lineIntersects.push(lineIntersect);
});
return lineIntersects;
};
const getStartingPoint = async (intersects: IPoint[]) => {
let result: IPoint = intersects[0];
let distance = result.x * result.x result.y * result.y;
intersects.forEach((i) => {
let newDistance = i.x * i.x i.y * i.y;
if (newDistance < distance) {
distance = newDistance;
result = i;
}
});
return resu<
};
const calcPolygonArea = async (polygon: IPoint[]) => {
let total = 0;
for (let i = 0, l = polygon.length; i < l; i ) {
let addX = polygon[i].x;
let addY = polygon[i == polygon.length - 1 ? 0 : i 1].y;
let subX = polygon[i == polygon.length - 1 ? 0 : i 1].x;
let subY = polygon[i].y;
total = addX * addY * 0.5;
total -= subX * subY * 0.5;
}
return Math.abs(total);
};
export const getPolygonVertices = async (lines: IPoint[][]) => {
let result: IPoint[] = [];
let intersections = await getIntersections(lines);
let intersectionVertices = intersections.map((x) => x.intersects).flat();
let startingPoint = await getStartingPoint(intersectionVertices);
let crossedLines = intersections.filter((x) =>
x.intersects.some(
(p) => p.x === startingPoint.x amp;amp; p.y === startingPoint.y
)
);
let newPoints: IPoint[] = [];
const x0 = 0;
const y0 = 0;
crossedLines.forEach((line) => {
let x1 = startingPoint.x;
let y1 = startingPoint.y;
let pointIndex = line.intersects.findIndex(
(p) => p.x === startingPoint.x amp;amp; p.y === startingPoint.y
);
let d;
if (line.intersects[pointIndex - 1]) {
let x2 = line.intersects[pointIndex - 1].x;
let y2 = line.intersects[pointIndex - 1].y;
d = (x0 - x1) * (y2 - y1) - (y0 - y1) * (x2 - x1);
if (d > 0) newPoints.push({ x: x2, y: y2 });
}
if (line.intersects[pointIndex 1]) {
let x2 = line.intersects[pointIndex 1].x;
let y2 = line.intersects[pointIndex 1].y;
d = (x0 - x1) * (y2 - y1) - (y0 - y1) * (x2 - x1);
if (d > 0) newPoints.push({ x: x2, y: y2 });
}
});
let result1: IPoint[] = [];
let result2: IPoint[] = [];
for (let i = 0; i < newPoints.length; i ) {
let tempResult: IPoint[] = [];
tempResult.push(startingPoint, newPoints[i]);
for (let j = 0; j < 50; j ) {
const uniqueValues = new Set(tempResult.map((v) => v.x));
if (uniqueValues.size < tempResult.length) {
if (i === 0) result1 = tempResu<
else result2 = tempResu<
break;
}
let newCrossedLines = intersections.filter((x) =>
x.intersects.some(
(p) =>
p.x === tempResult[tempResult.length - 1].x amp;amp;
p.y === tempResult[tempResult.length - 1].y
)
);
let newLine = newCrossedLines.filter((l) =>
l.intersects.every(
(p) =>
p.x !== tempResult[tempResult.length - 2].x amp;amp;
p.y !== tempResult[tempResult.length - 2].y
)
)[0];
let x1 = tempResult[tempResult.length - 1].x;
let y1 = tempResult[tempResult.length - 1].y;
let pointIndex = newLine.intersects.findIndex(
(p) =>
p.x === tempResult[tempResult.length - 1].x amp;amp;
p.y === tempResult[tempResult.length - 1].y
);
let d;
if (newLine.intersects[pointIndex - 1]) {
let x2 = newLine.intersects[pointIndex - 1].x;
let y2 = newLine.intersects[pointIndex - 1].y;
d = (x0 - x1) * (y2 - y1) - (y0 - y1) * (x2 - x1);
if (d > 0) tempResult.push({ x: x2, y: y2 });
}
if (newLine.intersects[pointIndex 1]) {
let x2 = newLine.intersects[pointIndex 1].x;
let y2 = newLine.intersects[pointIndex 1].y;
d = (x0 - x1) * (y2 - y1) - (y0 - y1) * (x2 - x1);
if (d > 0) tempResult.push({ x: x2, y: y2 });
}
}
}
const area1 = await calcPolygonArea(result1);
const area2 = await calcPolygonArea(result2);
area1 < area2 ? (result = result1) : (result = result2);
return resu<
}; По сути, сначала я получаю все пересечения всех линий на графике. Затем я нахожу ближайший к начальной точке диаграммы (0,0), поскольку наименьший многоугольник, окружающий его, должен содержать эту вершину. После этого я начинаю двигаться вдоль двух линий, которые составляют ближайшее пересечение. Повторяя процесс для этих двух начальных строк, я двигаюсь по часовой стрелке вдоль линии до следующего пересечения, где затем двигаюсь вдоль следующей строки, продолжая процесс, пока не получу дублирующуюся вершину в моем результирующем массиве, то есть пока многоугольник не будет закрыт. В конце я сравниваю два полигона и возвращаю меньший.
Скорее всего, есть более эффективный способ сделать это, но пока это работает!
Конечный результат:
Ответ №2:
Вот возможный алгоритм:
- Пока цикл не найден:
- Начните с некоторой точки
(x,y)на некоторой строкеL - Найдите следующую точку пересечения
(x',y')Lв направлении по часовой стрелке - Если начало координат
(0, 0)находится справа от этой строки:x = x'y = y'L =эта новая строка
- Начните с некоторой точки
- Если был найден цикл: этот цикл является многоугольником.
Комментарии:
1. Извините за поздний комментарий. Я пытался реализовать это решение, а также другое, и в итоге получилось то, что работает. Спасибо за помощь!