How to pre-process 2D polygon to speed up checking if a point is inside a polygon #8549
Comments
|
You can create a 2D constrained triangulation, and mark the triangles that are inside the polygons. |
|
Thanks! I'll try it out! |
|
I did not understand what you mean with "or not intensively on the same set of polygons." Maybe a drawing would help. |
|
Hi Andreas, I have a bunch of polygons that are already fixed. And I have a huge set of points. I want to know whether a point is inside of a polygon or not, for every pair of point and polygon. Since all the polygons will be queried multiple times, I was wondering if there's any method to pre-process the polygons so I can speed up all the checking. |
|
Insert all the polygons into a 2D arrangement data structure, and then
apply point-location queries.
You can even apply batch point location operations, where you use a bunch
of points and you get the location of each in an efficient way.
____ _ ____ _
/_____/_) o /__________ __ //
(____ ( ( ( (_/ (_/-(-'_(/
_/
…On Sat, 19 Oct 2024 at 00:15, Duo Zhang ***@***.***> wrote:
Hi Andreas,
I have a bunch of polygons that are already fixed. And I have a huge set
of points. I want to know whether a point is inside of a polygon or not,
for every pair of point and polygon. Since all the polygons will be queried
multiple times, I was wondering if there's any method to pre-process the
polygons so I can speed up all the checking.
—
Reply to this email directly, view it on GitHub
<#8549 (comment)>, or
unsubscribe
<https:/notifications/unsubscribe-auth/ABVBNODFEJYM5W3XATWTLXTZ4F26ZAVCNFSM6AAAAABP7QYQBKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDIMRTGI2DEOJXGU>
.
You are receiving this because you are subscribed to this thread.Message
ID: ***@***.***>
|
|
If I understand correctly, the OP does not only want to know if a point is inside any polygon, but also inside which one. Say, for example, you want to assign LiDAR points to a set of 2D building footprint polygons. If I am not mistaken, it is not possible to retrieve the input polygons from face handles returned by the locate function of the 2D constraint triangulation / 2D arrangement? Something like an AABB tree of a set of polygons could help here. But that does not exist either, right? |
|
Of course you can.
It takes a bit more care and processing.
Extend the face record of the underlying halfedge data structure with an
identifier of the polygon.
____ _ ____ _
/_____/_) o /__________ __ //
(____ ( ( ( (_/ (_/-(-'_(/
_/
…On Sat, 19 Oct 2024 at 13:09, Raphael Sulzer ***@***.***> wrote:
If I understand correctly, the OP does not only want to know if a point is
inside any polygon, but also inside which one. Say, for example, you want
to assign LiDAR points to a set of 2D building footprint polygons.
If I am not mistaken, it is not possible to retrieve the input polygons
from face handles returned by the locate function of the 2D constraint
triangulation / 2D arrangement.
Something like an AABB tree of a set of polygons could help here. But that
does not exist either, right?
—
Reply to this email directly, view it on GitHub
<#8549 (comment)>, or
unsubscribe
<https:/notifications/unsubscribe-auth/ABVBNOEH6EUAXAZBNQIIZ7TZ4IVXBAVCNFSM6AAAAABP7QYQBKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDIMRTG4ZTSNRZG4>
.
You are receiving this because you commented.Message ID:
***@***.***>
|
|
I guess it needs more input from @DuoZhangRobotics |
|
|
|
|
|
I have a hard time to single out the different polygons. Can you give them different colors and maybe not more than 10 just for identifying them. |
|
On Sun, 20 Oct 2024 at 18:07, Duo Zhang ***@***.***> wrote:
image.png (view on web)
<https:/user-attachments/assets/80904cab-9485-4279-983c-9e747969c62e>
image.png (view on web)
<https:/user-attachments/assets/9bbf8f60-57b0-4fe4-b8ae-cd0298f18268>
Sorry for the late reply. These are two simple sets of polygons in my
case. They are basically some visible areas from the CGAL's 2D Visiblity
library. If I use the locate functions from CGAL, it seems a little bit too
slow. If I convert the arrangements of the polygons into the polygon class
in CGAL, and then call cgal::bounded_side_2() function, it'll be so much
faster.
No it will not, or better stated, point-location in 2D arrangements is
extremely fast.
As a matter of fact, 2D arrangements are used as the underlying data
structure of most Boolean operations on polygons.
But in this way, I can just use plain C++ implementations with float type,
then I guess it'll be faster than CGAL in this case. And I don't think I
can convert all the polygons to an arrangement and do batch checking here?
Because the polygons have too many intersections among them.
If you can afford spending time on preprocessing, which consists of
constructing the arrangement, then you will benefit from the efficient
point-location. Construction is done with a sweep line alg,. which is
output sensitive and depends on the number of intersections (O(n log k),
where n is the number of edges of all polygons and k is the number of
intersections in your case.)
In this case, AABB tree or BVH wouldn't help too much, but there will be
… some improvements. I'm also thinking about using Cuda or avx to parallelize
everything. But according to my benchmarking, the AVX code doesn't help
much when -O3 is turned on compared with my plain c++ code, but they are
both approximately 2times faster than bounded_side_2() function. I guess
that's because I'm using the exact kernel in CGAL and only using float for
AVX and C++ only code.
—
Reply to this email directly, view it on GitHub
<#8549 (comment)>, or
unsubscribe
<https:/notifications/unsubscribe-auth/ABVBNOHBXM7QBSK6RJEIAO3Z4PBMVAVCNFSM6AAAAABP7QYQBKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDIMRVGAZTINZVGU>
.
You are receiving this because you commented.Message ID:
***@***.***>
|
|
Consider splitting the input set of polygons into subsets of polygons, such
that for each subset the number of intersections is small. (This may not be
easy or even possible...)
____ _ ____ _
/_____/_) o /__________ __ //
(____ ( ( ( (_/ (_/-(-'_(/
_/
…On Sun, 20 Oct 2024 at 18:28, Efi Fogel ***@***.***> wrote:
On Sun, 20 Oct 2024 at 18:07, Duo Zhang ***@***.***> wrote:
> image.png (view on web)
> <https:/user-attachments/assets/80904cab-9485-4279-983c-9e747969c62e>
> image.png (view on web)
> <https:/user-attachments/assets/9bbf8f60-57b0-4fe4-b8ae-cd0298f18268>
> Sorry for the late reply. These are two simple sets of polygons in my
> case. They are basically some visible areas from the CGAL's 2D Visiblity
> library. If I use the locate functions from CGAL, it seems a little bit too
> slow. If I convert the arrangements of the polygons into the polygon class
> in CGAL, and then call cgal::bounded_side_2() function, it'll be so much
> faster.
>
No it will not, or better stated, point-location in 2D arrangements is
extremely fast.
As a matter of fact, 2D arrangements are used as the underlying data
structure of most Boolean operations on polygons.
> But in this way, I can just use plain C++ implementations with float
> type, then I guess it'll be faster than CGAL in this case. And I don't
> think I can convert all the polygons to an arrangement and do batch
> checking here? Because the polygons have too many intersections among them.
>
If you can afford spending time on preprocessing, which consists of
constructing the arrangement, then you will benefit from the efficient
point-location. Construction is done with a sweep line alg,. which is
output sensitive and depends on the number of intersections (O(n log k),
where n is the number of edges of all polygons and k is the number of
intersections in your case.)
In this case, AABB tree or BVH wouldn't help too much, but there will be
> some improvements. I'm also thinking about using Cuda or avx to parallelize
> everything. But according to my benchmarking, the AVX code doesn't help
> much when -O3 is turned on compared with my plain c++ code, but they are
> both approximately 2times faster than bounded_side_2() function. I guess
> that's because I'm using the exact kernel in CGAL and only using float for
> AVX and C++ only code.
>
> —
> Reply to this email directly, view it on GitHub
> <#8549 (comment)>, or
> unsubscribe
> <https:/notifications/unsubscribe-auth/ABVBNOHBXM7QBSK6RJEIAO3Z4PBMVAVCNFSM6AAAAABP7QYQBKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDIMRVGAZTINZVGU>
> .
> You are receiving this because you commented.Message ID:
> ***@***.***>
>
|
Issue Details
Hi,
Thanks in advance for all your help. My code is currently checking whether a point is inside a polygon or not intensively on the same set of polygons. I am wondering if there are any methods that allow me to preprocess the polygon beforehand so I can do the checking a lot faster later. Thanks again.
Duo
Environment
The text was updated successfully, but these errors were encountered: