Package to do rectangle/box intersection?

#1

I need to check if rectanges and (3D boxes) intersect (and evenutally get the resulting rectange/box.
Is there any Haskell package doing this ?

1 Like
#2

You can try hgeometry: Geometric Algorithms, Data structures, and Data types., I don’t know if it has what you seek, but it has many geometric algorithms.

Edit: I found these:

instance (Ord r, Arity d) => HasIntersectionWith (Box d p r) (Box d q r)

Defined in Data.Geometry.Box.Internal

Methods

intersects :: Box d p r → Box d q r → Bool

instance (Ord r, Arity d) => IsIntersectableWith (Box d p r) (Box d q r)

Defined in Data.Geometry.Box.Internal

Methods

intersect :: Box d p r → Box d q r → Intersection (Box d p r) (Box d q r)

1 Like
#3

That’s exactly what I was looking for. I had a look a hgeometry but couldn’t find the HasIntersection instances for Boxes. Thanks

#4

Author of HGeometry here: Unfortunately, the latest version on hackage may not be in the best shape :(. I’ve been working on an update that uses a more classy-approach, so that it is easier to run the algorithms on custom data types (e.g. compute a convex hull of a list of [MyColoredPoints] directly, rather than having to convert them into something of type Point 2 R :+ AdditionalInformationSuchasColor]. Work has been progressing somewhat slowly though, and there are a lot of small changes in the type signatures of existing implementations to make that work. If anyone is interested, this latest version is at this branch: GitHub - noinia/hgeometry at hgeom1_again (I think I didn’t port rectangle intersection yet though; but I think that should not be too difficult).

3 Likes
#5

I use my cute_c2.h bindings macaroni.dev / cute-c2-hs ¡ GitLab for 2D collisions. Not on Hackage but I really should do that last mile.

It has AABBs but also circles, capsules, and arbitrary polygons.

It can do a boolean check or provide a collision manifold.

It also has a GJK implementation and a TOI (time-of-impact) algorithm built on top of that.

I’m not aware of any single-header library for 3D, but maybe I should ask around in the cute framework discord about that. C developers make some nice stuff.

1 Like
#6

I asked RandyGaul on the cute framework discord:

is there any nice library a la cute_c2.h but for 3D collisions out there? I love using cute_c2.h from Haskell (pure functions + single header makes it easy), but I haven’t been able to find a equally “low-level” 3D library. Those routines are usually included in larger physics engines.

He responded:

It doesn’t really exist
I could make one but I’m not developing a 3D game yet
Here is the closest one col.md ¡ GitHub
I actually helped Micha write the GJK function, as well as some other bits
it’s a missing library
Many people have asked for it over the years so there’s certainly a lot of demand

I did a survey myself, and I found a few other C libraries that are adjacent to this:

But nothing quite there.

If I were to implement it, tbh I might do C w/Haskell bindings on top just because more people could benefit from it.

1 Like
#7

While the question, if two bounding boxes (even is the Box is a rectangle :wink: intersect is very common, most of the time you are not interested in the actual intersection. This is something e.g. CAD software (or vector drawing programs) needs, you have to search for “constructive solid geometry”, CSG. In your case, one for “primitives” suffices.
So, searching for csg on hackage yields for example implicit: Math-inspired programmatic 2&3D CAD: CSG, bevels, and shells; gcode export..
And mecha mecha: A constructive solid geometry (CSG) modeling language.

1 Like
#8

I realized that the problem is simpler than I thought so I implemented it myself.

For information


affDimensionIntersection :: AffDimension -> AffDimension -> Maybe AffDimension
affDimensionIntersection a b = let
    bottomLeft = maxDimension [aBottomLeft a, aBottomLeft b]
    topRight = minDimension [aTopRight a, aTopRight b]
    in
         if and $ Prelude.zipWith (<) (dimensionToList bottomLeft) (dimensionToList topRight)
         then Just (AffDimension bottomLeft topRight)
         else Nothing

However, I also have other rectangle and box operations which could have benefitted from ‘hgeometry’.

(I can see that this geometry started in 2019 a few years later than my project), so I might be interested in replacing my bits

by a more robust external package. Unfortunately I am currently put off using geometry for two (silly) reasons, the dependency from vinyl

and the use of typeclasses. Typeclass might be a good idea from a designer point of view but make discoverability a nightmare (from the end user).

The regex typeclass interface is a good example of how typeclass based API are hard to use.

Another example, I looked at hgeometry before creating this post, but couldn’t find that it offers boxes intersection.

@Ambrose

Thanks for the link. However in my case, this is an overkill. My problem is far simpler than real time collision detection. I should have made it clearer
I just need the intersection of “rectangles” as in rectangles parallel to the axes (i.e. two corners) compared to free rectangles which can be rotated, which is in fact fairly straightforward to do.
Also It’s for boxes in a warehouse, so no real time involved, so no need to be “C” fast.

1 Like
#9

Unfortunately I am currently put off using geometry for two (silly) reasons, the dependency from vinyl
and the use of typeclasses. Typeclass might be a good idea from a designer point of view but make > discoverability a nightmare (from the end user).

I guess that means you will both be happy and unhappy with the current (in development) version ;). It no longer depends on vinyl (or at least; it doesn’t use it anymore to represent the intersection type). But it does more heavily depend on typeclasses. I’ll try to make sure/improve the documentation so that it is still easy to see what operations are available for a particular type.

2 Likes