Testing if two lines or vectors intersect/overlap

[David Adams-4]

I'll admit to being a bit embarrassed to ask what seems like a basic
math question - but perhaps it will give someone else the pleasure of
being smart ;-)

I'm looking for an efficient way in 4D to test if two lines intersect
or overlap. Imagine I've got a number line from 0 to 10. Next, imagine
three lines with a starting point and length.
       
        3 to 5
        5 to 7
        6 to 8

Sort of like this:

          0     1     2     3     4     5     6     7     8     9    10
Line 1                      xxxxxxxx
Line 2                                     xxxxxxxx
Line 3                                            xxxxxxxx

What I'm trying to do is find an efficient way of detecting that line
1 (3-5) does not overlap/intersect any of the other lines while the
other two do overlap. I can sort this out using a series of
brute-force comparison ("does this start before that ends") - but
figure there should be a straightforward formulaic way of detecting
when two lines overlap/intersect. I'm working in 4D 2004 at the moment
but don't think V11 has added much in the way of math commands. I am
aware of 4D_MATH so that's an option - assuming I figure out what to
do with it ;-)

In a real-world context, what I'm trying to do is detect scheduling
collisions. Times can all be measured as seconds or minutes from
midnight, making them non-negative integers - like my example above
(but with larger values). Date+time can be treated the same way by
picking some starting date and converting everything to, say minutes.
You get big numbers, but they're all still starting at the same origin
(0) point. So, conflicts should be detectable by comparing the time
(or date+time) as lines.

With that in mind...I guess I intuit that it should be possible to
build vectors or graphs based on a series of timelines. For example,
all of the starting dates and times a repeated event meets. If that's
the case, it seems it might be possible to express an entire series of
related events ("the Tuesday morning staff meeting") numerically for
comparison with some other series of events ("the bi-monthly progress
meeting") and get a product that is either null (no intersections) or
the points of intersection.

I haven't messed around with scheduling algorithms much and haven't
found any written in human after a bit of quick searching. All I've
really got is kind of an intuition that there ought to be a simple
formulaic approach. If so, the next question is if it's worth the
effort to implement in 4D given the lack of many math libraries. (I'm
not complaining about 4D, just trying to make an informed choice.)

Thanks for any help!
**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[Neil Dennis]

I would do the same as you and use brute-force. It works in this case,  
it is easy to implement and debug and wont take a long time to run on  
todays equipment.

It might be a time saver to change your start+length to a start/end  
for calculations.

--
Neil Dennis
4D Developer since 1990

GreaText - Designing Software for the Way You Work
6827 Mark Twain CT
Johnston, IA 50131

mailto:ndennis@...
http://www.greatext.com/





On Nov 8, 2009, at 11:21 PM, David Adams wrote:

> I'll admit to being a bit embarrassed to ask what seems like a basic
> math question - but perhaps it will give someone else the pleasure of
> being smart ;-)
>
> I'm looking for an efficient way in 4D to test if two lines intersect
> or overlap. Imagine I've got a number line from 0 to 10. Next, imagine
> three lines with a starting point and length.
>
> 3 to 5
> 5 to 7
> 6 to 8
>
> Sort of like this:
>
>          0     1     2     3     4     5     6     7     8     9    10
> Line 1                      xxxxxxxx
> Line 2                                     xxxxxxxx
> Line 3                                            xxxxxxxx
>
> What I'm trying to do is find an efficient way of detecting that line
> 1 (3-5) does not overlap/intersect any of the other lines while the
> other two do overlap. I can sort this out using a series of
> brute-force comparison ("does this start before that ends") - but
> figure there should be a straightforward formulaic way of detecting
> when two lines overlap/intersect. I'm working in 4D 2004 at the moment
> but don't think V11 has added much in the way of math commands. I am
> aware of 4D_MATH so that's an option - assuming I figure out what to
> do with it ;-)
>
> In a real-world context, what I'm trying to do is detect scheduling
> collisions. Times can all be measured as seconds or minutes from
> midnight, making them non-negative integers - like my example above
> (but with larger values). Date+time can be treated the same way by
> picking some starting date and converting everything to, say minutes.
> You get big numbers, but they're all still starting at the same origin
> (0) point. So, conflicts should be detectable by comparing the time
> (or date+time) as lines.
>
> With that in mind...I guess I intuit that it should be possible to
> build vectors or graphs based on a series of timelines. For example,
> all of the starting dates and times a repeated event meets. If that's
> the case, it seems it might be possible to express an entire series of
> related events ("the Tuesday morning staff meeting") numerically for
> comparison with some other series of events ("the bi-monthly progress
> meeting") and get a product that is either null (no intersections) or
> the points of intersection.
>
> I haven't messed around with scheduling algorithms much and haven't
> found any written in human after a bit of quick searching. All I've
> really got is kind of an intuition that there ought to be a simple
> formulaic approach. If so, the next question is if it's worth the
> effort to implement in 4D given the lack of many math libraries. (I'm
> not complaining about 4D, just trying to make an informed choice.)
>
> Thanks for any help!
> **********************************************************************
> Get the speed and power of 4D v11 SQL
> before upgrade prices increase - http://www.4d.com
>
>
> 4D Internet Users Group (4D iNUG)
> FAQ:  http://lists.4d.com/faqnug.html
> Archive:  http://lists.4D.com/archives.html
> Options: https://lists.4d.com/mailman/options/4d_tech
> Unsub:  mailto:4D_Tech-Unsubscribe@...
> **********************************************************************
>

**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[Mark Schaake2]

Hi David, there is a "Greedy" algorithm for doing just what you seek. Do this:

1. Initialize two arrays to hold start and end times of the potentially conflicting intervals, say start_al and end_al
2. Multi-sort the arrays based on the end time: MULTISORT ARRAYS(end_al;>;start_al)
3. Do the following...

You have a specific interval (s_l, e_l) that you are trying to make sure is not in conflict with any that are in the arrays...

LONGINT($i)
C_BOOLEAN($conflictExists_b)
$i:=1
$conflictExists_b:=False
While ( start_al{$i} <= e_l ) && (Not( $conflictExists_b ))
    If ( end_al{$i} >= e_l)
        $conflictExists_b:=True
    End if
End while

Maybe you'd consider this another "Brute Force" algorithm, but if you wanted to get real fancy you could implement a modified binary search to quickly find the first interval in (start_al, end_al) that ends past the start position s_l. If you want, I could send you an example of doing this too.

Hope this helps,

Mark

David Adams-4 wrote:

I'll admit to being a bit embarrassed to ask what seems like a basic
math question - but perhaps it will give someone else the pleasure of
being smart ;-)

