TRAKLA2 - Point in Polygon with R-Tree

Point in Polygon with R-Tree

Hide text Show text Hide pseudo-code Show pseudo-code
Task Instructions Find out whether points 1 and 2 are inside or outside a given polygon by examining the number of times a half-line drawn from a point intersects the polygon. The edges of the polygon are stored in an R-Tree. In order to measure whether the points are inside or outside the polygon you must open those nodes of the R-Tree that intersect the half-line drawn from a point. The half-line can be drawn by selecting a point by mouse. You must examine the points in order. A node of the R-tree can be selected by clicking it with the mouse. A selected node can be opened by clicking it again. When the algorithm finds intersection points, you must upkeep the number of points found in the counter below the visualization. Whether a point is inside or outside the polygon can be answered in the pull-down menu.
main Point in Polygon 1. Let root be the root node of the R-Tree and let p be the point being tested 2. point_in_polygon(root, p) POINT_IN_POLYGON(Node node, Point q) 1. let line l be a ray starting from q and parallel to the positive x-axis 2. intersections = 0 // preorder traversal 3. initialize stack S 4. S.push(node) 5. while (S.notEmpty()) do 6. nextNode = S.pop() 7. let r be the region occupied by nextNode 8. if l intersects r 9. if (node.isLeaf()) 10. for all edges e stored in node 11. if l intersects e 12. increment intersections 13. else 14. for all children nodes child of nextNode from right to left 15. S.push(child) 16. if intersections is odd 17. return true 18. else 19. return false