Генерируйте новые полигоны от (2D) полигона сокращения
Как Mike Stone сказал , DbUnit является большим для получения базы данных в известное состояние прежде, чем запустить Ваши тесты. Когда Ваши тесты закончены, DbUnit может отложить базу данных в состояние, это было в том, прежде чем Вы запустили тесты.
4 ответа
Сначала вы должны вычислить, какие сегменты линии разреза принадлежат внутренним элементам вашего исходного многоугольника. Это классическая проблема, и ее решение простое. Учитывая, что ваши точки c1, c2, c3 ... c6 расположены вдоль прямой именно в этом порядке, тогда отрезки c1-c2 , c3-c4 и т. д. всегда будут принадлежать внутренним элементам многоугольника (*).
Теперь мы можем построить простой рекурсивный алгоритм для разрезания многоугольников. Учитывая ваш большой входной массив, {a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}, начните с любой точки многоугольника, например, b ; добавить его в массив результат . Переместите входной массив вперед. Если вы встретите
- обычный узел многоугольника , поместите его в массив
result. ckузел, гдеkнечетное , найдитеc (k + 1)и продолжайте движение с его позиции. Узелck, гдеkявляется четным , найдитеc (k-1), переместитесь на его позицию и продолжайте движение вперед.
В последних двух случаях добавьте эти узлы в том порядке, в котором они встречались, в массив result . Добавьте узел ck , чтобы установить cut , и добавить еще один узел ( c (k + 1) или c (k-1) , в зависимости от того, что у вас есть) в глобальный набор done .
Если вам нужно выйти за пределы последнего элемента, переключитесь на первый элемент во входном массиве.
Рано или поздно вы встретите начальный узел, из которого вы проходили. Теперь в массиве result у вас есть вырезанный многоугольник. Помни это. Повторять процедуру рекурсивно, начиная с позиции каждого узла, который принадлежит набору cut и не принадлежит глобальному набору done .
Это решение, как я его вижу. Но это вычислительная геоментрия, поэтому она может оказаться немного сложнее, чем кажется.
Для нашего примера начнем с b :
done = {}, начнем сb. После первого прохода вы получитерезультат = [b, c4, c3, f, c2, c1],cut = {c4, c2},done = { c3, c1}; Рекурсия на узлыc4иc2.done = {c3; c1}, начать сc4(рекурсия с 1). После этого прохода вы получитерезультат = [c4, c, c5, c6, e, c3, c4],cut = {c5, c3},готово + = {c6, c4}; Обратитесь кc5.done = {c3; c1; c4; c6}, начать сc2(рекурсия с 1). После этого прохода вы получитерезультат = [c2, a, c1],cut = {c1},done + = {c2}; Не возвращайтесь кc1, так как это внаборе done;done = {c3; c1; c4; c6; c2}, начиная сc5(рекурсия из 2). После этого прохода вы получитерезультат = [c5, d, c6],cut = {c5},done + = {c6}; Не возвращайтесь кc5, так как он находится в набореdone;
Вуаля - вы получаете 4 нужных полигона.
(*) Обратите внимание, что для этого требуется больше «математическое» представление линии. Например, если одна из вершин многоугольника находится на линии, вершина должна быть удвоена, т.е. если точка c была немного ближе к правой стороне и на красной линии, линия будет иметь [c1, c2, c3, c, c, c6] точек на ней, а массив многоугольников будет [a, c1, b, c, c, c, d , c6, e, c3, f, c2] .
Иногда (не в этом примере) это может привести к вырезанию «пустых» многоугольников, например [a, a, a] . Если они вам не нужны, вы можете устранить их на поздних этапах. Во всяком случае, это вычислительная геометрия с огромным количеством граничных случаев. Я не могу включить их все в один ответ ...
Вы можете применить отсечение Weiler Atherton (фактически то, что предлагает Павел), но есть серьезное предостережение.
Из-за ошибок с плавающей запятой чрезвычайно трудно заставить работать алгоритм отсечения W / A - в таких случаях, как линия отсечения, проходящая через вершину, или точно по краю многоугольника,алгоритм может запутаться в том, по какому «пути» по периметру многоугольника ему следует следовать, и тогда он выдаст неверные результаты.
1 сторона поиска каждая точка
выберите одну точку, которая не находится на разрезе (например, a), и установите, что она находится с левой стороны (на самом деле это не соответствует)
когда вы переходите точки на разрезе, сторона точки, которую вы достигли менять. Таким образом, вы находите левую / правую точки.
Проблема в том, что вы также должны учитывать, что порядок точек должен быть предопределенным. (например, по часовой стрелке)
2 начните с каждой средней части cx и идите один раз по часовой стрелке и против часовой стрелки.
Для каждого многоугольника вы ударяете по средней части только в одном направлении.
Если вы «переполняете» c, это означает, что достичь внешнего полинома. Вы можете решить эту проблему, если вы определите c0 и cmax, которые лежат в polgon, и у вас есть чем
input = {a, c1, c0 ,c1, b, c4, c, c5, d, c6, c7, c6, e, c3, f, c2}
Самым простым в реализации является Sutherland-Hodgman . Единственная проблема заключается в том, что он оставляет небольшие полосы с нулевой площадью, соединяющие многоугольники на одной стороне линии. В вашем примере это даст вам что-то вроде:
{a c2 c3 e c6 c5 c c4 c1} и {b c1 c2 f c3 c6 d c5 c4}
Если бы вы могли смириться с этим или выяснить, как чтобы разбить их на нужные вам части, тогда вы обнаружите, что код, выполняющий фактическое отсечение, будет максимально простым.
Реализация просто требует двух стеков и одного прохода через вершины вашего многоугольника. В каждой вершине вы проверяете, пересекли ли вы линию с предыдущей вершины. Если да, вычислите точку пересечения и вставьте ее в одну из стопок. Затем вставьте новую вершину в одну из стопок. Действительно просто.