I'm looking for an efficient way in 4D to test if two lines intersect
or overlap. Imagine I've got a number line from 0 to 10. Next, imagine
three lines with a starting point and length.
       
        3 to 5
        5 to 7
        6 to 8

Sort of like this:

          0     1     2     3     4     5     6     7     8     9    10
Line 1                      xxxxxxxx
Line 2                                     xxxxxxxx
Line 3                                            xxxxxxxx

What I'm trying to do is find an efficient way of detecting that line
1 (3-5) does not overlap/intersect any of the other lines while the
other two do overlap. I can sort this out using a series of
brute-force comparison ("does this start before that ends") - but
figure there should be a straightforward formulaic way of detecting
when two lines overlap/intersect. I'm working in 4D 2004 at the moment
but don't think V11 has added much in the way of math commands. I am
aware of 4D_MATH so that's an option - assuming I figure out what to
do with it ;-)

In a real-world context, what I'm trying to do is detect scheduling
collisions. Times can all be measured as seconds or minutes from
midnight, making them non-negative integers - like my example above
(but with larger values). Date+time can be treated the same way by
picking some starting date and converting everything to, say minutes.
You get big numbers, but they're all still starting at the same origin
(0) point. So, conflicts should be detectable by comparing the time
(or date+time) as lines.

With that in mind...I guess I intuit that it should be possible to
build vectors or graphs based on a series of timelines. For example,
all of the starting dates and times a repeated event meets. If that's
the case, it seems it might be possible to express an entire series of
related events ("the Tuesday morning staff meeting") numerically for
comparison with some other series of events ("the bi-monthly progress
meeting") and get a product that is either null (no intersections) or
the points of intersection.

I haven't messed around with scheduling algorithms much and haven't
found any written in human after a bit of quick searching. All I've
really got is kind of an intuition that there ought to be a simple
formulaic approach. If so, the next question is if it's worth the
effort to implement in 4D given the lack of many math libraries. (I'm
not complaining about 4D, just trying to make an informed choice.)

Thanks for any help!
**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:[e-mail]
**********************************************************************

[David Adams-4]

On Mon, Nov 9, 2009 at 4:21 PM, David Adams <dpadams@...> wrote:

> I'm looking for an efficient way in 4D to test if two lines intersect
> or overlap. Imagine I've got a number line from 0 to 10. Next, imagine
> three lines with a starting point and length.

In case it makes any difference, I offer three lines in my example but
- in the real world - I may need to compare hundreds or even thousands
of 'lines'.

Thanks!
**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[Ortwin Zillgen]

line 1: Start1_x/Start1_y and End1_x/End1_y
line 1: Start2_x/Start2_y and End2_x/End2_y


   `F  rs_intersect (LAx1;LAy1;LAx2;LAy2;LBx1;LBy1;LBx2;LBy2) => Boolean
C_BOOLEAN($0)
Case of
        : ((($5>$1) & ($7>$1)) & (($5>$3) & ($7>$3)))  `2. Linie rechts von  
1. Linie
                $0:=False
        : ((($5<$1) & ($7<$1)) & (($5<$3) & ($7<$3)))  `2. Linie links von 1.  
Linie
                $0:=False
        : ((($6>$2) & ($8>$2)) & (($6>$4) & ($8>$4)))  `2. Linie oberhalb von  
1. Linie
                $0:=False
        : ((($6<$2) & ($8<$2)) & (($6<$4) & ($8<$4)))  `2. Linie unterhalb  
von 1. Linie
                $0:=False
        Else
                $0:=(((rs_ccw ($1;$2;$3;$4;$5;$6)*rs_ccw ($1;$2;$3;$4;$7;$8))<=0) &  
((rs_ccw ($5;$6;$7;$8;$1;$2)*rs_ccw ($5;$6;$7;$8;$3;$4))<=0))
End case

   ` *****  Ende der Methode: rs_intersect  *****

where rs_ccw (counter_clock-wise) is

   `F  rs_ccw(x1;y1;x2;y2;x3;y3)  =>  1, 0, -1   • CounterClockWise
C_INTEGER($0)
C_LONGINT($dx1;$dy1;$dx2;$dy2)
$dx1:=$3-$1
$dy1:=$4-$2
$dx2:=$5-$1
$dy2:=$6-$2
Case of
        : (($dx1*$dy2)>($dy1*$dx2))
                $0:=1  `P2 zwischen P1 und P3
        : (($dx1*$dy2)<($dy1*$dx2))
                $0:=-1  `auf einer Linie: P1 zwischen P2 und P3
        : (($dx1*$dy2)=($dy1*$dx2))
                Case of
                        : (($dx1*$dx2<0) | ($dy1*$dy2<0))
                                $0:=-1  `auf einer Linie: P1 zwischen P2 und P3
                        : ((($dx1*$dx1)+($dy1*$dy1))>=(($dx2*$dx2)+($dy2*$dy2)))
                                $0:=0  `P3 zwischen P1 und P2
                        Else
                                $0:=1  `P2 zwischen P1 und P3
                End case
End case

   ` *****  Ende der Methode: rs_ccw  *****

rs is for Robert Sedgewick <http://de.wikipedia.org/wiki/Robert_Sedgewick 
 >


Regards
Ortwin Zillgen
___________________________________________________
Stadt Land Fluß * Geographic Informationsystems
<mailto:info@...>   <http://dddd.mettre.de?4713>
RSS <feed://dddd.mettre.de/dddd.xml>
RSS <feed://dddd.mettre.de/f/DDDD_Links.xml>



**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com


4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[Sujit Shah]

If minutes are the smallest unit for this scheduling. You can load
each "meeting" in a 24*60 2-dimension array. Then check the number of
columns for each minute row.



--
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
"The butterfly does not count years, but moments, and therefore has
enough time." - Rabindranath Tagore
**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[Julio Carneiro]

David,

First you definitely ned to go Start+End, instead of Start+Len.

Trying to dig a bit deeper, what exactly are you looking for:
- look into a record set and find conflicts
- avoid adding conflicting records

Those a very different situations and the second is pretty easy to  
accomplish with 1 simple query.
Given a new set of start/end: newStart & new End, do:
    set query destination(into variable;$count)
    query([tbl];[tbl]start<=$newEnd;*)
    query([tbl];&;[tbl]end>=$newStart)
    set query destination(into current set)
    if ($count>0)
       .... you have a conflict
    end if

That will avoid creating conflicts in the first place, and maybe avoid  
the need to do a brute force 'conflict search', or maybe, do that  
eventually.

You can also extend the idea above if you do need to 'find conflicts',  
depending on your 'interval step'. That is, assuming you are talking  
about real events and you want to find events the cross on  a "day".
In that case you can take the initial and final dates (min(start) &  
max(end)), and wrap the test above inside a for/while loop to search  
for conflicts on each day between min(start) & max(end), something like:
$initial:=min([tbl]start)
$final:=max([tbl[end)
for ($d;$initial;$end)
    set query destination(into variable;$count)
    query([tbl];[tbl]start<=$d;*)
    query([tbl];&;[tbl]end>=$d)
    set query destination(into current set)
    if ($count>0)
       .... you have a conflict
    end if
end for

Obviously you can modify the algorithm above if you need more  
granularity in your conflict search, say hours or minutes (even  
seconds). But the time to run it may get prohibitive, depending on the  
size of your record set, or the possible values for min(start) max(end).

ANyway, I hope that gives you some ideas...

julio

On Nov 9, 2009, at 4:45 AM, David Adams wrote:

> On Mon, Nov 9, 2009 at 4:21 PM, David Adams <dpadams@...> wrote:
>
>> I'm looking for an efficient way in 4D to test if two lines intersect
>> or overlap. Imagine I've got a number line from 0 to 10. Next,  
>> imagine
>> three lines with a starting point and length.
>
> In case it makes any difference, I offer three lines in my example but
> - in the real world - I may need to compare hundreds or even thousands
> of 'lines'.
>

**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[Broderick, Sean - Direct Brands]

David Adams:

I would do this exactly like Julio describes, and I have had to deal with
this many times (for section, page and date ranges).

What I would do though, would be to use absolute start and stop markers in
indexed fields.

[schedule]event_key:=1101
[schedule]event_start:="2008-11-08-140000"
[schedule]event_end:="2008-11-08-153000"

(There are many permutations on such absolute time representations.)

Let's say the user attempts to revise this event, how do we know if there
will now be a conflict?

  set query destination(into variable;$count)
  query([schedule];[schedule]event_key#$current_event_key;*)
  query([schedule];&;[schedule]event_start<=$start_stamp;*)
  query([schedule];&;[schedule]event_end>=$end_stamp)
  set query destination(into current set)
  if ($count>0)
    $schedule_conflict:=true
  end if

If these fields are indexed, the query should not be expensive.

Sincerely,
Sean Broderick


______________________________________________________________________
This email has been scanned by the MessageLabs Email Security System.
For more information please visit http://www.messagelabs.com/email 
______________________________________________________________________
**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com


4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[Jesse Pina]

Hi all,

I just want to remind everyone about the "Create New Asset" feature in KB.

The solutions mentioned in this thread are perfect examples of things that
can be made into Tech Tips, so they can be searched, used, and commented on
by other developers.  So if you are a partner, I would definitely recommend
submitting these solutions as tech tips.

Kind regards,

--
Jesse Piña
Technical Services Team Member
4D, Inc.
**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com


4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[Alan Chan]

Hi David,

It's interesting that we plan to add booking/scheduling module in our ERP
system after we complete v11 conversion.

Depends on how far your scheduling application would go, I think the
design of the structure will affect your query algorithm. Do you want to
do scheduling based on:

1) fixed person (this is most easy part)
2) any number of persons in a group such as "any available C Ranking
Engineers would fill the schedule", if no such member is available, would
the system allow moving up to higher ranking engineers?
3) Resources such as "meeting room with capacity (require a meeting room
that could accomodate 12 persons)"
4) Resources such as travelling arrangement - require a Van for 12 persons
or 3 cars for 4 persons each ... etc?
5) Resources required such as "projector required" - need to check
available projector
6) Will the system require to register cost automatically for event that
requires all these resources? Will the system alert you if total cost of
the even exceed predefined budget?

Will the system popup list to allow users to select available Resources,
any available group member ... etc during entry? Will this be optimised to
work over the Internet?

Have fun.

Alan Chan


4D iNug Technical <4d_tech@...> writes:
>I haven't messed around with scheduling algorithms much and haven't
>found any written in human after a bit of quick searching. All I've
>really got is kind of an intuition that there ought to be a simple
>formulaic approach. If so, the next question is if it's worth the
>effort to implement in 4D given the lack of many math libraries. (I'm
>not complaining about 4D, just trying to make an informed choice.)


**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[Jeff Grann]

David,

 From reading your post, it sounds like you need to be able to  
compare a set of single (non-recurring) and RECURRING events to check  
for conflicts.

If this is the case, I have some questions:

1) Do you allow recurring events to repeat forever?  If so, you'll  
need to define a reasonable limit to your search.

2) I assume you are storing a single record for a recurrence event,  
and then the occurrences can be generated using its definition,  
rather than storing the occurrences as individual records.  Is this  
correct?

3) Do you need a simple boolean result (conflict/no conflict) or do  
you actually need to enumerate the conflicting dates/times?

4) You mention that you did a quick search for algorithms, but you  
didn't find any that were "written in human."  Are you saying that  
you thought you might have found one that would do what you want?  If  
so, does it just seem too complicated or impossible to implement in  
4D?  Or are you saying that you just couldn't tell if it would fit  
the bill?

5) Do you need to check an event (which could be non-recurring or  
recurring) against all other events to see if there is a conflict (1  
vs. N) or do you need to check all events against all other events  
for conflicts at the same time (N vs. N)?

The reason I ask is that I am just about to embark on a similar  
project and have many ideas on the subject.  And, of course, if there  
is a better way, I'm all ears.

-----
Jeff Grann
SuccessWare, Inc.

On Nov 9, 2009, at 12:21 AM, David Adams wrote:

> With that in mind...I guess I intuit that it should be possible to
> build vectors or graphs based on a series of timelines. For example,
> all of the starting dates and times a repeated event meets. If that's
> the case, it seems it might be possible to express an entire series of
> related events ("the Tuesday morning staff meeting") numerically for
> comparison with some other series of events ("the bi-monthly progress
> meeting") and get a product that is either null (no intersections) or
> the points of intersection.

**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[Thierry Hauchard]

Hi,

In SQL, you resolve that with one request (no loop) with synchronized
subrequest :

SELECT (EXISTS SELECT * FROM tbl b WHERE b.start < a.end AND b.end >
a.start) AS conflict , * FROM tbl a

The first column is then a boolean returning true if conflict.

You can add to this filtering : WHERE a.start > startFilter AND a.end <
endFilter
And you can add order :  ORDER BY conflict DESC  (to get conflict in
first place)

If you want only conflicts, your request becomes :

SELECT * FROM tbl a WHERE (EXISTS SELECT * FROM tbl b WHERE b.start <
a.end AND b.end > a.start)

I don't now if you can do that with 4Dv11...

Regards
--
Thierry


Julio Carneiro a écrit :

> ...
> In that case you can take the initial and final dates (min(start) &
> max(end)), and wrap the test above inside a for/while loop to search
> for conflicts on each day between min(start) & max(end), something like:
> $initial:=min([tbl]start)
> $final:=max([tbl[end)
> for ($d;$initial;$end)
>    set query destination(into variable;$count)
>    query([tbl];[tbl]start<=$d;*)
>    query([tbl];&;[tbl]end>=$d)
>    set query destination(into current set)
>    if ($count>0)
>       .... you have a conflict
>    end if
> end for

**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com


4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[David Adams-4]

On Tue, Nov 10, 2009 at 2:51 AM, Jesse Pina <JPina@...> wrote:
> Hi all,
>
> I just want to remind everyone about the "Create New Asset" feature in KB.
>
> The solutions mentioned in this thread are perfect examples of things that
> can be made into Tech Tips, so they can be searched, used, and commented on
> by other developers.  So if you are a partner, I would definitely recommend
> submitting these solutions as tech tips.

Can we upload resources - like sample databases - along with new assets?
**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com


4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[David Adams-4]

On Tue, Nov 10, 2009 at 6:19 AM, Alan Chan <alan@...> wrote:

> Depends on how far your scheduling application would go, I think the
> design of the structure will affect your query algorithm.

I'm sorting out algorithms first. What I'm imagining now is a
generalized [Event] table with something like this:

        Event_ID
        Start_Date
        Start_Time
        Start_Signature ` 2009-11-15-23250
        End_Date
        End_Time
        End_Signature
        Room_ID

...and a bunch of other fields for GUI-specific and possibly
logic-related stuff. For example:

        Event_Is_Locked_to_Changes
        Event_Lasts_All_Day

...and I'll assume I'll need some sort of a scheme for blocking out
holidays/building closure days of one sort or another.

I'm imagining linking to other people like so:


[Event] ---> [Room]

An [Event] occurs in a specific room.

[Event] <--> [Person]

An event may have many people, a person may participate in many events.

I'm imagining building out events as actual records. So, if a meeting
happens ever Tuesday for the next year, there will be 52 records.

Again, none of this is coded now - I'm sorting through options before
building the structure or code.


> 3) Resources such as "meeting room with capacity (require a meeting room
> that could accomodate 12 persons)"

The most important conflicts to avoid are

   meeting room - can't have double-booking
   meeting facilitator - the chair of the meeting can't be double-booked.

Meeting attendees can look after themselves - it won't stop a meeting
from being scheduled. All I want for attendee conflicts is to be able
to detect such conflicts in their schedules easily.

> 4) Resources such as travelling arrangement - require a Van for 12 persons
> or 3 cars for 4 persons each ... etc?

Nope, none such.

> 5) Resources required such as "projector required" - need to check
> available projector
Nope. The only resources are the chair/facilitator and the room itself.

> 6) Will the system require to register cost automatically for event that
> requires all these resources? Will the system alert you if total cost of
> the even exceed predefined budget?
This doesn't matter to us.

> Will the system popup list to allow users to select available Resources,
> any available group member ... etc during entry? Will this be optimised to
> work over the Internet?
Internet is possible some day, primarily for display. I'm expecting to
use hmCal for the user interface.
**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[Brendan Coveney]

On Nov 10, 2009, at 5:08 PM, David Adams wrote:

> On Tue, Nov 10, 2009 at 2:51 AM, Jesse Pina <JPina@...> wrote:
>> Hi all,
>>
>> I just want to remind everyone about the "Create New Asset" feature in KB.
>
> Can we upload resources - like sample databases - along with new assets?

I am not sure we are there yet but that is the plan.


Regards
Brendan
**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[David Adams-4]

On Wed, Nov 11, 2009 at 12:29 PM, Brendan Coveney <bcoveney@...> wrote:

> On Nov 10, 2009, at 5:08 PM, David Adams wrote:
>
>> On Tue, Nov 10, 2009 at 2:51 AM, Jesse Pina <JPina@...> wrote:
>>> Hi all,
>>>
>>> I just want to remind everyone about the "Create New Asset" feature in KB.
>>
>> Can we upload resources - like sample databases - along with new assets?
>
> I am not sure we are there yet but that is the plan.

That would be great!
**********************************************************************
Get the speed and power of 4D v11 SQL
before upgrade prices increase - http://www.4d.com
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[Bill Weale]

I'd suggest your considering:

[Event]<--[Room Event]-->[Room]

and

[Event]<--[Person-Event]--->[Person]

and,

etc.


This construct...

...makes it much easier in the future to add other classes of  
"Things"--the data/table equivalent to Rooms and Persons that may take  
part in each event

...allows you to use more than one of a class of "things", like rooms,  
for any given event

...makes, imo, for easier report development, especially conflict-
catching


I know you said that (right now) you don't need any other resource  
than just the room, but...

8-)

Bill




On Nov 10, 2009, at 8:17 PM, David Adams wrote:

> I'm imagining linking to other people like so:
>
>
> [Event] ---> [Room]
>
> An [Event] occurs in a specific room.
>
> [Event] <--> [Person]
>
> An event may have many people, a person may participate in many  
> events.

**********************************************************************
Get up to $600 to spend on Amazon.com
this holiday season - http://www.4d.com/serverpromo.html
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[Julio Carneiro]

Aha, now I can see what type of scheduling you are talking about.

Yours is a scheduler for Events plus multiple resources on each event  
(rooms, people, material, ...).

There many types of 'scheduling' applications. I've done a couple and  
each has its own needs and requirements. Hard to have a 'generic'  
scheduler.
You have 'appointment schedulers', iCal type applications, where you  
have 1 single resource (the calendar) and you book time on that  
resource (events).
Sometimes that is all you have. Events basically have a description  
and some metadata, but link to no other Entity.
For that type of 'agenda scheduler' you have essentially one entity,  
Events. If you allow multiple calendars then you need an extra one  
(Calendars). Data model here is simple Calendar->Event, or more  
generically Resource->Event.
Usually no need for conflict resolution here, as that can be easily  
accomplished by not allowing double-booking.

One other type allows for tracking of who/what is referred to/
responsible for an Event. Most of the time People. Here each Event is  
linked to another Entity representing who/what is being booked.
Typical example is a Doctor's appointment book, where you have the  
need to track the Patient booked for an Event.
Here you basically have a Event->Patient data model, or if you track  
multiple Calendars (Doctors), you'd have  Doctor->Event->Patient.
Same as above conflict resolution is usually accomplished by avoiding  
the creation of overlapping events (not entirely true in real life as  
dr's tend to book multiple patients at the same time and let conflict  
resolution be handled by front desk, shuffling patients in multiple  
rooms).

A third type covers the case where you need to track multiple  
resources linked to each Event. It can be rooms, people, people in  
different roles (chair/teacher & attendants), material (projector,  
computer,..). Or courses, class rooms, teachers & students, etc.
In that situation I like to look at it as an expanded version of type  
one above, where you treat each 'resource' as a "calendar", thus  you  
can look at all Events for "room 123", or all Events for David as  
teacher, or all Events for David as attendant, or all Events for  
"projector 123".
That requires a variation on the data model to allow for multiple  
'resources' sharing/referring to the same Event. Thus we would have  
Resource <- ResourceEvents -> Event.
Of course you usually need a very different set of metadata for each  
type of resource and that implies the need to break down Resource &  
ResourceEvents into multiple Entities, e.g., People & PeopleEvents,  
Room & RoomEvents, etc.
Yours seems the be this latest case. Here conflict resolution can be  
tricky (reason why you started this thread :)). In this case the  
simple collision avoidance is not enough as you are dealing with  
conflicts amongst multiple Calendars (resources). Rules for double  
booking are different for each resource type, you can double book  
attendants to an event, but each attendant cannot be double booked to  
multiple events.
So, I'd suggest you review your data model to allow for nXn  
relationship between Events and resources. That would make it easy to  
implement generic validation and conflict resolution rules/algorithms.

Besides all that, in each type/class of scheduling app you may have  
the need for 'recurring events'. How do you handle those? Do you have  
a single Event record and generate 'virtual events' as needed for  
validation/display/report? In that case, how do you deal with conflict  
resolution?
Or you may generate 'real' Events for each occurrence? How do you  
limit them in time, you need a finite # of records?
What if you want to make changes to the events? Do you allow changes  
to a single occurrence? Do you allow changes to all occurrences?
This is probably a topic for another book :-)

And there is still one fourth type, exemplified by TV program  
scheduling (of which I have a bit of experience ;-)). This is sort of  
a variation on the second type with the difference that you have  
Channel->Event->Program, but there you have a ton of business rules  
governing how/when programs are/can/must be scheduled. And those  
business rules vary according to the type of 'program' being scheduled  
(sitcom episode, movie, commercial, promos, etc).

cheers,
julio

On Nov 10, 2009, at 11:17 PM, David Adams wrote:

> On Tue, Nov 10, 2009 at 6:19 AM, Alan Chan <alan@...> wrote:
>
>> Depends on how far your scheduling application would go, I think the
>> design of the structure will affect your query algorithm.
>
> I'm sorting out algorithms first. What I'm imagining now is a
> generalized [Event] table with something like this:
>
> Event_ID
> Start_Date
> Start_Time
> Start_Signature ` 2009-11-15-23250
> End_Date
> End_Time
> End_Signature
> Room_ID
>
> ...and a bunch of other fields for GUI-specific and possibly
> logic-related stuff. For example:
>
> Event_Is_Locked_to_Changes
> Event_Lasts_All_Day
>
> ...and I'll assume I'll need some sort of a scheme for blocking out
> holidays/building closure days of one sort or another.
>
> I'm imagining linking to other people like so:
>
>
> [Event] ---> [Room]
>
> An [Event] occurs in a specific room.
>
> [Event] <--> [Person]
>
> An event may have many people, a person may participate in many  
> events.
>
> I'm imagining building out events as actual records. So, if a meeting
> happens ever Tuesday for the next year, there will be 52 records.
>
> Again, none of this is coded now - I'm sorting through options before
> building the structure or code.
>
>
>> 3) Resources such as "meeting room with capacity (require a meeting  
>> room
>> that could accomodate 12 persons)"
>
> The most important conflicts to avoid are
>
>   meeting room - can't have double-booking
>   meeting facilitator - the chair of the meeting can't be double-
> booked.
>
> Meeting attendees can look after themselves - it won't stop a meeting
> from being scheduled. All I want for attendee conflicts is to be able
> to detect such conflicts in their schedules easily.
>
>> 4) Resources such as travelling arrangement - require a Van for 12  
>> persons
>> or 3 cars for 4 persons each ... etc?
>
> Nope, none such.
>
>> 5) Resources required such as "projector required" - need to check
>> available projector
> Nope. The only resources are the chair/facilitator and the room  
> itself.
>
>> 6) Will the system require to register cost automatically for event  
>> that
>> requires all these resources? Will the system alert you if total  
>> cost of
>> the even exceed predefined budget?
> This doesn't matter to us.
>
>> Will the system popup list to allow users to select available  
>> Resources,
>> any available group member ... etc during entry? Will this be  
>> optimised to
>> work over the Internet?
> Internet is possible some day, primarily for display. I'm expecting to
> use hmCal for the user interface.
> **********************************************************************
> Get the speed and power of 4D v11 SQL
> before upgrade prices increase - http://www.4d.com
>
>
> 4D Internet Users Group (4D iNUG)
> FAQ:  http://lists.4d.com/faqnug.html
> Archive:  http://lists.4D.com/archives.html
> Options: https://lists.4d.com/mailman/options/4d_tech
> Unsub:  mailto:4D_Tech-Unsubscribe@...
> **********************************************************************

**********************************************************************
Get up to $600 to spend on Amazon.com
this holiday season - http://www.4d.com/serverpromo.html
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[David Adams-4]

On Fri, Nov 13, 2009 at 12:00 AM, Julio Carneiro <jjfourd@...> wrote:
> Aha, now I can see what type of scheduling you are talking about.

> There many types of 'scheduling' applications. I've done a couple and each
> has its own needs and requirements. Hard to have a 'generic' scheduler.
> You have 'appointment schedulers', iCal type applications, where you have 1
> single resource (the calendar) and you book time on that resource (events).
> Sometimes that is all you have. Events basically have a description and some
> metadata, but link to no other Entity.

Gee, that was perfectly clear in _my_mind...I guess I should have said
so.  Thanks for your breakdown of various types of scheduling
scenarios. I could look at mine a few ways but, as I understand it,
the primary goals and objectives are:

* Stop double-booking of rooms. (High potential for collision.)
* Stop double-booking of meeting leaders. (Not that hard - they don't
have a lot of meetings.)
* Detect conflicts by meeting attendees.
* Detect conflicts when trying to reschedule a meeting.

The last point is really important - and the primary reason I'm
looking for some speedy solutions. Meetings tend to have a regular
schedule - say Tuesday from 10:00-11:00 or every-other Monday from
8:30-9:00. Pretty normal stuff. Well, what happens if _one_ session
needs to be moved? Or, for that matter, a whole series? I'd like to be
able to quickly detect conflicts and quickly detect conflicts in
possible alternative times.

With that said, I'll mention that I'm figuring on a master 'meeting'
type record which defines the max/min date and the meeting pattern
(10:00-11:00 on every other Monday.) From there, I plan to build out
the event instances (appointments), largely so that exceptions can be
made. Such as, on Monday the 15th, the meeting will be from
10:30-11:30. In this application's case, it's fine to build out the
calendar in advance by several months or even a year - no problem. So,
I'll have real [Event] records to search, display, etc.

> For that type of 'agenda scheduler' you have essentially one entity, Events.
> If you allow multiple calendars then you need an extra one (Calendars). Data
> model here is simple Calendar->Event, or more generically Resource->Event.
> Usually no need for conflict resolution here, as that can be easily
> accomplished by not allowing double-booking.

Sounds good. I may well have scenarios where double-booking or
conflicts arise after-the-fact (the conference room is closed because
the air conditioning is being fixed) but that's the exception, not the
rule.

> One other type allows for tracking of who/what is referred to/responsible
> for an Event. Most of the time People. Here each Event is linked to another
> Entity representing who/what is being booked.

I'm figuring on

    [Event]
    ID_PrimaryKey
    Room_ForeignKey
    Leader_ForeignKey
    Start_Date
    Start_Time
    Start_Signature ` 2009-11-15-20150 sort of a thing - built in trigger
    End_Date
    End_Time
    End_Signature

