Jump to content
  • Advertisement
Sign in to follow this  
ApochPiQ

Combining line segments

This topic is 3762 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been messing around with some algorithms that generate a large number of line segments. These segments travel along a regular grid at either 90 degree or 45 degree angles. The algorithm that generates them works something like a combination of a ray marching system and cellular automata; in any case its details aren't important. What is important is that the segments generated are suboptimal. For example, instead of the line (0,0)-(2,0) the code would generate (0,0)-(1,0) and (1,0)-(2,0). I've decided (for a number of reasons) to solve the problem by means of a postprocessing step which recombines the smaller segments into larger ones. The following code is what I've come up with. The PruneDuplicateSegments() function pretty much does what it says on the tin; I've checked it and it works correctly.
static void CombineLinearSegments()
{
	vector<Segment> newsegments;
	bool couldcombine;

	PruneDuplicateSegments();
	do {
		Segment& s = *Segments.begin();
		Point2D& start = s.Start;
		Point2D& pos = s.End;

		int dx = SGN(static_cast<int>(pos.x) - static_cast<int>(s.Start.x));
		int dy = SGN(static_cast<int>(pos.y) - static_cast<int>(s.Start.y));
		int dxa = ABS(dx);
		int dya = ABS(dy);

		do {
			couldcombine = false;
			vector<Segment>::iterator iter_search = Segments.begin();
			++iter_search;
			while (iter_search != Segments.end()) {
				bool combined = false;

				int sdx = SGN(static_cast<int>(iter_search->End.x) - static_cast<int>(iter_search->Start.x));
				int sdy = SGN(static_cast<int>(iter_search->End.y) - static_cast<int>(iter_search->Start.y));
				int sdxa = ABS(sdx);
				int sdya = ABS(sdy);

				bool bothhorizontal = (dya == 0 && sdya == 0);
				bool bothvertical = (dxa == 0 && sdxa == 0);
				bool bothsamediagonal = (dx == sdx && dy == sdy) || (dx == -sdx && dy == -sdy);

				if (bothhorizontal || bothvertical || bothsamediagonal) {
					if (iter_search->Start == start) {
						start = iter_search->End;
						couldcombine = combined = true;
					}
					else if (iter_search->End == start) {
						start = iter_search->Start;
						couldcombine = combined = true;
					}
					else if (iter_search->Start == pos) {
						pos = iter_search->End;
						couldcombine = combined = true;
					}
					else if (iter_search->End == pos) {
						pos = iter_search->Start;
						couldcombine = combined = true;
					}
				}

				if (combined) {
					iter_search = Segments.erase(iter_search);
				}
				else {
					++iter_search;
				}
			}
		} while (couldcombine);

		newsegments.push_back(s);

		if (!Segments.empty()) {
			Segments.erase(Segments.begin());
		}
	} while (!Segments.empty());

	newsegments.swap(Segments);
}
The problem is that occasionally the routine doesn't combine every segment; it will leave a few odd overlapping segments that should have been connected into a single larger segment. I've racked my brain until it hurt over this, so I figured I'd turn it over to the mass intelligence of GDNet to see if anyone can spot what I'm doing wrong.

Share this post


Link to post
Share on other sites
Advertisement
My first guess is that since you're casting to int everywhere, your coordinates are not integers, and thus are not exact values. Since they are generated procedurally, it is possible that a coordinate displayed as "3.0" is actually stored as the binary equivalent of "2.999999999". Thus, when cast to an integer, it becomes "2" instead of "3".

You could do all the calculations in the appropriate floating point type and instead of testing for a delta of 0, test that the absolute value is less than some epsilon value that you can drive in a number of ways.

Alternately, instead of casting the coordinates to integers and using the default truncation, you could round them to the nearest integer.

Share this post


Link to post
Share on other sites
Rounding errors? It looks like there is a lot of rounding here, so having one small error from time to time isn't that strange (for example, this 1.0 is in fact 0.999, so int(0.999)-int(0)==0 while you wanted 1.

What about adding 0.25f to each value before the integer promotion? It will make sure that the integer promotions will work as expected (if all numbers are positive).

Share this post


Link to post
Share on other sites
The coordinates are unsigned int. The cast to int is necessary to avoid overflow issues with negative deltas. The coordinates are guaranteed to be small enough that there is no danger of overflow during the cast.

