Take a look at quad trees and octrees.
----- Original Message ----
From: pakachunka <[EMAIL PROTECTED]>
To: [email protected]
Sent: Saturday, March 22, 2008 10:21:00 AM
Subject: [c-prog] Re: How to find the triangle of a 2D Mesh that contains a
given point?
Hey Thomas,
thank you! The idea of pre-sorting is very good, specially because I
have a known number of triangles from start, so I can do a optimized
search tree.
However, I forgot to say that my mesh is not regular, that is, the
size and orientation of the triangles vary.
So, when you say sort the points, what do you mean? Sort by the
distance to (x=0, y=0) calculated by pitagoras? Make two sorted
lists, one for x and another one for y? But them the triangle
vertice found in list X may not be the same found in list Y, right?
Thanks
Tor
--- In [EMAIL PROTECTED] com, Thomas Hruska <[EMAIL PROTECTED] > wrote:
>
> pakachunka wrote:
> > Hello!
> >
> > Suppose I have a 2D Mesh Data Structure already set.
> >
> > I need to determine which triangle in the 2D mesh contains a
given
> > point (x,y).
> >
> > I need to do that very quick, since I will implement my code on
a Risc
> > Microcontroller, with very limited processing capabilities and
very
> > limited memory.
> >
> > Can you suggest some efficient algorithm for that?
> >
> > Thank you!
>
> Possible ideas:
>
> - Sort the points of each triangle in the mesh.
> - "Rectangles" would make a quick exclusion mechanism.
> - Adjacent points will only need to consider current and
adjacent
> "rectangles" on the next iteration.
>
> Storage limitations do make things interesting. Sorting points
(and the
> triangles themselves?) is an excellent start. You may be able to
figure
> something out by just doing that.
>
> --
> Thomas Hruska
> CubicleSoft President
> Ph: 517-803-4197
>
> *NEW* MyTaskFocus 1.1
> Get on task. Stay on task.
>
> http://www.CubicleS oft.com/MyTaskFo cus/
>
<!--
#ygrp-mkp{
border:1px solid #d8d8d8;font-family:Arial;margin:14px 0px;padding:0px 14px;}
#ygrp-mkp hr{
border:1px solid #d8d8d8;}
#ygrp-mkp #hd{
color:#628c2a;font-size:85%;font-weight:bold;line-height:122%;margin:10px 0px;}
#ygrp-mkp #ads{
margin-bottom:10px;}
#ygrp-mkp .ad{
padding:0 0;}
#ygrp-mkp .ad a{
color:#0000ff;text-decoration:none;}
-->
<!--
#ygrp-sponsor #ygrp-lc{
font-family:Arial;}
#ygrp-sponsor #ygrp-lc #hd{
margin:10px 0px;font-weight:bold;font-size:78%;line-height:122%;}
#ygrp-sponsor #ygrp-lc .ad{
margin-bottom:10px;padding:0 0;}
-->
<!--
#ygrp-mlmsg {font-size:13px;font-family:arial, helvetica, clean,
sans-serif;}
#ygrp-mlmsg table {font-size:inherit;font:100%;}
#ygrp-mlmsg select, input, textarea {font:99% arial, helvetica, clean,
sans-serif;}
#ygrp-mlmsg pre, code {font:115% monospace;}
#ygrp-mlmsg * {line-height:1.22em;}
#ygrp-text{
font-family:Georgia;
}
#ygrp-text p{
margin:0 0 1em 0;}
#ygrp-tpmsgs{
font-family:Arial;
clear:both;}
#ygrp-vitnav{
padding-top:10px;font-family:Verdana;font-size:77%;margin:0;}
#ygrp-vitnav a{
padding:0 1px;}
#ygrp-actbar{
clear:both;margin:25px 0;white-space:nowrap;color:#666;text-align:right;}
#ygrp-actbar .left{
float:left;white-space:nowrap;}
.bld{font-weight:bold;}
#ygrp-grft{
font-family:Verdana;font-size:77%;padding:15px 0;}
#ygrp-ft{
font-family:verdana;font-size:77%;border-top:1px solid #666;
padding:5px 0;
}
#ygrp-mlmsg #logo{
padding-bottom:10px;}
#ygrp-reco {
margin-bottom:20px;padding:0px;}
#ygrp-reco #reco-head {
font-weight:bold;color:#ff7900;}
#reco-grpname{
font-weight:bold;margin-top:10px;}
#reco-category{
font-size:77%;}
#reco-desc{
font-size:77%;}
#ygrp-vital{
background-color:#e0ecee;margin-bottom:20px;padding:2px 0 8px 8px;}
#ygrp-vital #vithd{
font-size:77%;font-family:Verdana;font-weight:bold;color:#333;text-transform:uppercase;}
#ygrp-vital ul{
padding:0;margin:2px 0;}
#ygrp-vital ul li{
list-style-type:none;clear:both;border:1px solid #e0ecee;
}
#ygrp-vital ul li .ct{
font-weight:bold;color:#ff7900;float:right;width:2em;text-align:right;padding-right:.5em;}
#ygrp-vital ul li .cat{
font-weight:bold;}
#ygrp-vital a{
text-decoration:none;}
#ygrp-vital a:hover{
text-decoration:underline;}
#ygrp-sponsor #hd{
color:#999;font-size:77%;}
#ygrp-sponsor #ov{
padding:6px 13px;background-color:#e0ecee;margin-bottom:20px;}
#ygrp-sponsor #ov ul{
padding:0 0 0 8px;margin:0;}
#ygrp-sponsor #ov li{
list-style-type:square;padding:6px 0;font-size:77%;}
#ygrp-sponsor #ov li a{
text-decoration:none;font-size:130%;}
#ygrp-sponsor #nc{
background-color:#eee;margin-bottom:20px;padding:0 8px;}
#ygrp-sponsor .ad{
padding:8px 0;}
#ygrp-sponsor .ad #hd1{
font-family:Arial;font-weight:bold;color:#628c2a;font-size:100%;line-height:122%;}
#ygrp-sponsor .ad a{
text-decoration:none;}
#ygrp-sponsor .ad a:hover{
text-decoration:underline;}
#ygrp-sponsor .ad p{
margin:0;}
o{font-size:0;}
.MsoNormal{
margin:0 0 0 0;}
#ygrp-text tt{
font-size:120%;}
blockquote{margin:0 0 0 4px;}
.replbq{margin:4;}
-->
____________________________________________________________________________________
Be a better friend, newshound, and
know-it-all with Yahoo! Mobile. Try it now.
http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ
[Non-text portions of this message have been removed]
