Подразделение четырехсторонней 2D-формы
Я ищу подход к разделению четырехсторонней фигуры на сетку. Например: 
В конечном итоге мне нужно иметь возможность конвертировать полученные фигуры в SVG, но я с удовольствием справлюсь с конвертацией в / из другой библиотеки или системы координат. Что я ищу, так это как подойти к расчету.
Предположим, что форма является четырехсторонней, нарисованной квадратично, где каждая сторона может быть вогнутой или выпуклой, но никакие края не пересекаются с другими краями или самими собой, и любая из четырех сторон не может быть изогнута.
Тот же подход для четырехстороннего многоугольника (форма с прямыми ребрами тривиальна), и если два противоположных ребра являются прямыми, легко найти пересекающиеся точки, потому что они будут лежать вдоль прямых линий, проведенных между подразделениями противоположных сторон., Отсюда относительно легко рассчитать кривую, необходимую для соединения их с предыдущей точкой вдоль альтернативной оси:
Однако, когда нет двух прямых, противоположных сторон (как в третьем примере выше), я не уверен, как найти точки, потому что больше нет уверенности в точках, лежащих вдоль прямой линии.
Я долго искал документированный подход, но безрезультатно.
Вот пример типа начальной формы, использующей SVG для ее описания (она не должна обрабатываться в SVG, пока я могу выводить в SVG.
<svg version="1.1" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" x="0px" y="0px"
viewBox="0 0 406.4 233.4" xml:space="preserve">
<path class="st0" d="M394.3,232.7c-106-37.8-353.7,0-353.7,0s-90.4-151.2,0-207.3s353.7,0,353.7,0S420.3,154.7,394.3,232.7z"/>
</svg>
РЕДАКТИРОВАТЬ: Я задал аналогичный вопрос в Математика Stack Exchange, и один из ответов описывает один подход - использование патча Кунса. Кора объяснение здесь.
2 ответа
Вы можете увидеть живой пример и полный код на Codepen здесь.
Представление данных
Простейшее представление данных на изображении ниже использует кривые Кубического Безье. Я считаю, что это также охватит все ваши варианты использования. Чтобы не загрязнять наш код различными частными случаями, нам потребуется, чтобы входные данные всегда были в формате четырех последующих кривых Кубического Безье, как если бы мы их рисовали. Это означает, что мы не можем использовать:
- Квадратичные кривые Безье (конвертируемые в кубические путем отражения другой контрольной точки)
- Сегменты (можно преобразовать в кривую Кубического Безье, расположив контрольные точки на равном расстоянии между конечными точками на линии)
- Закрыть путь [
ZКоманда SVG] (можно преобразовать в кривую Кубического Безье, рассчитав данный сегмент и затем взяв его оттуда)
Свое представление SVG
<path d=" M50 50
C 100 100 400 100 450 50
C 475 250 475 250 450 450
C 250 300 250 300 50 450
C 150 100 150 250 50 50"
fill="transparent"
stroke="black"
/>
Однако для удобства мы определим наши собственные структуры данных.
Point просто старый Vector2D учебный класс.
class Point {
constructor (x, y) {
this.x = x
this.y = y
}
}
Curve кубическая кривая Безье.
class Curve {
constructor (
startPointX, startPointY,
controlPointAX, controlPointAY,
controlPointBX, controlPointBY,
endPointX, endPointY) {
this.start = new Point(startPointX, startPointY)
this.controlA = new Point(controlPointAX, controlPointAY)
this.controlB = new Point(controlPointBX, controlPointBY)
this.end = new Point(endPointX, endPointY)
}
}
Grid это просто контейнер для кривых.
class Grid {
constructor (topSide, rightSide, bottomSide, leftSide, horizontalCuts, verticalCuts) {
this.topSide = topSide
this.rightSide = rightSide
this.bottomSide = bottomSide
this.leftSide = leftSide
// These define how we want to slice our shape. Just ignore them for now
this.verticalCuts = verticalCuts
this.horizontalCuts = horizontalCuts
}
}
Давайте заполним его той же формой.
let grid = new Grid(
new Curve(50, 50, 100, 100, 400, 100, 450, 50),
new Curve(450, 50, 475, 250, 475, 250, 450, 450),
new Curve(450, 450, 250, 300, 250, 300, 50, 450),
new Curve(50, 450, 150, 100, 150, 250, 50, 50),
8,
6
)
Нахождение точек пересечения
Видимо, вы уже реализовали это с помощью t подход (в отличие от истинной длины сплайсинга кривой), поэтому я помещу это здесь только для полноты картины.
Обратите внимание, что cuts фактическое количество точек пересечения (красных точек), которые вы получите. То есть начальной и конечной точек нет (но с незначительными правками cut() они могут быть)
function cut (cuts, callback) {
cuts++
for (let j = 1; j < cuts; j++) {
const t = j / cuts
callback(t)
}
}
class Curve {
// ...
getIntersectionPoints (cuts) {
let points = []
cut(cuts, (t) => {
points.push(new Point(this.x(t), this.y(t)))
})
return points
}
x (t) {
return ((1 - t) * (1 - t) * (1 - t)) * this.start.x +
3 * ((1 - t) * (1 - t)) * t * this.controlA.x +
3 * (1 - t) * (t * t) * this.controlB.x +
(t * t * t) * this.end.x
}
y (t) {
return ((1 - t) * (1 - t) * (1 - t)) * this.start.y +
3 * ((1 - t) * (1 - t)) * t * this.controlA.y +
3 * (1 - t) * (t * t) * this.controlB.y +
(t * t * t) * this.end.y
}
}
Нахождение кривых расщепления
function lerp (from, to, t) {
return from * (1.0 - t) + (to * t)
}
class Curve {
// ...
getSplitCurves (cuts, oppositeCurve, fromCurve, toCurve) {
let curves = []
cut(cuts, (t) => {
let start = new Point(this.x(t), this.y(t))
// NOTE1: We must go backwards
let end = new Point(oppositeCurve.x(1 - t), oppositeCurve.y(1 - t))
let controlA = new Point(
// NOTE2: Interpolate control points
lerp(fromCurve.controlA.x, toCurve.controlA.x, t),
lerp(fromCurve.controlA.y, toCurve.controlA.y, t)
)
let controlB = new Point(
// NOTE2: Interpolate control points
lerp(fromCurve.controlB.x, toCurve.controlB.x, t),
lerp(fromCurve.controlB.y, toCurve.controlB.y, t)
)
curves.push(new Curve(
start.x, start.y,
controlA.x, controlA.y,
controlB.x, controlB.y,
end.x, end.y
))
})
return curves
}
}
Есть некоторые подозрительные вещи с кодом выше.
NOTE1: Поскольку кривые представлены в том порядке, в котором вы их рисуете, противоположные стороны обращены в разные стороны. Например, верхняя сторона рисуется слева направо, а нижняя справа налево. Может быть, изображение поможет:
NOTE2 Это то, как мы получаем контрольные точки для Безье, разделяющих фигуру. t интерполяция на отрезке, соединяющем контрольные точки противоположных сторон.
Вот эти сегменты. Их конечные точки являются контрольными точками соответствующих кривых.
Это окончательный результат, когда мы рендерим кривые: 
Вы можете увидеть живой пример и полный код на Codepen здесь.
Куда пойти отсюда
Больше пересечений
Это явно не окончательный результат. Нам все еще нужно найти точки пересечения сгенерированных кривых. Однако найти пересечения двух кривых Безье нетривиально. Вот хороший ответ Stackru по этой теме, который приведет вас к этой аккуратной библиотеке, которая сделает всю тяжелую работу за вас (посмотрите код bezier3bezier3() и ты поймешь)
Расщепление кривых
Как только вы найдете точки пересечения, вы захотите найти, в каком t они происходят. Зачем t ты спрашиваешь? Таким образом, вы можете разделить кривую.
Фактический конечный результат
В конце вам нужно выбрать эти части кривых и расположить их так, чтобы они представляли отдельные поля сетки.
Как вы можете видеть, у вас еще долгий путь, я прошел лишь небольшую часть (и все же сумел написать длинный ответ:D).
Если ваши четыре стороны являются кубическими кривыми Безье, как насчет чего-то относительно простого:
Чтобы сделать горизонтальные разделители (сверху вниз), создайте новые кубические кривые Безье, интерполируя контрольные точки верхней и нижней сторон:
Затем разделите левую и правую стороны на одинаковое количество точек.
... и растянуть кривые делителя, чтобы они соединялись с этими точками:
Затем сделайте то же самое слева направо, чтобы создать вертикальные разделители.
Вот ручка для проверки различных форм: https://codepen.io/Sphinxxxx/pen/pKddee
Важные части находятся в BezierWrapper.lerpCurve() а также BezierWrapper.fitCurve()а также Bezier класс, взятый из https://gamedev.stackexchange.com/a/5427 чтобы получить равномерно распределенные точки вдоль кривой (.samples):
class BezierWrapper {
constructor(controls, sampleCount, classname) {
this.controls = controls;
this.classname = classname;
if(sampleCount) {
function point2obj(p) {
return { x: p[0], y: p[1] };
}
//https://gamedev.stackexchange.com/a/5427
const interpolator = new Bezier(point2obj(controls[0]),
point2obj(controls[1]),
point2obj(controls[2]),
point2obj(controls[3]));
const samples = this.samples = [];
for(let i = 1; i <= sampleCount; i++) {
const t = i / (sampleCount+1);
samples.push([interpolator.mx(t), interpolator.my(t)]);
}
}
}
static lerpCurve(source, target, t) {
function lerpCoord(from, to, t) {
const diffX = to[0] - from[0],
diffY = to[1] - from[1],
lerpX = from[0] + (diffX * t),
lerpY = from[1] + (diffY * t);
return [lerpX, lerpY];
}
const middle = source.map((c, i) => lerpCoord(c, target[i], t));
return middle;
}
static fitCurve(source, start, end) {
function distance(p1, p2) {
const dx = p2[0] - p1[0],
dy = p2[1] - p1[1];
return Math.sqrt(dx*dx + dy*dy);
}
//https://gist.github.com/conorbuck/2606166
function angle(p1, p2) {
const dx = p2[0] - p1[0],
dy = p2[1] - p1[1],
radians = Math.atan2(dy, dx);
return radians;
}
//https://stackru.com/questions/2259476/rotating-a-point-about-another-point-2d
function rotate(p, radians) {
const x = p[0],
y = p[1],
cos = Math.cos(radians),
sin = Math.sin(radians);
return [cos*x - sin*y, sin*x + cos*y];
}
const sourceStart = source[0],
sourceEnd = source[3],
scale = distance(start, end)/distance(sourceStart, sourceEnd),
rot = angle(start, end) - angle(sourceStart, sourceEnd);
//Translate, scale and rotate the source control points to make them fit the start and end points:
const sourceNorm = source.map(c => [c[0] - sourceStart[0], c[1] - sourceStart[1]]),
fittedNorm = sourceNorm.map(c => rotate([c[0]*scale, c[1]*scale], rot)),
fitted = fittedNorm.map(c => [c[0] + start[0], c[1] + start[1]]);
return fitted;
}
}