Add edge intersection test to Contains3D

[ikeough]

It might not be enough to only check vertices in non-convex cases. Consider to check edge intersections, see image.

_Originally posted by @aothms in https://github.com/hypar-io/Elements/pull/638#discussion_r792408055_

[DmytroMuravskyi]

There is Cover function that also checks Polygon and it checks for edge intersections but it's 2d oriented (uses Intersects2d). Its logic can be reused in Contains with adjustment that Contains only wants Inside result and not CoincidesAtEdge/Vertex.

It will fix this problem, but, in my opinion, there is some confusion between Cover/Contains/Contains3d functions.

• Some functions use Clipper lib: bool Contains(Polygon polygon) and bool Covers(Vector3 vector) while other have custom implementation.
• All Covers function state that they return true when "is within this Polygon or coincident with an edge" while Contains - "without coincidence with an edge or vertex". But Contains3D (and a function calling it) says "is within this Polygon or coincident with an edge." and returns accordingly breaking understanding of difference between the two.
• Some functions say "when compared on a shared plane." but they work only on XY plane, like bool Contains(Polygon polygon) where Clipper with 2d IntPoint is used or bool Covers(Polygon polygon) where Intersects2d is called.

In my opinion, ideally, there should be one private implementation (based on Clipper or custom implementation) for Point-Polygon containment and one for Polygon-Polygon containment that works efficiently on XY plane and different public function can be built on top of it depending on how they treat CoincidesAtEdge/Vertex case, do they expect 2d or 3d input. And if 3d input is expected then shared plane is first converted to XY plane.

[wynged]

how long do you think the larger effort would take? I think if we can time box it to 1/2 days, fix this bug, and preserve existing tests then it sounds like a good idea. If it's a longer effort let's do the quick fix for now and maybe make another issue to track these findings, but it doesn't have to be part of 2.1 milestone.

[DmytroMuravskyi]

The changes will fit in two days as all code is there it's just about interface being clear and code is reused. It's good idea to create another issue for this as it would require same amount of discussion. I'll focus on adding edge intersection test to Contains3D as well as make sure that all functions reusing the same internal algorithms.