...plus whatever else I might need to help out with the GUI and
various rules, such as 'locked' or 'can't schedule here'
(holidays/repairs on rooms.)

I'm not planning on storing a person's schedule as such. A meeting
leader will sort out if they can make a commitment or not.


> Besides all that, in each type/class of scheduling app you may have the need
> for 'recurring events'. How do you handle those? Do you have a single Event
> record and generate 'virtual events' as needed for
> validation/display/report? In that case, how do you deal with conflict
> resolution?

Yup, building out the actual appointments seems the way to go. As
mentioned, the ability to make exceptions to the overall pattern
(shift appointment time or room, skip a week, etc.)

> Or you may generate 'real' Events for each occurrence? How do you limit them
> in time, you need a finite # of records?
Yes, the user should be able to pick an absolute start/end date - I'll
default to several months out. In this case, this approach will fit
their business style - no one is worried about the first Tuesday in
May 2011 at this point.

> What if you want to make changes to the events? Do you allow changes to a
> single occurrence?
Yes.

> Do you allow changes to all occurrences?
> This is probably a topic for another book :-)
Yes, which is why I'm trying to find an efficient algorithm that
doesn't explode when the starting selection size goes up. I think I've
got one now that should work okay in the real world - I'll post that a
bit later.

> And there is still one fourth type, exemplified by TV program scheduling (of
> which I have a bit of experience ;-)). This is sort of a variation on the
> second type with the difference that you have Channel->Event->Program, but
> there you have a ton of business rules governing how/when programs
> are/can/must be scheduled. And those business rules vary according to the
> type of 'program' being scheduled (sitcom episode, movie, commercial,
> promos, etc).

Where I live is so rural that when I've told people I'm a programmer,
they've answered "? You mean, like for TV schedules?"
**********************************************************************
Get up to $600 to spend on Amazon.com
this holiday season - http://www.4d.com/serverpromo.html
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************

[Chuck Miller-2]

Hi David,

I think  true scheduling takes a little bit more effort than you are  
envisioning. Not only do you have to check for overlap of times for  
meeting, you need to check rooms, people, and tools needed (I.e)  
projector, monitor, computer etc). I'll take a look at some of my old  
comp sci texts and see if I can point you to an algorithm.


Regards

Chuck
---------------------------------------------------------------------------
Chuck Miller                          Voice: [phone]
Informed Solutions, Inc.              Fax: [phone]
----------------------------------------------------------------------------





On Nov 12, 2009, at 4:27 PM, David Adams wrote:

