Skip to main content
gamedev.net
🔒 Locked

removed

Started by pimstead 17 replies 500+ views
Original Post
pimstead
pimstead
removed [Edited by - pimstead on August 30, 2006 8:32:15 AM]
pimstead
pimstead
removed

[Edited by - pimstead on August 30, 2006 8:57:51 AM]
msn12b
msn12b
You need to sort the endpoints of each span, then run through that sorted list, keeping a running total of the spans as such:

1. If you hit the start of a span, add the span to your total.
2. If you hit the end of a span, remove that span from your total.

After each span, if your running total transitions to zero, increment the total number of intervals.

You may run into problems with intervals that are right next to each other, i.e. first.high==second.low. You should also sort the endpoints such that low points have priority.

MSN
pimstead
pimstead
removed

[Edited by - pimstead on August 30, 2006 8:39:17 AM]
pimstead
pimstead
remove

[Edited by - pimstead on August 30, 2006 8:02:39 AM]
clonemaker
clonemaker
eh well i didn''t test this. it is designed to combine overlapping intervals without modifying the intervals array.

    
int CombineIntervals(interval *intervals, int numintervals)
{
int numnonoverlapping=0;
int i;

int *isvalid = (int *)malloc(sizeof(int) *numintervals);
for (i=0; i<numintervals; i++){isvalid<i>=1;}

for (i=0; i<numintervals-1; i++)
{
if (!isvalid[i]) continue;
for (j=i+1; j<numintervals; j++)
{
if (!isvalid[j]) continue;
ilow=intervals[i].low;ihigh=intervals[i].high;
jlow=intervals[j].low;jhigh=intervals[j].high;
if ( (ilow<jhigh) && (ihigh>jlow) )
{
isvalid[j]=0;
intervals[i].low= (ilow<=jlow) ? ilow : jlow;
intervals[i].high= (ihigh>=jhigh) ? ihigh :jhigh;
}
}
}

for (i=0; i<numintervals; i++){numnonoverlapping+=isvalid[i];}
free(isvalid);
return numnonoverlapping;
}




cmaker- I do not make clones.
jaxson
jaxson
People were being... ''bitter'' because that is so obviously a homework problem that it isn''t even funny. There is no need to start spouting off about the wonderful job you have. No one said anything about jobs of any kind except for you. People are just irritated because sometimes there are strings of posts from other people that want their homework done for them with no effort on their part. You can''t learn if you don''t do it yourself.

Next time, something that might get a more friendly response would be "I have this homework problem that I''m completely stuck on. Could someone help me?" I''m sure you''ll get just as many useful answers and quite a few less people telling you not to post homework.
pimstead
pimstead
remove

[Edited by - pimstead on August 30, 2006 8:20:04 AM]
clonemaker
clonemaker
well, I have to say. This is a very interesting algorithm. nice. What I tried to solve by using some array and changing sizes was solved by just adding in a break statment. anyway, i believe the innermost loop can be replaced with:

    
if ((array[counter1].low<=array[counter2].high) &&
(array[counter1].high>=array[counter2].low) )
{
answer--;
break;
}





cmaker- I do not make clones.
Gladiator
Gladiator

That IS a homework question since I've seen the same question asked on another board (www.experts-exchange.com) so I know for sure it is.

/** moderator edit **/
-------------------------------
I'll screw up whoever screws around with the gamedev forum!

..-=gLaDiAtOr=-..

Edited by - felisandria on October 27, 2000 12:53:27 PM
AticAtac
AticAtac
This thread proves it ... Some people have definitly too much time for complaining about other people (obviously me too :-).
The point is, if you dont want to answer a question then its better to not answer it instead of posting "i wont answer this stupid question ...". If you do this then there will be such a thread where ppl start to insult eachother etc.
Just leave the post unanswered ... thats not so difficult or ?
Maybe some people like to answer it and in this case they even did it. His question had something to do with programming so thats ok. Are some of you guys going to define the rules for other people what they are allowed to post and what not ? I dont like this idea.
IF YOU DONT LIKE TO ANSWER A QUESTION WHICH IS HOMEWORK RELATED THEN *DO* *NOT* *ANSWER* ... its so easy.


felisandria
felisandria
Okay people.

I have had a very busy week trying to get a release out the door, and what I do NOT need is to find that the people of my forum think that somehow showing off their curse word vocabulary will make the forum a better place. I''m going to edit the heck out of this thing and the perpetrators had darn well better figure out how to be respectful and polite to their fellow message board inhabitants (and I mean ALL of you). Cussing somebody out isn''t helpful and it isn''t going to impress on them your values regarding what should and shouldn''t be posted (and personally I don''t care whether this is a homework problem or a piece of code to go on the space shuttle. Behave, darnit.)

-fel
~ The opinions stated by this individual are the opinions of this individual and not the opinions of her company, any organization she might be part of, her parrot, or anyone else. ~
logicX
logicX
And all of you are grounded for the weekend!!
Gladiator
Gladiator
Am I the only bad person in here? God, all my posts are gone... oh well, too bad...

-------------------------------
I'll screw up whoever screws around with the gamedev forum!

..-=gLaDiAtOr=-..

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.