C# - merge already adjacent rectangles into a clockwise polygon point list?

Question

0.00/5 (No votes)

See more:

Hello Codeproject!

I've made a flood fill recursive function in order to find all tiles in an array that are adjacent to one another. I'd like to use this list of tiles to make a polygon using their rectangle information - the polygon needs to end up being in a clockwise order, however, each time I try and do this I run into an error I do not seem to understand.

All the attempts I've made have been unsuccesful and it's really bothering me. No exceptions are thrown, however, all the polygons end up being invalid due to the points being either in the wrong order, or in the completely wrong position.

The tiles are not sorted by X, or Y. Am I missing something?

What I have tried:

What I've tried doing is run through the list like so:

for (int i =0; i<TileList.Count; i++) {


    PointList.AddRange(new Vector2[] {
            new Vector2(TileList[i].BoundingBox.X, TileList[i].BoundingBox.Y),
            new Vector2(TileList[i].BoundingBox.X + TileList[i].BoundingBox.Width, TileList[i].BoundingBox.Y),
            new Vector2(TileList[i].BoundingBox.X + TileList[i].BoundingBox.Width, TileList[i].BoundingBox.Y + TileList[i].BoundingBox.Height),
            new Vector2(TileList[i].BoundingBox.X, TileList[i].BoundingBox.Y + TileList[i].BoundingBox.Height),
    });


}

for(int i =0; i<PointList.Count; i++)
{
    for (int j = 0; j < PointList.Count; j++)
    {
        if(PointList[i] != PointList[j])
        {
            if (Vector2.Distance(PointList[i], PointList[j]) < 2)
            {
                PointList.Remove(PointList[i]);
                PointList.Remove(PointList[j]);
            }
        }
    }

}

PointList = PointList.OrderBy(p => Math.Atan2(p.X, p.Y)).ToList();

Posted 16-Feb-17 2:50am

Member 11841791

Updated 16-Feb-17 9:17am

v6

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

#realJSOP · Answer 1 · 2017-02-16T04:06:00

Solution 1

What you need to do is get a list of points of the rectangles in question, and determine their angle from a central reference point. Once you do that, you can sort the angles from lowest to highest value, and process each one in that order (essentially, in a clockwise direction).

I will leave it to your considerable google skills to find out how to calculate the angles.

Posted 16-Feb-17 4:06am

#realJSOP

Updated 16-Feb-17 4:18am

v2

Comments

Member 11841791 16-Feb-17 10:15am

Ah, I see what you mean now. I'm on it.

Member 11841791 16-Feb-17 10:26am

This is giving me the exact same problem as just sorting the points out by using Math.Atan.

Patrice T · Answer 2 · 2017-02-16T09:17:00

You need to do an analyze of your problem.
By adjacent, I understand that 2 rectangles are sharing a common side.
Take some points:

r
A  B  C
D  E  F

this gives rectangles ABED and BCFE.

To check if the 2 rectangles are adjacent or not, you need to find common 2 points between both rectangles.
Then, once you know they share the points, you have to merge them and get ACFD.
You need to device a method that guaranty that after merging, all points will remain clockwise.

C#

PointList.Remove(PointList[i]);
PointList.Remove(PointList[j]);

remove have the side effect of moving next elements down. To understand how the code go wrong, use the debugger and pay attention to the changes in the list.

When you don't understand what your code is doing or why it does what it does, the answer is debugger.
Use the debugger to see what your code is doing. Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute, it is an incredible learning tool.

Debugger - Wikipedia, the free encyclopedia[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]

The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.