Fix checking if polygon is convex #68
Conversation
WalkthroughThis update introduces an enumeration type Changes
Possibly related PRs
Poem
Tip ⚡🧪 Multi-step agentic review comment chat (experimental)
📜 Recent review detailsConfiguration used: CodeRabbit UI 📒 Files selected for processing (1)
⏰ Context from checks skipped due to timeout of 90000ms (4)
🔇 Additional comments (7)
✨ Finishing Touches
🪧 TipsChatThere are 3 ways to chat with CodeRabbit:
Note: Be mindful of the bot's finite context window. It's strongly recommended to break down tasks such as reading entire modules into smaller chunks. For a focused discussion, use review comments to chat about specific files and their changes, instead of using the PR comments. CodeRabbit Commands (Invoked using PR comments)
Other keywords and placeholders
CodeRabbit Configuration File (
|
There was a problem hiding this comment.
Pull Request Overview
This PR improves the convex polygon checking by adding assertions in the triangulation tests and introduces new utility functions and tests for generating regular and star-shaped (pentagram) polygons. The changes include:
- Adding an extra assertion in test_triangulate_polygon_py_convex to ensure the polygon is convex.
- Introducing helper functions (generate_regular_polygon, pentagram, rotation_matrix) for generating test polygons.
- Adding new parametrized tests that validate the convexity check on rotated and self-intersecting polygons.
Comments suppressed due to low confidence (2)
src/tests/test_triangulate.py:707
- Using 4pi in the pentagram function may be confusing; consider adding a comment to explain why a 4pi range is needed for generating the star shape.
angles = np.linspace(0, 4 * np.pi, n, endpoint=False)
src/tests/test_triangulate.py:704
- [nitpick] Consider renaming 'pentagram' to 'generate_pentagram' for consistency with 'generate_regular_polygon'.
def pentagram(reverse):
|
@coderabbitai review |
✅ Actions performedReview triggered.
|
There was a problem hiding this comment.
Actionable comments posted: 1
🧹 Nitpick comments (1)
src/PartSegCore_compiled_backend/triangulation/intersection.hpp (1)
132-153: Update function documentation to match enum return type.The function implementation correctly returns the Orientation enum values, but the documentation still refers to returning integer values 0, 1, and 2.
/** * Determines the orientation of the triplet (p, q, r). * * @param p The first point. * @param q The second point. * @param r The third point. * -* @return 0 if p, q and r are collinear. -* 1 if the triplet (p, q, r) is in a clockwise orientation. -* 2 if the triplet (p, q, r) is in a counterclockwise orientation. +* @return Orientation::COLLINEAR if p, q and r are collinear. +* Orientation::CLOCKWISE if the triplet (p, q, r) is in a clockwise orientation. +* Orientation::COUNTERCLOCKWISE if the triplet (p, q, r) is in a counterclockwise orientation. */
📜 Review details
Configuration used: CodeRabbit UI
Review profile: CHILL
Plan: Pro
📒 Files selected for processing (4)
src/PartSegCore_compiled_backend/triangulation/intersection.hpp(3 hunks)src/PartSegCore_compiled_backend/triangulation/point.hpp(1 hunks)src/PartSegCore_compiled_backend/triangulation/triangulate.hpp(3 hunks)src/tests/test_triangulate.py(2 hunks)
⏰ Context from checks skipped due to timeout of 90000ms (3)
- GitHub Check: Build wheels on macos-13
- GitHub Check: Build wheels on ubuntu-latest
- GitHub Check: Build wheels on windows-latest
🔇 Additional comments (9)
src/PartSegCore_compiled_backend/triangulation/triangulate.hpp (3)
606-634: Good implementation of polygon simplicity check.The function correctly checks if a polygon is simple by verifying that all angles are in non-decreasing order when traversing the vertices. The calculation handles angle normalization properly.
648-664: Good enhancements to convexity check.The changes to the
_is_convexfunction improve the code by:
- Handling edge cases (polygons with fewer than 3 points)
- Early returning true for triangles (which are always convex)
- Using the new
Orientationenum for better readability- Proper initialization of orientation variable
665-690: Well-integrated simplicity check.The function correctly uses the polygon's orientation to determine whether to check simplicity in forward or reverse order. This ensures correct handling of both clockwise and counterclockwise polygon definitions.
src/PartSegCore_compiled_backend/triangulation/intersection.hpp (1)
115-119: Good introduction of Orientation enum.Replacing integer literals with named constants improves code readability and maintainability. This enum clearly represents the three possible orientations of points.
src/tests/test_triangulate.py (5)
697-702: Well-implemented regular polygon generator.The function correctly generates regular polygons with configurable parameters. The use of numpy functions for angle generation and coordinate calculation is efficient.
704-711: Good pentagram generator for testing self-intersecting shapes.The function correctly generates a pentagram by using angles that span 4π radians rather than 2π, creating the star pattern. This is useful for testing self-intersecting polygons.
713-720: Correct implementation of 2D rotation matrix.The function correctly implements a 2D rotation matrix using numpy. The conversion from degrees to radians is properly handled.
725-732: Good test for self-intersecting polygons.This test ensures that self-intersecting shapes like pentagrams are correctly identified as non-convex, regardless of rotation angle or winding order.
734-742: Comprehensive test for convex polygon detection.This test verifies convexity detection across a range of regular polygons with different vertex counts, rotation angles, and winding orders. This provides thorough coverage of the convexity check functionality.
There was a problem hiding this comment.
Actionable comments posted: 1
🧹 Nitpick comments (4)
src/PartSegCore_compiled_backend/triangulation/point.hpp (3)
211-223: Consider adding documentation for the centroid function.The function correctly calculates the centroid of a collection of points and handles empty input appropriately. However, it would benefit from documentation comments that explain its purpose, parameters, and return value, similar to other functions in this file.
+/** + * Calculates the centroid (geometric center) of a set of points. + * + * If the input vector is empty, returns a point at the origin (0, 0). + * Otherwise, computes the average of all points' coordinates. + * + * @param point_list A vector of Point objects + * @return The centroid as a Point + */ Point centroid(const std::vector<Point> &point_list) { if (point_list.empty()) { return {0, 0}; } Point res(0, 0); for (auto &point : point_list) { res.x += point.x; res.y += point.y; } res.x /= float(point_list.size()); res.y /= float(point_list.size()); return res; }
220-221: Consider using static_cast for type conversion.Replace C-style cast with static_cast for more explicit type conversion, which is preferred in modern C++.
- res.x /= float(point_list.size()); - res.y /= float(point_list.size()); + res.x /= static_cast<float>(point_list.size()); + res.y /= static_cast<float>(point_list.size());
212-214: Use consistent initialization style.For consistency with the rest of the code, consider using the same initialization style throughout the function.
if (point_list.empty()) { - return {0, 0}; + return Point(0, 0); }src/PartSegCore_compiled_backend/triangulation/intersection.hpp (1)
179-184: Use enum values in conditional checks for better clarityWhile these comparisons will work due to implicit conversion between enum and int, it would be more consistent to use the enum values explicitly.
-if (o1 != o2 && o3 != o4) return true; +if (o1 != o2 && o3 != o4) return true; -if (o1 == 0 && _on_segment(p1, p2, q1)) return true; -if (o2 == 0 && _on_segment(p1, q2, q1)) return true; -if (o3 == 0 && _on_segment(p2, p1, q2)) return true; -if (o4 == 0 && _on_segment(p2, q1, q2)) return true; +if (o1 == Orientation::COLLINEAR && _on_segment(p1, p2, q1)) return true; +if (o2 == Orientation::COLLINEAR && _on_segment(p1, q2, q1)) return true; +if (o3 == Orientation::COLLINEAR && _on_segment(p2, p1, q2)) return true; +if (o4 == Orientation::COLLINEAR && _on_segment(p2, q1, q2)) return true;
📜 Review details
Configuration used: CodeRabbit UI
Review profile: CHILL
Plan: Pro
📒 Files selected for processing (2)
src/PartSegCore_compiled_backend/triangulation/intersection.hpp(2 hunks)src/PartSegCore_compiled_backend/triangulation/point.hpp(1 hunks)
⏰ Context from checks skipped due to timeout of 90000ms (4)
- GitHub Check: Test on windows-latest with Python 3.10
- GitHub Check: Test on windows-latest with Python 3.9
- GitHub Check: Test on windows-latest with Python 3.12
- GitHub Check: Test on windows-latest with Python 3.11
🔇 Additional comments (3)
src/PartSegCore_compiled_backend/triangulation/intersection.hpp (3)
115-119: Great addition of an Orientation enum!This is a good refactoring that replaces magic numbers with descriptive named constants, making the code more readable and self-documenting.
128-132: Documentation update correctly reflects the enum changeThe function documentation has been properly updated to reference the new enum values instead of integer literals.
153-154: Return statements correctly use the new enum valuesThe function logic has been updated to properly return enum values instead of integer literals, which is consistent with the function signature change.
There was a problem hiding this comment.
Pull Request Overview
This PR enhances polygon validation by improving convexity checks and expanding test coverage for various polygon configurations and rotations.
- Added an assertion to validate convex polygons in the triangulation test.
- Introduced helper functions to generate regular and self-intersecting polygons, as well as a rotation matrix function.
- Added new test cases to verify behavior on rotated polygons and self-intersecting shapes.
Comments suppressed due to low confidence (2)
src/tests/test_triangulate.py:709
- [nitpick] Consider adding an error message to the assertion to clarify that 'n' must be odd for generating a self-intersecting polygon.
assert n % 2 == 1
src/tests/test_triangulate.py:741
- [nitpick] Consider renaming 'test_is_convex2' to a more descriptive name like 'test_regular_polygon_convex' to better convey its purpose.
def test_is_convex2(angle, n_vertex, reverse):
There was a problem hiding this comment.
Actionable comments posted: 0
🧹 Nitpick comments (1)
src/tests/test_triangulate.py (1)
716-722: Add type hints to rotation_matrix function.While the implementation is correct, the function lacks type hints unlike the other new utility functions.
-def rotation_matrix(angle): +def rotation_matrix(angle: float) -> np.ndarray: return np.array( [ [np.cos(np.radians(angle)), -np.sin(np.radians(angle))], [np.sin(np.radians(angle)), np.cos(np.radians(angle))], ] )
📜 Review details
Configuration used: CodeRabbit UI
Review profile: CHILL
Plan: Pro
📒 Files selected for processing (1)
src/tests/test_triangulate.py(2 hunks)
⏰ Context from checks skipped due to timeout of 90000ms (4)
- GitHub Check: Test on windows-latest with Python 3.12
- GitHub Check: Test on windows-latest with Python 3.11
- GitHub Check: Test on windows-latest with Python 3.10
- GitHub Check: Test on windows-latest with Python 3.9
🔇 Additional comments (5)
src/tests/test_triangulate.py (5)
211-211: Good addition of convexity verification.Adding the assertion to verify that the polygon is actually convex before testing ensures the triangulation algorithm is only tested with valid inputs. This makes the test more robust and better aligned with the function's preconditions.
697-702: Well-implemented polygon generation utility.This function correctly implements regular polygon generation with proper type hints and parameterization. The ability to control orientation with the
reverseparameter adds flexibility for testing various scenarios.
704-714: Good implementation of self-intersecting polygon generator.The function ensures proper self-intersection by doubling the angle range to 4π. The assertion that checks for an odd number of vertices is a good safeguard to ensure the generated polygon will actually self-intersect as intended.
729-736: Comprehensive test for non-convexity of self-intersecting polygons.Great use of parametrization to test multiple configurations of self-intersecting polygons. The test ensures that the
is_convexfunction correctly identifies self-intersecting polygons as non-convex, regardless of rotation angle, vertex count, and orientation.
738-746: Thorough verification of convexity across polygon variations.This test effectively verifies that regular polygons are correctly identified as convex under various conditions including rotation, different vertex counts, and orientation. The comprehensive parametrization ensures good test coverage.
There was a problem hiding this comment.
Actionable comments posted: 0
🧹 Nitpick comments (2)
src/tests/test_triangulate.py (2)
716-722: Correctly implemented rotation matrixThe rotation matrix function is mathematically correct and properly converts the angle from degrees to radians using numpy's functions.
Consider adding a docstring to clarify that the angle is in degrees, since the function converts it to radians internally.
def rotation_matrix(angle: float) -> np.ndarray: + """Create a 2D rotation matrix for the given angle in degrees.""" return np.array( [ [np.cos(np.radians(angle)), -np.sin(np.radians(angle))], [np.sin(np.radians(angle)), np.cos(np.radians(angle))], ] )
738-745: Comprehensive test for convex polygonsThis test thoroughly verifies that regular polygons maintain their convexity property after rotation, with good coverage across different vertex counts and orientations.
Consider renaming
test_is_convex2to something more descriptive liketest_is_convex_regular_polygonto better reflect what it's testing.-def test_is_convex2(angle, n_vertex, reverse): +def test_is_convex_regular_polygon(angle, n_vertex, reverse):
📜 Review details
Configuration used: CodeRabbit UI
Review profile: CHILL
Plan: Pro
📒 Files selected for processing (1)
src/tests/test_triangulate.py(2 hunks)
🔇 Additional comments (5)
src/tests/test_triangulate.py (5)
211-211: LGTM: Improved input validationAdding this assertion is good practice as it ensures the test correctly validates that input polygons are convex before proceeding with triangulation tests.
697-702: Well-implemented polygon generation utilityThis helper function is well-implemented using numpy's vectorized operations. It provides a clean way to generate regular polygons for testing, including the ability to control orientation via the
reverseparameter.
704-714: Good implementation with appropriate validationThe self-intersecting polygon generation function is well-implemented with proper validation to ensure an odd number of vertices (which is required for the implementation to work correctly).
725-726: Good set of test anglesThis selection of angles provides good coverage for testing rotations, including edge cases (near 0°, near 90°, and near 360°).
728-736: Comprehensive parametrized test for non-convex polygonsThis test thoroughly verifies that self-intersecting polygons are correctly identified as non-convex across various configurations and rotations. The parametrization ensures good test coverage.
There was a problem hiding this comment.
Pull Request Overview
This PR enhances polygon validation by adding improved convexity checks and new testing functions.
- Introduces explicit assertions for polygon convexity in triangulation tests.
- Adds helper functions for generating both regular and self-intersecting polygons, along with a rotation matrix utility.
- Expands tests to validate behavior under various rotations and polygon configurations.
Comments suppressed due to low confidence (1)
src/tests/test_triangulate.py:709
- Consider revising the error message to be more grammatically clear, e.g., 'an odd number is required to generate a self-intersecting polygon'.
assert n % 2 == 1, 'need odd number to generate self-intersecting polygon'
Summary by CodeRabbit
New Features
Refactor
Tests