CODEWITHSUNDEEP
computational-geometrykdtree
sabari
sabari

Reputation: 849

Finding number of lattice points inside a region

Given a set of points in 2-D plane, How to find number of points lying on or inside any arbitrary triangle.
One method is to check all points whether they lie inside the given triangle.
But I read that Kd-tree can be used to find the number of points lying within a region in O(log n) time, where 'n' is number of points. But I did not understand how to implement that.
Is there any other simpler method to do that?
Or kd-tree will work? If so can someone explain how?

Upvotes: 1

Views: 848

Answers (1)

Ante
Ante

Reputation: 5448

It can be done by recursively checking position of sub-partitions to a triangle. To see which points of a tree node are in a triangle, check each of a node partition (there are 2 in a k-d tree) is it whole in a triangle, is it outside of a triangle or is it intersecting triangle. If partition is in triangle than add number of points in that partition to a result, if partition is out of triangle than do nothing for that partition, if partition intersects triangle than make same check for a sub-partitions of that partition.

For this, each tree node has to store number of points in its sub-tree, which is easy to do in tree creation.

Running time depends on a number of intersections of triangle edges with a partition boundaries. I'm not sure is it O(log n) in the worst case.

Upvotes: 1

Related Questions