Это не конкретно прямоугольники + прямоугольные треугольники, но хорошая точка исследования для изучения многоугольников тесселяции: Диаграммы Вороного и триангуляции Делоне и здесь и здесь .
На самом деле, если «просто правильные треугольники» достаточно хороши, они гарантированно триангулируют для вас, и вы всегда можете разбить любой треугольник на два прямоугольных треугольника, если они вам действительно нужны.Или вы можете отрубить «кончики» треугольников, чтобы сделать больше прямоугольников и несколько прямоугольников из прямоугольных треугольников.
Вы также можете попробовать обрезание уха , либо проведя радиально,если вы знаете, что у вас достаточно правильные многоугольники или «обрезка самого большого выпуклого фрагмента».Затем разделите каждый оставшийся треугольник на два, чтобы создать прямоугольные треугольники.
полигон http://static.eruciform.com/images/polygon.png
Вы можете попытаться сделать меньше разрывов, проведя в одну сторону, а затем в другую, чтобы сделать трапецию и разделитьэто по-другому, но тогда вам нужно сделать проверку, чтобы убедиться, что ваша линия разметки не пересекла другую линию где-нибудь.Вы всегда можете закрепить ухо, даже с чем-то практически фрактальным.
Однако иногда это создает очень тонкие треугольники.Вы можете выполнить эвристику, например, «взять самое большое», вместо того, чтобы непрерывно обрезать по краю, но это занимает больше времени, приближаясь к O (n ^ 2).Делоне / Ворной в большинстве случаев делают это быстрее, с менее тонкими треугольниками.