Был один треугольник, стало - ?

[d3drm]

Такая ситуация. Надо разделить треугольник, путем вырезания из него другой фигуры. Для начала самый примитив, вырезать из треугольника - треугольник.

Как это выглядит:



То есть по сути программа должна понимать с какими точками ей образовывать новые треугольники, чтобы заполнить оставшееся пространство... Есть мысли?

[d3drm]

Общий алгоритм в голове сложился... Вернее разложился на более мелкие вопросы. Один из них пока не могу решить. Видно, что при данной задаче треугольник деллится на 6. Также при этом каждая вершина начального треугольника соединяется с двумя вершинами вырезаемого. Как найти эти вершины?

[GSerg]

В принципе, возможно, что соединять со стороной внешнего треугольника надо ту вершину внутреннего, которая ближе всех. Любую из двух, если их две.
А полная теория по идее тут (триангуляция с поддержкой дырок в полигонах).

[GAGArin]

Брать линию до вершины и смотреть пересекает ли она третью сторону треугольника или уже проведенные линии, если нет то резать по ней. И так для каждой вершины по 3 раза (начиная рассмотрение с ближайших)

[Matew]

Уже проведенную линию можно пересечь, не пересекая сторон внутреннего треугольника можно тока в случае, когда стороны треугольников параллельны. А если треугольники подобны, то получается вообще интересный случай.

[GAGArin]

Уже проведенную линию можно пересечь, не пересекая сторон внутреннего треугольника можно тока в случае, когда стороны треугольников параллельны.

Не только.

[d3drm]

Брать линию до вершины и смотреть пересекает ли она третью сторону треугольника или уже проведенные линии, если нет то резать по ней. И так для каждой вершины по 3 раза (начиная рассмотрение с ближайших)

вот это какжется более-менее правдивым алгоритмом... можешь расписать подробнее? что есть третья сторона? противолежащая углу, чтоли?

[GAGArin]

Вот это какжется более-менее правдивым алгоритмом... можешь расписать подробнее? что есть третья сторона? противолежащая углу, чтоли?

Ну да. Есть три точки, берешь одну а для двух других вычисляешь уравнение прямой, потом уравнение прямой для выбранной точки и проверяемой вершины. Смотришь где пересечение (х например) если он не между иксами концов отрезка то покатит. Рисуешь прямую и записываешь её в проверяемые. Следущую проверяешь еще и на пересечение с ней.

Вот только назвать этот алгоритм лучшим я не могу. Может быть он и нечего, но не обещаю. ИМХО где-то должен быть лучше. Очень похожий может быть, но лучше.

[d3drm]

Вот вроде довел алго до ума, прошу протестить пытливый народ.

В проге - левой кнопкой строить большой треугольник, правой - маленький. Трег. появляется после расстановки трех точек. Далее кнопкой CUT режем треугольник.

Маленький треугольник никакими своими частями не должен выезжать за границы большого. Это еще не сделано.

Ну а остальное прошу помочь протестить вас. Если на скрине линии будут заезжать за вырезаемый треугольник или будут пересекаться, прошу сообщать здесь с выложенным скрином...

[GDC]

У меня вопрос!!
КАК ПОЛЬЗОВАТЬСЯ?Я идиот! Убейте меня, кто-нибудь!Я идиот! Убейте меня, кто-нибудь!Я идиот! Убейте меня, кто-нибудь!
я открыл у меня белый лист и три кнопки, где при нажатии на CUT ощибка!!!

[Kovu]

Наверно я гений, но до мя доперло как пользоваться прогой
Левой кнопкой мыши делаются 3 точки большого треугольника, правой-маленького
Кст а от каждой вершины большого треугольника должно быть 2 к вершинам маленького линии или нет?

[GDC]

Была глупость!!!!

Мне очень стыдно!

[GAGArin]

GDC
Человек тестирует алгоритм, а не делает мега прогу по нарезке треугольников. ИМХО это нормальное состояние.

Писать интерфейс на тест... ну скажем глупо.

[Хакер]

Этот человек видимо делает что-то вроде 3d редактора, а в данный момент делает возможность редактировать полигоны.

Я экстоsense

[d3drm]

GDC, Kovu дятлизм не излечим.

...В проге - левой кнопкой строить большой треугольник, правой - маленький. Трег. появляется после расстановки трех точек. Далее кнопкой CUT режем треугольник. ...

А что должно получиться написано и нарисовано выше.

Верно, как раз 3D редактор я и делаю, а данный алгоритм - это часть модуля вырезания "фигур из других фигур". В идеале треугольники должны резаться в произвольном положении исходного и вырезаемого, но вырезаение треугольника, когда он полностью находится внутри исходного оказалось самой сложной задачей. Помимо этого уже реализовано 5 случаев другого расположения треугольников (когда, например пересекаются две грани каждого; когда треугольники образуют собой шестиконечную звезду и т.д.)


Снова дятлам:
Если бы у меня было время писать интерфейс и хелп к данной программе, а также исключение ошибок, которые возникают в случае запрещенных (на словах) действий, то я бы лучше написал бота, проверяющего правильность построения геометрии и не выкладывал бы сюда программу.

[Kovu]

d3drm
ну так от каждой вершины большого треугольника должно быть 2 линии к вершинам маленького или нет?

[GAGArin]

d3drm
А не лучше тогда сразу в пространстве задачу решать? Честно говоря тоже думал что это 3д редактор будет )

[d3drm]

Kovu, да, так оно и должно быть =)

GAGArin, я чесс говоря с 3D редакторами мало дела имел, поэтому изобретаю колесо, не зная. что оно круглое. Данный инструмент будет работать в окне проекции, то есть вырезаться будут спроецированные модели. До полного вырезания фигур в 3Д пока еще не дорос =)

[Kovu]

Тогда держи баг

[GDC]

d3drm Че-то сглупил!!! Приношу извенения, тогда все понятно!!!

[GAGArin]

d3drm
Вообще если разобрался с 2д то разберешься и с 3д принципиальной разницы нет. Плоскости вместо прямых, прямые вместо точек. Точки вместо... Ну вобщем точки сами по себе )) Писать восстановление 3д по проекциям ИМХО сложнее чем просто помнить 3д и отрисовывать проекции по нему.

Kovu
Не думаю что это баг ) Ни один редактор лучше не разрежет.

[d3drm]

GAGArin, позможно ты прав, но на проекции легче тренироваться. браться сразу за сложные задачи и не выполнить их хуже чем решить простые.

Kovu, да, на самом деле это - фича Одна сторона преграждает доступ к двум маленьким, поэтому приходится соединять по другому. Вырожденный случай. Но спасибо все равно =)