search

grimsa / polysplit

An implementation of polygon splitting algorithm (unfinished)
MIT License
10 stars 6 forks source link

Incorrect vertex projection for perpendicular edges #4

Open grimsa opened 8 years ago

grimsa commented 8 years ago

As perpendicular edges (e.g. AB and CD, where A(0;0), B(0;20), C(5;10) and D(15;10)) have two equally viable angle-bisectors, some vertexes are projected along one, and some - along another bisector, leading to incorrectly determined projection points.

See failing test case: de.incentergy.geometry.utils.GeometryUtilsTest.GetProjectedPointTest#projectionForPerpendicularIntersectingEdges()

grimsa commented 8 years ago

Potential solution documented here: http://www.khetarpal.org/polygon-splitting/#comment-2449214878

For that we have to consider the orientation of both edges. For example, if we are traversing along the ring of the polygon, the bounded are will always lie on the left of each edge (or right, depending on direction of traversal). Let's say we are traversing in the direction of ABCDEF..., then polygon's area is on the left of each edge. Now if we have a pair of perpendicular edges, we can take the direction of both of them (left+left) and that will give us a quadrant. E.g. for AB and FG it would be the AFG one, for AB and DE it would be BED. Then the angle bisector we are interested in will be in that quadrant. And the rest is easy then. 1b