> On Fri, Nov 13, 2009 at 12:00 AM, Julio Carneiro <jjfourd@...>  
> wrote:
>> Aha, now I can see what type of scheduling you are talking about.
>
>> There many types of 'scheduling' applications. I've done a couple  
>> and each
>> has its own needs and requirements. Hard to have a 'generic'  
>> scheduler.
>> You have 'appointment schedulers', iCal type applications, where  
>> you have 1
>> single resource (the calendar) and you book time on that resource  
>> (events).
>> Sometimes that is all you have. Events basically have a description  
>> and some
>> metadata, but link to no other Entity.
>
> Gee, that was perfectly clear in _my_mind...I guess I should have said
> so.  Thanks for your breakdown of various types of scheduling
> scenarios. I could look at mine a few ways but, as I understand it,
> the primary goals and objectives are:
>
> * Stop double-booking of rooms. (High potential for collision.)
> * Stop double-booking of meeting leaders. (Not that hard - they don't
> have a lot of meetings.)
> * Detect conflicts by meeting attendees.
> * Detect conflicts when trying to reschedule a meeting.
>
> The last point is really important - and the primary reason I'm
> looking for some speedy solutions. Meetings tend to have a regular
> schedule - say Tuesday from 10:00-11:00 or every-other Monday from
> 8:30-9:00. Pretty normal stuff. Well, what happens if _one_ session
> needs to be moved? Or, for that matter, a whole series? I'd like to be
> able to quickly detect conflicts and quickly detect conflicts in
> possible alternative times.
>
> With that said, I'll mention that I'm figuring on a master 'meeting'
> type record which defines the max/min date and the meeting pattern
> (10:00-11:00 on every other Monday.) From there, I plan to build out
> the event instances (appointments), largely so that exceptions can be
> made. Such as, on Monday the 15th, the meeting will be from
> 10:30-11:30. In this application's case, it's fine to build out the
> calendar in advance by several months or even a year - no problem. So,
> I'll have real [Event] records to search, display, etc.
>
>> For that type of 'agenda scheduler' you have essentially one  
>> entity, Events.
>> If you allow multiple calendars then you need an extra one  
>> (Calendars). Data
>> model here is simple Calendar->Event, or more generically Resource-
>> >Event.
>> Usually no need for conflict resolution here, as that can be easily
>> accomplished by not allowing double-booking.
>
> Sounds good. I may well have scenarios where double-booking or
> conflicts arise after-the-fact (the conference room is closed because
> the air conditioning is being fixed) but that's the exception, not the
> rule.
>
>> One other type allows for tracking of who/what is referred to/
>> responsible
>> for an Event. Most of the time People. Here each Event is linked to  
>> another
>> Entity representing who/what is being booked.
>
> I'm figuring on
>
>    [Event]
>    ID_PrimaryKey
>    Room_ForeignKey
>    Leader_ForeignKey
>    Start_Date
>    Start_Time
>    Start_Signature ` 2009-11-15-20150 sort of a thing - built in  
> trigger
>    End_Date
>    End_Time
>    End_Signature
>
> ...plus whatever else I might need to help out with the GUI and
> various rules, such as 'locked' or 'can't schedule here'
> (holidays/repairs on rooms.)
>
> I'm not planning on storing a person's schedule as such. A meeting
> leader will sort out if they can make a commitment or not.
>
>
>> Besides all that, in each type/class of scheduling app you may have  
>> the need
>> for 'recurring events'. How do you handle those? Do you have a  
>> single Event
>> record and generate 'virtual events' as needed for
>> validation/display/report? In that case, how do you deal with  
>> conflict
>> resolution?
>
> Yup, building out the actual appointments seems the way to go. As
> mentioned, the ability to make exceptions to the overall pattern
> (shift appointment time or room, skip a week, etc.)
>
>> Or you may generate 'real' Events for each occurrence? How do you  
>> limit them
>> in time, you need a finite # of records?
> Yes, the user should be able to pick an absolute start/end date - I'll
> default to several months out. In this case, this approach will fit
> their business style - no one is worried about the first Tuesday in
> May 2011 at this point.
>
>> What if you want to make changes to the events? Do you allow  
>> changes to a
>> single occurrence?
> Yes.
>
>> Do you allow changes to all occurrences?
>> This is probably a topic for another book :-)
> Yes, which is why I'm trying to find an efficient algorithm that
> doesn't explode when the starting selection size goes up. I think I've
> got one now that should work okay in the real world - I'll post that a
> bit later.
>
>> And there is still one fourth type, exemplified by TV program  
>> scheduling (of
>> which I have a bit of experience ;-)). This is sort of a variation  
>> on the
>> second type with the difference that you have Channel->Event-
>> >Program, but
>> there you have a ton of business rules governing how/when programs
>> are/can/must be scheduled. And those business rules vary according  
>> to the
>> type of 'program' being scheduled (sitcom episode, movie, commercial,
>> promos, etc).
>
> Where I live is so rural that when I've told people I'm a programmer,
> they've answered "? You mean, like for TV schedules?"
> **********************************************************************
> Get up to $600 to spend on Amazon.com
> this holiday season - http://www.4d.com/serverpromo.html
>
>
> 4D Internet Users Group (4D iNUG)
> FAQ:  http://lists.4d.com/faqnug.html
> Archive:  http://lists.4D.com/archives.html
> Options: https://lists.4d.com/mailman/options/4d_tech
> Unsub:  mailto:4D_Tech-Unsubscribe@...
> **********************************************************************

**********************************************************************
Get up to $600 to spend on Amazon.com
this holiday season - http://www.4d.com/serverpromo.html
   

4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4D.com/archives.html
Options: https://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:4D_Tech-Unsubscribe@...
**********************************************************************