#### Archived

This topic is now archived and is closed to further replies.

# Finding sector based on map coords

This topic is 6932 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I currently have my map as a bunch of triangular sectors (which are made up of lines, which are made up of vertices.. lines and vertices are never duplicated. a sector also has 3 pointers to its neighboring sectors. a line is marked as blocking or non-blocking, and only the blocking ones are drawn [as walls]) I need to be able to take two map coordinates and turn them back into the sector they belong to (if they are exactly on a line, it could just choose the first sector that shares that line, but should never return a value saying that these coordinates belong to no sector. that return value is reserved for coordinates outside the map boundaries) Currently the map is implemented as an array of sectors, and I would like to keep this as simple as possible (ie, no bintrees or quadtrees or whatever, but if that is the only feasible way, then so be it) Thanks in advance, Adam M. adamm@san.rr.com

##### Share on other sites
Windows locked up half-way through my first reply, so I''ll make this short:

Take all your lines (3 in this case) and traverse them in clockwise order. I am not sure how you would get them in clockwise order, but I''m guessing that you could start at the leftmost vertex of the 6 you''re working with, and move to the connecting vertex above it. And follow from there.

Treating the lines as planes, check if the point you want is to the right of the line or not. If you precalculate the normals of these lines, this should be a quick operation. If you can''t, I still don''t think it''s a tragedy

If the point is to the right of all your lines/planes, it is within the triangle.

I believe this should work for any convex polygon, although I am no geometry expert these days. Essentially this is a collision detection algorithm.

##### Share on other sites
I am not too good at anything other than square-tile based maps, but here is my suggestion. Feel very free to ignore it.

When you create the map, don''t you know which places are in which sectors? If so, just make every place have a pointer to its sector. Might be a big memory hog, but I think it would work...

--------------------

You are not a real programmer until you end all your sentences with semicolons;

Visit the ROAD Programming Website for more programming help.

##### Share on other sites
to Kylotan:

Well my problem is that I don''t have 3 lines to check, I have about 700

Yeah, there are 3 lines per sector, but given arbitrary coordinates, I wouldn''t have any idea which sector to start checking against.

It wouldn''t be too hard to do if I did a linear search through all the sectors and checked whether the point was within the bounding box of the sector (and then did your test to see if it was within that triangle), but I think that would be slow...

Thanks for the suggestion though

To Yanroy:

since my sectors aren''t square, it''s not a simple division of the coordinates to find what sector it''s in :/

Although I might combine your idea with Kylotan''s to get something workable... I might superimpose a rectangular grid over my map, and for each grid square, hold a list of sectors under that square.. then I''d divide the coordinates to find which square, and do a bounding box check against the sectors in the grid square.. and then do Kylotan''s check against the 7 possible sectors..

Yeah, I think that would work
Thanks for the insight, guys!

• 15
• 13
• 35
• 39