🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Find infinity or a rect from set of 'halfspaces' 2d

Started by
2 comments, last by _WeirdCat_ 5 years, 7 months ago

First i need to define what halfspace for me is: a set of two lines one vertical and one horizontal [ they ofc are defined (A1, B1, C1) and (A2, B2, C2)] and a point at which those lines intersect)

The available halfspace is always behind these two lines.

But i need somehow to find areas where this set of halfspaces define (it can be a rect or just an halfspace with a intersection point - i meant that i cant define infinity (well actually i could because i anyway cut a space to some xy dimension so nothing that exceeds those values wont exist ok so from now one i need only to find rectangles that are defined by these halfspaces (the best would be all points. 

 

See image below i am trying to find blue rects.

Hopefully one will understand what in trying to do if not tell me ill try to describe that more naturally

IMG_20181113_184259.jpg

Advertisement
4 hours ago, _WeirdCat_ said:

Hopefully one will understand

Not really, but what you describe sounds like building / using a 2D BSP tree.

There the definition of 'Halfspace' is one or the other side of a single line which seperates them. (The line can have start and end point, but it is extended to infinity when dividing space.)

Then each of the two spaces can be divided further recursively to two child subspaces, using new lines which form intersections with the parent line. (Those intersections clip the child lines so they are no longer infinite.)

The result is always a set of convex cells. Finding Boxes which fall into a certain subspace can be done efficiently by traversing the tree bottom down, and of course you can limit your seperating lines to be axis aligned.

The first Doom game used this kind of trees to define its levels.

Yeah i came up with same conclusion about parenthes of child subspaces etc. Thanks for info

This topic is closed to new replies.

Advertisement