How to check if a line intersects a convex polygon?
Suppose you are given the equation of a line (in 2d) and equations of the lines forming a convex polygon (the polygon can be unlimited). How to determine if a line intersects a polygon?
Also, are there computational geometry libraries where such tasks are predefined? I ask because I'm not only interested in 2D version but also in n-dimensional geometry.
source to share
For the 2D case, I think the problem is simplified a little.
The line divides the space into two areas.
If the polygon is present in only one of these areas, then the line does not intersect it.
If the polygon is present in both areas, then the line intersects it.
So:
Take any perpendicular to the line, making an intersection with enter the origin.
Project each vertex of the polyhedron onto a perpendicular.
If these projections occur with both signs, then the polygon intersects the line.
[Update after elexhobby's comment.]
Forgot to enable unrestricted case handling.
I wanted to add that it is possible to create a "virtual vertex" to represent the open area. We really need the "direction" of the open area. We can think of this as the average of the vectors for the edge of the open area.
We then process the dot product of that direction with the normal and add it to the set of vertex projections.
source to share
In geometry, usually see wikipedia , the polygon is limited. What you describe is usually called a polyhedron or polyhedron see Wikipedia
There are several geometry libraries available, two that come to mind are boost (polygon) and CGAL. Typically, there is a clear separation between computational methods that deal with 2d, 3d and Nd - for obvious reasons.
For your problem, I would use multiple binary space with a split tree. I would take the first line of your "poly" and cut the query line against it, creating a ray. The beam started at the intersection of two lines and continued towards the interior of the half-space created by the first "poly" line. Now I will repeat the procedure with the ray and the second "poly" line. (this can generate a segment instead of a ray). If at some point the beginning of the ray (or now the segment) lies on the outside of the polyline in question and does not intersect it, then the answer will not be - the line does not intersect your "poly". Otherwise, it intersects. Pay special attention to different cases with parallel edges. Straight forward enough and works for multidimensional cases.
source to share
I'm not entirely sure, but I think you can address this with duality. First normalize your line equations as you a.x+b.y=1
would consider many points (a,b)
.
They should form a convex polygon, and I am guessing that the newline may not correspond to a point within the polygon. This can be easily verified by confirming that the new point is on the same side of all edges. (If you don't know the order of the lines, create a convex hull first.)
source to share
Let's start with finite polygons.
To cross a polygon, a line must cross one of its edges. An intersection between a line and an edge is only possible if the two points are on opposite sides of the line.
This can be easily verified by using sign(cross_product(Ep-Lp,Ld))
for two edge points. Ep
- regional point Lp
- a point on the line Ld
- the direction vector of the line cross_product(A,B)=Ax*By-Ay*Bx
.
To solve infinite polygons, we can introduce "infinite points". If we have half an infinite edge with a point E1
and a direction Ed
, its "second point" will be something like E1+infinity*Ed
, where infinity
is "a large enough number".
For infinite points, the check will be slightly different:
cross_product(Ep-Lp,Ld)=
=cross_product(E1+infinity*Ed-Lp,Ld)=
=cross_product(E1-Lp+infinity*Ed,Ld)=
=cross_product(E1-Lp,Ld)+cross_product(infinity*Ed,Ld)=
=cross_product(E1-Lp,Ld)+infinity*cross_product(Ed,Ld)
If cross_product(Ed,Ld)
equal to zero (the line is parallel to the edge), the sign will be determined by the first component. Otherwise, the second component will dominate and determine the sign.
source to share