[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Pingus-CVS] r3818 - trunk/pingus/src/display
From: |
grumbel at BerliOS |
Subject: |
[Pingus-CVS] r3818 - trunk/pingus/src/display |
Date: |
Mon, 14 Jul 2008 09:20:51 +0200 |
Author: grumbel
Date: 2008-07-14 09:20:49 +0200 (Mon, 14 Jul 2008)
New Revision: 3818
Added:
trunk/pingus/src/display/rect_merger.cpp
trunk/pingus/src/display/rect_merger.hpp
Log:
Implemented function to transform a set of rectangles into an non-overlapping
set of rectangles
Added: trunk/pingus/src/display/rect_merger.cpp
===================================================================
--- trunk/pingus/src/display/rect_merger.cpp 2008-07-13 13:32:12 UTC (rev
3817)
+++ trunk/pingus/src/display/rect_merger.cpp 2008-07-14 07:20:49 UTC (rev
3818)
@@ -0,0 +1,282 @@
+// Pingus - A free Lemmings clone
+// Copyright (C) 2008 Ingo Ruhnke <address@hidden>
+//
+// This program is free software: you can redistribute it and/or modify
+// it under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+//
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with this program. If not, see <http://www.gnu.org/licenses/>.
+
+#include <assert.h>
+#include <iostream>
+#include "../math/vector2i.hpp"
+#include "../math/size.hpp"
+#include "rect_merger.hpp"
+
+struct Mark {
+ enum Type { START_MARK = 0, END_MARK = 1 } type;
+ int pos;
+
+ Mark(Type type_, int pos_) : type(type_), pos(pos_) {}
+};
+
+struct Row {
+ int top;
+ int bottom;
+ std::vector<Mark> marks;
+};
+
+bool rect_y_sorter(const Rect& lhs, const Rect& rhs)
+{
+ return lhs.top < rhs.top;
+}
+
+bool rect_xy_sorter(const Rect& lhs, const Rect& rhs)
+{
+ if (lhs.left == rhs.left)
+ {
+ return lhs.top < rhs.top;
+ }
+ else
+ {
+ return lhs.left < rhs.left;
+ }
+}
+
+bool mark_sorter(const Mark& lhs, const Mark& rhs)
+{
+ if (lhs.pos == rhs.pos)
+ {
+ return (lhs.type < rhs.type);
+ }
+ else
+ {
+ return (lhs.pos < rhs.pos);
+ }
+}
+
+void generate_rows(const std::vector<Rect> rects, std::vector<Row>& rows)
+{
+ // Figure out where we need to split the rectangles
+ std::vector<int> row_lines;
+ for(std::vector<Rect>::const_iterator i = rects.begin(); i != rects.end();
++i)
+ {
+ row_lines.push_back(i->top);
+ row_lines.push_back(i->bottom);
+ }
+ std::sort(row_lines.begin(), row_lines.end());
+
+ // Create rows
+ int start = row_lines.front();
+ for(std::vector<int>::const_iterator i = row_lines.begin()+1; i !=
row_lines.end(); ++i)
+ {
+ if (*i != start)
+ {
+ Row row;
+ row.top = start;
+ row.bottom = *i;
+
+ rows.push_back(row);
+
+ start = *i;
+ }
+ }
+}
+
+void split_rectangles(const std::vector<Rect>& rects, std::vector<Row>& rows)
+{ // For this to work rects must be sorted by rects[i].top
+ std::vector<Rect>::const_iterator rect_it = rects.begin();
+ for(std::vector<Row>::iterator row_it = rows.begin(); row_it != rows.end()
&& rect_it != rects.end(); ++row_it)
+ {
+ for(; rect_it->top == row_it->top; ++rect_it)
+ {
+ Mark start(Mark::START_MARK, rect_it->left);
+ Mark end (Mark::END_MARK, rect_it->right);
+
+ // Add the gives rectangle to all rows it overlaps
+ std::vector<Row>::iterator this_row_it = row_it;
+ do
+ {
+ this_row_it->marks.push_back(start);
+ this_row_it->marks.push_back(end);
+
+ if (this_row_it->bottom < (rect_it->bottom))
+ ++this_row_it;
+ else
+ break;
+ }
+ while (1);
+ }
+ }
+
+ // Sort the marker in the rows
+ for(std::vector<Row>::iterator i = rows.begin(); i != rows.end(); ++i)
+ std::sort(i->marks.begin(), i->marks.end(), mark_sorter);
+}
+
+void generate_rectangles(const std::vector<Row>& rows, std::vector<Rect>&
rects_out)
+{
+ for(std::vector<Row>::const_iterator i = rows.begin(); i != rows.end(); ++i)
+ {
+ const std::vector<Mark>& marks = i->marks;
+
+ assert(marks.front().type == Mark::START_MARK);
+
+ int start = marks.front().pos;
+ int parenthesis_count = 1;
+ for(std::vector<Mark>::const_iterator mark_it = marks.begin()+1; mark_it
!= marks.end(); )
+ {
+ if (mark_it->type == Mark::END_MARK)
+ parenthesis_count -= 1;
+ else // if (mark_it->type == START_MARK)
+ parenthesis_count += 1;
+
+ if (parenthesis_count == 0)
+ {
+ if (mark_it+1 != marks.end() &&
+ (mark_it+1)->type == Mark::START_MARK &&
+ (mark_it+1)->pos == mark_it->pos)
+ {
+ parenthesis_count += 1;
+ }
+ else
+ {
+ rects_out.push_back(Rect(start, i->top,
+ mark_it->pos, i->bottom));
+ ++mark_it;
+ if (mark_it != marks.end())
+ start = mark_it->pos;
+ }
+ }
+ else
+ {
+ ++mark_it;
+ }
+ }
+ }
+}
+
+void merge_vertical_rectangles(std::vector<Rect>& rects_in, std::vector<Rect>&
rects_out)
+{
+ std::sort(rects_in.begin(), rects_in.end(), rect_xy_sorter);
+
+ assert(!rects_in.empty());
+ Rect rect = rects_in.front();
+ for(std::vector<Rect>::const_iterator i = rects_in.begin()+1; i !=
rects_in.end();)
+ {
+ //std::cout << "pos: " << i - rects_in.begin() << "/" << rects_in.size()
<< std::endl;
+ // Expand the rectangle vertically as much as possible
+ while(rect.left == i->left &&
+ rect.right == i->right &&
+ rect.bottom == i->top)
+ {
+ rect.bottom = i->bottom;
+ ++i;
+ if (i == rects_in.end())
+ break;
+ }
+ rects_out.push_back(rect);
+
+ if (i != rects_in.end())
+ {
+ rect = *i;
+ ++i;
+ }
+ }
+}
+
+void merge_rectangles(std::vector<Rect> rects_in, std::vector<Rect>& rects_out)
+{
+ if (rects_in.empty())
+ return;
+
+ //std::cout << "--- Merge rectangles: " << rects_in.size() << std::endl;
+
+ if (0)
+ for(std::vector<Rect>::const_iterator i = rects_in.begin(); i !=
rects_in.end(); ++i)
+ std::cout << " rectin: " << *i << std::endl;
+
+ // Prepare rectangles
+ std::sort(rects_in.begin(), rects_in.end(), rect_y_sorter);
+
+ // Generate rows
+ std::vector<Row> rows;
+ generate_rows(rects_in, rows);
+ split_rectangles(rects_in, rows);
+
+ // Print rows
+ if (0)
+ for(std::vector<Row>::iterator i = rows.begin(); i != rows.end(); ++i)
+ {
+ std::cout << " row: " << i->top << "-" << i->bottom << " - ";
+ for(std::vector<Mark>::iterator mark_it = i->marks.begin(); mark_it !=
i->marks.end(); ++mark_it)
+ {
+ std::cout << ((mark_it->type == Mark::START_MARK) ? "'(" : "')")
+ << mark_it->pos
+ << "' ";
+ }
+ std::cout << std::endl;
+ }
+
+ std::vector<Rect> rects_out_step1;
+ generate_rectangles(rows, rects_out_step1);
+ merge_vertical_rectangles(rects_out_step1, rects_out);
+}
+
+#ifdef __TEST__
+
+// g++ -Wall -O2 -D__TEST__ rect_merger.cpp ../math/rect.cpp
../math/origin.cpp -o rect_merger
+
+#include <stdlib.h>
+
+int main()
+{
+ srand(time(NULL));
+
+ std::vector<Rect> rects_in;
+ std::vector<Rect> rects_out;
+
+ // Generate random rectangles
+ for(int i = 0; i < 20; ++i)
+ {
+ rects_in.push_back(Rect(Vector2i(rand() % 800 - 200,
+ rand() % 800 - 200),
+ Size(rand() % 400 + 10,
+ rand() % 400 + 10)));
+ }
+
+ merge_rectangles(rects_in, rects_out);
+
+ std::cout << "<?xml version='1.0' standalone='no'?>\n"
+ << "<!DOCTYPE svg PUBLIC '-//W3C//DTD SVG 1.1//EN' "
+ << "'http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd'>\n"
+ << "<svg width='800' height='800' "
+ << "xmlns='http://www.w3.org/2000/svg' version='1.1'>" <<
std::endl;
+
+ std::cout << "<g>" << std::endl;
+ for(std::vector<Rect>::iterator i = rects_in.begin(); i != rects_in.end();
++i)
+ std::cout << " <rect fill='blue' style='fill-opacity:0.5' x='" << i->left
<< "' y='" << i->top
+ << "' width='" << i->get_width() << "' height='" <<
i->get_height() << "' />" << std::endl;
+ std::cout << "</g>" << std::endl;
+ std::cout << std::endl;
+
+ std::cout << "<g>" << std::endl;
+ for(std::vector<Rect>::iterator i = rects_out.begin(); i != rects_out.end();
++i)
+ std::cout << " <rect fill='yellow' stroke='black'
style='fill-opacity:0.5' x='" << i->left << "' y='" << i->top
+ << "' width='" << i->get_width() << "' height='" <<
i->get_height() << "' />" << std::endl;
+ std::cout << "</g>" << std::endl;
+ std::cout << "</svg>" << std::endl;
+
+ return 0;
+}
+
+#endif
+
+/* EOF */
Property changes on: trunk/pingus/src/display/rect_merger.cpp
___________________________________________________________________
Name: svn:keywords
+ Id
Name: svn:eol-style
+ native
Added: trunk/pingus/src/display/rect_merger.hpp
===================================================================
--- trunk/pingus/src/display/rect_merger.hpp 2008-07-13 13:32:12 UTC (rev
3817)
+++ trunk/pingus/src/display/rect_merger.hpp 2008-07-14 07:20:49 UTC (rev
3818)
@@ -0,0 +1,27 @@
+// Pingus - A free Lemmings clone
+// Copyright (C) 2008 Ingo Ruhnke <address@hidden>
+//
+// This program is free software: you can redistribute it and/or modify
+// it under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+//
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with this program. If not, see <http://www.gnu.org/licenses/>.
+
+#ifndef HEADER_RECT_MERGER_HPP
+#define HEADER_RECT_MERGER_HPP
+
+#include <vector>
+#include "../math/rect.hpp"
+
+void merge_rectangles(std::vector<Rect> rects_in, std::vector<Rect>&
rects_out);
+
+#endif
+
+/* EOF */
Property changes on: trunk/pingus/src/display/rect_merger.hpp
___________________________________________________________________
Name: svn:keywords
+ Id
Name: svn:eol-style
+ native
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Pingus-CVS] r3818 - trunk/pingus/src/display,
grumbel at BerliOS <=