One Soap Box

I got some progress done on the world map editor today. Last night while failing at going to sleep at a decent time, I figured out how to solve the problem I described earlier. I’ll outline my solution here. I’m pretty sure it’s O(n²), but it may be O(n³).

The algorithm has only one input, which is the size for the target area. This all occurs on an infinite 2-dimensional plane. Objects are limited to integer coordinates and sizes and all edges must be parallel to either the x or the y axis.

Add rectangles to the plane that the target rectangle is not allowed to be in (locked map positions). For each rectangle that already exists, check if the space between the rectangles is larger than the target size (horizontal space between must be greater than the width of the target area and similar for the vertical space with the height). (Unfortunately, I just found a corner case which I did not see before…ah well, this is a start in any case.) When finished adding all of the rectangles, it’s time to merge these into polygon outlines. Unfortunately, Qt does not do this with QPolygon::union, it just tacks on drawing paths as far as I can tell, which is not what I need or can use.

To combine these into polygons, first set up a list of bitfields, one ofr each rectangle. Initialize the ith bit in the ith bitfield as 1 and the rest as 0. Loop over each rectangle for every other rectangle. If the two touch, bitwise-or their fields together. Then remove duplicate entries in the list. Generate polygons from the bitfields using the following algorithm to preserve the outline(s):

The first part is to find where the collisions between the polygon and the rectangle are. By looping over each point in a polygon find out if it lies on an edge of the rectangle. If it does, store the information that it should start the next portion of the outline on the other polygon and where. If they share a vertex, there are two cases, the first is that the vertices are in a single edge that makes the vertices not on the outside anymore and the other being that the polygons touch each other at the vertex. If it is the former, the vertex should not occur in the final outline.

After finding the collision information between the polygon and the rectangle (and vice versa), find a point guaranteed to be on the outermost outline (finding the point closest to any of the four corners guarantees this). From here, start moving around the polygon going from point to point marking each as visited unless there is something to do with the collision info and we need to switch the outlining to the other polygon. When we return to our starting position, the outline is complete. Until all of the original vertices are visited, continue finding an outermost unvisited vertex. Any after the first are going to be holes inside of the first.

With these polygons, we have outlines of the collidable regions of the plane. In order to find the best positioning for the given area (as measured by distance from a point), we traverse the outside of the polygons. The only possible positions for the target area are concave corners and places where the edges intersect the axes extending from the requested point that are parallel to the x and y axes. Finding the best position given the possible candidate positions is trivial.

The corner case when generating the rectangles in between others to complete the mask is when two rectangles are not in line with each other, but the rectangle formed by their closest corners are smaller than the target area. This gives a bound on the edges towards the other rectangle. I’m not sure of how to handle this right now, but it’s a small case right now.

I’m fairly proud of the algorithm despite it being less than optimal. I have it caching things so even if it is O(n³), it is only recalculated when the target size changes or the set of collidable rectangles change.

I also think I can redo the sigmodrtree library in a lot fewer lines using KWidgetDelegate to simplify the look of the items and cleave maybe 5k lines of code from it (it’s currently at 10k lines). And it should be able to be done by the 0.2.0 release time. I hope to have the Trac instance be public at some point, but with only 2 weeks left here, it’d be down for a while before summer plans get figured out.

In other news, we had an assignment to do Markov chains for my Intro to AI class. Since this class tends to have overly simple assignments, instead of just doing 1 or 2 length chains of words (my Falcon version is arbitrary length, but it runs out of RAM for low chain lengths and large text source), I made a C version which initially had RAM issues (allocating 256 pointers per tree node on x86_64 is expensive). It now runs with low RAM and a lot faster using realloc for the children of nodes for the tree (used to represent the database for the chains). Words would start to show up around chains of 4 or 5. Sentences at around 6 or 7. For 8 and up, it depended on the size of the input, but it was almost too much above 10 or 12 even given a large input such as big.txt (which is 6.2MB and contains a few books from Project Gutenberg). A chain size of 8 to 10 gave nearly grammatically correct sentences. Fifteen was too high and caused it to output verbatim paragraphs. Overall it was an interesting little assignment. I just wish that the class was actually more thought provoking than the simple assignments that are given make it out to be. That’s for another rime though.

Also, this is my first post using Lekhonee, a nice little application by Kushal Das. It needs some polishing, but it seems to do its job so far. Thanks.