Skip to main content
added 11 characters in body
Source Link
wondra
  • 4.9k
  • 1
  • 22
  • 36

To test whether a point lies inside of polygon you have some options, most notablybest known crossing number algorithm andor more "stable" winding algorithm(there is pretty fast implementation too).
Alternatively, you can also use some of spatial partitioning algorithms too, most notably BSP-type. While spatial partitioning will probably offer superior query performance, it will require dynamic updating structure(if rooms can be changed later) - there are dynamic variations of those algorithms, but it will be significantly harder to implement.

To test whether a point lies inside of polygon you have some options, most notably crossing number algorithm and winding algorithm(there is pretty fast implementation too).
Alternatively, you can also use some of spatial partitioning algorithms too, most notably BSP-type. While spatial partitioning will probably offer superior query performance, it will require dynamic updating structure(if rooms can be changed later) - there are dynamic variations of those algorithms, but it will be significantly harder to implement.

To test whether a point lies inside of polygon you have some options, best known crossing number algorithm or more "stable" winding algorithm(there is pretty fast implementation too).
Alternatively, you can also use some of spatial partitioning algorithms too, most notably BSP-type. While spatial partitioning will probably offer superior query performance, it will require dynamic updating structure(if rooms can be changed later) - there are dynamic variations of those algorithms, but it will be significantly harder to implement.

Source Link
wondra
  • 4.9k
  • 1
  • 22
  • 36

To test whether a point lies inside of polygon you have some options, most notably crossing number algorithm and winding algorithm(there is pretty fast implementation too).
Alternatively, you can also use some of spatial partitioning algorithms too, most notably BSP-type. While spatial partitioning will probably offer superior query performance, it will require dynamic updating structure(if rooms can be changed later) - there are dynamic variations of those algorithms, but it will be significantly harder to implement.