Я ищу подход к разделению четырехугольной формы на сетку. Например:

В конечном итоге мне нужно иметь возможность преобразовать полученные фигуры в 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>
EDIT: я спросил аналогичный вопрос в Stack Exchange Maths, и один из ответов описывает один подход - использование Патч енотов. Объяснение Quora здесь.
@sjaustirni Я имею в виду двумерные многоугольники. Когда я говорю «квадратичный», я имею в виду, что у них есть четыре угла, соединенные кривыми, которые можно описать квадратичными кривыми - т.е. каждая сторона представляет собой одну кривую. Стороны могут быть выпуклыми или вогнутыми, и хотя (как в первой точке) они могут выглядеть так, как будто они отображаются на трехмерном объекте, это не мое намерение.
Тогда, возможно, использование слова полигоны - не лучшая идея (стороны многоугольников - прямые). В любом случае, всегда ли формы симметричны по оси, как показано на рисунке? Кроме того, что вы знаете о формах вначале, каков ввод? Пути, похожие на кубические кривые Безье?
@sjaustirni Спасибо. Ты прав. Я обновил вопрос. Что касается того, что я знаю вначале, фигура будет состоять из четырех точек примерно квадратной формы, каждая точка соединена вогнутой или выпуклой кривой. Форма не обязательно будет симметричной по какой-либо оси.
Не беспокойтесь :) хмммм, не могли бы вы добавить пример ввода в вопрос (например, в виде структуры данных)? Ведь вы знаете, что кривые можно представить по-разному. Это кривые SVG Безье? Если да, то они просто кубические или, возможно, квадратичные (см. Ссылку, которую я разместил выше)?
У вас есть только мобильный телефон на данный момент, поэтому не могу добавить пример, но вы можете предположить, что кубические кривые Безье и эта форма описана с помощью SVG.
@sjaustirni К вопросу добавлен пример svg.



![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)


Вы можете увидеть живой пример и полный код на Codepen здесь.
В простейшем представлении данных изображения ниже используются кубические кривые Безье. Я считаю, что это также охватывало бы все ваши варианты использования. Чтобы не загромождать наш код различными частными случаями, нам потребуется, чтобы входные данные всегда были в формате четырех последующих кубических кривых Безье, как если бы мы их нарисовали. Это означает, что мы не можем использовать:
Z SVG command] (конвертируется в кубическую кривую Безье путем вычисления данного сегмента и последующего его взятия оттуда)Его представление в формате 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 здесь.
Очевидно, это не окончательный результат. Нам еще нужно найти точки пересечения сгенерированных кривых. Однако найти пересечения двух кривых Безье нетривиально.
Вот хороший ответ StackOverflow по теме, которая приведет вас к этому аккуратная библиотека, который сделает за вас тяжелую работу (посмотрите код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://stackoverflow.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;
}
}
Я не уверен, существует ли квадратные многоугольники (хотя я не эксперт и с радостью буду исправлен), но, может быть, вы имели в виду многоугольники в неевклидовом пространстве? Если да, то гарантированно ли эти многоугольники будут прямоугольниками в геометрии на поверхности цилиндра или геометрией на поверхности конуса или эллиптической геометрией (то есть на поверхности шара), как показано на первом рисунке?