(And I'm completely familiar with floating point inaccuracy and how to deal with it, but thanks [wink])

Share this post


Link to post
Share on other sites
Consider the vector of segments:
0,0 -> 1,0
1,0 -> 2,0
2,0 -> 3,0
After one iteration you have the following:
newsegments:
0,0 -> 2,0
Segments:
2,0 -> 3,0
but the contents newsegments can never be merged with the contents of Segments.


EDIT: Nope, misread your code. I can't see anything wrong. Are you sure your inputs are well-formed?

I tried rewriting your code (been doing a lot of this sort of thing at work). Completely untested:
int sign(int value)
{
if (value == 0)
{
return 0;
}
if (value > 0)
{
return 1;
}
return -1;
}

void CombineLinearSegments()
{
PruneDuplicateSegments();
bool modified;
do
{
modified = false;
for (vector<Segment>::iterator segment = Segments.begin(), segments_end = Segments.end(); segment != segments_end; ++segment)
{
int dx = sign(static_cast<int>(segment->End.x) - static_cast<int>(segment->Start.x));
int dy = sign(static_cast<int>(segment->End.y) - static_cast<int>(segment->Start.y));
for (vector<Segment>::iterator other_segment = segment + 1; other_segment != segments_end;)
{
int other_dx = sign(static_cast<int>(other_segment->End.x) - static_cast<int>(other_segment->Start.x));
int other_dy = sign(static_cast<int>(other_segment->End.y) - static_cast<int>(other_segment->Start.y));
if ((dx == other_dx && dy == other_dy) || (dx == -other_dx && dy == -other_dy))
{
if (segment->Start == other_segment->Start)
{
segment->Start = other_segment->End;
}
else if (segment->Start = other_segment->End)
{
segment->Start = other_segment->Start;
}
else if (segment->End = other_segment->Start)
{
segment->End = other_segment->End;
}
else if (segment->End = other_segment->End)
{
segment->End = other_segment->Start;
}
else
{
continue;
}
std::swap(*other_segment, Segments.back());
Segments.pop_back();
segments_end = Segments.end();
modified = true;
}
}
}
} while (modified);
}


Σnigma

[Edited by - Enigma on June 30, 2008 2:08:55 PM]

Share this post


Link to post
Share on other sites
Only one problem with your rewrite - it doesn't properly handle segments that are oriented in opposite directions. For instance, (0,0)-(1,0) should combine with (2,0)-(1,0) because they are colinear, but since you do a comparison of the sign rather than the absolute value of the sign, these cases will be missed. Once your code is updated to handle that particular edge case, it's effectively isomorphic to mine.


Thanks for the effort, though [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQ
Only one problem with your rewrite - it doesn't properly handle segments that are oriented in opposite directions. For instance, (0,0)-(1,0) should combine with (2,0)-(1,0) because they are colinear, but since you do a comparison of the sign rather than the absolute value of the sign, these cases will be missed. Once your code is updated to handle that particular edge case, it's effectively isomorphic to mine.
(0,0)-(1,0)
dx = 1
dy = 0
(2,0)-(1,0)
other_dx = -1
other_dy = 0
((1 == -1 && 0 == 0) || (1 == 1 && 0 == 0)) == true

I agree that our code should be exactly equivalent, but given that they were written from scratch by two different people it gives you a point of differentiation. If they both produce the same output it would strongly imply the error lies in the inputs, if they produce different output then at least one algorithm is incorrect and they can be piecewise compared to discover the difference.

Σnigma

Share this post


Link to post
Share on other sites
Ah you're right, I misread the boolean logic.


However, there's another issue - iterator invalidation. When two segments are successfully collapsed, the pop_back call invalidates the iterator pointing to the final element in the vector. If that element was in the process of being combined, the next run through the loop will trigger a failure.

That was the original rationale behind using a secondary container to build up the list - since I had to both modify an item in-place and remove it while doing two nested loops, it was easier to take the hit on storage than try to muddle through a hack to get the iterators working properly. Since this is a preprocessing routine anyways, the extra overhead is unimportant.

Share this post


Link to post
Share on other sites
Can't you provide a simple minimal case where the code fails?(you mentioned it fails occasionally) It would be easier to find the problem this way...

Share this post


Link to post
Share on other sites
Well, it turned out to be a problem in the input data. There were some degenerate segments that started and ended on the same point. Problem is, since the length was 0, they never showed up on the debug display. I had to filter by hand through a list of several hundred segments, but at least I found it [smile]


Thanks all for the contributions!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!